Оператор WITH

Оператор WITH позволяет задавать общие табличные выражения (ОТВ). Обычные (нерекурсивные) общие табличные выражения — это по сути представления, ограниченные по области применения конкретным запросом. ОТВы могут ссылаться друг на друга и быть вложенными. Рекурсивные ОТВы могут ссылаться на сами себя.

Примеры основных ОТВов

Создайте ОТВ, назвав его cte, и используйте его в основном запросе:

WITH cte AS (SELECT 42 AS x)
SELECT * FROM cte;

Создайте два ОТВа cte1 и cte2, где второе ОТВ ссылается на первое ОТВ:

WITH
    cte1 AS (SELECT 42 AS i),
    cte2 AS (SELECT i * 100 AS x FROM cte1)
SELECT * FROM cte2;

Материализация ОТВов

DuckDB может использовать материализацию ОТВов, то есть подстановку ОТВов в основной запрос. Это выполняется с помощью эвристик: если ОТВ выполняет групповую агрегацию и используется более одного раза, он материализуется. Материализацию можно явно включить, задав ОТВ с помощью AS MATERIALIZED и отключить, используя AS NOT MATERIALIZED.

В качестве примера рассмотрим следующий запрос, который трижды вызывает одно и то же ОТВ:

WITH t(x) AS (⟨complex_query⟩)
SELECT *
FROM
    t AS t1,
    t AS t2,
    t AS t3;

Подстановка дублирует определение t для каждого обращения, что приводит к следующему запросу:

SELECT *
FROM
    (⟨complex_query⟩) AS t1(x),
    (⟨complex_query⟩) AS t2(x),
    (⟨complex_query⟩) AS t3(x);

Если ⟨complex_query⟩ является дорогостоящей операцией, материализация с использованием ключевого слова MATERIALIZED может повысить производительность. В этом случае ⟨complex_query⟩ вычисляется только один раз.

WITH t(x) AS MATERIALIZED (⟨complex_query⟩)
SELECT *
FROM
    t AS t1,
    t AS t2,
    t AS t3;

Если нужно отключить материализацию, используйте NOT MATERIALIZED:

WITH t(x) AS NOT MATERIALIZED (⟨complex_query⟩)
SELECT *
FROM
    t AS t1,
    t AS t2,
    t AS t3;

Рекурсивные ОТВы

WITH RECURSIVE позволяет определить ОТВы, которые могут ссылаться на себя. Обратите внимание, что запрос должен быть сформулирован таким образом, чтобы гарантировать завершение, в противном случае он может зациклиться.

Пример: Последовательность Фибоначчи

WITH RECURSIVE может использоваться для выполнения рекурсивных вычислений. Например, вот как WITH RECURSIVE можно использовать для вычисления первых десяти чисел Фибоначчи:

WITH RECURSIVE FibonacciNumbers (RecursionDepth, FibonacciNumber, NextNumber) AS (
        -- Base case
        SELECT
            0 AS RecursionDepth,
            0 AS FibonacciNumber,
            1 AS NextNumber
        UNION ALL
        -- Recursive step
        SELECT
            fib.RecursionDepth + 1 AS RecursionDepth,
            fib.NextNumber AS FibonacciNumber,
            fib.FibonacciNumber + fib.NextNumber AS NextNumber
        FROM
            FibonacciNumbers fib
        WHERE
            fib.RecursionDepth + 1 < 10
    )
SELECT
    fn.RecursionDepth AS FibonacciNumberIndex,
    fn.FibonacciNumber
FROM
    FibonacciNumbers fn;

Пример: Обход дерева

WITH RECURSIVE может использоваться для обхода деревьев. Например, рассмотрим иерархию тегов:

CREATE TABLE tag (id INTEGER, name VARCHAR, subclassof INTEGER);
INSERT INTO tag VALUES
    (1, 'U2',     5),
    (2, 'Blur',   5),
    (3, 'Oasis',  5),
    (4, '2Pac',   6),
    (5, 'Rock',   7),
    (6, 'Rap',    7),
    (7, 'Music',  9),
    (8, 'Movies', 9),
    (9, 'Art', NULL);

Следующий запрос возвращает путь от узла Oasis к корню дерева (Art).

WITH RECURSIVE tag_hierarchy(id, source, path) AS (
        SELECT id, name, [name] AS path
        FROM tag
        WHERE subclassof IS NULL
    UNION ALL
        SELECT tag.id, tag.name, list_prepend(tag.name, tag_hierarchy.path)
        FROM tag, tag_hierarchy
        WHERE tag.subclassof = tag_hierarchy.id
    )
SELECT path
FROM tag_hierarchy
WHERE source = 'Oasis';

Обход графа

