Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: Рекурсивное Cte и раскрутка дерева  [new]
churupaha
Member

Откуда: Краснодар
Сообщений: 1015
a_voronin
Я пробовал писать развертку дерева на NATIVE_COMPILATION и получил прирост, хотя и не столь внушительный.


Потому что дело не в издержках исполнялки T-SQL кода, а в структуре данных и в диктуемом ею алгоритме.

В этом посте 18098761 видно, что без индексов сложность "алгоритма рекурсии" O(N^2). Какая разница, будет он реализован на CLR, NATIVE_COMPILATION, T-SQL?
3 сен 15, 16:10    [18105043]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4804
churupaha
a_voronin
Я пробовал писать развертку дерева на NATIVE_COMPILATION и получил прирост, хотя и не столь внушительный.


Потому что дело не в издержках исполнялки T-SQL кода, а в структуре данных и в диктуемом ею алгоритме.

В этом посте 18098761 видно, что без индексов сложность "алгоритма рекурсии" O(N^2). Какая разница, будет он реализован на CLR, NATIVE_COMPILATION, T-SQL?


Потому что циклы и курсоры в T-SQL не столь оптимальны. А вот в CLR, NATIVE_COMPILATION они рулят.
3 сен 15, 16:24    [18105104]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
churupaha
Member

Откуда: Краснодар
Сообщений: 1015
a_voronin
churupaha
пропущено...


Потому что дело не в издержках исполнялки T-SQL кода, а в структуре данных и в диктуемом ею алгоритме.

В этом посте 18098761 видно, что без индексов сложность "алгоритма рекурсии" O(N^2). Какая разница, будет он реализован на CLR, NATIVE_COMPILATION, T-SQL?


Потому что циклы и курсоры в T-SQL не столь оптимальны. А вот в CLR, NATIVE_COMPILATION они рулят.


А вот этот самый Nested Loop в плане - скорее всего класс C++. Ну это ладно, суть то в том, что как быстры не были бы циклы, где-либо, при увеличении числа строк N, время работы со структурами данных "в лоб" будет N^2.

А тут предлагается:

18102689
18102919

1) Для "раскрутки дерева" считать просто таблицу, так как уже все "раскручено".
2) Или считать часть таблицы, для вычитки поддерева обычным запросом с where __path like '/1/2/3%' и индексом по __path (covered, не covered зависит.)

У (2) сложность алгоритма будет похожа на O(log(M, N)). Сравните график логарифма log(M, N) с параболой N^2.
3 сен 15, 16:33    [18105149]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
churupaha
Member

Откуда: Краснодар
Сообщений: 1015
+

churupaha
Nested Loop в плане - скорее всего класс C++


И не только Nested Loops но и Index Scan (это все про тот же план выполнения с рекурсией)
3 сен 15, 16:36    [18105162]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4804
churupaha,

А кто вам сказал, что на C# сделать O(n ln n) не получиться. Там есть очень даже нехилые структуры данных. Понятно, что двойным циклом хрень будет . А если хеш таблицы?
3 сен 15, 16:36    [18105165]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
churupaha
Member

Откуда: Краснодар
Сообщений: 1015
a_voronin
churupaha,

А кто вам сказал, что на C# сделать O(n ln n) не получиться. Там есть очень даже нехилые структуры данных. Понятно, что двойным циклом хрень будет . А если хеш таблицы?


Ну вы то в NATIVE_COMPILATION делали? Потому, я все и поставил в равные условия. Да, можно, на C# сообразить структуру данных, а зачем, если все это делается штатными средствами БД без доп. костыля и очень красиво. Т. е. я подвожу к тому, а на T-SQL таки нельзя, да?

Картинка с другого сайта.
3 сен 15, 16:42    [18105177]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4804
churupaha

Ну вы то в NATIVE_COMPILATION делали?


Велосипед изобретал

Картинка с другого сайта.
3 сен 15, 17:49    [18105308]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Makar4ik
Member

Откуда: Когда-то были Лужки, а теперь Бордюр-Сити.
Сообщений: 2676
Mike_za,

