SQL HowTo: ближайший общий предок в дереве (LCA)

В иерархических структурах регулярно возникает потребность определить ближайшего общего предка в дереве, он же наименьший общий предок (Lowest (Least) Common Ancestor).

Правда, "классические" алгоритмы для решения этой задачи работают лишь с парой узлов (раз, два, три, четыре), а мы, используя всю мощь PostgreSQL, будем решать задачу сразу для нескольких узлов.

Очевидно, что раз у нас речь идет о "деревьях" и "путях", мы никуда не денемся в нашем запросе от рекурсии. Поэтому, для дерева с картинки начало запроса будет выглядеть примерно так:

WITH RECURSIVE tree(id, pid) AS (
  VALUES
    (1, NULL)
  , (2, 1)
  , (3, 1)
  , (4, 2)
  , (5, 2)
  , (6, 5)
  , (7, 5)
)

Наивный алгоритм

Самый простой вариант, который не требует придумывания какого-то сложного алгоритма - "физически" построить пути от каждого исходного узла до корня, а затем выделить у них общую часть. Последний элемент в этой части и будет искомым LCA:

В нашем примере мы получим следующие пути:

1 - 2 - 4
1 - 2 - 5 - 6
1 - 2 - 5 - 7

Воспользуемся для их генерации рекурсией, формируя массивы из пройденных элементов:

, path AS (
  SELECT
    ARRAY[id] p
  FROM
    tree
  WHERE
    id = ANY('{4,6,7}'::integer[]) -- отбираем исходные узлы
UNION ALL
  SELECT
    array_prepend(tree.pid, p) -- новый элемент добавляем в начало
  FROM
    path
  , tree
  WHERE
    tree.id = path.p[1] AND -- "шагаем" от последнего добавленного узла
    tree.pid IS NOT NULL -- выше корня не идем
)

Список узлов мы тут сразу передали строковым представлением массива, а не через IN или ARRAY, чтобы запрос легко параметризовался без необходимости "клеить" его текст.

Однако, рекурсия нам вернет вообще все пути, которые мы прошли - между каждой парой узлов:

{4}
{6}
{7}
{2,4}
{5,6}
{5,7}
{1,2,4}
{2,5,6}
{2,5,7}
{1,2,5,6}
{1,2,5,7}

А нам нужны только те, которые ведут в "корень" - то есть самые длинные для каждого из стартовых элементов. Оставим только их, "материализовав" длину массива с помощью LATERAL, чтобы не переписывать ее определение несколько раз:

, path2root AS (
  SELECT DISTINCT ON(p[ln]) -- уникализируем по последнему (исходному) элементу
    p
  , ln
  FROM
    path
  , LATERAL
      array_length(path.p, 1) ln -- однократно вычисляем длину массива-пути
  ORDER BY
    p[ln]
  , ln DESC -- оставляем самые длинные
)

p         | ln
{1,2,4}   |  3
{1,2,5,6} |  4
{1,2,5,7} |  4

Ага, что-то уже начинает просматриваться!

Теперь нам осталось всего лишь найти, до какой максимальной позиции все префиксы массивов еще совпадают. Для этого переберем все индексы от 1 до длины кратчайшего из путей (логично, что общий путь не может быть длиннее кратчайшего):

, pos AS (
  SELECT
    max(i)
  FROM
    generate_series(
      1
    , (
        SELECT
          min(ln)
        FROM
          path2root
      ) -- длина кратчайшего пути
    ) i
  WHERE
    (
      SELECT
        count(DISTINCT p[1:i]) -- путь-префикс
      FROM
        path2root
    ) = 1 -- "один разный" - то есть все совпадают
)

Осталось лишь узнать, что за элемент стоит на этой позиции у любой из записей - раз префиксы у них всех одинаковы, то и искомый LCA - последний элемент общего префикса в любой из них:

SELECT
  p[(TABLE pos)]
FROM
  path2root
LIMIT 1;

WITH RECURSIVE tree(id, pid) AS (
  VALUES
    (1, NULL)
  , (2, 1)
  , (3, 1)
  , (4, 2)
  , (5, 2)
  , (6, 5)
  , (7, 5)
)
, path AS (
  SELECT
    ARRAY[id] p
  FROM
    tree
  WHERE
    id = ANY('{4,6,7}'::integer[])
UNION ALL
  SELECT
    array_prepend(tree.pid, p)
  FROM
    path
  , tree
  WHERE
    tree.id = path.p[1] AND
    tree.pid IS NOT NULL
)
, path2root AS (
  SELECT DISTINCT ON(p[ln])
    p
  , ln
  FROM
    path
  , LATERAL
      array_length(path.p, 1) ln
  ORDER BY
    p[ln]
  , ln DESC
)
, pos AS (
  SELECT
    max(i)
  FROM
    generate_series(
      1
    , (
        SELECT
          min(ln)
        FROM
          path2root
      )
    ) i
  WHERE
    (
      SELECT
        count(DISTINCT p[1:i])
      FROM
        path2root
    ) = 1
)
SELECT
  p[(TABLE pos)]
FROM
  path2root
LIMIT 1;

Счетчик посещений

Как-то не особо легко и просто получилось у нас в предыдущем варианте...

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

Очевидно, что именно в LCA должны сойтись все пути, и большее значение недостижимо (откуда бы взять их еще больше?), а с каждым следующим шагом "вверх" их суммарная длина будет только увеличиваться на их количество.

