← вся теориятеория к собесу · FastAPI, Django и API

Пагинация и фильтрация в API

Пагинация и фильтрация больших коллекций

Отдать коллекцию целиком - путь к таймаутам и OOM (out of memory), поэтому пагинация обязательна, а её реализация выдаёт зрелость. Собес проверяет, знаешь ли ты, почему offset тормозит на глубине, и умеешь ли keyset-пагинацию со стабильным порядком.

Типовые формулировки: «offset или курсор?», «почему пагинация с большим offset медленная?», «как получить стабильный порядок страниц».

Offset/limit и его потолок

Большие коллекции отдают страницами, не целиком, иначе память, сеть и таймауты. Простейшее - offset/limit: limit задаёт размер страницы, offset сколько пропустить. Плюс - можно прыгнуть на любую страницу; минус - плохо масштабируется.

Deep offset тормозит: чтобы отдать страницу с offset=100000, БД проходит и ОТБРАСЫВАЕТ все пропускаемые строки - время растёт с offset. Хуже того, вставки между запросами сдвигают окно, и на границах страниц появляются дубли или пропуски.

// И всегда ставь потолок на limit: запрос limit=100000 без ограничения выкачает и положит сервис.

offset/limit: пропустить N, взять размер страницы
total: общее число записей выборки; COUNT дорог на больших таблицах

Keyset и стабильный порядок

Keyset (cursor) пагинация лечит обе беды offset: вместо «пропустить N» она берёт WHERE ключ > последнего виденного и идёт по индексу - время не зависит от глубины, а сдвиг окна вставками не ломает выборку. Цена - нельзя прыгнуть на произвольную страницу, только «дальше».

Для стабильного порядка нужен уникальный тай-брейкер: ORDER BY created_at, id, иначе строки с одинаковым created_at встают в неопределённом порядке и пагинация «едет». Курсор валиден лишь при неизменных фильтре и сортировке. Точный total (COUNT) на больших выборках дорог - его иногда избегают или кешируют.

// Фильтр и сортировку выражают query-параметрами (?status=paid&sort=-created_at), поля - по белому списку; в ответ кладут next-курсор и has_more.

-- keyset: страница по последнему ключу, по индексу
SELECT * FROM orders
WHERE (created_at, id) < (:last_created, :last_id)
ORDER BY created_at DESC, id DESC LIMIT 20;

keyset/cursor: страница по последнему виденному ключу, по индексу
тай-брейкер: уникальный вторичный ключ сортировки для стабильности

Как отвечать: «Почему пагинация с большим offset медленная?»

Потому что offset не «прыгает» к нужным строкам - БД всё равно проходит и отбрасывает все пропускаемые. При offset=100000 движок читает сто тысяч строк, выкидывает их и только потом отдаёт двадцать, поэтому время растёт линейно с глубиной. Плюс между запросами вставки сдвигают окно, и на стыках страниц появляются дубли или пропуски. Лечу это keyset-пагинацией: беру WHERE по последнему виденному ключу с уникальным тай-брейкером вроде (created_at, id) и иду по индексу - тогда стоимость страницы не зависит от глубины. Минус keyset - нельзя прыгнуть на произвольную страницу, только листать дальше.

Объяснена механика тормоза (проход и отбрасывание строк), названа вторая беда (сдвиг окна), дано решение keyset с тай-брейкером и честно назван его минус - полный разбор трейдофа.

На чём валят

−Deep offset на большой таблице: БД сканирует и отбрасывает пропускаемые строки - время растёт с offset.
−Сортировка без уникального тай-брейкера: порядок неоднозначен, пагинация едет - дубли и пропуски.
−Не ограничивать limit сверху: запрос limit=100000 выкачивает и кладёт сервис.
−Считать точный total через COUNT на каждой странице большой таблицы - дорого, кешируй или избегай.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 12, остальные разбираются в тренажёре.