А вы не смотрели в сторону плоского кэша?
Обновляющегося, скажем, в триггере?
Где есть ссылки у каждой записи, скажем, на все 7 уровней вверх?
Как я понимаю, вас выборка беспокоит больше всего?
То есть со временем вставки на 3 секунды больше можно смириться, пока кэш перестраивается?
3 сен 15, 23:12    [18105932]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
Mike_za
Правильно ли я понимаю, что при наличии правильных индексов, рекурсивная цте замененная на N запросов по количеству уровней может быть сильно быстрее?


Если вы будете сохранять результаты каждого из этих N запросов во временную таблицу и после соединять эту таблицу с новым запросом - то реализуете тот же самый Spool, только своими руками, накладные расходы такого способа скорее всего будут выше.

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

Если смотреть в сторону оптимизации, то я бы смотрел в сторону материализации уже готового результата в момент добавления записи, чтобы ничего не разворачивать и не считать в запросе. Это будет быстрее всего.

## fa diezz ##
Интересное дело, а почему назвали Stack Spool = true? Ведь по факту записи из spool'а читаются в соответствии с FIFO, а не LIFO?

Судя по простому тесту как раз LIFO.
+
declare @t table(id int, parent_id int)
insert @t values (1,null);
insert @t values (2,1);
insert @t values (3,1);
insert @t values (4,1);
insert @t values (5,2);
insert @t values (6,2);
insert @t values (7,3);
insert @t values (8,3);
insert @t values (9,4);
insert @t values (10,4);

with r as (
	select lev = 1, id, parent_id from @t t where parent_id is null
	union all
	select lev = r.lev+1, t.id, t.parent_id from @t t join r on t.parent_id = r.id
)
select * from r;

1 итерация - помещаем в стек строчку (1, нулл).
2 итерация - берем из стека (1,нулл), джойним по парент = 1, помещаем в стек стоки (2,1), (3,1), (4,1).
3 итерация - берем из стека последнюю строку (4,1), джойнм по парент = 4, получаем (9,4), (10,4)
4 итерация - берем из стека следующую строку (3,1), джойнм по парент = 3, получаем (7,3), (8,3)
5 итерация - берем из стека следующую строку (2,1), джойнм по парент = 3, получаем (5,2), (6,2)
Результат:
(1, нулл)
(2,1)
(3,1)
(4,1)
(9,4)
(10,4)
(7,3)
(8,3)
(5,2)
(6,2)
Строки нигде не переупорядочиваются, велика вероятность, что они возвращаются в том порядке, в каком были помещены в таблицу Spool. Вполне себе LIFO.
4 сен 15, 10:59    [18107281]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
## fa diezz ##
Guest
SomewhereSomehow
Mike_za
Правильно ли я понимаю, что при наличии правильных индексов, рекурсивная цте замененная на N запросов по количеству уровней может быть сильно быстрее?


Если вы будете сохранять результаты каждого из этих N запросов во временную таблицу и после соединять эту таблицу с новым запросом - то реализуете тот же самый Spool, только своими руками, накладные расходы такого способа скорее всего будут выше.

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

Если смотреть в сторону оптимизации, то я бы смотрел в сторону материализации уже готового результата в момент добавления записи, чтобы ничего не разворачивать и не считать в запросе. Это будет быстрее всего.

## fa diezz ##
Интересное дело, а почему назвали Stack Spool = true? Ведь по факту записи из spool'а читаются в соответствии с FIFO, а не LIFO?

Судя по простому тесту как раз LIFO.
+
declare @t table(id int, parent_id int)
insert @t values (1,null);
insert @t values (2,1);
insert @t values (3,1);
insert @t values (4,1);
insert @t values (5,2);
insert @t values (6,2);
insert @t values (7,3);
insert @t values (8,3);
insert @t values (9,4);
insert @t values (10,4);

with r as (
	select lev = 1, id, parent_id from @t t where parent_id is null
	union all
	select lev = r.lev+1, t.id, t.parent_id from @t t join r on t.parent_id = r.id
)
select * from r;

