Привет. На stackoverflow был вопрос про то, как свернуть вложенное

дерево до корневых элементов. Типа, есть дерево категорий вида id, parent_id, name и мы хотим получить первый уровень, у которого в колонке children будут непосредственные предки, у тех в свою очередь их предки и т.д.
Там был предложен подход с рекурсивными cte, когда мы сначала строим дерево с уровнями, потом находим самый нижний уровень и начиная с нижнего тоже рекурсивным cte собираем дерево обратно. Но у этого способа есть проблема, когда разные деревья заканчиваются на разном уровне. В этом случае деревья, которые менее длинные, как-то криво разбиваются на части и получается в итоге дубли корневых категорий с разным набором детей. Может, есть более элегантный вариант? Вот пример такой ситуации: http://sqlfiddle.com/#!17/022f80/10

Я, например, не понял, что вообще нужно. Вы бы хоть ссылку или более подробную постановку задачи дали... > у которого в колонке children будут непосредственные предки, у тех в свою очередь их предки и т.д. Предки в колонке children?!

Вот http://sqlfiddle.com/#!17/022f80/38/0 Задача сложная из-за того, что слой рекурсии нельзя использовать в OUTER JOIN. Интересно, это только в PostgreSQL такое ограничение?

Круто, спасибо!

О, решили уже. Но вот это жестоко, конечно ;) FROM ( SELECT branch_parent, branch_child FROM c_with_level branch_parent JOIN c_tree branch_child ON branch_child.lvl - 1 = branch_parent.lvl ) branch Это же, грубо говоря, примерно O(N²)... Я о том, что предыдущий уровень целиком соединяется столько раз, сколько узлов на текущем, нет? > Интересно, это только в PostgreSQL такое ограничение? Это много где, потому что все эти ограничения — из ISO SQL. И PostgreSQL ещё мало запрещает (т.е. далеко не всё, что предписывает стандарт). Насколько я помню, MS SQL запрещает ещё больше, но не всё (ну и нарушает стандарт в "недозапрещённных" местах, т.е. выдаёт по сути неправильные результаты); MariaDB (если я правильно понял) тоже запрещает почти всё (но как-то выполняет mutual recursion, запрещённую в стандарте); sqlite и DB2 запрещают всё прямо по стандарту.

Можно соединять по двум условиям: равенству ид родителя и соответствию уровня, но тогда придётся начинать не с максимального уровня, а сразу со всех листьев дерева (но фиксировать максимальный уровень для всех листьев), а в рекурсивной части нужен будет left join по ИД и условию уровень родителя равен уровню строки cte - 1, соответственно, если не находим родителя, пробрасываем строки наверх с уменьшенным уровнем. Не придётся соединять весь уровень. Объяснил сумбурно, если совсем непонятно, могу завтра привести запрос.

Да, я не понял (казалось бы, эти уровни нужны для правильной свёртки). Интересно было бы посмотреть на запрос.

http://sqlfiddle.com/#!17/b0d7a/6/0

Да, хорошее решение. :) Теперь понятно, спасибо! Вообще удивительно, сколько приходится мучиться с рекурсивными CTE, чтобы получить аналог того, что настоящей рекурсией решается очень просто: ;) -- Функция: CREATE OR REPLACE FUNCTION children_jsonb(_fromparent bigint) RETURNS jsonb LANGUAGE sql STABLE AS $function$ SELECT COALESCE(jsonb_agg(to_jsonb(can) || jsonb_build_object('children', children_jsonb(can.id))), '[]') AS res FROM customer_area_node AS can WHERE can.parent_id = _fromparent; $function$; -- Использование: SELECT id, jsonb_pretty(to_jsonb(can) || jsonb_build_object('children', children_jsonb(can.id))) AS res FROM customer_area_node AS can WHERE can.parent_id IS NULL; Кстати, к вопросу о соответствии / расширению стандарта — в PostgreSQL есть следующий трюк, с помощью которого "перебиваются" вообще все эти ограничения на рекурсивные CTE: WITH RECURSIVE ttree AS ( -- Walk a (sub)forest, top-down, get level (distance from a root) SELECT *, 0 AS level_num FROM customer_area_node AS t WHERE t.parent_id IS NULL UNION ALL SELECT t.*, ttree.level_num + 1 AS level_num FROM ttree JOIN customer_area_node AS t ON t.parent_id = ttree.id ), a_level AS ( -- Walk it bottom-up, level by level SELECT ttree.*, to_jsonb(ttree) || '{"children": []}'::jsonb AS children FROM ttree WHERE ttree.level_num = (SELECT MAX(m.level_num) FROM ttree AS m) UNION ALL ( -- This "trick" violates (or extends?) ISO SQL, but works in PostgreSQL WITH lower_level AS (SELECT * FROM a_level) SELECT ttree.*, to_jsonb(ttree) || jsonb_build_object('children', COALESCE((SELECT jsonb_agg(lower_level.children) FROM lower_level WHERE lower_level.parent_id = ttree.id ), '[]') ) AS children FROM ttree WHERE ttree.level_num = (SELECT MIN(l.level_num) - 1 FROM lower_level AS l) ) ) SELECT *, jsonb_pretty(children) FROM a_level WHERE level_num = 0;

Интересный трюк, надо будет попробовать. По хорошему, можно было бы обойтись простым рекурсивным запросом внутри функции, которая пройдёт по датасету for-ом и соберёт рекурсивный запрос. Но не уверен, что это будет быстрее работать чем сборка рекурсивного json-а на cte. Рекурсивная функция рискует вывалиться в stackoverflow если вдруг дерево окажется слишком глубоким (например, дерево из 1000 элементов вложенных друг в друга)

Да, c рекурсивной функцией в таком случае получится ERROR: stack depth limit exceeded. Я просто имел в виду, что записывается она тривиально, а rCTE-аналоги... как-то нет. ;)