П'ять способів пагинации в Postgres, від базових до дивовижних

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

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

  • Більш швидке завантаження початкової сторінки
  • Більш висока точність, коли загальні дані змінюються
  • Більш швидкі операції на великих обсягах даних
  • Інкапсуляція бізнес-логіки
  • Більш висока продуктивність на клієнтів з обмеженими ресурсами
PostgreSQL дає нам певну кількість технік пагинации на стороні сервера, які відрізняються за швидкістю, цілісності (не втрачають запису), а також підтримку шаблонів доступу до певних сторінок. Не всі методи працюють не у всіх ситуаціях, деякі вимагають спеціальних даних, або запитів. Розглянемо методи у порядку спільності, починаючи з тих, які працюють з будь-якими запитами, і продовжуючи тими, які вимагають впорядкованих даних. Закінчимо ми декількома екзотичними методами, які ґрунтуються на внутрішньому пристрої PostgreSQL.

Розбиття довільних запитів
Limit-Offset
Найпростіший метод пагинации, limit-offset, є і найбільш ризикованим. На жаль, він є однією з основ навчальних посібників з веб-розробки. Бібліотеки об'єктно-реляційного відображення (ORM) роблять використання цього методу легким і привабливим, від SQLAlchemy'ого .slice(1, 3) до ActiveRecord'ого .limit(1).offset(3) і до Sequelize'ого .findAll({ offset: 3, limit: 1 }). Це не збіг, що limit-offset використовується повсюдно, ви можете прикріплювати його до будь-якого запиту без подальшої модифікації.

ORM методи limit'а і offset'а це одна справа, допоміжні бібліотеки для пагинации можуть бути ще більш оманливі. Приміром, популярна Ruby бібліотека Kaminari використовує limit-offset за замовчуванням, приховуючи його за високорівневим інтерфейсом.

У цієї техніки є дві великі проблеми, неконсистентность результату і неефективність зміщення. Консистентним пов'язана з тим, що проходження за результатами повинно отримувати кожен елемент строго один раз, без пропусків або повторів. Неефективність зміщення пов'язана з затримкою, що виникає при зсуві результатів на велике зміщення.

Ось яким чином limit-offset пагинация може бути неконсистентной. Припустимо що користувач переходить зі сторінки n на сторінку n + 1, поки в той же момент новий елемент вставлений на сторінку n. Це викличе і дублювання (останній елемент зі сторінки n витіснений на сторінку n + 1), і пропуск (новий елемент). В якості альтернативи, припустимо що вилучений елемент n, в той момент, коли користувач перейшов на сторінку n + 1. Попередньо завантажений початковий елемент сторінкиn + 1 зрушиться на сторінку n і буде пропущений.

Тепер на тему неефективності. Великі зрушення в дійсності дорого коштує. Навіть якщо є індекс, базі доведеться сканувати всі сховище, вважаючи рядка. Для використання індексу ми повинні відфільтрувати стовпець за значенням, але в даному випадку нам потрібно певну кількість рядків, незалежно від їх значень стовпців. Крім того, рядки не зобов'язані мати однаковий розмір при зберіганні, і деякі з них можуть бути присутніми на диску, але бути позначені як видалені, так що база даних не зможе використовувати просту арифметику, щоб знайти місце на диску і почати читання результатів. Давайте виміряємо уповільнення.

-- Створюємо таблицю з випадковими рядками змінюваного розміру
CREATE TABLE AS medley
SELECT
generate_series(1,10000000) AS n,
substr(concat(md5(random()::text), md5(random()::text)), 1, (random() * 64)::integer + 1) AS description;

-- Оповіщаємо планувальник про кардинально змінився розмірі таблиці
VACUUM ANALYZE;

-- Малі зрушення освежающе швидкі
EXPLAIN ANALYZE SELECT * FROM medley LIMIT 100;

Орієнтовна вартість досить низька:

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..1.85 rows=100 width=38) (actual time=0.008..0.036 rows=100 loops=1)
-> Seq Scan on medley (cost=0.00..185460.60 rows=9999660 width=38) (actual time=0.007..0.017 rows=100 loops=1)
Planning time: 0.040 ms
Execution time: 0.059 ms
(4 rows)

Вибір offset = 1000, змінює його вартість до 19 і час виконання до 0.609 мс. Як тільки offset = 5000000, вартість стає вже 92734 і час виконання 758.484 мс.

Ці проблеми не обов'язково означають, що limit-offset метод непридатний у Вашому випадку. В деяких додатках, користувачі, як правило, не проходять багато сторінок в результатах, і Ви можете навіть використовувати обмеження кількості сторінок на стороні сервера. Якщо неконсистентность даних і обмеження кількості сторінок не є проблемою у Вашому додатку, то limit-offset метод цілком підходить для Вас.

