Реализация грида для работы с большими таблицами. Часть 1

в 6:24, , рубрики: Алгоритмы, Анализ и проектирование систем, базы данных, пользовательский интерфейс, Программирование, Проектирование и рефакторинг, таблицы

Таблица (грид) с вертикальной полосой прокрутки — наиболее распространённый элемент пользовательского интерфейса для работы с данными реляционной БД. Однако известны сложности, с которыми приходится сталкиваться, когда таблица содержит так много записей, что тактика их полной вычитки и сохранения в оперативной памяти становится неразумной.

Какие-то приложения на большие таблицы не рассчитаны и «зависают» при попытке открыть на просмотр/редактирование таблицу с миллионами записей. Иные отказываются от использования грида с вертикальной полосой прокрутки в пользу постраничного отображения или предлагают пользователю лишь иллюзию, что при помощи полосы прокрутки можно быстро перейти к нужной (хотя бы к самой последней) записи.

Реализация грида для работы с большими таблицами. Часть 1 - 1

Мы расскажем об одном из возможных методов реализации табличного элемента управления, обладающего свойствами Log(N)-быстрого 1) первоначального отображения 2) прокрутки на всём диапазоне записей 3) перехода к записи с заданным уникальным ключом. Всё это — при двух ограничениях: 1) записи могут быть отсортированы только по индексированному набору полей и 2) collation-правила базы данных должны быть известны алгоритму.

Изложенные в статье принципы были реализованы автором в проекте с его участием на языке Java.

Основной принцип

Двумя ключевыми функциональными возможностями табличного элемента управления (грида) являются

  1. прокрутка — отображение записей, соответствующих положению бегунка полосы прокрутки,
  2. переход к записи, заданной по комбинации ключевых полей.

Сперва рассмотрим простейшие подходы к их реализации и покажем, почему они непригодны в случае большого числа записей.

Наиболее прямолинейный подход заключается в считывании в оперативную память всех записей (или хотя бы их первичных ключей), после чего прокрутка осуществляется выборкой сегмента массива, а позиционирование — поиском записи в массиве. Но при большом количестве записей, во-первых, слишком много времени занимает процесс изначальной загрузки массива и, как следствие, задерживается отображение грида на экране, а во-вторых, оперативную память начинают занимать данные таблицы, что снижает общее быстродействие.

Другой подход заключается в «перекладывании» вычислений на СУБД: выборку записей для отображения в окне прокрутки осуществлять при помощи конструкций вида select… limit… offset ..., позиционирование — сводить к select… и count(*). Однако и offset, и count(*) связаны с перебором записей внутри сервера, они имеют в общем случае скорость выполнения O(N), и потому неэффективны при большом числе записей. Частый их вызов приводит к перегрузке сервера БД.

Итак, нам нужно реализовать систему, которая не требовала бы полной закачки данных в память и при этом не перегружала бы сервер неэффективно выполняющимися запросами. Для этого поймём, какие запросы являются эффективными, а какие — нет.

При условии, что по полю k построен индекс, быстрыми являются следующие запросы (они используют index lookup и выполняются за время Log(N)):

  1. Запрос A. Найти первую и последнюю запись в наборе данныx:
    select ... order by k [desc] limit 1
  2. Запрос B. Найти h первых записей с ключом, большим или равным данному значению K:
    select ... order by k where k >= K limit h

Замечательным свойством запроса B является то, что в качестве параметра ему необязательно подставлять ключ существующей в базе данных записи: он одинаково быстро находит как запись по её первичному ключу, так и ближайшую к заданному ключу запись. Этим мы будем активно пользоваться.

Не являются быстрыми следующие запросы:

  1. Запрос C Подсчитать общее количество записей в наборе данных:
    select count(*) ...
  2. Запрос D. Подсчитать число записей, предшествующих записи с ключом, большим или равным данному:
    select count(*) ... where key < K

Запросы B и D можно обобщить на случай сортировки по набору из нескольких полей order by k1, k2, k3… при условии, что на этих полях построен составной индекс. Условие k >= K должно быть обобщено на логическое условие сравнения нескольких значений в лексикографическом порядке:

where k1 >=  K1 and (k1 > K1 or (k2 >= K_2  and (k2 > K2 or ...)))

Основной принцип заключается в том, чтобы в процедурах, требующих быстрого отклика для пользователя, обходиться только быстрыми запросами к БД.

«Угадывание» зависимости первичного ключа от номера записи

На время представим себе, что первичный ключ нашей таблицы имеет всего одно целочисленное поле (далее мы снимем это ограничение).

