В большинстве учетных систем, типа нашего СБИС, рано или поздно возникает проблема быстрого отображения реестра, в который по просьбам бизнес-пользователей накручено несколько комбинируемых фильтров с очень редкой выборкой, ну никак не ложащихся в вашу красивую структуру базы данных и индексов базовой таблицы реестра - что-нибудь типа "список продаж покупателям, у которых день рождения выпадает на 29 февраля".
Универсального способа сделать "хорошо" тут нет, но я расскажу про модель запроса, которая позволит вам дать пользователю быстрый отклик, но при этом весьма эффективно с точки зрения PostgreSQL.
Традиционно, существует несколько базовых подходов к работе с навигацией по реестру:
вычитать вообще все (заодно посчитать количество записей для "правильного" пейджинга)
вычитать конкретную "страницу" с использованием
OFFSET
вычитать блок записей "по курсору"
Основные подводные камни каждого из этих вариантов и способы их обхода я уже подробно рассматривал в статьях "PostgreSQL Antipatterns: навигация по реестру" и "PostgreSQL 13: happy pagination WITH TIES".
Если с первыми двумя вариантами все понятно, и никакой "эффективности" там даже близко не будет, то с третьим вполне можно поработать.
Возьмем в качестве примера вот такую структуру базы:
CREATE TABLE client(
client_id
serial
PRIMARY KEY
, client_dt
date
);
CREATE TABLE sale(
sale_id
serial
PRIMARY KEY
, sale_dt
date
, client_id
integer
REFERENCES client
ON DELETE RESTRICT
);
Понятно, что тут не хватает индекса для поддержки foreign key(client_id)
, и в реальной жизни без него можно хлебнуть горя, но для нашей задачи он не требуется, и мы не станем его создавать.
А вот уникальный индекс для навигации в обратном хронологическом порядке нам точно пригодится:
-- индекс для итераций по реестру
CREATE UNIQUE INDEX ON sale(sale_dt DESC, sale_id DESC);
Наполним наши таблицы тестовыми данными:
INSERT INTO client(client_dt)
SELECT
(now() - random() * '10 year'::interval)::date
FROM
generate_series(1, 1e5); -- 100K клиентов
INSERT INTO sale(client_id, sale_dt)
SELECT
(random() * (1e5 - 1))::integer + 1
, (now() - random() * '10 year'::interval)::date
FROM
generate_series(1, 1e6); -- 1M продаж за 10 лет
Благодаря упомянутым выше статьям мы знаем, что начитка блока данных на каждой следующей итерации будет весьма быстрой:
SELECT
*
FROM
sale
WHERE
(sale_dt, sale_id) < ($1, $2) -- последние полученные на предыдущем шаге значения
ORDER BY
sale_dt DESC, sale_id DESC
LIMIT 25;
Итерации на клиенте, фильтрация на бизнес-логике
Во многих случаях попытка добавить фильтрацию при итеративной разработке приведет к любимому многими ORM паттерну пересылки набора id
между базой и бизнес-логикой:
ids <- `SELECT id FROM ... LIMIT 25`
key <- last(ids)
res <- `SELECT * FROM ... WHERE id IN (${ids.join(',')}) AND <cond>`
Такой кейс детально рассмотрен в статье "PostgreSQL Antipatterns: «слишком много золота»", и исправлялось бы достаточно тривиально - внесением подзапроса с фильтрацией в основной запрос, если бы не необходимость возвращать для чтения следующего сегмента "нефильтрованный" ключ.
То есть отрисовка реестра в такой модели выглядит примерно так:
браузер посылает на БЛ запрос сегмента до 25 записей (столько примерно влезает на первый экран без скролла) = ~30мс - зависит от лагов на сети от клиента до нашего сервера
БЛ из тратит 10мс на вычитку блока из 25 записей документов, их обработку и запоминание "следующего ключа"
БЛ тратит еще 10мс на дополнительную проверку по БД для 25 полученных ранее идентификаторов
Если искомый документ встречается с частотой 1:1000, то для заполнения первого экрана на 25 записей мы будем вынуждены сделать с клиента 1000 итераций по 25 записей, потратив на это (30ms + 10ms + 10ms) x 1000 = 50 секунд.
Казалось бы, решение очевидно - давайте запрашивать с БЛ сегментами не по 25, а по 100 или даже 1000 записей! Но в таком случае мы рискуем получить-таки все эти 1000 записей (если фильтр оказался не такой уж редкий) с необходимостью сразу отрисовать в интерфейсе - а это долго!
Итерации и фильтрация на базе данных
Проблематика понятна - давайте попробуем "приземлить" все операции как можно ближе к данным. Для этого воспользуемся методиками, описанными в статьях "SQL HowTo: пишем while-цикл прямо в запросе, или «Элементарная трехходовка»" и "SQL HowTo: наперегонки со временем".
В целом, что мы хотим:
каждая отдельная "клиентская" итерация должна быть ограничена по времени - то есть не продолжаться дольше, чем пользователь психологически готов ждать до появления первых данных, если они есть - скажем, 100мс
такая итерация должна возвращать не сильно больше запрошенного лимита записей (укладываться хотя бы в 2x)
мы можем захотеть ограничить глубину поиска конкретной датой - например, чтобы показать предупреждение в интерфейсе
Теперь давайте соберем подходящий запрос.
Возврат "нефильтрованного" ключа
Очевидно, что раз нам надо делать на базе какие-то итерации, но в SQL-запросе это превратится в рекурсивную выборку:
WITH RECURSIVE R AS (
... -- передаваемый с клиента JSON с ключом с предыдущей итерации
UNION ALL
... -- итерация по базе
)
( -- первая запись в resultset - ключ для следующей итерации
...
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
...
);
Первой записью в нашем resultset будет как раз последняя запись блока "до фильтрации", а остальные - уже отфильтрованный сегмент.
Примем следующую структуру для рекурсивной CTE:
i
- номер итерацииk
- ключевая запись для начала итерацииa
- массив отфильтрованных записейs
- общее количество уже найденных записей
Тогда часть запроса выше превратится вот в такую:
WITH RECURSIVE R AS (
SELECT
-- номер итерации
0 i
-- запись для начала итерации
, json_populate_record(
-- таблица, по которой будем итерировать
NULL::sale
-- сюда мы передаем json-параметром $1 данные ключа, полученного на предыдущей итерации
, '{"sale_dt" : "infinity", "sale_id" : 0}'::json
) k
-- массив отфильтрованных записей
, '{}'::sale[] a
-- общее количество уже найденных записей
, 0 s
UNION ALL
...
)
( -- первая запись в resultset - ключ для следующей итерации
SELECT
(k).* -- разворачиваем поле-запись в отдельные столбцы
FROM
R
ORDER BY
i DESC -- ключ с последней итерации
LIMIT 1
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
SELECT
(unnest(a)).* -- разворачиваем массивы записей, а затем - записи
FROM
R
);
Чтобы лучше понять происходящее, посмотрим на схему работы запроса, который мы строим:
Осталось реализовать шаг рекурсии и его ограничения.
Раз мы хотим ограничить как суммарное количество возвращаемых за одну итерацию уже отфильтрованных записей, так и время работы запроса, оба этих условия необходимо использовать совместно:
WHERE
-- limit time
clock_timestamp() < statement_timestamp() + '100 msec'::interval AND
-- limit resultset
R.s < 25 -- pageLimit
И, вот он, самый сложный для понимания блок запроса, в котором и происходит основная "магия":
SELECT
-- увеличиваем счетчик итераций
R.i + 1
-- подставляем новый ключ
, T.kn
-- сохраняем блок отфильтрованных записей
, T.a
-- увеличиваем счетчик найденного
, R.s + coalesce(array_length(T.a, 1), 0)
FROM
R
, LATERAL (
-- находим сегмент из pageLimit нефильтрованных записей
WITH Ts AS (
SELECT
T
FROM
sale T
WHERE
(sale_dt, sale_id) < ((k).sale_dt, (k).sale_id) -- !!!
ORDER BY
sale_dt DESC, sale_id DESC -- !!! должно соответствовать индексу
LIMIT 25 -- pageLimit
)
SELECT
(
-- последняя запись сегмента - следующий ключ
TABLE Ts OFFSET 24 -- pageLimit - 1
) kn
-- сворачиваем в массив записей
, ARRAY(
SELECT
T
FROM
Ts
WHERE
-- прикладной фильтр по сегменту документов сразу
(T).client_id = ANY(ARRAY(
SELECT
client_id
FROM
client
WHERE
client_id = ANY(ARRAY( -- свертка идентификаторов
SELECT
(T).client_id
FROM
Ts
)) AND
client_dt::text ~ '-02-29$' -- условие фильтрации
))
) a
) T
Полный текст запроса
WITH RECURSIVE R AS (
SELECT
-- номер итерации
0 i
-- запись для начала итерации
, json_populate_record(
-- таблица, по которой будем итерировать
NULL::sale
-- сюда мы передаем json-параметром $1 данные ключа, полученного на предыдущей итерации
, '{"sale_dt" : "infinity", "sale_id" : 0}'::json
) k
-- массив отфильтрованных записей
, '{}'::sale[] a
-- общее количество уже найденных записей
, 0 s
UNION ALL
SELECT
-- увеличиваем счетчик итераций
R.i + 1
-- подставляем новый ключ
, T.kn
-- сохраняем блок отфильтрованных записей
, T.a
-- увеличиваем счетчик найденного
, R.s + coalesce(array_length(T.a, 1), 0)
FROM
R
, LATERAL (
-- находим сегмент из pageLimit нефильтрованных записей
WITH Ts AS (
SELECT
T
FROM
sale T
WHERE
(sale_dt, sale_id) < ((k).sale_dt, (k).sale_id) -- !!!
ORDER BY
sale_dt DESC, sale_id DESC -- !!!
LIMIT 25 -- pageLimit
)
SELECT
(
-- последняя запись сегмента - следующий ключ
TABLE Ts OFFSET 24 -- pageLimit - 1
) kn
-- сворачиваем в массив записей
, ARRAY(
SELECT
T
FROM
Ts
WHERE
-- прикладной фильтр по сегменту документов сразу
(T).client_id = ANY(ARRAY(
SELECT
client_id
FROM
client
WHERE
client_id = ANY(ARRAY( -- свертка идентификаторов
SELECT
(T).client_id
FROM
Ts
)) AND
client_dt::text ~ '-02-29$' -- условие фильтрации
))
) a
) T
WHERE
-- limit time
clock_timestamp() < statement_timestamp() + '100 msec'::interval AND
-- limit resultset
R.s < 25 -- pageLimit
)
( -- первая запись в resultset - ключ для следующей итерации
SELECT
(k).* -- разворачиваем поле-запись в отдельные столбцы
FROM
R
ORDER BY
i DESC -- ключ с последней итерации
LIMIT 1
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
SELECT
(unnest(a)).* -- разворачиваем массивы записей, а затем - записи
FROM
R
);
Проверим план нашего запроса для стартовой итерации на наших тестовых данных:
Как мы видим, сработала отсечка по таймауту на 100ms, после чего клиент получит уже отфильтрованные 10 найденных записей. Для этого "внутри" PostgreSQL пришлось совершить 637 итераций вычитки-фильтрации 25 записей. Если мы вернемся к первичной оценке, что каждая итерация с клиента длится порядка 50ms, то 637 - около 30 секунд!
Так что можно считать, что работу клиентского интерфейса мы только что ускорили в 300 раз!