Коли використовувати: Limit-Offset. Програми з обмеженою глибиною пагинации і толерантні до неконсистентності результату.

Курсори
Незважаючи на свої недоліки, метод limit-offset має плюс у вигляді відсутності впливу на сервер. На противагу цьому підходу, є інший метод поділу на сторінки, курсори. Як і зміщення, курсори можуть бути використані з будь-якими запитами, але вони відрізняються тим, що вимагають від сервера окремого з'єднання і транзакції через HTTP клієнт.

Ось яким чином можуть бути використані курсори:

-- Ми повинні перебувати в транзакції
BEGIN;
-- Відкриваємо курсор для запиту
DECLARE medley_cur CURSOR FOR SELECT * FROM medley;
-- Отримуємо 10 рядків
FETCH 10 FROM medley_cur;
-- ...
-- Отримуємо ще 10 рядків, з того місця, де зупинилися минулого разу
FETCH 10 FROM medley_cur;
-- Все готово
COMMIT;

Курсори мають бажане властивість консистентности пагинации на будь-які запити, показуючи результати, наявні в базі на момент початку транзакції. Рівень ізоляції транзакції гарантує, що розділений на сторінки результат не зміниться.

Кожен підхід поділу на сторінки має свої слабкі сторони, і курсори — не виняток: вони залежні від використання ресурсів і зв'язки клієнт-сервер. Кожна відкрита транзакція споживає виділені ресурси бази, і не масштабується для великої кількості клієнтів. Звичайно ж, існують «WITH HOLD» курсори, які можуть існувати за межами транзакції, але вони повинні матеріалізовувати дані.Таким чином, зазначені помилки роблять пагінацію вказівники придатною тільки для вузького кола ситуацій, наприклад для внутрішньої мережі.

Додавання зв'язку з HTTP до курсорів вносить з собою ускладнення. Сервери повинні ідентифікувати клієнтів між запитами, неважливо через токен, або зберігаючи ідентифікатор, наприклад такий як IP-адреса клієнта в рамках сесії. Сервери повинні вирішувати, коли звільняти транзакції у зв'язку з простоєм. Нарешті, балансування навантаження на сервер стає складним, так як клієнт повинен підключатися до конкретного сервера кожен раз.

Коли використовувати: Курсори. Додаток всередині мережі, на єдиному сервері, яке повинно розділяти на сторінки запити з варійованими і змінним порядком, особливо коли важлива консистентним результату.

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

До прикладу, давайте повернеться до нашого прикладу:

-- Додаємо індекс для пагинации (btrees підтримують нерівність)
CREATE INDEX n_idx ON medley USING btree (n);
SELECT * FROM medley ORDER BY n ASC LIMIT 5;

З моїми випадковими даними він повертає:

n | description
---+-------------------------------------------------------------
1 | 74f70e009396
2 | 8dac5a085eb670a29058d
3 | fce303a32e89181bf5df1601487
4 | fddcced2c12e83516b3bd6cc94f23a012dfd
5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621
(5 rows)

Тепер користувач може подивитися на максимальний n з результату і використовувати його для виклику наступної сторінки:

SELECT * FROM medley
WHERE n > 5
ORDER BY n ASC
LIMIT 5;

Навіть при фільтрації з n > 5000000, це працює швидше, ніж у limit-offset прикладі.

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..0.62 rows=5 width=38) (actual time=0.101..0.103 rows=5 loops=1)
-> Index Scan using n_idx on medley (cost=0.43..185579.42 rows=5013485 width=38) (actual time=0.100..0.102 rows=5 loops=1)
Index Cond: (n > 5000000)
Planning time: 0.071 ms
Execution time: 0.119 ms
(5 rows)

Така пагинация працює швидко і при цьому гарантує цілісність даних. Будь-які додавання/видалення до поточної сторінки залишать результат незмінним. Два слабкі місця цього методу — це відсутність довільного доступу і можливого з'єднання між клієнтом і сервером.

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

EXPLAIN ANALYZE SELECT max(n) FROM medley;
QUERY PLAN
------------------------------------------------------------------------------------------------------------
Result (cost=0.46..0.47 rows=1 width=0) (actual time=0.021..0.021 rows=1 loops=1)
InitPlan 1 (returns $0)
-> Limit (cost=0.43..0.46 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=1)
-> Index Only Scan Backward using n_idx on medley (cost=0.43..284688.43 rows=10000000 width=4) (actual time=0.017..0.017 rows=1 loops=1)
Index Cond: (n IS NOT NULL)
Heap Fetches: 0
Planning time: 0.087 ms
Execution time: 0.042 ms
(8 rows)

