Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
В предыдущих статьях "PostgreSQL Antipatterns: навигация по реестру", "PostgreSQL 13: happy pagination WITH TIES" и "SQL HowTo: курсорный пейджинг с неподходящей сортировкой" я уже рассматривал проблемы навигации по данным, представленных в виде плоского реестра.
Но что если мы хотим выводить данные не простым "бесконечным списком", а в виде иерархической структуры с быстрой навигацией по узлам - например, обширный каталог товаров или меню ресторана, как это делает Presto - наш продукт для автоматизации заведений питания?
Формируем датасет
Для начала сгенерируем наш тестовый иерархичный каталог на 100K позиций:
CREATE TABLE hier(
id -- PK
integer
PRIMARY KEY
, pid -- ссылка на "предка"
integer
REFERENCES hier
ON DELETE CASCADE
, ord -- пользовательский порядковый номер внутри раздела
integer
);
INSERT INTO hier
SELECT
id
, nullif((random() * id)::integer, 0) pid
, (random() * 1e5)::integer ord
FROM
generate_series(1, 1e5) id; -- 100K записей
Из размера уже становится понятно, что решения вроде "Давайте все сразу развернем в нужном порядке как описано тут, а потом спозиционируемся через OFFSET
" адекватно работать не будут.
Теперь договоримся, что порядок вывода записей внутри одного раздела, определяемый полем ord
, будет уникальным. Для этого нам надо вычистить все дубли пар (pid, ord)
, как мы делали это в статье "DBA: вычищаем клон-записи из таблицы без PK":
DELETE FROM
hier
WHERE
ctid = ANY(ARRAY(
SELECT
unnest((array_agg(ctid))[2:]) ctids
FROM
hier
GROUP BY
pid, ord
HAVING
count(*) > 1
));
-- теперь никто не мешает индексу по разделу быть уникальным
CREATE UNIQUE INDEX ON hier(pid, ord);
Алгоритм обхода
Давайте формализуем описание алгоритма, как он должен набрать N
записей для следующей "страницы", начиная с конкретного ключа - пары (pid, ord)
. Он будет состоять всего из 3 разных вариантов, которые надо проверить последовательно.
Взять первого по порядку потомка на уровень ниже:
Если такого нет, взять "соседа" на текущем уровне:
Если такого нет, взять "соседа" у ближайшего предка, у которого он есть:
Если же ни у одного предка не оказалось "соседа" - все, мы обошли все дерево.
Собираем SQL
наш алгоритм итеративно переходит от одной записи к другой - то есть для SQL это будет рекурсивным запросом;
паттерн "если такого нет, возьми следующий вариант" легко реализуется с помощью кейса
UNION ALL + LIMIT 1
(см. статью);"ближайшего предка с соседом" придется искать тоже рекурсивно;
для ограничения количества набираемых
N
записей разумнее всего использовать обычный счетчик.
Звучит не слишком страшно, но надо учесть, что п.3 разделится еще на два - когда узел находится где-то в глубине дерева, и когда он находится в корне (pid IS NULL
):
WITH RECURSIVE T AS(
SELECT
h -- тут будет лежать сразу цельная запись, чтобы не перечитывать ее повторно
, 0 i -- счетчик найденных записей
FROM
hier h
WHERE
id = 10000 -- последняя прочитанная на предыдущей итерации запись
UNION ALL
SELECT
X._h
, i + 1
FROM
T
, LATERAL (
-- первый потомок
(
SELECT
_h
FROM
hier _h
WHERE
pid = (T.h).id
ORDER BY
ord
LIMIT 1
)
UNION ALL
-- ближайший "сосед"
(
SELECT
_h
FROM
hier _h
WHERE
pid = (T.h).pid AND
ord > (T.h).ord
ORDER BY
ord
LIMIT 1
)
UNION ALL
-- ближайший "сосед" ближайшего предка
(
WITH RECURSIVE _T AS(
SELECT
T.h p -- берем текущую запись в качестве "предка"
, NULL::hier _h -- "соседа" у нее заведомо нет
UNION ALL
SELECT
__h
, (
-- сработает только один из блоков с противоположными условиями
(
SELECT
__h
FROM
hier __h
WHERE
(_T.p).pid IS NOT NULL AND -- мы еще не в корне
pid = (_T.p).pid AND
ord > (_T.p).ord
ORDER BY
pid, ord -- подгоняем под индекс
LIMIT 1
)
UNION ALL
(
SELECT
__h
FROM
hier __h
WHERE
(_T.p).pid IS NULL AND -- уже в корне
pid IS NULL AND
ord > (_T.p).ord
ORDER BY
pid, ord -- подгоняем под индекс
LIMIT 1
)
LIMIT 1
)
FROM
_T
INNER JOIN
hier __h
ON __h.id = (_T.p).pid -- рекурсивный обход "вверх" по иерархии
)
SELECT
_h
FROM
_T
WHERE
_h IS DISTINCT FROM NULL
LIMIT 1
)
LIMIT 1
) X
WHERE
X._h IS DISTINCT FROM NULL AND
i < 20 -- количество записей на странице
)
SELECT
(h).* -- разворачиваем поля записи
FROM
T
WHERE
i > 0; -- убираем "стартовую" запись
Проверим план запроса на explain.tensor.ru:
Все выполнение для поиска 20 записей заняло меньше полмиллисекунды! При этом никаких Seq Scan
или Sort
, все исключительно по индексам (всего 58 обращений):
А разве попроще нельзя?..
Конечно, можно! Достаточно заметить, что случаи #2
и #3
логически одинаковы - нужно взять ближайшего "соседа" по всей цепочке предков, но начиная с самой же записи. Поэтому второй блок из UNION ALL
можно просто убрать - и результат останется ровно тем же самым!
Но вот план - немного ухудшится, и вместо 150 страниц данных для тех же записей придется читать уже 163, поскольку рекурсивный поиск первого предка теперь будет производиться для каждой записи - даже для той, у которой есть "сосед".