Comments 15
понадобится какой-нибудь там хитрый JOIN, но нет
Ясно-понятно. Мы не умеем в джойн, поэтому сделаем подзапрос. Может сразу CTE прикрутить?
Задача решается элементарным селфджойном, чтобы проверить потомка на нулл. Парент уже есть в полях. Дальше можно и кейсом, можно и ифом выдать нужное значение
Встречался с такой задачей часто на больших таблицах. Безусловно, должен быть join. С масштабируемостью in (...) - начинаются проблемы от 10к+ элементов, к тому же где-то этот массив в памяти надо разместить. Ну и P должен быть проиндексирован, а иначе Nested loops.
Причем селфджойн скорее всего будет эффективней:
Оптимизатор скорее всего сделает его hash-join-ом (https://habr.com/ru/articles/657021/). Вместо ужасного N IN (SELECT DISTINCT P FROM Tree) внутри CASE, с которым не понятно как оптимизатор справится, даже при наличии индекса по P... А без индекса вообще мрак на большой таблице.
Self-join тут не стреляет. У узла может быть много детей, что породит дубликаты, а DISTINCT - это дорого.
Так себе решение... скорее всего оно будет медленное, и чем больше таблица, тем хуже производительность. Коррелированный WHEN EXISTS смотрится выгоднее - особенно если имеются соотв. индексы.
Классика жанра. :) На sql.ru была даже прибитая гвоздиком тема для поиска всех потомков дерева и не обязательно бинарного на переменных и в один проход по таблице... эх, жаль закрылся скуль-ру..
Открылась его копия, и не одна.
Тут даже регистрироваться можно, но активность нулевая, все в телеграм ушли.
спасибо, не знал. добавил себе вкладку
Глянул, к сож. веток прибитых сверху гвоздиком не обнаружил, а искать поиском как-не задалось. Давно .. 2011-2014, где-то там, решение Бочкова, которое искалось "всем миром".
Пардон, нашлось (стоило вспомнить Бочкова) https://resql.ru/forum/topic.php?fid=47&tid=1830048 :) Тут много разных решений..
А можно альтернативные решения в студию? Я современный SQL не знаю, мне бы глянуть возможности.
А еще если бы бенчмарк сделать, и определить, кто прав по вопросу быстродействия. Тема для продолжения статьи.
https://gist.github.com/portnov/2e5d0522e26513d7f594df4fe73ae862
Надо заметить, распределение мест зависит от объёма данных, от степени ветвления дерева... на небольшом наборе данных выигрывает предложенный в статье запрос. На 1млн строк выигрывает "ручное" решение с union all.
проще некуда без IN на t-sql :
CREATE TABLE #Tree (
N int,
P int
);
INSERT INTO #Tree
VALUES
( 1, 2),
( 3, 2),
( 6, 8),
( 9, 8),
( 2, 5),
( 8, 5),
( 5, null);
----SELECT * FROM #Tree;
declare @root1 int
select @root1= N from #Tree where p is null
select N,'корень' from #Tree where p is null
select P,'ветвь' from #tree
where P != @root1
group by p
select t.N,'лист' from #tree t
left join #tree u
on t.n = u.p
where u.n is null
drop table #Tree
Рекомендую такое решение:
Hidden text
SELECT N AS Node,
CASE
WHEN T.P IS NULL THEN 'Root'
WHEN S.P IS NOT NULL THEN 'Inner'
ELSE 'Leaf'
END AS "Type"
FROM Tree T
LEFT JOIN
(
SELECT DISTINCT P FROM Tree
) S on S.P = T.N
;тут всего два скана и один хэш джоин, и подойдет практически для любой базы
Часто на практике нужно возвратить также уровень элемента из такой таблицы. В примере из статьи для промежуточных элементов мы получим только информацию о том, что он не конечный и не начальный. Возвратить таблицу вида "Node", "Parent", "Level" из исходной с произвольным количеством промежуточных уровней можно рекурсивным запросом.
with cte as (
select N as [Node]
,P as [Parent]
,1 as [Level]
from t1 as d
where d.P is null
union all
select d1.N
,d1.P
,cte.[Level]+1 as lvl
from t1 as d1 inner join cte on d1.P=cte.[Node])
select * from cte
SQL Задача про бинарное дерево