Інше питання пагинации по ключовим значенням, з'єднання клієнт/сервер, вимагає уваги. Спочатку користувач не знає які колонки проіндексовані. Сервер, ймовірно, надасть кінцеву точку з фіксованим результатом, ніж дозволить клієнту змінювати порядок. Наданий клієнту код може не знати який стовпець впорядкований, сервер повинен надати підказку як запросити на наступну сторінку. RFC5988 визначає ставлення попередньої і наступної HTTP посилань для кодування посилань для користувача, за яким він повинен перейти.

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

Коли використовувати: Пагинация по ключовим значенням. Масштабовані додатки, які обслуговують дані послідовно стовпця(ів), індексованих для порівняння. Підтримує фільтрацію.

Дивовижна, спеціалізована пагинация
Clustered TID Scan
Ми можемо отримати нестандартні методи розбиття на сторінки для особливих ситуацій з використанням PostgreSQL функцій низького рівня. Наприклад, ми можемо отримати реально випадковий доступ до даних, якщо ми

  1. Не вимагаємо від сторінок того, щоб вони були однакового розміру
  2. Підтримуємо тільки єдину черговість для розділених на сторінки рядків
Трюк полягає в тому, щоб вибрати повернені сторінки, які пов'язані зі сторінками з бази даних на диску, або з певними частинами цих сторінок на диску. Кожна таблиця в базі даних PostgreSQL містить у собі секретну колонку, яка називається ctid і ідентифікує її рядок:

SELECT ctid, * FROM medley WHERE n <= 10;
ctid | n | description
--------+----+-------------------------------------------------------------
(0,1) | 1 | 74f70e009396
(0,2) | 2 | 8dac5a085eb670a29058d
(0,3) | 3 | fce303a32e89181bf5df1601487
(0,4) | 4 | fddcced2c12e83516b3bd6cc94f23a012dfd
(0,5) | 5 | f51ae548dd27f51147e53e839eeceb6b0c92922145276d668e73d4a6621
(0,6) | 6 | eb9fe1dfe1e421903f96b3b5c5dfe1ee1253582d728c35b4ee7330b
(0,7) | 7 | e95202d7f5c612f8523ae705d
(0,8) | 8 | 6573b64aff262a2b940326
(0,9) | 9 | a0a43
(0,10) | 10 | 82cdc134bd249a612cfddd3088dd09e32de5f4fa33
(10 rows)

Кожен ctid представляє з себе наступний вигляд: (сторінка, рядок). PostgreSQL може отримувати рядка дуже швидко за ctid'у, насправді, так працюють індекси — вони пов'язують значення колонок з ctid'мі.

Слід звернути увагу, хоч PostgreSQL і визначає відношення порядку на основі tid типу, він не може ефективно отримати ctid'и з нерівності

EXPLAIN ANALYZE SELECT count(1) FROM medley WHERE ctid >= '(0,1)'::tid AND ctid < '(1,0)'::tid;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Aggregate (cost=235589.00..235589.01 rows=1 width=0) (actual time=1241.851..1241.852 rows=1 loops=1)
-> Seq Scan on medley (cost=0.00..235464.00 rows=50000 width=0) (actual time=477.933..1241.802 rows=116 loops=1)
Filter: ((ctid >= '(0,1)'::tid) AND (ctid < '(1,0)'::tid))
Rows Removed by Filter: 9999884
Planning time: 0.047 ms
Execution time: 1241.889 ms
(6 rows)

Запит діапазонів не працює, але все ще існує спосіб ефективного запиту всіх рядків зі сторінки на диску. Кожна сторінка містить current_setting('block_size') байтів даних (зазвичай 8к). Рядки пов'язані 32-бітним покажчиком, так що, здебільшого, доводиться block_size/4 рядків на сторінку. (Насправді рядки, як правило, ширше, ніж мінімальний розмір і чверть розміру блоку забезпечує верхню межу рядків на сторінці.) Наступна послідовність буде генерувати всі можливі ctid'и на j-ій сторінці

SELECT ('(' || j || ',' || s.i || ')')::tid
FROM generate_series(0,current_setting('block_size')::int/4) AS s(i);

Давайте скористаємося їй, щоб отримати всі рядки у нашому прикладі на нульовій сторінці.

SELECT * FROM medley WHERE ctid = ANY (ARRAY
(SELECT ('(0,' || s.i || ')')::tid
FROM generate_series(0,current_setting('block_size')::int/4) AS s(i)
)
);

Планувальник визначив вартість виконання цього запиту рівній cost=25.03..65.12 і виконує його за 2.765 мс. Запит сторінки під номером 10000 має таку ж вартість. Таким чином ми отримуємо реально довільний доступ, чому б його не любити?

Тут є три вузькі місця:

  1. Коли рядка видалені — вони залишають дірки в сторінках.
  2. Порядок рядків не може бути значущим. База даних вставляє рядки в дірки, залишені від видалення рядків, що призведе до випадання з послідовності рядків.
  3. «Where» не підтримується
