Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 6

Сортировка производится по full_path, для этих узлов поле содержит:

IdealGraphVisualizer (DIR) branding (DIR) src (DIR) main (DIR) nbm (DIR)

и

IdealGraphVisualizer (DIR) branding (DIR) src (DIR) main (DIR) nbm-branding (DIR)

У меня стабильно по-разному выводятся, но я подписи перепутал, сейчас исправлю ))

Рейтинг скрыт

Некоторые соображения про большой запрос (в основном из контекста MSSQL, но кое-что в доках Postgresql перепроверил и там вроде всё то же самое):

В блоке Levels UNION, который даёт доп. сортировку и DISTINCT, кажется, что можно смело заменить на UNION ALL, потому как по крайней мере колонка node_level точно ни на каком уровне иерархии не совпадет. Фрагмент concat(coalesce(concat(prev.parents, '-'), ''), cast(Mapping.parent_node_id as varchar)) Можно бы упростить: CONCAT игнорирует NULL и COALESCE выглядит просто лишним. Такой же coalesce есть в блоке FineTree. Конвертацию инта в строку вроде бы concat в postgres тоже делает автоматически, т.е. как будто достаточно concat(prev.parents, '-', Mapping.parent_node_id). Если хочется единообразия, то можно сделать по аналогии со строчкой нижеconcat_ws('-', prev.parents, Mapping.parent_node_id)

В блоке Branches два схожих фрагмента:

		case
			when root_node_id is null then
				case
					when node_id = last_value(node_id) over WindowByParents then '└── '
					else '├── '
				end
			else ''
		end as node_branch,

если перевернуть первое условие, то код станет более прямолинейным:


		case
			when root_node_id is not null then ''
			when node_id = last_value(node_id) over WindowByParents then '└── '
			else '├── '
		end as node_branch,

В Tree UNION тоже больше похож на UNION ALL. Финальную сортировку корректнее в финальном же запросе и разместить, а то cte FineTree как сортированная вьюха получается. В Branches сортировка выглядит просто лишней.

Множественные джойны на RootNodes кажется, что не нужны - у всех корневых узлов nest_level = 0 и можно пользоваться этим знанием. Избавиться от этого джойна возможно в Branches и в Tree. Вместе с этим можно будет выкинуть два CTE: Mapping и RootNodes. Фильтр `parent_node_id is null / node_id in (3, 10, 17)` идеально подходит для первого запроса рекурсивного CTE Levels. И в кейсах (рассмотренных чуть выше) получится более естественное для восприятия условие when nest_level = 0 then ''

И очень желательно во всех запросах колонкам алиас источника расставить: СУБД разберётся, где чьё, а человеку читать тяжело. Большую часть, если не всё, из того, что происходит в Branches и Tree, как будто можно сделать ещё в Levels и повторно большую рекурсию не гонять.

Рейтинг скрыт

Спасибо, по большей части замечания по делу!

В целом я не занимался оптимизацией, т.к. эффект от нее будет заметен на объемных иерархиях (1 млн строк и более), а необходимость их визуализации довольно сомнительна. Но почему бы не оптимизировать то, что может быть оптимизировано?

Отвечу по пунктам:

В блоке Levels UNION, который даёт доп. сортировку и DISTINCT, кажется, что можно смело заменить на UNION ALL, потому как по крайней мере колонка node_level точно ни на каком уровне иерархии не совпадет.

Принято, и в Tree тоже! node_id должен быть уникален в иерархии, поэтому DISTINCT здесь никогда не даст эффекта.
Интересно, что в случае PostgreSQL план запроса одинаковый для ALL и DISTINCT, а в MySQL для ALL эффект виден - на плане запроса, выигрыш в быстродействии заметить я не смог на иерархии в 85000 строк

Фрагмент concat(coalesce(concat(prev.parents, '-'), ''), cast(Mapping.parent_node_id as varchar)) Можно бы упростить: CONCAT игнорирует NULL и COALESCE выглядит просто лишним.

Нет, здесь вы не совсем правы. В моем варианте в PostgreSQL поле parents у узлов первого уровня выглядит как '-0' вместо '0' в MySQL, что не критично для партиционирования в окне по значению в этом поле. Но в MySQL CONCAT() не игнорирует NULL, и в вашем варианте все значения в parents будут NULL. Моя задача была написать максимально универсальный код, поэтому оставлю свой вариант.