Пусть каждому положению бегунка полосы прокрутки соответствует целое число от 0 до Реализация грида для работы с большими таблицами. Часть 1 - 2, где Реализация грида для работы с большими таблицами. Часть 1 - 3 — общее число записей в таблице, Реализация грида для работы с большими таблицами. Часть 1 - 4 — число строк, умещающихся на одной странице в гриде. Если бегунок полосы прокрутки выставлен в положение Реализация грида для работы с большими таблицами. Часть 1 - 5, то это означает, что при отрисовке грида необходимо пропустить Реализация грида для работы с большими таблицами. Часть 1 - 6 первых записей в таблице, а затем вывести Реализация грида для работы с большими таблицами. Часть 1 - 7 записей. Это как раз то, за что отвечают ключевые слова offset и limit в PostgreSQL, и при большом числе записей мы не можем ими пользоваться. Но если бы некоторым «волшебным» образом мы бы могли за быстрое время уметь вычислять функцию Реализация грида для работы с большими таблицами. Часть 1 - 8 и обратную ей функцию Реализация грида для работы с большими таблицами. Часть 1 - 9, связывающую первичный ключ и число записей с ключом, меньшим данного, то тогда при помощи запроса B, подставляя туда значение Реализация грида для работы с большими таблицами. Часть 1 - 10, мы могли бы быстро получать набор записей для отображения пользователю. Задача перехода к нужной записи решалась бы таким образом: т. к. первичный ключ заранее известен, его сразу можно использовать в качестве параметра быстрого запроса B, а полосу прокрутки следовало бы установить в положение Реализация грида для работы с большими таблицами. Часть 1 - 11. Поставленная задача была бы решена!

(Заметим, что запрос D, вызываемый с параметром k, как раз возвращает значение Реализация грида для работы с большими таблицами. Часть 1 - 12, но 1) он медленный и 2) нам нужно уметь вычислять как Реализация грида для работы с большими таблицами. Часть 1 - 13, так и обратную ей.)

Естественно, функция Реализация грида для работы с большими таблицами. Часть 1 - 14 целиком определяется данными в таблице, поэтому, чтобы точно восстановить взаимозависимость значений ключа и номера записи, необходимо прочесть из базы в оперативную память все ключи через одного: для корректного срабатывания запроса B в промежуточных точках можно считать, что Реализация грида для работы с большими таблицами. Часть 1 - 15 (вспомним замечательное свойство запроса B). Это уже лучше, чем запоминать все подряд ключи, но всё ещё недостаточно хорошо, т. к. требует O(N) времени и оперативной памяти для первоначального отображения таблицы. К счастью, можно обойтись гораздо меньшим значением точно известных точек для функции Реализация грида для работы с большими таблицами. Часть 1 - 16, и чтобы понять это, нам потребуется небольшой комбинаторный анализ возможных значений Реализация грида для работы с большими таблицами. Часть 1 - 17.

Пусть мы выполнили запрос

select min(k), max(k), count(*) from foo

и получили результаты: 0, 60, 7. Т. е. теперь мы знаем, что в нашей таблице всего 7 записей (и значит, максимальное значение Реализация грида для работы с большими таблицами. Часть 1 - 18 равно 6), первая из записей имеет ключ 0, а последняя — ключ 60. Одним таким запросом мы фактически узнали значения Реализация грида для работы с большими таблицами. Часть 1 - 19 в трёх точках: Реализация грида для работы с большими таблицами. Часть 1 - 20, Реализация грида для работы с большими таблицами. Часть 1 - 21 и Реализация грида для работы с большими таблицами. Часть 1 - 22. И это ещё не всё, ведь из самого определения Реализация грида для работы с большими таблицами. Часть 1 - 23 следует, что:

  1. Реализация грида для работы с большими таблицами. Часть 1 - 24 монотонно растёт,
  2. при увеличении Реализация грида для работы с большими таблицами. Часть 1 - 25 на единицу, Реализация грида для работы с большими таблицами. Часть 1 - 26 увеличивается на единицу или не увеличивается, поэтому график функции Реализация грида для работы с большими таблицами. Часть 1 - 27, кроме точки Реализация грида для работы с большими таблицами. Часть 1 - 28, целиком лежит в параллелограмме Реализация грида для работы с большими таблицами. Часть 1 - 29, Реализация грида для работы с большими таблицами. Часть 1 - 30, Реализация грида для работы с большими таблицами. Часть 1 - 31, Реализация грида для работы с большими таблицами. Часть 1 - 32,
  3. общее число возможных функций Реализация грида для работы с большими таблицами. Часть 1 - 33 равно числу способов распределения Реализация грида для работы с большими таблицами. Часть 1 - 34 записей по Реализация грида для работы с большими таблицами. Часть 1 - 35 значениям ключа (позиции первой и последней записи фиксированы), т. е.
    Реализация грида для работы с большими таблицами. Часть 1 - 36

  4. число возможных функций Реализация грида для работы с большими таблицами. Часть 1 - 37, которые в точке Реализация грида для работы с большими таблицами. Часть 1 - 38 принимают значение Реализация грида для работы с большими таблицами. Часть 1 - 39, определяется произведением количества комбинаций записей с ключом, меньшим Реализация грида для работы с большими таблицами. Часть 1 - 40, и большим или равным Реализация грида для работы с большими таблицами. Часть 1 - 41:
    Реализация грида для работы с большими таблицами. Часть 1 - 42