У деяких ситуаціях це не проблема. Один випадок — це дані, природний порядок яких співвідноситься з порядком додавання в базу, такі як тільки зростаючі дані інтервалів часу. Інший — це дані, які не змінюються часто. Це пов'язано з тим, що ми маємо контроль над розташуванням рядків на сторінках через команду CLUSTER.

Давайте повернемося до нашого прикладу. Його рядки на диску упорядковані за n колонці в зростаючому порядку, так як це порядок, в якому ми додавали їх в базу. Але що якщо ми хочемо відсортувати їх по стовпцю description? Для цього нам доведеться фізично перебудувати таблицю, створивши індекс на колонці description і виконати кластеризацію.

CREATE INDEX description_idx ON medley USING btree (description);
CLUSTER medley USING description_idx;

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

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

SELECT pg_relation_size('medley') / current_setting('block_size')::int;

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

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

Для початку давайте поглянемо на статистику по нашому прикладу:

SELECT array_length(histogram_bounds, 1) - 1
FROM pg_stats
WHERE tablename = 'medley'
AND attname = 'n';

В моїй базі даних колонка n має 101 граничний показник, тобто 100 діапазонів між ними. Конкретні значення не надто вибиваються, так як дані рівномірно розподілені.

{719,103188,193973,288794, ... ,9690475,9791775,9905770,9999847}


Зверніть увагу, що значення приблизні. Перше число це не рівне 0, і останнє це не рівно десять мільйонів. Діапазони поділяють нашу інформацію в блок розміру B = 10,000,000 / 100 = 100,000 рядків.

Ми можемо використовувати діапазони гістограм складальника статистики PostgreSQL для отримання ймовірнісно правильних сторінок. Якщо ми вибираємо розмір сторінки на клієнтській стороні, що дорівнює W, то як ми отримаємо i-шу сторінку? Вона буде перебувати в блоці IW / B, зі зміщенням IW% B.

Вибираючи W = 20, давайте запитаємо сторінку 270000 з нашої тестової таблиці.

WITH bookmark AS (
SELECT (histogram_bounds::text::int[])[((270000 * 20) / 100000)+1] AS start,
(histogram_bounds::text::int[])[((270000 * 20) / 100000)+2] AS stop
FROM pg_stats
WHERE tablename = 'medley'
AND attname = 'n'
LIMIT 1
)
SELECT *
FROM medley
WHERE n >= (select, start from bookmark)
AND n < (select stop from bookmark)
ORDER BY n ASC
LIMIT 20
OFFSET ((270000 * 20) % 100000);

Це виконується швидко (зверніть увагу що зсув відбувається за час, близький до нуля в даному випадку). Запит повертає рядок з n=5407259 до 5407278. Істинні значення на сторінці 270000 рівні з n = 5400001 до 5400020. Промах становить 7239, або приблизно 0.1%.

Нам пощастило з вибором сторінки в цьому випадку. Для контрасту, сторінка 74999 вимагає зміщення на 99980. Ми знаємо, що наше зміщення буде не більше 100000. Верхня межа знаходиться у нас під контролем, якщо ми хочемо досягти компромісу. Налаштовуючи складальник статистики PostgreSQL, ми можемо отримати більш точну гістограму за стовпцями.

ALTER TABLE medley ALTER COLUMN n SET statistics 1000;
VACUUM ANALYZE;

Тепер ми маємо 1000, замість 100 значень гістограми. В моїй базі даних це виглядає наступним чином:

{10,10230,20863, ..., 9980444,9989948,9999995}

При цьому крок нашого зміщення буде не більше 10000. Компроміс полягає в тому, що планувальник тепер переглядає більше величин, але сповільнюється. Так що це щось середнє між неефективністю зміщення і накладними витратами складальника статистики.

Цей гібридний «набір ключів/зміщення» метод ймовірно не підходить для багатьох застосувань пагинации в реальному житті. І тут не буде працювати умова «where». Крім того, він неточний і стає тільки більше і більше неточним при зміні таблиці і якщо збирач статистики давно не запускався.

Коли використовувати: Набір ключів з оціночними закладками. вам потрібен глибокий, але приблизний довільний доступ, без будь-якої додаткової фільтрації.

Висновки
Як і багато інші інженерні рішення, вибір техніки пагинации вимагає компромісів. Можна з упевненістю сказати, що пагинация по набору ключів найбільш застосовна для середнього сайту з впорядкованим лінійним доступом. Однак навіть limit/offset метод має свої сильні сторони, і більш екзотичні методи забезпечують спеціальні експлуатаційні характеристики для певних видів даних. Як ви бачите, є досить багато можливостей. Виберіть правильний інструмент для роботи і не дозволяйте пагинации бути закритою книгою.
Джерело: Хабрахабр

0 коментарів

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