1 итерация - помещаем в стек строчку (1, нулл).
2 итерация - берем из стека (1,нулл), джойним по парент = 1, помещаем в стек стоки (2,1), (3,1), (4,1).
3 итерация - берем из стека последнюю строку (4,1), джойнм по парент = 4, получаем (9,4), (10,4)
4 итерация - берем из стека следующую строку (3,1), джойнм по парент = 3, получаем (7,3), (8,3)
5 итерация - берем из стека следующую строку (2,1), джойнм по парент = 3, получаем (5,2), (6,2)
Результат:
(1, нулл)
(2,1)
(3,1)
(4,1)
(9,4)
(10,4)
(7,3)
(8,3)
(5,2)
(6,2)
Строки нигде не переупорядочиваются, велика вероятность, что они возвращаются в том порядке, в каком были помещены в таблицу Spool. Вполне себе LIFO.


Спасибо, а строки:

автор
(9,4), (10,4)
(7,3), (8,3)
(5,2), (6,2)


разве не помещались в стек? чтобы потом при join'e по parent_id = 9, 10, 7, 8, 5, 6 получить пустое множество?
4 сен 15, 11:35    [18107497]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
## fa diezz ##
Guest
SomewhereSomehow,

Почему один и тот же оператор плана, отображается в одном месте Index Spool (Lazy Spool), а в другом месте Table Spool (Lazy Spool)? И такой вопрос, для чего там Index Spool, по факту индекс то не используется? Или в тот Index Spool с Stack Spool = true ключем индекса является порядковый номер в котором вставили элемент? А на вытаскивании элементов из Table Spool вычитывается листовой уровень индекса в Index Spool справа (с наибольших номеров?) чтобы эмулировать поведение стека? o_O
4 сен 15, 11:44    [18107564]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34621
Mike_za,
при уже отобранных 3 тыщ записей зачем вообще думать о плиз производительности?
4 сен 15, 12:12    [18107761]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
## fa diezz ##
Спасибо, а строки:
разве не помещались в стек? чтобы потом при join'e по parent_id = 9, 10, 7, 8, 5, 6 получить пустое множество?

Помещались, конечно. Просто шаги, которые ничего не возвращают я опустил из описания для краткости.

## fa diezz ##
Почему один и тот же оператор плана, отображается в одном месте Index Spool (Lazy Spool), а в другом месте Table Spool (Lazy Spool)? И такой вопрос, для чего там Index Spool, по факту индекс то не используется? Или в тот Index Spool с Stack Spool = true ключем индекса является порядковый номер в котором вставили элемент? А на вытаскивании элементов из Table Spool вычитывается листовой уровень индекса в Index Spool справа (с наибольших номеров?) чтобы эмулировать поведение стека? o_O

Оператор не один и тот же, узлы все-таки разные, просто они связаны (Node ID -> Primary Node ID). Чтобы узнать, как именно внутри организован этот вид спула, нужно найти и расковырять страницы в памяти, которые он создает, т.к. это не документировано. Времени на это сейчас нет, можете попробовать сами это сделать. Чисто по смыслу, я не вижу тут профита от Index Spool, нет никакого ключа поиска, возможно просто особенность внутренней реализации.
4 сен 15, 14:09    [18108624]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
Mike_za,

Вот еще вспомнил статью в тему:
Optimize Recursive CTE Query

В ней команда SQL CAT разбирает случай, когда делать циклов выгоднее, чем рекурсивным CTE и приводит следующие критерии, когда rCTE не эффективно:
SQL CAT
There is a scenario where using a CTE construct is significantly less efficient than the traditional approach to traversing the Parent-Child construct. This blog will describe how and when a WHILE loop performs better than the CTE. The characteristics that can contribute to CTEs being a less than optimal choice are:
Non-Unique Parent/Child Key
Complex Predicates

В итоге, переписав на цикл с использованием табличных переменных удалось ускорить запрос в 36 раз.
В примерах, где нет описанных выше условий, накладные расходы на такую реализацию могут превысить расходы на выполнение rCTE.

В любом случае, надо пробовать на своих данных и выбирать наиболее подходящее решение. Самое быстрое, конечно, по прежнему, если все уже посчитано.
4 сен 15, 14:20    [18108704]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
Спасибо всем за активное обсуждение!

SomewhereSomehow,да, я уже натыкался на этот линк после создания сего топика)

На самом деле я не до конца описал свою задачу.
Есть дерево 3.5к узлов. И на часть узлов повешены объекты (вторая таблица).

Полностью задача звучала так: показать непосредственных детей узла. у которых зацеплены объекты, либо на их наследниках зацеплены объекты.

У коллеги старый код был написан через цикл снизу вверх. Я же написал раскрутку через cte и увидел дикую просадку по нагрузке.
4 сен 15, 23:04    [18111659]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
В варианте с циклом брались только те родители, которых еще нет в результате. И в итоге за 2 -3 итерации получалось полное множество зацеленных с их полными путями до рута, из которого выбирался один заказанный дочерний уровень одного узла.
4 сен 15, 23:17    [18111705]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
Количество итераций определялось максимально длинной пустой цепочкой вверх
4 сен 15, 23:20    [18111715]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
В итоге остановился на материализации в кеше части дерева, включающего в себя заполненные и пустые узлы ко всем нижним заполненным. (Id, parent_id)

Вариант с сохранением полных путей для каждого элемента не понравился. Во первых 3500 превратились в 19 тысяч записей. А во вторых джоин на таблицу заполненных узлов убивает весь профит.
4 сен 15, 23:25    [18111735]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
Собственно цте полностью повторяла бы цикл, если бы можно было сделать лефт джоин в рекурсивной части
4 сен 15, 23:28    [18111745]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
MasterZiv, с описанным итоговым кешом никаких 3 тысяч (200 logical reads ) не будет
4 сен 15, 23:29    [18111748]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
Mike_za
На самом деле я не до конца описал свою задачу.

Вот так всегда выясняется ко второй странице темы =)
Не зря в правилах написали
автор
Подумайте также над тем, чтобы описать решаемую Вами задачу целиком. Возможно, что тот способ решения, который Вы стремитесь воплотить в жизнь, не является наилучшим, а лишь кажется Вам таковым.

Т.е. всегда лучше начинать с озвучивания целой задачи, а уже далее приводить вариант своего решения.

Mike_za
Полностью задача звучала так: показать непосредственных детей узла. у которых зацеплены объекты, либо на их наследниках зацеплены объекты.

Если нет условий на фильтрацию "зацепленых" объектов, которое сильно ограничивает выборку, то я бы разделил задачу на две:
- достать дерево по родителю
- достать свойства объектов
Первую часть можно поместить во временную таблицу и создать хорошие индексы. Далее все должно быть приемлемо по скорости.
Трудно комментировать не зная задачи.

Но я не буду вдаваться в возможные архитектурные решения, моя миссия на этом форуме другая =)

В качестве пятничного настроения и в тему поста.

Есть такая книга, где отметились Glory, лександр Гладченко, Гавриленко Сергей Алексеевич и т.д.

Картинка с другого сайта.

И вот первая глава, первой части:
Картинка с другого сайта.

Поищите этот материал, может быть там можно найти идею!
Год выпуска книги 2007 - 8 лет прошло, а как актуально =)
4 сен 15, 23:36    [18111766]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
MasterZiv
Mike_za,
при уже отобранных 3 тыщ записей зачем вообще думать о плиз производительности?

Ну когда циклы (600 чтений) превратились в цте (150 000 чтений ) мне поплохело.
Цель то была уменьшить 600)))
5 сен 15, 00:23    [18111878]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
SomewhereSomehow, ну алгоритмы то не стареют)))
Еще раз всем спасибо.
5 сен 15, 00:27    [18111883]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Makar4ik
Member

Откуда: Когда-то были Лужки, а теперь Бордюр-Сити.
Сообщений: 2676
Mike_za
MasterZiv
Mike_za,
при уже отобранных 3 тыщ записей зачем вообще думать о плиз производительности?

Ну когда циклы (600 чтений) превратились в цте (150 000 чтений ) мне поплохело.
Цель то была уменьшить 600)))
Ну ты же по сути, джоинишь много раз...
5 сен 15, 00:28    [18111885]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
Mike_za,

И Вам спасибо, лишний раз подумал, надо делать доклад про Spool!
18042173

Там много интересного =)
Если найду платформу где выступить - расскажу.
5 сен 15, 00:31    [18111892]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить