Все заметки
Программирование

OFFSET 200 000: почему 10 000-я страница тормозит и как keyset-пагинация это чинит

OFFSET всё равно читает каждую пропущенную строку и сдвигает страницы, когда приходят новые записи. Keyset-пагинация по (created_at, id), курсор в base64, цена COUNT(*) и полная реализация на Django.

В админке есть список заказов: новые сверху, по 20 на страницу. Первые страницы открываются мгновенно. Потом кто-то ищет старый заказ, вписывает в URL ?page=10000, и страница заметно задумывается. В это же время в мобильном приложении пользователь жмёт «Загрузить ещё» и видит заказ, который только что уже листал: пока он скроллил, пришёл новый заказ и всё сдвинулось на одну позицию вниз.

У обеих проблем один корень: OFFSET. Разберём, почему он деградирует, как устроена keyset (cursor) пагинация, как кодировать курсор, сколько на самом деле стоит COUNT(*) и как всё это написать на Django.

Как работает OFFSET и почему он тормозит

Paginator в Django и срезы вида qs[200000:200020] в итоге превращаются в такой SQL:

SELECT id, customer_id, amount, created_at
FROM shop_order
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 200000;

Кажется, что PostgreSQL «перепрыгивает» сразу к 200 001-й строке. Это не так. В B-tree индексе нет понятия «N-й элемент»: это упорядоченное дерево, по нему можно искать по ключу, но не по порядковому номеру. Поэтому executor достаёт строки по порядку, выбрасывает первые 200 000 и возвращает следующие 20. В документации PostgreSQL это сказано прямо: строки, пропущенные через OFFSET, всё равно вычисляются на сервере, поэтому большой OFFSET может быть неэффективен.

Это легко увидеть через EXPLAIN ANALYZE. Время зависит от вашего железа, поэтому я его не привожу; смотреть нужно на actual rows:

psql -c "EXPLAIN ANALYZE SELECT * FROM shop_order ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 200000;"

 Limit  (... rows=20 ...) (actual time=... rows=20 loops=1)
   ->  Index Scan using order_created_id_desc on shop_order
         (... rows=302000 ...) (actual time=... rows=200020 loops=1)

Limit вернул 20 строк, но Index Scan под ним прочитал 200 020. Работа растёт линейно с номером страницы: 10-я страница дешёвая, 10 000-я дорогая. А если подходящего индекса под ORDER BY нет, всё ещё хуже: PostgreSQL придётся прочитать таблицу и отсортировать.

Вторая проблема: страницы «плывут»

Помимо скорости, результат OFFSET нестабилен. Пользователь посмотрел первую страницу (строки 1–20). Тем временем пришло три новых заказа. Он запрашивает вторую страницу: OFFSET 20. Теперь на позициях 21–40 стоят бывшие строки 18–37, и три заказа он увидит дважды. Если строку удалили, наоборот, одна строка не покажется никогда.

В админке это просто неудобство. А в ленте с бесконечным скроллом или, хуже того, в фоновой задаче, которая постранично экспортирует или обрабатывает данные, это означает дубли и пропущенные записи.

Keyset пагинация: «продолжи с того места, где я остановился»

Идея простая: вместо «пропусти N строк» говорим «дай строки после последней, которую я видел». Последняя строка — это значение ключа сортировки. Чище всего передать его через row comparison (сравнение кортежей) в PostgreSQL:

-- first page
SELECT id, customer_id, amount, created_at
FROM shop_order
ORDER BY created_at DESC, id DESC
LIMIT 21;

-- next page: last row of the previous page was
-- (created_at = '2026-11-03 18:42:07.512301+05', id = 918273)
SELECT id, customer_id, amount, created_at
FROM shop_order
WHERE (created_at, id) < ('2026-11-03 18:42:07.512301+05', 918273)
ORDER BY created_at DESC, id DESC
LIMIT 21;