Таким образом, если каждый из возможных вариантов считать равновероятным, то вероятность того, что для заданного значения inline_formula имеется ровно inline_formula записей с ключом, строго меньшим inline_formula, задаётся отношением inline_formula, известным как гипергеометрическое распределение. Для inline_formula, inline_formula картина выглядит вот таким образом:

Реализация грида для работы с большими таблицами. Часть 1 - 49

Свойства гипергеометрического распределения хорошо известны. В случае inline_formula всегда inline_formula, а на отрезке inline_formula среднее значение inline_formula линейно зависит от k:

Реализация грида для работы с большими таблицами. Часть 1 - 54

Дисперсия значения Реализация грида для работы с большими таблицами. Часть 1 - 55 имеет форму перевернутой параболы с нулями на краях отрезка Реализация грида для работы с большими таблицами. Часть 1 - 56 и максимумом посередине

некрасивая формула
Реализация грида для работы с большими таблицами. Часть 1 - 57

(Грубо можно считать, что средняя ошибка меньше, чем inline_formula.)

Расчёт значений по вышеприведённым формулам для Реализация грида для работы с большими таблицами. Часть 1 - 59, Реализация грида для работы с большими таблицами. Часть 1 - 60 показывает такую картину для возможных минимальных и максимальных (красные линии), среднего (голубая линия) значений Реализация грида для работы с большими таблицами. Часть 1 - 61, а также границ среднеквадратичного отклонения (серая область):

Реализация грида для работы с большими таблицами. Часть 1 - 62

Итак, ломаная, построенная между точками Реализация грида для работы с большими таблицами. Часть 1 - 63, Реализация грида для работы с большими таблицами. Часть 1 - 64, и Реализация грида для работы с большими таблицами. Часть 1 - 65 является статистически обоснованным приближением для вычисления функции Реализация грида для работы с большими таблицами. Часть 1 - 66 и обратной Реализация грида для работы с большими таблицами. Часть 1 - 67, и это приближение даёт нам возможность довольно точно «угадать» значения функции даже если всё, что мы о ней знаем — это её значения в трёх точках, полученные при помощи одного запроса. По сути, мы для «угадывания» выполняем первую итерацию алгоритма интерполяционного поиска, только аккуратно определив граничные значения.

Если теперь для какого-то Реализация грида для работы с большими таблицами. Часть 1 - 68, Реализация грида для работы с большими таблицами. Часть 1 - 69 станет известно новое точное значение Реализация грида для работы с большими таблицами. Часть 1 - 70, мы можем добавить пару Реализация грида для работы с большими таблицами. Часть 1 - 71 к интерполяционной таблице и при помощи кусочной интерполяции получить уточнённый расчёт значения Реализация грида для работы с большими таблицами. Часть 1 - 72 для решения задачи прокрутки, а применяя обратную кусочную интерполяцию, вычислять уточнённое значение Реализация грида для работы с большими таблицами. Часть 1 - 73 при решении задачи позиционирования. С каждой накопленной точкой дипазон возможных расхождений будет сужаться, и мы будем получать всё более и более точную картину для функции Реализация грида для работы с большими таблицами. Часть 1 - 74.

Если ключевых полей несколько и типы данных не INT

На практике дело не ограничивается единственным целочисленным полем для сортировки набора данных. Во-первых, тип данных может быть другим: строка, дата и прочее. Во-вторых, сортируемых полей может быть несколько. Это затруднение устраняется, если мы умеем вычислять

  1. функцию-нумератор inline_formula, переводящую набор значений полей произвольных типов в натуральное число,
  2. обратную ей функцию inline_formula, переводящую натуральное число обратно в набор значений полей, inline_formula.

Функция-нумератор должна обладать тем свойством, что если набор inline_formula меньше набора inline_formula в смысле лексикографического порядка, то должно быть Реализация грида для работы с большими таблицами. Часть 1 - 80.

Говоря языком математики, биекция inline_formula должна устанавливать изоморфизм порядка между множеством возможных значений наборов полей и множеством натуральных чисел. Заметим: для того, чтобы задача поиска подходящей inline_formula была математически разрешима, важно, чтобы множества возможных значений полей inline_formula были конечными. К примеру, между множеством всех лексикографически упорядоченных пар натуральных (пар действительных) чисел и множеством натуральных (действительных) чисел невозможно построить изоморфизм порядка. Разумеется, множество всех возможных значений любого машинного типа данных является конечным, хотя и очень большим.

Для представления значений inline_formula не подходят стандартные 32- и 64-битовые целочисленные типы: так, чтобы перенумеровать одни лишь всевозможные 10-байтовые строки, уже не хватит 64-битового (8-байтового) целого. В своей реализации мы использовали класс java.math.BigInteger, способный представлять целые числа произвольной величины. При этом объём оперативной памяти, занимаемой значением inline_formula, примерно равен объёму, занимаемому набором значений Реализация грида для работы с большими таблицами. Часть 1 - 86.

При наличии обратимой функции-нумератора inline_formula и обратимой функции-интерполятора inline_formula,

  • прокрутка грида сводится к вычислению значений ключевых полей inline_formula, где inline_formula — положение вертикальной полосы прокрутки, после чего быстрый запрос к БД находит inline_formula первых записей, больших или равных inline_formula,
  • позиционирование сводится к считыванию inline_formula первых записей из БД по заранее известным значениям inline_formula, и к вычислению положения бегунка полосы прокрутки inline_formula.

Схема взаимодействия процедур

На этом этапе мы можем отвлечься от математики и разобраться собственно с алгоритмической частью. Общая схема взаимодействия процедур системы показана на рисунке ниже. Использована «приблизительная UML Activity» нотация, при этом сплошной стрелкой показана последовательность выполнения процедур, а пунктирной стрелкой — асинхронный вызов в отдельном потоке выполнения:

Реализация грида для работы с большими таблицами. Часть 1 - 96

Допустим, что пользователь изменил положение бегунка вертикальной полосы прокрутки (см. в левый нижний угол диаграммы). Интерполятор вычисляет значение номера комбинации значений ключевых полей (Реализация грида для работы с большими таблицами. Часть 1 - 97) с типом BigInteger. На основе этого значения нумератор восстанавливает комбинацию ключевых полей Реализация грида для работы с большими таблицами. Часть 1 - 98.

Здесь важно понимать, что на данном этапе в полях Реализация грида для работы с большими таблицами. Часть 1 - 99 не обязательно будут находиться значения, действительно присутствующие в базе данных: там будут лишь приближения. В строковых полях, например, будет бессмысленный набор символов. Тем не менее, благодаря замечательному свойству запроса B, вывод из базы данных Реализация грида для работы с большими таблицами. Часть 1 - 100 строк с ключами, большими или равными набору Реализация грида для работы с большими таблицами. Часть 1 - 101, окажется приблизительно верным результатом для данного положения полосы прокрутки.

Если пользователь отпустил полосу прокрутки и какое-то время не трогал её, асинхронно (в отдельном потоке выполнения) запускается запрос D, определяющий порядковый номер записи, а значит, и точное положение полосы прокрутки, которое соответствует тому, что отображено пользователю. Когда запрос будет завершён, на основе полученных данных будет пополнена интерполяционная таблица. Если к этому моменту пользователь не начал снова прокручивать таблицу, вертикальный бегунок «отскочит» на новое, уточнённое положение.

При переходе к записи последовательность вызовов процедур происходит в обратную сторону. Т. к. значения ключевых полей уже известны, для пользователя запросом B сразу извлекаются данные из базы. Нумератор вычисляет Реализация грида для работы с большими таблицами. Часть 1 - 102, и затем интерполятор определяет приблизительное положение полосы прокрутки как Реализация грида для работы с большими таблицами. Часть 1 - 103. Параллельно, в асинхронном потоке выполнения, выполняется уточняющий запрос, по результатам которого в интерполяционную таблицу добавляется новая точка. Через секунду-другую бегунок полосы прокрутки «отскочит» на новое, уточнённое положение.

