Рекурсивные (Иерархические) запросы

Дерево в БД можно представить достаточно просто:

ID | PID | NAME| VALUE

Куда сложней из такой таблицы вытаскивать данные. Можно это делать рекурсивно выполняя маленькие запросы, узнающие значение и родителя.
Оказывается эту задачу можно решить одним запросом используя лишь один T-SQL.
Рассмотрим на примере: необходимо выбрать все ветки/листья элемента, вывести значения элементов и построить полный путь до каждого.
Для этого можно использовать следующий запрос:

WITH tree ( data , id , pid , level , pathstr ) 
AS ( SELECT t.NAME, t.ID, t.PID, 0, CAST ( t.VALUE AS VARCHAR ( 4000 ) ) 
FROM table t
WHERE t.ID = 1 
UNION ALL 
SELECT t.NAME, t.ID, t.PID, t.level + 1 , CAST ( tr.pathstr + '\' + t.VALUE) AS VARCHAR ( 4000 ) ) 
FROM table t
INNER JOIN tree tr 
ON ( t.PID = tr.id ) 
) 
SELECT tr.* 
FROM tree tr 
ORDER BY tr.level, tr.pathstr 

Что делает каждая его часть:

WITH tree ( <список столбцов для выборки из дерева > ) 
AS ( 
<Начальное условие, откуда начнется рекурсия> 
Изначально путь = NAME корня, а уровень задан в 0
Строку с путем кастим к максимальному VARCHAR, т.к. путь может быть очень длинным.
UNION ALL 
<связка текущего запроса с деревом (родитель с идентификатором)>
Тут же мы увеличиваем уровень вложенности, и формируем следующий элемент пути
) 
<Тут мы работаем с полученными значениями, как с обычной таблицей>

Результат будет примерно такой:

id | pid | level | data                | pathstr
1  |  0  |   0   | Значение Корня      | Корень 
2  |  1  |   1   | Значение уровня 1   | Корень / Уровень 1
3  |  1  |   1   | Значение уровня 1.1 | Корень / Уровень 1.1
4  |  2  |   2   | Значение уровня 2   | Корень / Уровень 1 / Уровень 2

Вывод результата выборки в строчку: FOR XML PATH

Бывает необходимость вывести результат выборки в строчку.
Рассмотрим на примере. Есть задача и список исполнителей, необходимо построчно вывести задачи и ответственных. В случае группировки по задаче, ответственному мы получим число записей = число задач * число ответственных, нам же требуется вывести задачи построчно. Это отлично реализуется с помощью инструкции MS SQL - FOR XML PATH, изначально используемой для формирования xml строки из выборки.

Пример кода: task - Задачи, executer - Исполнитель:

SELECT
e.name, -- название задачи
(SELECT t.name + ', ' -- список исполнителей для задачи через запятую
 FROM task t
 WHERE t.executor = e.id
 FOR XML PATH(''))
FROM executer e

Рассмотрим более интересный пример, более близкий к изначальному применению FOR XML PATH - сформируем CSV файл из таблицы одним запросом без всяких циклов:

SELECT
t.field1 + ';' + --объединяем список столбцов через разделитель
t.field2 + ';' +
t.field3 + ';' +
t.field4 + ';
' --перенос строки
FROM table t WHERE 1=1 FOR XML PATH('')

Если field не строка, то его нужно привести: CAST(field AS VARCHAR(50)).

Добавление для ORACLE

SELECT t.executor, wmsys.wm_concat(t.name) 
FROM FROM task t 
GROUP BY t.executor

NOT IN в MS SQL

В продолжение топика по оптимизации подзапросов в MS SQL, хотел бы сказать еще по поводу использования NOT IN. Точней его не использовании, т.к. в противном случае не подтягивается индекс и происходит полный перебор. Если есть возможность замените на эквивалентный запрос или перечисление констант.
Было:

...
field NOT IN (value1, value 2)
...

Стало:

...
field <> value1 AND field2 <> value2
...

Что быстрей LEFT JOIN или подзапрос в SELECT

Часто требуется выбрать дополнительные параметры плюсом к основной выборке.
Это можно сделать двумя способами:

• LEFT JOIN к основному запросу
• Подзапрос в секции SELECT

Пример запроса, выбирающего номенклатуру и товарную группу номенклатуры:

Подзапрос в секции SELECT:

SELECT nom.Наименование,
(SELECT tg.Наименование FROM Товарная группа tg WHERE tg.ID = nom.Товарная группа)
FROM Номенклатура nom

Вариант с LEFT JOIN:

SELECT nom.Наименование, tg.Наименование
FROM Номенклатура nom
LEFT JOIN Товарная группа tg
 ON(tg.ID = nom.Товарная группа)

После разбора плана выполнения запроса в MS SQL Server, было выявлено:

• При выборке в секции SELECT требуется дополнительное время на слияние основной выборки и подзапроса. Вышло 1% от общего времени.(+ LEFT JOIN / - SELECT)
• Оказалось, что каждый LEFT JOIN выполняется отдельным потоком! В то время как подзапросы выполняются последовательно после основной выборки. (+ LEFT JOIN / - SELECT)
• Каждый LEFT JOIN объединяется в результирующую выборку, что требует дополнительной памяти. В то время как подзапрос вернет нам одно значение на каждую строку, т.е. для получения результата нам нужно меньше памяти. (- LEFT JOIN / + SELECT)

Вывод: В условиях многоядерных серверов LEFT JOIN имеет неоспоримые преимущества

Ограничения в подзапросах:
При выборке дополнительных параметров в секции SELECT мы можем столкнуться с ситуацией, когда подзапрос вернул нам более одной записи. Отсечь это можно, указав принудительно число выбираемых записей:

SELECT nom.Наименование,
(SELECT TOP 1 tg.Наименование FROM Товарная группа tg WHERE tg.ID = nom.Товарная группа)
FROM Номенклатура nom

Такой запрос выполнялся дольше на 96% по сравнению с аналогичным без TOP 1

Разбор плана показал, что 1% дополнительного времени тратится вложенный цикл, а 95% на просмотр определенных строк не кластеризованного индекса!
Из этого можно сделать один вывод: никогда не используйте без надобности ограничения в подзапросах.

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