Выражение (created_at, id) < (a, b) сравнивается лексикографически: сначала created_at < a, а при равенстве id < b. Ровно как ORDER BY created_at DESC, id DESC.

Теперь главное. Если есть B-tree индекс по (created_at, id), PostgreSQL использует это условие как Index Cond: спускается по дереву к нужной точке и читает оттуда 21 строку. Ничего не выбрасывается:

 Limit  (... rows=21 ...) (actual time=... rows=21 loops=1)
   ->  Index Scan using order_created_id_desc on shop_order
         (actual time=... rows=21 loops=1)
         Index Cond: (ROW(created_at, id) < ROW('2026-11-03 18:42:07.512301+05'::timestamptz, 918273))

Теперь первая страница и «10 000-я» стоят одинаково: один спуск по дереву плюс чтение LIMIT строк. Новые строки ничего не сдвигают: условие говорит «после этой строки», а не «после 20-й позиции».

OFFSET помнит, «сколько строк пропустить», а keyset — «где я остановился». Первое ломается при изменении данных, второе нет.

Одна лишняя строка (LIMIT 21) нужна, чтобы узнать, есть ли следующая страница: пришла 21-я строка — следующая страница есть, саму строку пользователю не показываем.

Зачем нужен второй ключ

Пагинация только по created_at выглядит соблазнительно, но это ошибка. created_at не уникален: bulk-импорт, несколько записей в одной транзакции (now() возвращает время начала транзакции) или просто совпавшая метка времени. Если граница страницы попадёт между двумя строками с одинаковым created_at:

  • WHERE created_at < :last потеряет вторую;
  • WHERE created_at <= :last продублирует первую.

Решение — сделать порядок полным, добавив в конец уникальный столбец. Обычно это первичный ключ: ORDER BY created_at DESC, id DESC. Тогда у каждой строки однозначное место в порядке, и курсор указывает ровно на одну точку.

Реализация в Django

Модель и индекс. Порядок столбцов в индексе должен совпадать с ORDER BY. PostgreSQL умеет читать B-tree в обратную сторону, поэтому подойдёт и индекс (created_at, id); важно, чтобы направления обоих столбцов совпадали.

# shop/models.py
from django.db import models


class Order(models.Model):
    customer_id = models.BigIntegerField()
    amount = models.DecimalField(max_digits=12, decimal_places=2)
    created_at = models.DateTimeField()  # NOT NULL by default

    class Meta:
        indexes = [
            models.Index(fields=["-created_at", "-id"], name="order_created_id_desc"),
        ]

Теперь курсор. Отдавать клиенту внутреннюю структуру незачем: кладём created_at и id в JSON и кодируем URL-safe base64. Для клиента это просто непрозрачная (opaque) строка, которую он возвращает в следующем запросе.

# shop/cursors.py
import base64
import json
from datetime import datetime


class InvalidCursor(ValueError):
    pass


def encode_cursor(created_at: datetime, pk: int) -> str:
    raw = json.dumps({"c": created_at.isoformat(), "i": pk}, separators=(",", ":"))
    return base64.urlsafe_b64encode(raw.encode()).decode().rstrip("=")


def decode_cursor(cursor: str) -> tuple[datetime, int]:
    try:
        padded = cursor + "=" * (-len(cursor) % 4)
        data = json.loads(base64.urlsafe_b64decode(padded))
        return datetime.fromisoformat(data["c"]), int(data["i"])
    except (ValueError, KeyError, TypeError) as exc:
        raise InvalidCursor("bad cursor") from exc

isoformat() сохраняет микросекунды. Это важно: timestamptz в PostgreSQL хранится с точностью до микросекунд, и если в курсоре окажется время, округлённое до миллисекунд, строки на границе будут дублироваться или теряться. По этой же причине клиент не должен собирать курсор сам: Date в JavaScript знает только миллисекунды.

Функция страницы. В Django ORM нет публичного API для сравнения кортежей, поэтому пишем эквивалентное условие через Q:

