Реалізація гріду для роботи з великими таблицями. Частина 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. Знайти першу і останню запис у наборі даних:
    select ... order by k [desc] limit 1
  2. Запит B. Знайти h перших записів з ключем, більшим або рівним даному значенню K
    select ... order by k де 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 до , де — загальна кількість записів у таблиці, — число рядків, які розташовуються на одній сторінці в гріді. Якщо бігунок смуги прокрутки виставлений в положення , то це означає, що при відображенні гріду необхідно пропустити перших записів у таблиці, а потім вивести записів. Це якраз те, за що відповідають ключові слова offset і limit в PostgreSQL, і при великому числі записів ми не можемо ними користуватися. Але якщо б деяким «чарівним» чином ми б могли за короткий час вміти обчислювати функцію і зворотний їй функцію , що зв'язує первинний ключ і число записів з ключем, меншим цього, то тоді за допомогою запиту B, підставляючи туди значення , ми могли б швидко отримувати набір записів для відображення користувачеві. Завдання переходу до потрібного запису вирішувалася б таким чином: т. к. первинний ключ заздалегідь відомий, його можна використовувати в якості параметра швидкого запиту B, а смугу прокрутки слід було б встановити в положення . Поставлена задача була б вирішена!

(Зауважимо, що запит D, що викликається з параметром k, як раз повертає значення , але 1) він повільний і 2) нам потрібно вміти обчислювати як , так і зворотну їй.)

Природно, функція цілком визначається даними таблиці, тому, щоб точно відновити взаємозалежність значень ключа та номера запису, необхідно прочитати з бази в оперативну пам'ять всі ключі через одного: для коректного спрацьовування запиту B в проміжних точках можна вважати, що (згадаймо чудове властивість запиту B). Це вже краще, ніж запам'ятовувати все підряд ключі, але все ще недостатньо добре, т. к. вимагає O(N) часу й оперативної пам'яті для первинного відображення таблиці. На щастя, можна обійтися набагато меншим значенням точно відомих точок для функції , і щоб зрозуміти це, нам буде потрібно невеликий комбінаторний аналіз можливих значень .

Нехай ми виконали запит
select min(k), max(k), count(*) from foo
і отримали результати по: 0, 60, 7. Тобто тепер ми знаємо, що в нашій таблиці всього 7 записів (і отже, максимальне значення одно 6), перша з записів має ключ 0, а остання — ключ 60. Одним таким запитом ми фактично дізналися значення у трьох точках: . І це ще не все, адже з самого визначення слід, що:
  1. монотонно зростає,
  2. при збільшенні на одиницю, збільшується на одиницю або не збільшується, тому графік функції , крім точки , цілком лежить в параллелограмме ,
  3. загальне число можливих функцій дорівнює числу способів розподілу записів за значенням ключа (позиції першої і останньої записи фіксовані), т. е.


  4. число можливих функцій , які в точці приймають значення , визначається добутком кількості комбінацій записів з ключем, меншим , і більшим або рівним :




Таким чином, якщо кожен із можливих варіантів вважати равновероятным, то ймовірність того, що для заданого значення inline_formulaє рівно inline_formulaзаписів з ключем, суворо меншим inline_formula, задається відношенням inline_formula, відомим як гіпергеометричний розподіл. inline_formulainline_formulaкартина виглядає таким чином:



Властивості гіпергеометричного розподілу добре відомі. У разі inline_formulaзавжди inline_formula, а на відрізку inline_formulaсереднє значення inline_formulaлінійно залежить від k:


Дисперсія значення має форму переверненої параболи з нулями на краях відрізка і максимумом посередині
некрасива формула
(Грубо можна вважати, що середня помилка менше, ніж inline_formula.)

Розрахунок значень за вищенаведеними формулами для показує таку картину для можливих мінімальних і максимальних (червоні лінії), середнього (блакитна лінія) значень , а також кордонів середньоквадратичного відхилення (сіра область):



Отже, ламана, побудована між точками є статистично обґрунтованим наближенням для обчислення функції і зворотного , і це наближення дає нам можливість досить точно «вгадати» значення функції навіть якщо всі, що ми про неї знаємо — це її значення в трьох точках, отримані за допомогою одного запиту. По суті, ми для «вгадування» виконуємо першу ітерацію алгоритму інтерполяційного пошуку, тільки акуратно визначивши граничні значення.

Якщо тепер для якогось стане відомо нове точне значення , ми можемо додати пару до інтерполяційної таблиці і за допомогою кусочной інтерполяції отримати уточнений розрахунок значення для вирішення завдання прокрутки, а застосовуючи зворотний кусково інтерполяцію, обчислювати уточнене значення при вирішенні задачі позиціонування. З кожної накопиченої точкою діпазон можливих розбіжностей звужуватиметься, і ми будемо отримувати все більш і більш точну картину для функції .

Якщо ключових полів кілька і типи даних INT

На практиці справа не обмежується єдиним цілим числом полем для сортування набору даних. По-перше, тип даних може бути іншим: рядок, дата та інше. По-друге, відсортовані поля може бути кілька. Це утруднення усувається, якщо ми вміємо обчислювати

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

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

Для представлення значень inline_formulaне підходять стандартні 32 — і 64-бітові цілочисельні типи: так, щоб пронумерувати одні лише всілякі 10-байтові рядки, вже не вистачить 64-бітового (8-байтового) цілого. У своїй реалізації ми використовували клас java.math.BigInteger, здатний представляти цілі числа довільної величини. При цьому об'єм оперативної пам'яті, займаної значенням inline_formula, приблизно дорівнює об'єму, що займають набором значень .

При наявності оборотної функції-нумератора inline_formulaі оборотної функції-интерполятора inline_formula,

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


Схема взаємодії процедур

На цьому етапі ми можемо відволіктися від математики і розібратися власне з алгоритмічної частиною. Загальна схема взаємодії процедур системи показана на малюнку нижче. Використана «приблизна UML Activity» нотація, при цьому суцільною стрілкою показана послідовність виконання процедур, а пунктирною стрілкою — асинхронний виклик в окремому потоці виконання:



Припустимо, що користувач змінив положення бігунка вертикальної смуги прокручування (див. в лівий нижній кут діаграми). Інтерполятор обчислює значення номера комбінації значень ключових полів () з типом BigInteger. На основі цього значення нумератор відновлює комбінацію ключових полів .

Тут важливо розуміти, що на даному етапі в полях не обов'язково будуть знаходитися значення, дійсно присутні в базі даних: там будуть лише наближення. В строкових полях, наприклад, буде безглуздий набір символів. Тим не менш, завдяки чудовій властивості запиту B, висновок з бази даних рядків з ключами, більшими або рівними набору , виявиться приблизно вірним результатом для даного положення смуги прокручування.

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

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

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

Екземпляр класу-интерполятора має зберігати в собі проміжні точки монотонно зростаючої функції між безліччю 32-бітних цілих чисел (номерів записів у таблиці) та безліччю об'єктів типу BigInteger (порядкових номерів комбінацій значень ключових полів).

Відразу ж після ініціалізації гріду необхідно в окремому потоці виконання запросити загальна кількість записів у таблиці, щоб отримати правильне значення . До того моменту, як це значення буде отримано за допомогою виконується в паралельному потоці запиту, можна використовувати деяке значення за замовчуванням (наприклад, 1000) — це не вплине на коректність роботи.

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

Ясно, що по заданому номеру такий словник за логарифмічний час знаходить дві точки (), між якими будує пряму інтерполяцію функції . Але той факт, що зростає монотонно, дозволяє за короткий час виробляти і зворотне обчислення. Справді: якщо дано номер комбінації пошук кусочного сегмента, в якому лежить , можна провести в словнику методом дихотомії. Відшукавши потрібний сегмент, ми виробляємо зворотний інтерполяцію і знаходимо номер , відповідний .

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



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

Висновок до першої частини
Отже, ми розібралися, як в цілому влаштована наша система: основними її частинами є інтерполятор нумератор, а також повністю обговорили реалізацію интерполятора. Щоб завершити вирішення завдання необхідно тепер реалізувати нумератор — биекцию inline_formula, увязывающую набори значень ключових полів, що складаються з дат, рядки, відсортованих за допомогою Unicode collation rules і т. п. зі зростаючими в тому ж порядку числами.

Цьому буде присвячена друга частина статті.

Ще я готую наукову публікацію, і ви можете також ознайомитися з препринтом наукової версії цієї статті arxiv.org.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.