Оператор WITH RECURSIVE можно использовать для выражения обхода графов произвольной структуры. Однако если граф имеет циклы, запрос должен обнаруживать циклы, чтобы избежать бесконечных циклов. Один из способов достижения этого — хранить путь обхода в списке и перед расширением пути новой дугой проверять, посещался ли её конечный узел ранее (см. пример ниже).

Рассмотрим следующий ориентированный граф из бенчмарка LDBC Graphalytics:

CREATE TABLE edge (node1id INTEGER, node2id INTEGER);
INSERT INTO edge VALUES
    (1, 3), (1, 5), (2, 4), (2, 5), (2, 10), (3, 1),
    (3, 5), (3, 8), (3, 10), (5, 3), (5, 4), (5, 8),
    (6, 3), (6, 4), (7, 4), (8, 1), (9, 4);

Обратите внимание, что граф содержит ориентированные циклы, например, между узлами 1, 2 и 5.

Перечисление всех путей от узла

Следующий запрос возвращает все пути, начинающиеся с узла 1:

WITH RECURSIVE paths(startNode, endNode, path) AS (
        SELECT -- Define the path as the first edge of the traversal
            node1id AS startNode,
            node2id AS endNode,
            [node1id, node2id] AS path
        FROM edge
        WHERE startNode = 1
        UNION ALL
        SELECT -- Concatenate new edge to the path
            paths.startNode AS startNode,
            node2id AS endNode,
            array_append(path, node2id) AS path
        FROM paths
        JOIN edge ON paths.endNode = node1id
        -- Prevent adding a repeated node to the path.
        -- This ensures that no cycles occur.
        WHERE list_position(paths.path, node2id) IS NULL
    )
SELECT startNode, endNode, path
FROM paths
ORDER BY length(path), path;

Обратите внимание, что результат этого запроса не ограничен кратчайшими путями, например, для узла 5 результаты включают пути [1, 5] и [1, 3, 5].

Перечисление кратчайших путей (без весов) от узла

В большинстве случаев перечисление всех путей непрактично или нереализуемо. Вместо этого нас интересуют только (без весов) кратчайшие пути. Для их нахождения вторую половину запроса WITH RECURSIVE следует изменить так, чтобы узел включался только в том случае, если он ещё не посещался. Это реализуется с помощью подзапроса, проверяющего, не содержит ли какой-либо из предыдущих путей этот узел:

WITH RECURSIVE paths(startNode, endNode, path) AS (
        SELECT -- Define the path as the first edge of the traversal
            node1id AS startNode,
            node2id AS endNode,
            [node1id, node2id] AS path
        FROM edge
        WHERE startNode = 1
        UNION ALL
        SELECT -- Concatenate new edge to the path
            paths.startNode AS startNode,
            node2id AS endNode,
            array_append(path, node2id) AS path
        FROM paths
        JOIN edge ON paths.endNode = node1id
        -- Prevent adding a node that was visited previously by any path.
        -- This ensures that (1) no cycles occur and (2) only nodes that
        -- were not visited by previous (shorter) paths are added to a path.
        WHERE NOT EXISTS (
                FROM paths previous_paths
                WHERE list_contains(previous_paths.path, node2id)
              )
    )
SELECT startNode, endNode, path
FROM paths
ORDER BY length(path), path;

Перечисление кратчайших путей (без весов) между двумя узлами

WITH RECURSIVE также можно использовать для нахождения всех (без весов) кратчайших путей между двумя узлами. Для обеспечения остановки рекурсивного запроса как только мы достигнем целевого узла, используется функция окна функция окна, которая проверяет, входит ли целевой узел в состав вновь добавленных узлов.

Следующий запрос возвращает все кратчайшие пути (без весов) между узлами 1 (начальный узел) и 8 (целевой узел):

WITH RECURSIVE paths(startNode, endNode, path, endReached) AS (
   SELECT -- Define the path as the first edge of the traversal
        node1id AS startNode,
        node2id AS endNode,
        [node1id, node2id] AS path,
        (node2id = 8) AS endReached
     FROM edge
     WHERE startNode = 1
   UNION ALL
   SELECT -- Concatenate new edge to the path
        paths.startNode AS startNode,
        node2id AS endNode,
        array_append(path, node2id) AS path,
        max(CASE WHEN node2id = 8 THEN 1 ELSE 0 END)
            OVER (ROWS BETWEEN UNBOUNDED PRECEDING
                           AND UNBOUNDED FOLLOWING) AS endReached
     FROM paths
     JOIN edge ON paths.endNode = node1id
    WHERE NOT EXISTS (
            FROM paths previous_paths
            WHERE list_contains(previous_paths.path, node2id)
          )
      AND paths.endReached = 0
)
SELECT startNode, endNode, path
FROM paths
WHERE endNode = 8
ORDER BY length(path), path;

Ограничения

DuckDB не поддерживает взаимно рекурсивные ОТВы. См. соответствующий вопрос и обсуждение в репозитории DuckDB.

Синтаксис