# shop/pagination.py
from django.db.models import Q

from .cursors import decode_cursor, encode_cursor
from .models import Order


def orders_page(cursor: str | None = None, limit: int = 20):
    qs = Order.objects.order_by("-created_at", "-id")
    if cursor:
        created_at, pk = decode_cursor(cursor)
        qs = qs.filter(
            Q(created_at__lt=created_at) | Q(created_at=created_at, id__lt=pk),
            created_at__lte=created_at,  # redundant, but gives the planner an index condition
        )
    rows = list(qs[: limit + 1])  # one extra row tells us whether a next page exists
    has_next = len(rows) > limit
    rows = rows[:limit]
    next_cursor = encode_cursor(rows[-1].created_at, rows[-1].pk) if has_next else None
    return rows, next_cursor

Условие created_at__lte=created_at логически избыточно: обе ветки OR его подразумевают. Но оно даёт планировщику простое диапазонное условие, которое PostgreSQL использует как Index Cond, а OR применяет как фильтр к нескольким прочитанным строкам. Без него на одном OR планировщик может не найти хороший план, так что проверяйте EXPLAIN на своих данных.

Если нужен именно row comparison, можно передать RawSQL как булево выражение в filter(). Имя таблицы здесь приходится писать руками, держите это в голове:

from django.db.models import BooleanField
from django.db.models.expressions import RawSQL

qs = qs.filter(
    RawSQL(
        '("shop_order"."created_at", "shop_order"."id") < (%s, %s)',
        (created_at, pk),
        output_field=BooleanField(),
    )
)

Во view невалидный курсор должен давать 400, а не 500, а limit — быть ограничен:

# shop/views.py
from django.http import JsonResponse

from .cursors import InvalidCursor
from .pagination import orders_page


def order_list(request):
    try:
        limit = max(1, min(int(request.GET.get("limit", 20)), 100))
    except ValueError:
        limit = 20
    try:
        rows, next_cursor = orders_page(request.GET.get("cursor"), limit)
    except InvalidCursor:
        return JsonResponse({"error": "invalid cursor"}, status=400)
    return JsonResponse({
        "results": [
            {"id": o.pk, "amount": str(o.amount), "created_at": o.created_at.isoformat()}
            for o in rows
        ],
        "next_cursor": next_cursor,
    })

Если вы на DRF, там есть готовый CursorPagination, построенный на той же идее. Требование у него то же: поле сортировки должно быть неизменяемым и по возможности уникальным.

Total count: сколько стоит «Всего: 4 812 337»

Paginator в Django вызывает count(), чтобы посчитать число страниц, то есть SELECT COUNT(*) на каждый запрос. В PostgreSQL число строк в таблице нигде не хранится готовым. Причина — MVCC: каждая транзакция видит свой снапшот, и в один и тот же момент «количество строк» для двух транзакций может отличаться. Поэтому точный COUNT(*) пересчитывает все видимые строки. Index-only scan может помочь, но всё равно проходит по всем записям индекса. То есть если ускорить саму страницу через keyset, а рядом оставить COUNT(*), медленное место просто переедет.

Варианты:

Подход Точность Цена Когда подходит
COUNT(*) точно читает все подходящие строки маленькая таблица или сильный фильтр
pg_class.reltuples оценка почти бесплатно вся таблица без фильтров
Оценка из EXPLAIN оценка, иногда сильно мимо почти бесплатно фильтрованный запрос, показать «~12 тыс.»
Не показывать count — бесплатно бесконечный скролл, API
-- exact: reads every visible row
SELECT count(*) FROM shop_order;

-- estimate for the whole table: updated by VACUUM / ANALYZE
SELECT reltuples::bigint AS estimate
FROM pg_class
WHERE oid = 'shop_order'::regclass;

reltuples обновляется при VACUUM, ANALYZE (в том числе autovacuum) и CREATE INDEX. Если таблицу ещё ни разу не анализировали, в PostgreSQL 14 и новее там будет -1, учитывайте это в коде. Для фильтрованного запроса оценку планировщика можно взять прямо из Django:

import json


def estimate_count(qs) -> int:
    plan = json.loads(qs.order_by().explain(format="json"))
    return int(plan[0]["Plan"]["Plan Rows"])


# usage
qs = Order.objects.filter(customer_id=42)
approx = estimate_count(qs)

Эта оценка опирается на статистику и на сложных условиях может ошибаться в разы. Поэтому в UI показывайте её как «около 12 000», а не как точное число. А чаще всего правильный ответ — не считать вовсе: «есть следующая страница» и так бесплатно даёт LIMIT + 1.

Грабли в продакшене

  • Нельзя прыгнуть на страницу N. Keyset даёт только «следующую/предыдущую». Если бизнес просит «перейти на 47-ю страницу», обычно на самом деле нужен фильтр по дате или ID: «перейти к марту 2025» легко пишется как WHERE created_at < '2025-04-01'.
  • Предыдущая страница. Переворачиваете условие (>), переворачиваете сортировку (ORDER BY created_at, id), берёте LIMIT + 1 и разворачиваете результат в Python. Направление удобно хранить в самом курсоре.
  • Смешанные направления. Для ORDER BY created_at DESC, id ASC условие (created_at, id) < (...) не работает: сравнение кортежей идёт в одном направлении по обоим столбцам. Тут условие пишется вручную через OR, а индекс создаётся как (created_at DESC, id ASC).
  • NULL. Сравнение с NULL даёт NULL, такие строки не проходят условие и полностью выпадают из пагинации. Делайте столбцы сортировки NOT NULL или стройте индекс по выражению с COALESCE.
  • Сортировка по изменяемому полю. При пагинации по updated_at или score строка может переехать, пока пользователь листает: показаться на двух страницах или не показаться вовсе. Keyset и тут лучше OFFSET, но не идеален.
  • Фильтр и индекс. Добавили WHERE customer_id = 42 — индекс тоже должен быть (customer_id, created_at, id). Иначе PostgreSQL будет читать строки чужих клиентов и выбрасывать их фильтром, и вы вернётесь к проблеме OFFSET.
  • Курсору нельзя доверять. Base64 — не шифрование, любой может его раскодировать и подменить. Обычно это не страшно: курсор — лишь позиция, а проверка прав должна быть в самом queryset. Если же кладёте в курсор фильтры, подписывайте его через django.core.signing.
  • Фоновые задачи. Для обработки большой таблицы пачками используйте не OFFSET, а WHERE id > :last_id ORDER BY id LIMIT 1000 — простейшую форму keyset.

Короткий чеклист

  • Есть ли в конце ORDER BY уникальный столбец (обычно id)?
  • Есть ли индекс по столбцам ORDER BY в том же порядке и направлении? Стоят ли столбцы фильтра в начале индекса?
  • В EXPLAIN ANALYZE условие видно как Index Cond, а actual rows близко к LIMIT?
  • Курсор непрозрачный (base64), микросекунды сохраняются, невалидный курсор даёт 400.
  • limit ограничен сверху, следующая страница определяется через LIMIT + 1.
  • Столбцы сортировки NOT NULL.
  • На большой таблице вместо точного COUNT(*) — оценка или отсутствие count.

Итог

OFFSET хорош для маленьких таблиц и первых нескольких страниц, но он платит за каждую пропущенную строку и сдвигает страницы при изменении данных. Keyset пагинация с ключом, делающим порядок полным, и подходящим индексом отдаёт любую страницу за одинаковую цену. Делайте курсор непрозрачным, а COUNT(*) используйте только там, где он действительно нужен, и по возможности в виде оценки.

// комментарии

Загружаем комментарии...

    // следующий шаг

    Давайте построим что-нибудь вместе.

    Написать в Telegram
    aslbek@asldev: ~
    ❯