Пагинация в API: offset, cursor и keyset — как листать данные без дублей и тормозов

Чем offset-пагинация плоха на больших таблицах, как работает keyset (seek) и курсор, зачем tiebreaker по id, как подписать курсор, листать назад и не делать COUNT(*). SQL и Python.

14 мин чтениясистемный дизайн · api · базы данных · python

Коротко

СпособЗапросГлубокие страницыВставки во время чтенияПереход на страницу N
OffsetLIMIT 20 OFFSET 40000медленно, O(N)O(N)дубли и пропускида
Keyset (seek)WHERE (created_at, id) < (?, ?) LIMIT 20быстро, как перваястабильнонет
Курсор (page token)keyset, упакованный в непрозрачную строкубыстростабильнонет
  • Offset прост и позволяет прыгать на любую страницу, но база всё равно читает и выбрасывает все предыдущие строки. На странице 50 000 это заметно, а при вставках страницы «съезжают».
  • Keyset (его же называют seek method) запоминает последний показанный элемент и просит «всё, что после него». Работает по индексу за одинаковое время на любой глубине.
  • Сортировка должна быть уникальной. ORDER BY created_at без id в конце теряет строки с одинаковым временем.
  • Курсор для клиента непрозрачен. Внутри — ключ последней строки, фильтры и версия формата, снаружи — строка, которую клиент не разбирает и не может подделать.
  • COUNT(*) на каждый запрос не нужен. Чтобы понять, есть ли следующая страница, достаточно взять на одну строку больше.

Зачем пагинация вообще

GET /orders без ограничений однажды вернёт миллион строк: база будет их читать, сервер — сериализовать в JSON на сотни мегабайт, сеть — передавать, а клиент — падать по памяти. Пагинация ограничивает размер ответа и делает время ответа предсказуемым.

Требования к ней обычно такие:

  1. Ответ быстрый на любой странице, а не только на первой.
  2. Пролистав всё, клиент увидит каждую запись ровно один раз, даже если данные меняются.
  3. Клиент не может одним запросом положить базу (лимит на размер страницы).
  4. Формат можно менять, не ломая клиентов.

Offset нарушает первые два пункта. Посмотрим, как именно.

Offset-пагинация

Самый очевидный вариант: страница pp размера kk — это LIMIT k OFFSET p*k.

SELECT id, created_at, amount FROM orders ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 40000;

В API это выглядит как ?page=2001&per_page=20 или ?offset=40000&limit=20.

Проблема 1: глубокие страницы медленные

OFFSET не умеет «перепрыгнуть» к нужной строке. База идёт по индексу (или, хуже, сортирует всю таблицу), читает первые 40 020 строк и выбрасывает 40 000. Стоимость растёт линейно с номером страницы.

Проверим на SQLite: миллион заказов, индекс по (created_at, id), по три заказа в секунду, чтобы время повторялось.

