Пагинация в API: offset, cursor и keyset — как листать данные без дублей и тормозов
Чем offset-пагинация плоха на больших таблицах, как работает keyset (seek) и курсор, зачем tiebreaker по id, как подписать курсор, листать назад и не делать COUNT(*). SQL и Python.
Коротко
| Способ | Запрос | Глубокие страницы | Вставки во время чтения | Переход на страницу N |
|---|---|---|---|---|
| Offset | LIMIT 20 OFFSET 40000 | медленно, | дубли и пропуски | да |
| 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 на сотни мегабайт, сеть — передавать, а клиент — падать по памяти. Пагинация ограничивает размер ответа и делает время ответа предсказуемым.
Требования к ней обычно такие:
- Ответ быстрый на любой странице, а не только на первой.
- Пролистав всё, клиент увидит каждую запись ровно один раз, даже если данные меняются.
- Клиент не может одним запросом положить базу (лимит на размер страницы).
- Формат можно менять, не ломая клиентов.
Offset нарушает первые два пункта. Посмотрим, как именно.
Offset-пагинация
Самый очевидный вариант: страница размера — это 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-дереве за и читает ровно 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 элементов?». Сильный ответ:
- Назвать проблему offset: линейное время и сдвиг при вставках и удалениях.
- Предложить keyset по уникальному ключу сортировки
(created_at, id)с индексом на ту же пару. - Отдавать клиенту непрозрачный подписанный курсор с фильтрами и версией, а не сырые значения.
- Ограничить размер страницы, вместо
COUNT(*)отдаватьhas_moreчерезLIMIT n + 1. - Сказать, когда offset допустим: маленькие таблицы и админки с переходом на страницу N.
Частые уточняющие вопросы:
- Как сделать переход на конкретную страницу при keyset? Никак напрямую. Либо offset (если глубина ограничена), либо заранее посчитанные «закладки» — ключи каждой сотой страницы.
- Что будет, если строку из курсора удалили? Ничего: условие
< (ts, id)не требует, чтобы такая строка существовала, позиция определяется значениями. - Как листать назад? Зеркальное условие и сортировка, результат разворачивается; в курсор кладут направление.
- Что делать, если сортировку выбирает пользователь? Индекс на каждую поддерживаемую сортировку с
idв конце и проверка, что курсор создан для той же сортировки.
Как пагинация вписывается в общий план интервью, описано в статье про подходы к проектированию систем.