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;

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