Вас может удивить тот факт, что пагинация, распространенная, как таковая, в веб приложениях, с легкостью может быть реализована нерационально. В этой статье мы испробуем различные способы пагинации на стороне сервера и обсудим их удобство при использовании в 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 medley AS
  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 метод имеет свои сильные стороны, и более экзотические методы обеспечивают специальные эксплуатационные характеристики для определенных видов данных. Как вы видите, есть довольно много возможностей. Выберите правильный инструмент для работы и не позволяйте пагинации быть закрытой книгой.