#pagination_filtering1 / 5
Как работает классическая offset/limit пагинация?
A)offset задаёт размер страницы, а limit — общее число доступных страниц в выборке
B)Сервер сам решает границы страниц, а offset и limit клиент передавать не обязан
C)limit задаёт размер страницы, offset пропускает первые N строк
D)Оба параметра указывают номер страницы, дублируя друг друга для надёжности
показать ответ и разбор
+C)limit задаёт размер страницы, offset пропускает первые N строк
// разбор: Offset/limit — простейшая схема: limit — сколько строк вернуть (размер страницы), offset — сколько пропустить с начала (offset = page * limit). Удобно и позволяет прыгать на произвольную страницу. Минусы вылезают на глубоких страницах и при конкурентных вставках — их закрывает keyset/cursor-пагинация. Для небольших/статичных наборов offset вполне достаточно.
#pagination_filtering2 / 5
Почему OFFSET 100000 LIMIT 20 работает медленно на большой таблице?
A)База сортирует всю таблицу заново на каждый запрос со смещением такого размера
B)Такой запрос блокирует таблицу целиком до полного завершения
C)БД всё равно проходит и отбрасывает первые 100000 строк, прежде чем взять 20
D)Большой offset переполняет целочисленный тип, и БД переходит к медленному режиму
показать ответ и разбор
+C)БД всё равно проходит и отбрасывает первые 100000 строк, прежде чем взять 20
// разбор: OFFSET не «перепрыгивает» строки — БД должна получить и упорядочить строки вплоть до смещения, а затем отбросить пропускаемые и вернуть нужные. Чем глубже страница, тем больше лишней работы: время растёт линейно с offset. Отсюда deep pagination тормозит. Решение — keyset/cursor-пагинация: фильтровать по значению последнего виденного ключа, а не считать смещение.
#pagination_filtering3 / 5
Как устроена keyset (cursor) пагинация и чем она лучше offset на глубине?
A)Берёт строки после последнего виденного ключа (WHERE id > :last) — по индексу, без пропуска
B)Она использует тот же OFFSET, только смещение считается на стороне клиента
C)Она заранее грузит все страницы в кеш сервера, поэтому и отдаёт их быстро
D)Она отдаёт страницы в случайном порядке, зато не нагружает базу сортировкой
показать ответ и разбор
+A)Берёт строки после последнего виденного ключа (WHERE id > :last) — по индексу, без пропуска
// разбор: Keyset (cursor) пагинация не считает смещение, а фильтрует: следующую страницу берут условием по последнему виденному значению отсортированного ключа (WHERE (created_at, id) > (:last_ts, :last_id) LIMIT n). При наличии индекса БД сразу прыгает в нужное место — время не зависит от глубины. Плюс страницы стабильны при вставках. Минус — нельзя прыгнуть на произвольный номер страницы.
#pagination_filtering4 / 5
При offset-пагинации между запросами страниц вставили новую строку. Что увидит клиент?
A)Сдвиг данных: строка может повториться на след. странице или потеряться
B)База данных автоматически заблокирует вставки до конца обхода всех страниц клиентом
C)Ничего: offset-пагинация полностью устойчива к вставкам и удалениям между запросами
D)Клиент получит явную ошибку рассинхронизации и должен будет начать обход заново
показать ответ и разбор
+A)Сдвиг данных: строка может повториться на след. странице или потеряться
// разбор: Offset считает позицию от начала. Если между запросами страниц набор изменился (вставка/удаление в уже пройденной части), окно сдвигается: одна и та же строка может попасть на границу двух страниц (дубль) или проскочить мимо (пропуск). Keyset-пагинация от этого устойчива, потому что якорится на значении ключа, а не на числовом смещении.
#pagination_filtering5 / 5
Клиент хочет знать общее число записей (total) для показа «страница 3 из 200». Какой подтекст?
A)Общее число совпадает с размером текущей страницы, отдельно его не считают
B)COUNT по большой отфильтрованной выборке дорог — иногда его избегают или кешируют
C)Ничего: точный total на таблице считается мгновенно и дёшево для базы
D)Total можно узнать только полной выгрузкой всех строк на сторону приложения
показать ответ и разбор
+B)COUNT по большой отфильтрованной выборке дорог — иногда его избегают или кешируют
// разбор: Точный COUNT(*) по большой, да ещё отфильтрованной выборке заставляет БД пройти много строк — на горячем пути это дорого. Варианты: не показывать точный total (курсор + «есть ещё»), давать приблизительную оценку (из статистики планировщика), кешировать счётчик или считать асинхронно. Классический «N из M» с точным M — роскошь, оправданная не всегда.

дальше

Теорию прочитали. Навык ставится повторением

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

Открыть тренажёр Вся тема: FastAPI, Django и API