Есть таблицы с полями NODE(ID_NODE, ID_PARENT, TYPE). Среди всех моих типов есть тип "Каталог"(номер, скажем, 1).

Нужно написать хранимую процедуру, которая бы возвращала количество ВСЕХ детей(внук, правнук и т.д.) в каталоге. Причем внутренние узлы-каталоги не должны считаться, но если у них есть дети-НЕкаталоги, то дети считались. Сейчас реализовано так:

CREATE PROCEDURE dbo.DocChildrenCount @id_node int
AS
BEGIN
    DECLARE @res int
    DECLARE @lev int
    CREATE TABLE #ChildNodeList
    (
        ID_NODE int PRIMARY KEY,
        LEV int NOT NULL
    )
    SELECT @lev = 0
    INSERT INTO #ChildNodeList (ID_NODE, LEV)
    SELECT ID_NODE, @lev FROM NODE
        WHERE ID_NODE = @id_node
    WHILE (@@ROWCOUNT > 0)
    BEGIN
        SELECT @lev = @lev + 1
        INSERT INTO #ChildNodeList (ID_NODE, LEV)
        SELECT DISTINCT N.ID_NODE, @lev FROM NODE N
            WHERE N.ID_PARENT IN (SELECT ID_NODE FROM #ChildNodeList) AND
            N.ID_NODE NOT IN (SELECT ID_NODE FROM #ChildNodeList)
    END

    SELECT @res=count(*)
    FROM #ChildNodeList C, NODE N 
    WHERE C.ID_NODE = N.ID_NODE
        AND N.ID_ITEMTYPE <>1

RETURN @res
END

Но работает все довольно медленно. Как ускорить?

Изменения ускоряющие запрос (без изменения алгоритма):
1. Заменяем временную таблицу в базе данных на таблицу в памяти, да и поддержка целостности не нужна:

    declare @ChildNodeList table ( ID_NODE int, LEV int )

2. Изменяем запрос в цикле перенеся ограничения выборки из директивы WHERE в директиву FROM, т.к. вложенные запросы в WHERE выполняются для каждого кортежа в таблице существенно тормозя:

INSERT @ChildNodeList
SELECT DISTINCT N.ID_NODE, @lev 
  FROM NODE N
  inner join @ChildNodeList CNL on CNL.ID_NODE = N.ID_PARENT
  left outer join @ChildNodeList CNL2 on CNL2.ID_NODE = N.ID_NODE
WHERE CNL2.ID_NODE is null

Вот и все. На первый взгляд.
Желаю удачи!

Здравствуйте, DePress, Вы писали:

DP>Есть таблицы с полями NODE(ID_NODE, ID_PARENT, TYPE). Среди всех моих типов есть тип "Каталог"(номер, скажем, 1).

DP>Нужно написать хранимую процедуру, которая бы возвращала количество ВСЕХ детей(внук, правнук и т.д.) в каталоге. Причем внутренние узлы-каталоги не должны считаться, но если у них есть дети-НЕкаталоги, то дети считались. Сейчас реализовано так:
....
DP>Но работает все довольно медленно. Как ускорить?

Предлагается ход из теории деревьев.
Смысл в следующем: потребуется еще одна таблица, в которой будешь хранить ID_NODE, ID_PARENT, TYPE
НО! элементы ID_NODE это не только прямые дети элементов ID_PARENT, но и дети всех нижележащих каталогов ID_PARENT
Т.е. для дерева
1
--2
--3
--5
--6
--4
--7

исходная таблица:
NODE(ID_NODE, ID_PARENT, TYPE)
1 0 1
2 1 0
3 1 1
4 1 1
5 3 0
6 3 0
7 4 0

получится:
NODE2(ID_NODE, ID_PARENT, TYPE)
1 0 1
2 1 0
3 1 1
5 3 0
5 1 0
6 3 0
6 1 0
4 1 1
7 4 0
7 1 0

Соответсвенно, если тебе надо количество всех детей каталога 1 выполняешь запрос:
SELECT COUNT(*) FROM NODE2 WHERE ID_PARENT=1 AND TYPE=0

Результат получаешь мгновенно.
НО, есть маленькая неприятность: эту вторую табличку заполняешь один раз, а потом по триггеру на табличке NODE ты ее update'ишь. Можешь, конечно, просто перестроить ее заново, если изменения таблицы NODE происходят редко и время выполнения UPDATE или INSERT в данном случае некритично.
В противном же случае придется написать триггера на INSERT, UPDATE и DELETE в которых будешь перестраивать те ветки, в которых произошли изменения. Трудозатраты не маленькие, на раз за день не напишешь, может порядка недельки с отладкой уйдет, но зато количество детей будешь получать мгновенно без всяких функций.

Еще вторую таблицу можешь использовать для одновременных операций сразу над всеми детьми какого-либо каталога. Например удалить всех детей каталога 1:
DELETE FROM NODE
WHERE ID_NODE IN
(SELECT ID_NODE FROM NODE2 WHERE ID_PARENT=1)

Опаньки, потерялись пробелы в дереве. Вот так должно быть:
1
|-2
|-3
..|-5
..|-6
|-4
..|-7

Здравствуйте, ShAlexNik, Вы писали:

SAN>Изменения ускоряющие запрос (без изменения алгоритма):
SAN>1. Заменяем временную таблицу в базе данных на таблицу в памяти, да и поддержка целостности не нужна:
SAN>2. Изменяем запрос в цикле перенеся ограничения выборки из директивы WHERE в директиву FROM, т.к. вложенные запросы в WHERE выполняются для каждого кортежа в таблице существенно тормозя:

Спасибо за ответ. Со стороны, для МЕНЯ, как-то не очевидно, что этот алгоритм работает быстрее. Как мне сравнить скорости? (Запускаю у себя на дереве с 12000 элементов время работы 0 сек и там и там).

Здравствуйте, H.Sheremet, Вы писали:


HS>Предлагается ход из теории деревьев.
HS>Смысл в следующем: потребуется еще одна таблица, в которой будешь хранить ID_NODE, ID_PARENT, TYPE
HS>НО! элементы ID_NODE это не только прямые дети элементов ID_PARENT, но и дети всех нижележащих каталогов ID_PARENT
HS>Соответсвенно, если тебе надо количество всех детей каталога 1 выполняешь запрос:
HS>SELECT COUNT(*) FROM NODE2 WHERE ID_PARENT=1 AND TYPE=0

HS>Результат получаешь мгновенно.
HS>НО, есть маленькая неприятность: эту вторую табличку заполняешь один раз, а потом по триггеру на табличке NODE ты ее update'ишь. Можешь, конечно, просто перестроить ее заново, если изменения таблицы NODE происходят редко и время выполнения UPDATE или INSERT в данном случае некритично.
Идея, конечно, хорошая и возможно я ее буду использовать в других БД. Но пользователи довольно редко будут использовать эту возможность. Поэтому создавать дополнительную таблицу + обслуживание будет себе дороже.

Но все-равно СПАСИБО за ответ и идею.

Здравствуйте, ShAlexNik, Вы писали:

SAN>1. Заменяем временную таблицу в базе данных на таблицу в памяти, да и поддержка целостности не нужна:
AFAIK, таблицы — переменные и временные таблицы создаются в одном и том же месте. Точнее, в TempDB. B производительность их совершенно одинаковая. См. Query Plan в Query Analyser.