SQL и рекурсия

Довольно таки давно в PostgreSQL реализовали CTE.

Common Table Expression (CTE) — это временные результирующие наборы, определенные в области выполнения единичных инструкций SELECT, INSERT, UPDATE, DELETE. Проще говоря, это вьюха которая определяется на момент выполнения запроса.

Возможно, CTE покажется простой альтернативой вложенных запросов, но прелесть в том что CTE позволяет делать рекурсивные запросы.

Ремарка

Надо отметить, что CTE далеко не новинка и реализовано не только в PostgreSQL, но и в некоторых других РСУБД, окромя мерзкого MySQL.

CTE как он есть

Запрос с CTE выглядит так:

WITH [RECURSIVE] cte_name [(column_name [,...])] AS (SELECT ...)
SELECT ... FROM cte_name

Например, простейший запрос в вакууме:

WITH t(n) AS (SELECT 42) SELECT n FROM t

выдаст нам в результате 42.

Никто не мешает использовать UNION:

WITH t(n) AS (SELECT 41 UNION ALL SELECT 43) SELECT avg(n) FROM t

даст опять же 42.

CTE может быть несколько:

WITH t(n) AS (SELECT 41 UNION ALL SELECT 43),
     e(n) AS (SELECT 40 UNION ALL SELECT 44)
SELECT avg(t.n), avg(e.n) FROM t, e

Результатом будет ROW(42, 42).

Рекурсия

Теперь о самом вкусном — о рекурсии. Модификатор RECURSIVE разрешает внутри CTE ссылаться на самого себя. Например, факториал числа 5 будет выглядеть так:

WITH RECURSIVE f(n, fact) AS (
    SELECT 5, 1
  UNION ALL
    SELECT n - 1, n * fact FROM f WHERE n > 1
) SELECT * FROM f;

Результатом будет:

 n | fact 
---+------
 5 |    1
 4 |    5
 3 |   20
 2 |   60
 1 |  120
(5 rows)

Порядок выполнения рекурсивного выражения таков:

1. Выполняется первый запрос:
   

   SELECT 5, 1

   Его результат заносится в конечный результат запроса и во временную рабочую таблицу.
2. Пока рабочая таблица не пустая, повторяются следующие действия:
1. Выполняется второй запрос
   

   SELECT n - 1, n * fact FROM f WHERE n > 1

   используя текущую рабочую таблицу. Результат заносится в конечный результат запроса и в промежуточную таблицу.
2. Содержимое рабочей таблицы заменяется содержимым промежуточной, и последняя очищается.

При использовании UNION (не UNION ALL), на шагах 1 и 2.1 удаляются дубликаты.

Рекурсивные структуры данных

Имея на вооружении такой инструмент, как CTE, становится очень просто решать проблему эффективного хранения рекурсивных структур таких как: односвязный список, деревья, графы и т. д.

Например, для односвязного списка достаточно колонки next_id. Операции вставки и удаления будут O(1), но при этом получение первого элемента списка или всех в порядке связывания O(n).

В моём маленьком тесте выборка рассортированного по связи списка размером миллион заняла 3-4 с. По сути, это миллион index scan-ов ради одной записи. Причём, вставка в начало списка того же размера с абсолютным позиционированием (как в acts_as_list) занимала 8 с (фактически происходит UPDATE по всей таблице), а выборка — 1-1,5 с. Тут, типо, важны компромисс и правильное использование.

Оптимизировать получение первого элемента из односвязного списка можно кешированием его id или использованием двусвязного списка. В нём у первого элемента prev_id IS NULL, у последнего — next_id IS NULL.

Та же ситуация с деревьями, с тем отличием, что из-за обратной связи по parent_id получение корневых элементов — это один маленький запрос по условию parent_id IS NULL. Если сравнивать со способом materialized path, то с CTE получаем гораздо меньше блокировок, разрешая другим транзакциям спокойно работать с ветвями изменяемых узлов.

Резюме

В целом, можно сказать, что CTE, по сравнению с традиционными способами хранения рекурсивных данных, облегчает операции изменения и избавляет от множества блокировок. Но при этом становятся дороже выборки, требующие рекурсии: при малой вложенности эта разница почти или вовсе незаметна, но при большей вложенности (эмпирические тесты показали >100000) она становится ощутимой. На практике такая вложенность редко встречается, а если и встречается, то, скорее всего, требует других инструментов и/или алгоритмов.

Также, важно заметить, что CTE делает более простыми запросы для обхода графа.

В следующем нескором посте я даже попробую сделать бенчмарки, дабы оценить профиты и непрофиты от CTE в числах.