import random import sqlite3 import time db = sqlite3.connect(':memory:') db.execute('CREATE TABLE orders (id INTEGER PRIMARY KEY, user_id INT, ' 'created_at INT, amount INT)') random.seed(1) db.executemany( 'INSERT INTO orders (user_id, created_at, amount) VALUES (?, ?, ?)', ((random.randint(1, 1000), 1_700_000_000 + i // 3, random.randint(1, 10_000)) for i in range(1_000_000))) # по три заказа в секунду: время повторяется db.execute('CREATE INDEX idx_orders_created ON orders (created_at, id)') def offset_page(page, size=20): return db.execute( 'SELECT id, created_at FROM orders ORDER BY created_at DESC, id DESC ' 'LIMIT ? OFFSET ?', (size, page * size)).fetchall() def keyset_page(after=None, size=20): if after is None: return db.execute( 'SELECT id, created_at FROM orders ORDER BY created_at DESC, id DESC ' 'LIMIT ?', (size,)).fetchall() last_id, last_created = after return db.execute( 'SELECT id, created_at FROM orders WHERE (created_at, id) < (?, ?) ' 'ORDER BY created_at DESC, id DESC LIMIT ?', (last_created, last_id, size)).fetchall() def bench(fn, *args, repeat=20): start = time.perf_counter() for _ in range(repeat): fn(*args) return (time.perf_counter() - start) / repeat * 1000 for page in (0, 1_000, 10_000, 49_000): # курсор, указывающий на ту же позицию, что и OFFSET prev = offset_page(page - 1)[-1] if page else None assert keyset_page(prev) == offset_page(page) print(f'страница {page:>6}: OFFSET {bench(offset_page, page):7.2f} мс, ' f'keyset {bench(keyset_page, prev):5.2f} мс')
страница 0: OFFSET 0.01 мс, keyset 0.01 мс страница 1000: OFFSET 0.15 мс, keyset 0.01 мс страница 10000: OFFSET 1.46 мс, keyset 0.01 мс страница 49000: OFFSET 7.16 мс, keyset 0.01 мс

Абсолютные цифры зависят от машины, важна форма: offset растёт линейно, keyset стоит на месте. И это лучший случай для offset — база в памяти, а индекс покрывающий (в нём есть все нужные колонки). С SELECT * на тех же данных страница 49 000 заняла у меня 17 мс: для каждой пропущенной строки база ещё и ходит в таблицу. На реальном диске и таблице в сотни миллионов строк это превращается в секунды и в лёгкий способ положить базу перебором страниц. Подробнее о покрывающих индексах — в статье про индексы в базах данных.

Проблема 2: данные едут под ногами

Лента из 10 постов, по 4 на страницу. Пока человек читает первую страницу, появляются два новых.

import sqlite3 db = sqlite3.connect(':memory:') db.execute('CREATE TABLE posts (id INTEGER PRIMARY KEY, created_at INT)') db.executemany('INSERT INTO posts (id, created_at) VALUES (?, ?)', [(i, 100 + i) for i in range(1, 11)]) # посты 1..10 NEWEST = 'ORDER BY created_at DESC, id DESC' def ids(rows): return [r[0] for r in rows] # OFFSET: пока читали первую страницу, появились два новых поста p1 = ids(db.execute(f'SELECT * FROM posts {NEWEST} LIMIT 4 OFFSET 0')) db.executemany('INSERT INTO posts VALUES (?, ?)', [(11, 111), (12, 112)]) p2 = ids(db.execute(f'SELECT * FROM posts {NEWEST} LIMIT 4 OFFSET 4')) print('OFFSET:', p1, p2) # OFFSET: а если пост с первой страницы удалили db.execute('DELETE FROM posts WHERE id IN (11, 12)') p1 = ids(db.execute(f'SELECT * FROM posts {NEWEST} LIMIT 4 OFFSET 0')) db.execute('DELETE FROM posts WHERE id = 9') p2 = ids(db.execute(f'SELECT * FROM posts {NEWEST} LIMIT 4 OFFSET 4')) print('OFFSET:', p1, p2) db.execute('INSERT INTO posts VALUES (9, 109)') # Keyset: курсор — последний показанный (created_at, id) p1 = db.execute(f'SELECT * FROM posts {NEWEST} LIMIT 4').fetchall() db.executemany('INSERT INTO posts VALUES (?, ?)', [(11, 111), (12, 112)]) last_id, last_created = p1[-1] p2 = db.execute(f'SELECT * FROM posts WHERE (created_at, id) < (?, ?) ' f'{NEWEST} LIMIT 4', (last_created, last_id)).fetchall() print('keyset:', ids(p1), ids(p2))
OFFSET: [10, 9, 8, 7] [8, 7, 6, 5] OFFSET: [10, 9, 8, 7] [5, 4, 3, 2] keyset: [10, 9, 8, 7] [6, 5, 4, 3]
  • После вставки посты 8 и 7 показаны дважды. В бесконечной ленте это раздражает, а в экспорте данных — портит отчёт.
  • После удаления пост 6 не увидит никто: все строки сдвинулись на одну позицию вверх, и он «перепрыгнул» на первую страницу, которую уже прочитали.
  • Keyset спокойно пережил вставку: «всё, что старше поста 7», не зависит от того, что появилось сверху.

Второй случай опаснее первого. Дубли видно, а пропуски — нет. Если по offset-пагинации синхронизируют данные между системами, часть записей просто не доедет, и никто не заметит.

Когда offset всё-таки нормален

  • Маленькие таблицы и админки, где страниц десятки, а не тысячи.
  • Нужен переход «на страницу 7» и общее число страниц — типичная таблица в бэк-офисе.
  • Данные почти не меняются, или дубли с пропусками не критичны.

Если глубокие страницы всё-таки нужны, помогает «отложенный join» (deferred join): сначала по узкому индексу найти только id нужной страницы, а потом дочитать полные строки по этим 20 ключам.

SELECT o.* FROM orders o JOIN ( SELECT id FROM orders ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 980000 ) page ON o.id = page.id ORDER BY o.created_at DESC, o.id DESC;

На тех же данных это ускорило SELECT * на странице 49 000 с 17 до 6.5 мс. Линейный рост никуда не делся, но константа стала меньше. Другой популярный приём — просто запретить глубокие страницы. Например, в Elasticsearch from + size по умолчанию ограничены 10 000 документами (настройка index.max_result_window), а дальше предлагается search_after — тот же keyset.

Keyset-пагинация (seek method)

Вместо номера страницы клиент передаёт ключ последней увиденной строки, а сервер просит «следующие 20 строк после этого ключа»:

-- первая страница SELECT id, created_at, amount FROM orders ORDER BY created_at DESC, id DESC LIMIT 20; -- следующая: (:ts, :id) — последняя строка предыдущей страницы SELECT id, created_at, amount FROM orders WHERE (created_at, id) < (:ts, :id) ORDER BY created_at DESC, id DESC LIMIT 20;

С индексом по (created_at, id) база находит нужную точку в B-дереве за O(log⁡n)O(\log n) и читает ровно 20 записей подряд. Поэтому время одинаковое на первой и на миллионной странице. Название «seek» отсюда же: мы не пропускаем строки, а сразу ищем позицию.

Чем приходится платить:

  • Нельзя прыгнуть на страницу N. Только вперёд и назад от текущей позиции. Для ленты и бесконечной прокрутки это не проблема, для таблицы с номерами страниц — проблема.
  • Сортировка ограничена индексом. Если пользователь может сортировать по пяти колонкам, нужны пять индексов (каждый с id в конце), иначе keyset превратится в полный скан.
  • Логика сложнее, особенно при разных направлениях сортировки и листании назад. Об этом ниже.

Tiebreaker: почему нужен id в конце

Самая частая ошибка — курсор только по времени. Пусть пять событий, три из которых записаны одной транзакцией с одинаковым created_at:

import sqlite3 db = sqlite3.connect(':memory:') db.execute('CREATE TABLE events (id INTEGER PRIMARY KEY, created_at INT)') # пачка событий записана одной транзакцией — одинаковое время db.executemany('INSERT INTO events VALUES (?, ?)', [(1, 10), (2, 20), (3, 20), (4, 20), (5, 20), (6, 30)]) def walk(query, size=2): seen, cursor = [], None while True: rows = db.execute(query(cursor), {'size': size, **(cursor or {})}).fetchall() if not rows: return seen seen += [r[0] for r in rows] cursor = {'id': rows[-1][0], 'created_at': rows[-1][1]} def by_time_only(cursor): where = 'WHERE created_at > :created_at' if cursor else '' return f'SELECT id, created_at FROM events {where} ORDER BY created_at LIMIT :size' def with_tiebreaker(cursor): where = 'WHERE (created_at, id) > (:created_at, :id)' if cursor else '' return f'SELECT id, created_at FROM events {where} ORDER BY created_at, id LIMIT :size' print('только время:', walk(by_time_only)) print('время + id: ', walk(with_tiebreaker))
только время: [1, 2, 6] время + id: [1, 2, 3, 4, 5, 6]

Первая страница закончилась на событии 2 со временем 20. Условие created_at > 20 отрезало события 3, 4 и 5 — они потеряны. Если поставить >=, получим обратную проблему: событие 2 придёт повторно, а при большой пачке одинаковых значений клиент зациклится на одной странице.

Правило: ключ сортировки должен быть уникальным. Добавьте в конец ORDER BY первичный ключ, и в курсор, и в индекс. Время в миллисекундах «почти уникально», но «почти» — это и есть баг, который всплывёт на проде.

Разные направления сортировки

Сравнение кортежей (a, b) < (x, y) работает, только если обе колонки сортируются в одну сторону. Если нужно «дорогие сверху, при равной цене — по возрастанию id», условие раскрывают вручную. Листание назад — зеркальное условие и сортировка, а результат разворачивается:

import random import sqlite3 db = sqlite3.connect(':memory:') db.execute('CREATE TABLE products (id INTEGER PRIMARY KEY, price INT)') random.seed(2) db.executemany('INSERT INTO products VALUES (?, ?)', [(i, random.choice([100, 200, 300])) for i in range(1, 16)]) # Сортировка: дорогие сверху, при равной цене — по возрастанию id. # Row value (price, id) < (?, ?) здесь не подходит: направления разные. NEXT = '''SELECT id, price FROM products WHERE price < :price OR (price = :price AND id > :id) ORDER BY price DESC, id ASC LIMIT :n''' # Назад: условие и сортировка зеркальные, результат разворачиваем PREV = '''SELECT id, price FROM products WHERE price > :price OR (price = :price AND id < :id) ORDER BY price ASC, id DESC LIMIT :n''' def forward(after, n=4): return db.execute(NEXT, {'price': after[1], 'id': after[0], 'n': n}).fetchall() def backward(before, n=4): rows = db.execute(PREV, {'price': before[1], 'id': before[0], 'n': n}).fetchall() return rows[::-1] everything = db.execute('SELECT id, price FROM products ORDER BY price DESC, id ASC').fetchall() page1 = everything[:4] page2 = forward(page1[-1]) page3 = forward(page2[-1]) print(page1, page2, page3, sep='\n') assert page1 + page2 + page3 == everything[:12] assert backward(page3[0]) == page2 # «предыдущая» от третьей — снова вторая print('назад от третьей:', backward(page3[0]))
[(6, 300), (7, 300), (10, 300), (12, 300)] [(14, 300), (15, 300), (4, 200), (8, 200)] [(9, 200), (1, 100), (2, 100), (3, 100)] назад от третьей: [(14, 300), (15, 300), (4, 200), (8, 200)]

Для такого запроса индекс должен быть (price DESC, id ASC) — в PostgreSQL и современных MySQL направление можно задать для каждой колонки индекса. Условие с OR планировщики иногда разворачивают плохо, поэтому EXPLAIN обязателен. В PostgreSQL сравнение row values (a, b) < (x, y) по индексу (a, b) работает эффективно, в старых версиях MySQL — не всегда; если не уверены, проверьте план. Иногда помогает добавить избыточное условие price <= :price, которое планировщик точно умеет превратить в диапазон.

NULL в колонке сортировки

NULL не сравнивается ни с чем: (NULL, 5) < (100, 7) даёт не true и не false, а NULL, и строка молча пропадает из выдачи. Варианты: сделать колонку NOT NULL, сортировать по COALESCE(col, значение) с индексом по выражению или явно обрабатывать «хвост» из NULL-значений отдельной веткой условия. Самый надёжный — первый.

Курсор: keyset, завёрнутый в токен

Отдавать клиенту ?after_ts=1700000200&after_id=7 можно, но это привязывает API к схеме таблицы. Поменяли сортировку — сломали всех клиентов. Поэтому значения упаковывают в непрозрачную строку — курсор, или page token:

{ "items": [101, 100, 98], "next_page_token": "ROYWF8sLCxK7Y9HsHVSE5HsiYWZ0ZXIiOlsx..." }

Так делают многие публичные API. В рекомендациях Google (AIP-158) это page_size, page_token и next_page_token. У Stripe — параметры starting_after и ending_before с id объекта и флаг has_more. GitHub в REST API отдаёт ссылки на соседние страницы в заголовке Link. Детали разные, идея одна: клиент получает от сервера «где продолжить» и возвращает это без изменений.

Что положить внутрь курсора:

  • ключ последней строки — значения всех колонок сортировки, включая id;
  • параметры запроса: фильтры и сортировку. Иначе клиент возьмёт курсор от status=paid и подставит его в запрос с status=new, получив бессмыслицу;
  • версию формата, чтобы потом его можно было поменять.

Base64 — это не защита: клиент раскодирует JSON за секунду и начнёт подставлять свои значения. Курсор подписывают HMAC, и сервер отвергает всё, что подписи не соответствует:

import base64 import hashlib import hmac import json SECRET = b'change-me' # в проде — из секретов, а не из кода class BadCursor(Exception): pass def _b64(data: bytes) -> str: return base64.urlsafe_b64encode(data).decode().rstrip('=') def encode_cursor(payload: dict) -> str: raw = json.dumps(payload, separators=(',', ':'), sort_keys=True).encode() sig = hmac.new(SECRET, raw, hashlib.sha256).digest()[:16] return _b64(sig + raw) def decode_cursor(token: str) -> dict: try: blob = base64.urlsafe_b64decode(token + '=' * (-len(token) % 4)) except ValueError: raise BadCursor('не base64') sig, raw = blob[:16], blob[16:] good = hmac.new(SECRET, raw, hashlib.sha256).digest()[:16] if not hmac.compare_digest(sig, good): raise BadCursor('подпись не совпала') return json.loads(raw) token = encode_cursor({'v': 1, 'after': [1700000200, 7], 'status': 'paid'}) print(decode_cursor(token)) # Клиент разобрал курсор и поменял фильтр, оставив старую подпись blob = base64.urlsafe_b64decode(token + '=' * (-len(token) % 4)) tampered = _b64(blob[:16] + blob[16:].replace(b'paid', b'void')) try: decode_cursor(tampered) except BadCursor as exc: print('отклонён:', exc)
{'after': [1700000200, 7], 'status': 'paid', 'v': 1} отклонён: подпись не совпала

Если в курсоре есть что-то, чего клиент не должен видеть, его шифруют, а не только подписывают. Обычно хватает подписи: ключ сортировки и так виден в самих данных.

Обработчик целиком

Соберём эндпоинт GET /orders?status=paid&page_size=4&page_token=... поверх функций выше. Две детали, на которые стоит обратить внимание: лимит на page_size и запрос LIMIT n + 1.

db = sqlite3.connect(':memory:') db.execute('CREATE TABLE orders (id INTEGER PRIMARY KEY, status TEXT, created_at INT)') db.executemany('INSERT INTO orders VALUES (?, ?, ?)', [(i, 'paid' if i % 3 else 'new', 1000 + i // 2) for i in range(1, 21)]) db.execute('CREATE INDEX idx_status_created ON orders (status, created_at, id)') def list_orders(status, limit=3, page_token=None): limit = max(1, min(limit, 100)) # клиент не должен просить миллион params = {'status': status, 'n': limit + 1} where = 'status = :status' if page_token: cur = decode_cursor(page_token) if cur.get('status') != status: raise BadCursor('курсор от другого запроса') params['ts'], params['id'] = cur['after'] where += ' AND (created_at, id) < (:ts, :id)' rows = db.execute( f'SELECT id, created_at FROM orders WHERE {where} ' f'ORDER BY created_at DESC, id DESC LIMIT :n', params).fetchall() # Взяли на одну строку больше: так без COUNT(*) понятно, есть ли ещё has_more = len(rows) > limit rows = rows[:limit] next_token = None if has_more: last_id, last_ts = rows[-1] next_token = encode_cursor({'v': 1, 'status': status, 'after': [last_ts, last_id]}) return {'items': [r[0] for r in rows], 'next_page_token': next_token} token, pages = None, [] while True: page = list_orders('paid', limit=4, page_token=token) pages.append(page['items']) token = page['next_page_token'] if token is None: break print(pages) first = list_orders('paid', limit=4) try: list_orders('new', page_token=first['next_page_token']) except BadCursor as exc: print('отклонён:', exc)
[[20, 19, 17, 16], [14, 13, 11, 10], [8, 7, 5, 4], [2, 1]] отклонён: курсор от другого запроса

Индекс (status, created_at, id) устроен по правилу левого префикса: сначала колонка фильтра по равенству, потом колонки сортировки. Тогда база находит нужный status, внутри него — позицию курсора и читает строки подряд.

Последняя страница возвращает next_page_token: null, а не пустую страницу после неё: за счёт лишней строки сервер знает, что дальше ничего нет, и клиенту не нужен лишний запрос.

Общее количество: нужно ли total

Интерфейсы любят «Показано 1–20 из 48 213». Но COUNT(*) с фильтром на большой таблице — это проход по всем подходящим строкам. В PostgreSQL из-за MVCC он не берётся из метаданных и честно сканирует индекс или таблицу. Делать это на каждый запрос страницы — дороже самой страницы.

Что делают вместо этого:

  • Не показывают total. Для ленты достаточно has_more.
  • Показывают приблизительное значение: «больше 10 000», оценку планировщика (reltuples в PostgreSQL, вывод EXPLAIN) или кэшированный счётчик.
  • Считают отдельным запросом, только когда пользователь его попросил, и кэшируют.
  • Ограничивают подсчёт: SELECT COUNT(*) FROM (SELECT 1 FROM ... LIMIT 10001) — либо точное число, либо «10 000+».

Другие подходы

  • Пагинация по снимку. Для ранжированных лент, где порядок меняется между запросами, на старте сохраняют список id (в Redis на несколько минут), и курсор указывает позицию в нём. Подробно — в разделе про курсор в статье о ленте новостей.
  • Курсоры базы данных (DECLARE CURSOR в PostgreSQL) держат открытую транзакцию на сервере. Для экспорта внутри одного процесса — удобно, для HTTP API без состояния — нет: соединение не может жить между запросами разных клиентов.
  • Диапазон по id для пакетной обработки. Фоновая задача, которая обходит всю таблицу, делает WHERE id > :last ORDER BY id LIMIT 1000 — это тот же keyset по первичному ключу, самый дешёвый из возможных.
  • Монотонные id. Если id растут вместе со временем (Snowflake, ULID, UUIDv7), сортировка «по времени» превращается в сортировку по id, и курсор становится одним числом. Как такие id устроены — в статье про генератор уникальных id.

Типичные ошибки

  • Offset на большой таблице, а потом удивление, почему бот, перебирающий страницы, положил базу.
  • Нет tiebreaker. Сортировка по неуникальной колонке теряет или дублирует строки на границе страниц.
  • Нет подходящего индекса. Keyset без индекса по колонкам сортировки — это тот же полный скан с сортировкой.
  • Курсор не привязан к фильтрам. Курсор от одного запроса работает в другом и выдаёт странный результат.
  • Курсор не подписан. Клиенты начинают генерировать его сами, и сменить формат уже нельзя.
  • Нет лимита на page_size. ?limit=1000000 выключает пагинацию целиком.
  • COUNT(*) в каждом ответе. Подсчёт оказывается дороже самой страницы.
  • NULL в колонке сортировки. Строки с NULL молча выпадают из выдачи.
  • Клиент собирает курсор сам или хранит его вечно. Курсор — одноразовая ссылка «где продолжить», а не стабильный идентификатор.

Как отвечать на собеседовании

Пагинация всплывает почти в любом системном дизайне с лентой, историей заказов или поиском: «как клиент получит следующие 20 элементов?». Сильный ответ:

  1. Назвать проблему offset: линейное время и сдвиг при вставках и удалениях.
  2. Предложить keyset по уникальному ключу сортировки (created_at, id) с индексом на ту же пару.
  3. Отдавать клиенту непрозрачный подписанный курсор с фильтрами и версией, а не сырые значения.
  4. Ограничить размер страницы, вместо COUNT(*) отдавать has_more через LIMIT n + 1.
  5. Сказать, когда offset допустим: маленькие таблицы и админки с переходом на страницу N.

Частые уточняющие вопросы:

  • Как сделать переход на конкретную страницу при keyset? Никак напрямую. Либо offset (если глубина ограничена), либо заранее посчитанные «закладки» — ключи каждой сотой страницы.
  • Что будет, если строку из курсора удалили? Ничего: условие < (ts, id) не требует, чтобы такая строка существовала, позиция определяется значениями.
  • Как листать назад? Зеркальное условие и сортировка, результат разворачивается; в курсор кладут направление.
  • Что делать, если сортировку выбирает пользователь? Индекс на каждую поддерживаемую сортировку с id в конце и проверка, что курсор создан для той же сортировки.

Как пагинация вписывается в общий план интервью, описано в статье про подходы к проектированию систем.

Потренироваться в спокойной обстановке

Все задачи