В блоке Branches два схожих фрагмента ...

Полностью соглашусь, переписал изначально использовавшийся мною тернарный IF() не самым удачным образом

Множественные джойны на RootNodes кажется, что не нужны - у всех корневых узлов nest_level = 0 и можно пользоваться этим знанием. Избавиться от этого джойна возможно в Branches и в Tree.

Да, здесь можно пожертвовать единообразием (определения начальных узлов соединением с RootNodes) ради экономии 2 строк кода, плюс в MySQL план запроса сокращается на 2 строки.

В реальных условиях это может быть не столь однозначно - например, если в таблице создан индекс по полю node_id, соединение с RootNodes по нему будет происходить быстро, в отличие от применения условия node_level = 0 - это вычисляемое поле, все записи будут сканироваться.

У меня изначально была идея сохранять уровень node_level оригинальным, т.е. если в качестве начального указан узел с уровнем 4, то именно это значение и будет у него в поле node_level, но я отказался от этой идеи, так как в RootNodes может быть передано несколько начальных узлов из разных уровней, но визуализированы они будут как одинаковые по уровню - поэтому принимаю предложение.

Вместе с этим можно будет выкинуть два CTE: Mapping и RootNodes.

Здесь не могу согласиться. И одно, и другое служит для параметризации запроса, по сути это интерфейсные CTE, их удобно располагать в начале, чтобы не "трогать" смысловую часть. Mapping позволяет использовать запрос без каких-либо изменений с любой структурой данных - это более дружественная для новичков реализация, а опытные в любом случае адаптируют запрос к своим условиям.

И очень желательно во всех запросах колонкам алиас источника расставить: СУБД разберётся, где чьё, а человеку читать тяжело. Большую часть, если не всё, из того, что происходит в Branches и Tree, как будто можно сделать ещё в Levels и повторно большую рекурсию не гонять.

Каждый CTE использует только предыдущий, указанный в FROM - как сформулировано в задаче. При таком варианте алиасы избыточны кмк.

Идею "все сделать в Levels" предоставлю возможность реализовать кому-то другому, мне по душе подход с разделением большого на меньшее и решение "слона по частям" ))

В целом интересно проверить на большой иерархии, от 1 млн. строк. Видимо, придется продолжить...

Собственно, результат оптимизации:

PostgreSQL и SQLite
with recursive 
Mapping as (
	select 
		id 					as node_id, 
		parent_id as parent_node_id,
		concat(name, ' (', bytes, ')')	as node_name
	from ZipArchive
),

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 						-- Exactly one line below should be uncommented
		parent_node_id is null	-- Uncomment to build from root(s)
		-- node_id in (27233)	-- Uncomment to add node_id(s) into the brackets
),

Levels as (
	select
		node_id,
		parent_node_id,
		node_name,
		cast(parent_node_id as varchar) as parents,
		cast(node_name as varchar) as full_path,
		0 as node_level
	from
		Mapping
		inner join RootNodes on node_id = root_node_id
		
	union all
	
	select 
		Mapping.node_id, 
		Mapping.parent_node_id,
		Mapping.node_name,
		concat(coalesce(concat(prev.parents, '-'), ''), cast(Mapping.parent_node_id as varchar)),
		concat_ws(' ', prev.full_path, Mapping.node_name),
		prev.node_level + 1
	from 
		Levels as prev
		inner join Mapping on Mapping.parent_node_id = prev.node_id
),

Branches as (
	select
		node_id,
		parent_node_id,
		node_name,
		parents,
		full_path,
		node_level,
		case
			when node_level = 0 then ''
			when node_id = last_value(node_id) over WindowByParents then '└── '
			else '├── '
		end as node_branch,
		case
			when node_level = 0 then ''
			when node_id = last_value(node_id) over WindowByParents then '    '
			else '│   '
		end as branch_through
	from Levels
	window WindowByParents as (
		partition by parents
		order by node_name
		rows between current row and unbounded following
		)
	order by full_path
),