Модифицируем нашу рекурсию, чтобы при проходе через узел учитывать длину пройденного пути, каждый из которых идентифицируется узлом-источником:

, path AS (
  SELECT
    id src -- откуда вышли
  , id dst -- докуда уже дошли
  , 0 ln   -- за сколько шагов
  FROM
    tree
  WHERE
    id = ANY('{4,6,7}'::integer[])
UNION ALL
  SELECT
    src
  , tree.pid
  , ln + 1 -- увеличиваем путь на 1 пройденное ребро
  FROM
    path
  , tree
  WHERE
    tree.id = path.dst AND -- шагаем от последнего посещенного узла
    tree.pid IS NOT NULL
)

src | dst | ln
  4 |   4 | 0
  6 |   6 | 0
  7 |   7 | 0 -- три исходных узла, а дальше - результат рекурсии
  4 |   2 | 1
  6 |   5 | 1
  7 |   5 | 1
  4 |   1 | 2
  6 |   2 | 2
  7 |   2 | 2
  6 |   1 | 3
  7 |   1 | 3

Теперь осталось найти узел, для которого выполнится описанное выше условие. К счастью, возможности SQL позволяют нам сделать это "в одно действие":

SELECT
  dst             -- ищем среди всех достигнутых узлов
FROM
  path
GROUP BY
  1               -- группируем по тому же dst
ORDER BY
  count(src) DESC -- максимум количества узлов-источников
, sum(ln)         -- минимум суммы пройденных путей
LIMIT 1;

WITH RECURSIVE tree(id, pid) AS (
  VALUES
    (1, NULL)
  , (2, 1)
  , (3, 1)
  , (4, 2)
  , (5, 2)
  , (6, 5)
  , (7, 5)
)
, path AS (
  SELECT
    id src
  , id dst
  , 0 ln
  FROM
    tree
  WHERE
    id = ANY('{4,6,7}'::integer[])
UNION ALL
  SELECT
    src
  , tree.pid
  , ln + 1
  FROM
    path
  , tree
  WHERE
    tree.id = path.dst AND
    tree.pid IS NOT NULL
)
SELECT
  dst
FROM
  path
GROUP BY
  1
ORDER BY
  count(src) DESC
, sum(ln)
LIMIT 1;

Ну, уже существенно проще!

PostgreSQL 14 вступает в дело

А еще проще - можно написать?.. А почему бы и нет!

Для этого достаточно заставить PostgreSQL самостоятельно считать пройденный нами по дереву путь и его длину, воспользовавшись появившейся с версии 14 возможностью определять порядок поиска в рекурсивных запросах.

Плюсом, мы можем спокойно избавиться от условия "не ходить выше корня", поскольку лишний NULL-элемент в пути для второго алгоритма никакой погоды не делает:

, path AS (
  SELECT
    id src
  , id dst
  FROM
    tree
  WHERE
    id = ANY('{4,6,7}'::integer[])
UNION ALL
  SELECT
    src
  , tree.pid
  FROM
    path
  , tree
  WHERE
    tree.id = path.dst
) SEARCH DEPTH FIRST BY dst SET path

Форма SEARCH DEPTH FIRST BY dst SET path означает, что к результату будет автоматически добавлен столбец path типа record[], в который будет помещаться "цепочка" проходимых dst:

src | dst | path
  4 |   4 | {(4)}
  6 |   6 | {(6)}
  7 |   7 | {(7)}
  4 |   2 | {(4),(2)}
  6 |   5 | {(6),(5)}
  7 |   5 | {(7),(5)}
  4 |   1 | {(4),(2),(1)}
  6 |   2 | {(6),(5),(2)}
  7 |   2 | {(7),(5),(2)}
  4 |     | {(4),(2),(1),()}
  6 |   1 | {(6),(5),(2),(1)}
  7 |   1 | {(7),(5),(2),(1)}
  6 |     | {(6),(5),(2),(1),()}
  7 |     | {(7),(5),(2),(1),()}

А когда у нас есть уже готовый "путь", длину-то мы от него и сами можем взять:

SELECT
  dst
FROM
  path
GROUP BY
  1
ORDER BY
  count(src) DESC
, sum(array_length(path, 1))
LIMIT 1;

Итого, весь запрос, который необходим для поиска LCA, сжался до следующего вида:

WITH RECURSIVE tree(id, pid) AS (
  VALUES
    (1, NULL)
  , (2, 1)
  , (3, 1)
  , (4, 2)
  , (5, 2)
  , (6, 5)
  , (7, 5)
)
, path AS (
  SELECT
    id src
  , id dst
  FROM
    tree
  WHERE
    id = ANY('{4,6,7}'::integer[])
UNION ALL
  SELECT
    src
  , tree.pid
  FROM
    path
  , tree
  WHERE
    tree.id = path.dst
) SEARCH DEPTH FIRST BY dst SET path
SELECT
  dst
FROM
  path
GROUP BY
  1
ORDER BY
  count(src) DESC
, sum(array_length(path, 1))
LIMIT 1;

Правда, тут стоит заметить, что формирование и хранение массивов в памяти - достаточно затратная процедура. Поэтому если у вас сотни исходных узлов и дерево глубиной в десятки уровней - могут быть проблемы. Не злоупотребляйте!