Пагинация на масштабе: почему OFFSET умирает, а keyset-курсоры живут

Лента с бесконечным скроллом плавная первые десять страниц, а потом сыплются тикеты: «приложение виснет, когда долго скроллишь». Эндпоинт — ?page=10000&size=20. В стейджинге он отвечал за 8мс; в проде, на таблице в 50 миллионов строк, тот же запрос занимает 8.2 секунды и иногда отваливается по таймауту. Код никто не менял. План запроса всегда собирался делать именно это — он читает двести тысяч строк, выбрасывает все, кроме последних двадцати, и чем глубже скроллит пользователь, тем медленнее. Баг был в стратегии пагинации, присутствовал с первого дня, невидимый, пока таблица не выросла.

Почему OFFSET тем медленнее, чем глубже

LIMIT 20 OFFSET 200000 читается как «перепрыгни к строке 200000», но у базы нет способа перепрыгнуть. Она обязана выдать строки в отсортированном порядке, отсчитать первые 200000, выбросить их и только потом начать возвращать твои 20. Работа пропорциональна оффсету, а не размеру страницы. Страница 1 мгновенна; страница 10000 — это двести тысяч строк впустую потраченного I/O на каждый запрос, и эта цена повторяется для следующей страницы, и следующей.

-- Offset-пагинация: чем глубже страница, тем больше строк просканировано и выброшено
SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 200000;   -- база читает 200020 строк, возвращает 20

Цифры жестокие и стабильные по разным бенчмаркам. На таблице в несколько миллионов строк offset-страница 1000 приземляется около 890мс, а страница 10000 вырастает примерно до 8.2 секунды — на порядок медленнее при том же payload, чисто потому что строк, которые надо пропустить, больше. Keyset-пагинация по тем же данным держится ровно: 8мс, 9мс, 11мс, 12мс, страница за страницей, потому что она вообще не отсчитывает прошлые строки. Заявленные ускорения — 17x на наборах в миллион строк и до 177x на тех глубоких страницах, где offset разваливается.

Result drift: баг, который OFFSET прячет даже на маленьких таблицах

Даже когда offset достаточно быстр, он неверен при конкурентных записях. Границы страниц вычисляются по позиции в живом, сдвигающемся результирующем наборе. Вставь строку ближе к началу между страницей 1 и страницей 2 — и каждая последующая строка съезжает на одну вниз: элемент, который был последним на странице 1, снова появляется первым на странице 2 (дубликат, который пользователь видит дважды). Удали строку — и один элемент пропускается целиком, пользователь его не увидит. Этот drift — не проблема нагрузки; он случается на крошечной таблице в тот момент, когда два запроса оказываются по разные стороны записи, а на любой активной ленте это происходит постоянно.

Keyset (курсорная) пагинация: сикай, не пропускай

Keyset-пагинация заменяет «пропусти N строк» на «дай мне строки после этой конкретной строки». Ты сортируешь по стабильному, уникальному, проиндексированному ключу и переносишь значения ключа последней строки вперёд как курсор. Следующий запрос становится диапазонным сиком, который индекс удовлетворяет напрямую, без отсчёта.

-- Keyset-пагинация: сикаем сразу за последнюю увиденную строку, O(log n) вне зависимости от глубины
SELECT id, title, created_at
FROM articles
WHERE (created_at, id) < ('2026-05-01 09:00:00', 918273)  -- последняя строка предыдущей страницы
ORDER BY created_at DESC, id DESC
LIMIT 20;

Два требования, которые нельзя нарушать. Первое: ключ сортировки должен быть уникальным и стабильным — created_at сам по себе не уникален (две строки могут делить timestamp, из-за чего строка на стыке страниц теряется или дублируется), поэтому ты добавляешь tiebreaker вроде первичного ключа: сортируй по (created_at, id) и сравнивай кортеж целиком. Второе: нужен составной индекс в точном порядке колонок и направлении твоего ORDER BY:

CREATE INDEX idx_articles_created_id ON articles (created_at DESC, id DESC);

Без этого индекса сравнение кортежа в WHERE всё ещё работает, но планировщик откатывается к сортировке+скану, и ты теряешь ровный latency. С ним каждая страница — один диапазонный скан по индексу: база прыгает к позиции курсора и читает ровно 20 строк.

Курсор непрозрачен, и это решение про контракт

Никогда не отдавай клиентам сырые (created_at, id). Кодируй keyset в непрозрачную строку — Base64 от JSON со значениями сортировки это распространённый паттерн — и возвращай как nextCursor. Клиент обращается с ним как с чёрным ящиком и присылает обратно дословно. Это покупает свободу менять ключ сортировки, добавлять поля или переезжать на другое хранилище позже, не ломая контракт клиента; это также не даёт клиентам собирать руками курсоры, которые сикают в дорогую область. Спека Relay Connection в GraphQL формализует ровно это: edges несут покурсорные значения cursor, а pageInfo несёт hasNextPage / endCursor. Для двунаправленной пагинации ты поддерживаешь и after/first, и before/last, переворачивая оператор сравнения (< становится >) и направление ORDER BY, а затем разворачивая возвращённый срез, чтобы клиент видел стабильный порядок.

Скрытая цена: тотальные счётчики

Даже с keyset футер «Показано 1–20 из 4 812 339» — это своя ловушка производительности. В Postgres COUNT(*) нельзя ответить из метаданных, потому что MVCC означает, что каждая транзакция видит свой набор видимых строк — движку приходится обойти строки, чтобы посчитать те, что видимы тебе. На большой таблице это полный скан, который тем медленнее, чем больше таблица, и часто затмевает страничный запрос, к которому прилагается. Ходы сеньора: убрать точный тотал (большинству продуктов он не нужен), взять быструю оценку из pg_class.reltuples (поддерживается актуальной через ANALYZE, обычно в пределах ~10% от настоящего значения) или достать LIMIT n+1 и сообщать только «есть следующая страница» — а это всё, что бесконечному скроллу когда-либо реально нужно.