В иерархических структурах регулярно возникает потребность определить ближайшего общего предка в дереве, он же наименьший общий предок (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;Правда, тут стоит заметить, что формирование и хранение массивов в памяти - достаточно затратная процедура. Поэтому если у вас сотни исходных узлов и дерево глубиной в десятки уровней - могут быть проблемы. Не злоупотребляйте!