Чем больше пользователь будет «бродить» по данным вертикальным бегунком, тем больше точек будет собираться в интерполяционной таблице и тем меньше будут «отскоки». Практика показывает, что достаточно всего 4-5 удачных точек в интерполяционной таблице, чтобы «отскоки» стали очень малы.

Экземпляр класса-интерполятора должен хранить в себе промежуточные точки монотонно растущей функции между множеством 32-битных целых чисел (номеров записей в таблице) и множеством объектов типа BigInteger (порядковых номеров комбинаций значений ключевых полей).

Сразу же после инициализации грида необходимо в отдельном потоке выполнения запросить общее количество записей в таблице, чтобы получить корректное значение Реализация грида для работы с большими таблицами. Часть 1 - 104. До того момента, как это значение будет получено при помощи выполняющегося в параллельном потоке запроса, можно использовать некоторое значение по умолчанию (например, 1000) — это не повлияет на корректность работы.

Интерполятор должен уметь за быстрое по количеству интерполяционных точек время вычислять значение как в одну, так и в другую сторону. Однако заметим, что чаще требуется вычислять значение порядкового номера комбинации по номеру записи: такие вычисления производятся много раз за секунду в процессе прокрутки грида пользователем. Поэтому за основу реализации модуля интерполятора удобно взять словарь на основе бинарного дерева, ключами которого являются номера записей, а значениями — порядковые номера комбинаций (класс TreeMap<Integer, BigInteger> в языке Java).

Ясно, что по заданному номеру Реализация грида для работы с большими таблицами. Часть 1 - 105 такой словарь за логарифмическое время находит две точки (Реализация грида для работы с большими таблицами. Часть 1 - 106), между которыми строит прямую интерполяцию функции Реализация грида для работы с большими таблицами. Часть 1 - 107. Но тот факт, что Реализация грида для работы с большими таблицами. Часть 1 - 108 растёт монотонно, позволяет за быстрое время производить и обратное вычисление. В самом деле: если дан номер комбинации Реализация грида для работы с большими таблицами. Часть 1 - 109, Реализация грида для работы с большими таблицами. Часть 1 - 110, поиск кусочного сегмента, в котором лежит Реализация грида для работы с большими таблицами. Часть 1 - 111, можно произвести в словаре методом дихотомии. Отыскав нужный сегмент, мы производим обратную интерполяцию Реализация грида для работы с большими таблицами. Часть 1 - 112 и находим номер Реализация грида для работы с большими таблицами. Часть 1 - 113, соответствующий Реализация грида для работы с большими таблицами. Часть 1 - 114.

При пополнении словаря интерполяционными точками необходимо следить за тем, чтобы интерполируемая функция оставалась монотонной. Так как другие пользователи могут удалять и добавлять записи в просматриваемую таблицу, актуальность известных словарю интерполяционных точек может утратиться, а вновь добавляемая точка может нарушить монотонность. Поэтому метод добавления новой интерполяционной точки должен проверять, что «точке слева» от только что добавленной соответствует меньшее, а «точке справа» — большее значение. Если оказывается, что это не так, следует исходить из предположения, что последняя добавленная точка соответствует актуальному положению вещей, а некоторые из старых точек утратили свою актуальность. По отношению к вновь добавленной точке следует удалять все точки слева, содержащие большее значение, и все точки справа, содержащие меньшее значение. Процесс «срезания выбивающейся точки» показан на рисунке:

Реализация грида для работы с большими таблицами. Часть 1 - 115

Также интерполятор должен содержать в себе механизм, в целях экономии памяти защищающий словарь от переполнения излишними точками, и отбрасывающий наименее существенные из них (как мы помним, не имеет смысла хранить все точки подряд — достаточно только через одну).

Заключение к первой части

Итак, мы разобрались, как в целом устроена наша система: основными её частями являются интерполятор и нумератор, а также полностью обсудили реализацию интерполятора. Чтобы завершить решение задачи, необходимо теперь реализовать нумератор — биекцию inline_formula, увязывающую наборы значений ключевых полей, возможно, состоящих из дат, строки, отсортированных при помощи Unicode collation rules и т. п. с растущими в том же порядке числами.

Этому будет посвящена вторая часть статьи.

Ещё я готовлю научную публикацию, и вы можете также ознакомиться с препринтом научной версии этой статьи на arxiv.org.

Автор: IvanPonomarev

Источник

Поделиться новостью

* - обязательные к заполнению поля