Tree as (
	select
		node_id,
		parent_node_id,
		node_name,
		parents,
		full_path,
		node_level,
		node_branch,
		cast(branch_through as varchar) as all_through
	from Branches
	where node_level = 0
		
	union all
	
	select 
		Branches.node_id,
		Branches.parent_node_id,
		Branches.node_name,
		Branches.parents,
		Branches.full_path,
		Branches.node_level,
		Branches.node_branch,
		concat(prev.all_through, Branches.branch_through)
	from 
		Tree as prev
		inner join Branches on Branches.parent_node_id = prev.node_id
),

FineTree as (
	select
		tr.node_id,
		tr.parent_node_id,
		tr.node_name,
		tr.parents,
		tr.full_path,
		tr.node_level,
		concat(coalesce(parent.all_through, ''), tr.node_branch, tr.node_name) as fine_tree
	from
		Tree as tr
		left join Tree as parent on
			parent.node_id = tr.parent_node_id
	order by tr.full_path
)

select fine_tree, node_id from FineTree
;

MySQL и SQLite
with recursive 
Mapping as (
	select 
		id 					as node_id, 
		parent_id as parent_node_id,
		concat(name, ' (', bytes, ')')	as node_name
	from ZipArchive
),

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 							-- Keep uncommented exactly one line below 
		parent_node_id is null	-- Uncomment to build from root(s)
		-- node_id in (27233)	-- Uncomment to add node_id(s) into the brackets
),

Levels as (
	select
		node_id,
		parent_node_id,
		node_name,
		cast(parent_node_id as char(2000)) as parents,
		cast(node_name as char(2000)) as full_path,
		0 as node_level
	from
		Mapping
		inner join RootNodes on node_id = root_node_id
		
	union all
	
	select 
		Mapping.node_id, 
		Mapping.parent_node_id,
		Mapping.node_name,
		concat(coalesce(concat(prev.parents, '-'), ''), cast(Mapping.parent_node_id as char(2000))),
		concat_ws(' ', prev.full_path, Mapping.node_name),
		prev.node_level + 1
	from 
		Levels as prev
		inner join Mapping on Mapping.parent_node_id = prev.node_id
),

Branches as (
	select
		node_id,
		parent_node_id,
		node_name,
		parents,
		full_path,
		node_level,
		case
			when node_level = 0 then ''
			when node_id = last_value(node_id) over WindowByParents then '└── '
			else '├── '
		end as node_branch,
		case
			when node_level = 0 then ''
			when node_id = last_value(node_id) over WindowByParents then '    '
			else '│   '
		end as branch_through
	from Levels
	window WindowByParents as (
		partition by parents
		order by node_name
		rows between current row and unbounded following
		)
	order by full_path
),

Tree as (
	select
		node_id,
		parent_node_id,
		node_name,
		parents,
		full_path,
		node_level,
		node_branch,
		cast(branch_through as char(2000)) as all_through
	from Branches
	where node_level = 0
		
	union all
	
	select 
		Branches.node_id,
		Branches.parent_node_id,
		Branches.node_name,
		Branches.parents,
		Branches.full_path,
		Branches.node_level,
		Branches.node_branch,
		concat(prev.all_through, Branches.branch_through)
	from 
		Tree as prev
		inner join Branches on Branches.parent_node_id = prev.node_id
),

FineTree as (
	select
		tr.node_id,
		tr.parent_node_id,
		tr.node_name,
		tr.parents,
		tr.full_path,
		tr.node_level,
		concat(coalesce(parent.all_through, ''), tr.node_branch, tr.node_name) as fine_tree
	from
		Tree as tr
		left join Tree as parent on
			parent.node_id = tr.parent_node_id
	order by tr.full_path
)

select fine_tree, node_id from FineTree
;

SQLite всеяден, оба варианта работают в нем одинаково

Рейтинг скрыт

Похоже, я несколько ввел всех в заблуждение - последний вариант запроса для PostgreSQL корректно исполняется в SQLite, но не в MySQL, что-то я вчера в ночи попутал. Исправлю текст в статье.

Рейтинг скрыт

Когда переносил из xml объёмом в 116 станиц в mssql в пять связанных таблиц, то рекурсию не стал использовать, а использовал фильтрацию по параметрам, так как их было больше 50 плюс пустые уровни только для связности в исходной таблице иерархии с узлами и данными. И задача была практическая. А вообще, когда разрабатывал запросы из этих таблиц для sqlite и мssql,то с множеством CTE запросы были идентичны и за исключением замены ТОP на Limit.

Рейтинг скрыт
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr