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

Откуда: Москва
Сообщений: 1176
А насколько вообще оптимально раскручивать дерево рекурсивной цте?

Имеем 3000 строк вида
id uniqueidentifier, parent_id uniqueidentifier....
Глубина 7 уровней. 1 рут
Все уже переложено во времянку, пробовал создавать всяческие индексы.
Ну уж больно количество чтений большое: Сильно больше, чем если сделать 7 раз полный скан всей таблицы в цикле.
2 сен 15, 00:12    [18097771]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
Пс. В планах loop join в рекурсивной части
2 сен 15, 00:14    [18097778]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
Пс2. Без index spool никак обойтись не получится?
2 сен 15, 00:14    [18097780]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4846
Mike_za
А насколько вообще оптимально раскручивать дерево рекурсивной цте?


Могу предложить циклом в NATIVE_COMPILATION -- будет немного быстрее
2 сен 15, 00:19    [18097799]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
a_voronin, 2005 sql
2 сен 15, 00:22    [18097806]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
Mike_za,

Если в глубину гарантированно не более 7 уровней (остальные, даже если есть, не интересуют), - то зачем вообще рекурсия?
Банальные 6 LEFT JOIN от FROM-корня
2 сен 15, 07:17    [18098017]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
dma_caviar
Member

Откуда: https://itproduct.ru
Сообщений: 2361
Cygapb-007
Mike_za,

Если в глубину гарантированно не более 7 уровней (остальные, даже если есть, не интересуют), - то зачем вообще рекурсия?
Банальные 6 LEFT JOIN от FROM-корня

Хе-хе) Недавно пробовали работать с одним челом. Он как раз запилил 7 джоинов в справочнике номенклатурных групп. Там нужно было вверх по иерархии доставать товарную наценку, в зависимости от того на каком уровне она определена.
Я теперь этот запрос на собеседованиях показываю, типа, скажите что тут не так и что можно было бы сделать с этим скриптом))
2 сен 15, 08:56    [18098179]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Cygapb-007
Member

Откуда:
Сообщений: 1677
dma_caviar
Cygapb-007
Mike_za,

Если в глубину гарантированно не более 7 уровней (остальные, даже если есть, не интересуют), - то зачем вообще рекурсия?
Банальные 6 LEFT JOIN от FROM-корня

Хе-хе) Недавно пробовали работать с одним челом. Он как раз запилил 7 джоинов в справочнике номенклатурных групп. Там нужно было вверх по иерархии доставать товарную наценку, в зависимости от того на каком уровне она определена.
Я теперь этот запрос на собеседованиях показываю, типа, скажите что тут не так и что можно было бы сделать с этим скриптом))
Вверх по иерархии - это совсем другая задача, вам не кажется? Вероятно, нет...
2 сен 15, 09:20    [18098238]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
dma_caviar,
Какой правильный ответ?

В моих задачах и вверх нужно, и вниз нужно. И в теории уровней может быть и не 7.
2 сен 15, 10:20    [18098568]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
SomewhereSomehow
Member

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

Без Spool в рекурсивных CTE обойтись нельзя, т.к. сервер реализует рекурсию при помощи этих операторов. Это особый вид спула, называемый Stack Spool.

На примере:
+
use tempdb;
go
create table t(id uniqueidentifier primary key, parent_id uniqueidentifier, padding char(100) not null default (''));
insert t(id) values (newid());
declare @i int = 0;
while @i < 6 begin
	insert t(id, parent_id) select newid(), id from t cross apply (select 1 union all select 1 union all select 1) x(x)
	set @i += 1;
end;
go

-- Логических чтений в одном сканированиитаблицы
set statistics io on;
select * from t
set statistics io off;

-- Рекурсивный запрос
set statistics io, time on;
with r as (
	select lev = 1, id, parent_id, padding from t where parent_id is null
	union all
	select lev = r.lev+1, t.id, t.parent_id, t.padding from t join r on t.parent_id = r.id
)
select * from r option(maxrecursion 7)
;
set statistics io, time off;
go


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

1. Выполнение начинается с верхней ветки плана, которая считает не рекурсивную часть CTE и записывает в родительский Spool (обозначено Parent).

2. Далее оператор конкатенации спрашивает вторую, нижнюю ветку плана – дай строку. Nested Loops спрашивает дочерний Spool (обозначено Child), дай строку, тот читает строку, которая была в него записана ранее (первая строка записана на шаге 1, последующие на шаге 3) и удаляет ее.

3. Происходит соединение по parent_id с полем из таблицы, результат соединения записывается в родительский Spool.

4. Шаг 2 повторяется.

Assert проверяет уровень рекурсии, Compute Scalar вычисляют выражения. Так работает рекурсивный CTE.

По чтениям. Не знаю, как у вас, ни плана, ни статистики не видел.

Может быть как в этом репро – не хватает индексов?

В данном примере индекса нет. Одно сканирование таблицы t – 105 логических чтений, в таблице 4096 строк, оператор сканирование выполняется 4096 раз. Еще одно сканирование при выполнении не рекурсивной части. Итого чтений – 104 + 104*4096 = 426088 чтений. Что мы и видим.

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

Чтобы избежать такого количества чтений, нужно сделать покрывающий индекс по Parent_ID
+
create index ix_parent_id on t(parent_id) include(padding);
go
set statistics io, time on;
with r as (
	select lev = 1, id, parent_id, padding from t where parent_id is null
	union all
	select lev = r.lev+1, t.id, t.parent_id, t.padding from t join r on t.parent_id = r.id
)
select * from r option(maxrecursion 7)
;
set statistics io, time off;
go


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

Время выполнения также сократилось с 1613 мс до 200 мс, примерно в 8 раз.

В целом, рекурсивные CTE не самая быстрая и эффективная вещь в сиквеле, но если их использовать правильно и в нужных местах/задачах, то вполне нормально. Если это какая-то высоконагруженная система и борьба идет за каждую миллисекунду, то рекурсивное CTE не лучший выбор, в таком случае, лучше подумать об архитектурных изменениях, например, хранить уже материализованное, пред-рассчитанное дерево.
2 сен 15, 10:54    [18098761]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
SomewhereSomehow, большое спасибо.

С индексам все было хорошо.
Меня смущал NestedLoop в рекурсивной части, приводящий к выполнению IndexSeek 3000 раз.
Но из вашего объяснения следует что от этого никуда и не деться.

Правильно ли я понимаю, что при наличии правильных индексов, рекурсивная цте замененная на N запросов по количеству уровней может быть сильно быстрее?
2 сен 15, 13:08    [18099531]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Mike_za, так вы проверьте. Мне кажется, если сделать 7 соединений, по производительности это будет так же, как и CTE.

Если нужно повышать производительность при небольшом количестве уровней - возможно, имеет смысл на hierarchyid перейти?
2 сен 15, 15:25    [18100314]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
2005 ((
2 сен 15, 16:16    [18100575]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Minamoto
Member

Откуда: Москва
Сообщений: 1162
Mike_za, можно просто хранить Materialized Path. HierarchyID всего лишь упрощает работу с таким способом хранения.
3 сен 15, 10:21    [18102689]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Yuri Abele
Member

Откуда: Латвия> Литва > Тольятти > Wiesbaden > Karlsruhe
Сообщений: 1661
> HierarchyID всего лишь упрощает работу с таким способом хранения.

он еще к тому же и заметно медленнее во многих операция, т.к. это .NET тип, который сериализует/десериализует значение поля при обращении к его (.NET объекта) методам.
Поэтому соглашусь - просто хранить путь и искать потомков/предков/корень и т.п. с помощью LIKE/PATHINDEX/SUBSTRING и т.д. намного быстрее.
3 сен 15, 10:47    [18102919]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4846
Mike_za,
CLR попробуйте
3 сен 15, 10:58    [18103016]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
## fa diezz ##
Guest
SomewhereSomehow
...


Интересное дело, а почему назвали Stack Spool = true? Ведь по факту записи из spool'а читаются в соответствии с FIFO, а не LIFO?
3 сен 15, 11:08    [18103115]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
a_voronin, как именно его попробовать?
3 сен 15, 11:21    [18103218]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4846
Mike_za
a_voronin, как именно его попробовать?


CLR функцию напишите, которая дерево строит кодом на C#.
3 сен 15, 14:12    [18104401]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9785
a_voronin
CLR функцию напишите, которая дерево строит кодом на C#.
Выигрыш за счет чего будет?
3 сен 15, 14:59    [18104595]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4846
invm
a_voronin
CLR функцию напишите, которая дерево строит кодом на C#.
Выигрыш за счет чего будет?


За счёт ума и сообразительности автора CLR.
3 сен 15, 15:02    [18104627]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9785
a_voronin
За счёт ума и сообразительности автора CLR.
Ясно.
3 сен 15, 15:16    [18104734]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9785
a_voronin
а счёт ума и сообразительности автора CLR.
Т.е. сами вы не пробовали, не знаете и не умеете. Но, тем не менее, рекомендуете ТСу этот способ.
В общем, все как всегда
3 сен 15, 15:19    [18104766]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
a_voronin
Member

Откуда: Москва
Сообщений: 4846
invm
a_voronin
а счёт ума и сообразительности автора CLR.
Т.е. сами вы не пробовали, не знаете и не умеете. Но, тем не менее, рекомендуете ТСу этот способ.
В общем, все как всегда


Не имёться вам потролиться.

Я пробовал писать развертку дерева на NATIVE_COMPILATION и получил прирост, хотя и не столь внушительный. Поскольку у ТС SQL 2005, то я предложил попробовать CLR, как ближайшее приближение к NATIVE_COMPILATION.
3 сен 15, 15:25    [18104825]     Ответить | Цитировать Сообщить модератору
 Re: Рекурсивное Cte и раскрутка дерева  [new]
churupaha
Member

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


зачем, если можно

18102689
18102919

Joe Celko's Trees and Hierarchies in SQL for Smarties
3 сен 15, 15:35    [18104905]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить