Вообще-то рекурсия для SQL -- вещь достаточно неестественная. Тем не менее жизнь довольно часто подбрасывает ситуации, когда её требуется реализовать. Причём эффективно. Именно в базе. И данных вполне может оказаться приличное количество. Об одном таком случае в вкратце попробую рассказать. Случай весьма примечательный тем, что сначала было найдено очевидное решение, а затем -- эффективное. Разница в скорости составила два порядка.
В развитии данной истории принимали активное участие Мария Баркова и Сергей Степанов -- сотрудники проекта Архив. Другую информацию о работе с деревьями в SQL вообще и InterBase в частности можно найти на здесь, (в разделе «Прочее» есть ряд ссылок по теме деревьев).
Ну и последняя часть рассказа с участием UDF всплыла в ходе переписки с Евгением Жилкиным (Eugene Zhilkin, CS Ltd) в декабре 2001 года.
Итак, в БД имеется дерево. То есть таблица, в структуре которой предусмотрена ссылка на родительскую запись той же таблицы. Однако одной такой ссылкой дело, естественно, не ограничивалось -- присутствовало значительное количество других полей, часть из которых изрядного объёма, другая -- ссылки на прочие таблицы. Короче, таблица не всегда лёгкая даже для обычных, нерекурсивных выборок. Кроме этого, различные справочные и детализирующие таблицы, с которыми главная (древесная) таблица связана многочисленными ключами, тоже примитивизмом не отличались.
Так вот, задача стояла примерно так: выявить (и выдать список ключей) те
записи главной таблицы, у которых нет ни одного из трёх оговорённых
видов детализации, и так же нет ни у одного ``потомка'' записи согласно
главной таблице. Детализация в данном случае -- одна из других таблиц,
ссылающихся на главную через foreign key. Соотношение -- многие
(детализация) - к - одному (главная таблица).
Таким образом, требовалось пройтись по главной таблице, выявить в ней поддеревья, по каждой ветке поддерева проверить наличие записей детализации, и если по всему поддереву наличие нигде обнаружено, вернуть ключ корня этого поддерева. То есть как выяснится чуть позже, решить задачу можно несколькими способами, но результат, естественно, должен быть эквивалентным. Надеюсь, я не слишком Вас запутал.
Основные трудности, как можно видеть, следующие:
Почти буквально как поставлена задача. Процедура обходит поддеревья и выбирает подходящие записи. Выбор основан на подсчёте количества нужных записей детализации по всему поддереву. Таким образом, на вход принимается ссылка на ``родителя'' проверяемых записей, в качестве результата возвращается множество, включающее в себя для каждой записи ключ (ID), дополнительную информацию (которая нас здесь не слишком интересует), и количество найденных записей детализации нужного вида (RefCount).
Если передать в качестве параметра NULL, то процедура пройдётся
по всем корням поддеревьев, потому что они ``родителя'' не имеют. И
соответственно будет проверена вся база.
Имена главных героев изменены :-).
alter procedure sp_Ver1(RefRoot integer)
returns ( ID integer, ...дополнительная информация...,
RefCount integer) as
declare variable ChildRefCount; /* Количество потомков
с детализацией */
begin
for select m.ID, ...дополнительная информация...
from MainTable m, ...справочники...
where ( (m.RefParent = :RefRoot) or
(m.RefParent is null) and (:RefRoot is null))
and (...соединение со справочниками...)
into :ID, ...
do begin
RefCount = 0;
/* Если нет детализации по текущей
главной записи ... */
if ((not exists( select ID from Детализация
where RefMain = :ID and..ещё условия))
and (not exists(другая детализация ...))...)
then begin /* ... то проверяем потомков рекурсивно */
if (exists( select ID from MainTable
where RefParent = :ID))
then begin /* Если потомки есть, то идем по ним */
for select RefCount from sp_Ver1(:ID)
into :ChildRefCount do
RefCount = :RefCount + :ChildRefCount;
end
end /* if not exists */
else RefCount = 1;
suspend;
end /* for select from MainTable */
end /* procedure */
Возвращаемое значение RefCount -- это конечно не полное количество. Для задачи важно лишь определить, нулевое оно, или нет.
Можно конечно покритиковать это решение за несколько избыточное местами
применение exists(), но оптимизация таких мелочей сути бы
не изменила -- работает такое неизбежно долго -- порядка часа. Плюс-минус
в ту или другую сторону в зависимости от мощности сервера и других
второстепенных факторов.
Так как процедура рекурсивная, то создаётся в два приёма. Сначала пустая с нужным заголовком (в примере опущено), а затем окончательная, ссылающаяся на собственный, уже существующий, заголовок.
И тем не менее, любая реляционная СУБД больше приспособлена к работе с линейными потоками записей а не с деревьями. В данном случае, хоть мы и имеем дело с деревом, то это лишь часть задачи. Другие части -- проверка наличия детализации и выборка дополнительной информации. Выполняются вполне традиционным образом. Таким образом, основное направление следующего шага в том, чтобы взять все эти три подзадачи, и поделить.
Данное решение уже позволило сократить обработку с часа до минуты на тех же данных.
alter procedure sp_GetAllChildren(ParentID integer)
returns (ChildID integer) as
declare variable DirectChildID integer;
begin
ChildID = :ParentID; suspend;
for select ID from MainTable
where RefParent=:ParentID into :DirectChildID do
begin
ChildID = :DirectChildID;
suspend;
for select ChildID
from sp_GetAllChildren(:DirectChildID)
where ChildID <> :DirectChildID
into :ChildID do
suspend;
end /* for select from MainTable */
end /* procedure */
Выборка включает в себя в том числе и корень поддерева, переданный в качестве параметра. По этой причине внутри приняты меры, чтобы не выдавать наружу узлы по два раза.
create procedure sp_Ver2
returns ( ID integer, ...доп. информация...,
RefCount integer) as
declare variable ChildID integer; /* Ссылка на потомка
текущей записи */
declare variable RefDescr integer; /* Ссылка на справочник
из главной таблицы
для доп. информации */
begin
for select ID, RefDescr from MainTable
into :ID, :RefDescr do
begin
RefCount = 0;
for select ChildID from sp_Ver2(:ID)
into :ChildID do
if( exists( select ID from Детализация
where RefMain = :ChildID ...)
or exists(другая детализация ...) ...
then RefCount = :RefCount + 1;
if( :RefCount = 0 )
then begin
select ...доп. информация... from Справочник
where ID = :RefDescr into :...;
suspend;
end /* if :RefCount = 0 */
end /* for select */
end /* procedure */
Следует заметить, что выборка справочников для главной таблицы, которые в данном случае играют весьма вспомогательную роль, отложена на самый конец и делается исключительно для тех записей, что уже однозначно попадают в окончательный результат. В основном цикле выбирается лишь ссылка на справочник (ну в жизни разумеется ссылка в таблице не одна, но сути это не меняет).
Кроме этого, в процессе ``доводки'' процедуры была сделана ещё одна
оптимизация. Если внимательно посмотреть на внутренний цикл, то можно
обнаружить, что выполнять его следует только пока не найдено ни одной
записи с детализацией. К сожалению, простых средств прекратить
цикл в InterBase нет, но можно добавить в выборку for select
условие where RefCount = 0. Это по крайней мере сделает
лишнюю прокрутку цикла холостой.
Таким образом, в результате всех описанных мер мы получили выигрыш более чем на полтора порядка. Но оказалось, что и это не предел. Ещё одна неэффективность этого подхода в том, что записи главной таблицы (всё-таки) часто анализируются по-нескольку раз. Один раз -- сами по себе, другие -- как чьи-то потомки (подчинённые). Вот тут-то, при анализе этой неэффективности, у меня и родилась мысль подойти к задаче ``с другого конца''. Начать обработку не с главной таблицы, а как раз с исключаемых детализаций. А на главную выйти в конце.
Кроме того, что было сказано в предыдущем абзаце, этот вариант ещё и наиболее правильный с точки зрения сведения всей обработки к к линейным операциям. Достаточно сказать, что он не рекурсивный, даже несмотря на то, что имеет дело с рекурсивной структурой.
create procedure sp_ListExcluded
returns (ID integer) as
begin
for select RefMain from Детализация where ...
union select RefMain from ДругаяДетализация ...
into :ID do
begin
suspend;
while(:ID is not null) do /* проход до корня */
begin
select RefParent from MainTable
where ID =:ID into :ID;
if(:ID is not null)
then suspend;
end /* while id is not null */
end /* for select union */
end /* procedure */
Внешний цикл делается через union, а не union all.
Конечно, второй сам по себе эффективнее, но в данном случае выборки
изрядно пересекаются, так что ликвидировать дубликаты с точки зрения
последующей работы важнее.
Конечно, при данной технологии одна и та же запись главной таблицы
всё-таки может попасть выборку несколько раз, если у неё
в дереве имеется несколько подчинённых узлов. Но это совершенно
несложно устранить путём select distinct id from sp_ListExcluded.
Опять же, distinct может показаться ресурсоёмкой операцией --
сортировка ведь. Однако в данном случае речь идёт исключительно
о сортировке ключей, целых чисел. Физический объём измеряется
не мегабайтами, а сотнями килобайт. Для современного сервера совершенно
немного. Так что опасаться не за что. Как раз самое
время принять меры, чтобы ужать выборку.
Остаётся пройтись по главной таблице и извлечь из неё записи, отсутствующие
в результате sp_ListExcluded. Если бы не некоторые ``но'', то вполне
вероятно, что можно было бы обойтись одним запросом примерно такого вида:
select ID
from MainTable m left outer join sp_ListExcluded x
on o.ID = x.ID
where x.ID is null
Хитрость заключается в том, что внешнее соединение для недостающих
записей формирует NULL (из процедуры он появиться не может),
и именно такие записи отлавливаются условием where.
К сожалению, на момент, когда это всё происходило, вопрос
о соединении с процедурами не был
изучен, а версия InterBase была 4.2, то есть гораздо более привередливая
к такого рода операциям. Провернуть запрос такого вида напрямую не
удалось. Пришлось создавать временную таблицу, загонять в неё выборку
select distinct из процедуры, а затем соединять. И с главной
таблицей, и со справочниками -- всё сразу получилось достаточно
просто и эффективно.
В целом данный вариант оказался примерно вдвое быстрее предыдущего, рекурсивного. Временную таблицу оказалось всё-таки немного полезнее проиндексировать. Даже несмотря на накладные расходы на её заполнение и очистку, получившиеся возможности оптимизации дали существенный выигрыш. Правда следует заметить, что решение не было рассчитано на частое выполнение таких операций. Вполне возможно, что если их часто повторять без очистки старых версий, то торможение от временной таблицы возросло бы во много раз.
Ну и под конец -- о способе Евгения Жилкина, фактически выходящем за рамки SQL. Как известно, InterBase поддерживает такой механизм, как UDF. То есть функции пользователя, вызываемые из SQL, и написанные на компилируемых языках. Работающие по этой причине весьма быстро. Как оказалось, быстрее временных таблиц. Дальше процитирую первоисточник:
Целью задачи был расчёт кол-ва необходимых деталей, стандартных и покупных изделий, материалов, состава необходимых операций и трудовых ресурсов, стоимости операций, покупных изделий и т.п. для производства единицы изделия, входящего в конечный заказ на производство. Задача решалась для разных предприятий (машиностроение/приборостроение) с учётом особенностей опытного-мелкосерийного и серийного производства. Основной алгоритм (т.н. "разузлование") заключался в том, что для каждой сборочной единицы (СЕ) определялись её составляющие: ДСЕ (детали и сборочные единицы), СТИ (стандартные изделия), ПКИ (покупные изделия), материальные операции и трудовые операции. И так уровень за уровнем [Д]СЕ (и СТИ) "расползались" на аналогичные составляющие. Каждое разузлование записывалось (по каждой сущности) в виде итогов (итоговое кол-во, стоимость и т.п.) в таблицу.
Нулевой вариант, отметённый "с гневом" сразу - "вытягивать на клиента и считать". На "больших" заказах - данных - огромное количество.
Первый подход был сделан очень похожим способом на описанный тобою (i.e. процедурная рекурсия), только осложнялся он тем, что связочных таблиц - несколько, и каждая со своими свойствами. От данного метода ушли, т.к. время обработки одного "среднего" заказа составляло от 50 мин до 2-3 часов. На "больших" IB обваливался. И ещё иногда случались обвалы даже на "простых заказах" - чуть ниже опишу причины.
Второй подход был похож на твой последний, но отличался тем, что данные скидывались в промежуточную таблицу. Заодно по ней определялось - проходили ли мы конкретный узел или нет. Т.е. как таковой, рекурсии уже не было. По времени - примерно аналогично, но обвалов не случалось.... Значительно на время влияли факторы IB: "свеженькая" БД (после backup/restore) или нет; первым разузловывался "большой" заказ или наоборот. И т.п. т.е. влияло больше размазывание страниц, отводимых на временную таблицу, по файлу данных.
И наконец - третий и последний вариант. Его необходимость продиктовывалась тем, что некоторые пользователи иногда ошибались и "зацикливали" связи. Легко найти циклы, когда они на одном-двух уровнях, но на большем - очень трудно. Это и вызывало слёты IB при рекурсивном методе. А при втором подходе - иногда - неверные результаты (т.к. всё зависело от того, на какую "вершину" цикла попадёт в первый раз алгоритм. Если как раз на ту, в которой сидела некорректная связь, то алгоритм не зацикливался, но неправильно учитывал количественную взаимосвязь сущностей внутри цикла и их собственные ответвления ниже, вне цикла).
Мы сделали dll, которая содержала набор udf для инициализации (закачки данных) функцию расчёта, и набор функций выкачивания данных обратно. При расчёте, заодно, производился поиск циклов, и при обнаружении - состав циклов выводился обратно и сохранялся в базе для последующего ручного разбора.
Изюминка, собственно состоит в том, что udf ОЧЕНЬ быстро вызывается и ОЧЕНЬ быстро обрабатывает данные. Первые варианты такого решения привели к расчёту за 1 - 8 мин. Впоследствии, проанализировав - на что больше всего тратится времени, поняли - на выделение памяти под элементы в TList (!!!). Дело в том, что он выделяет (и довыделяет (метод Grow)) памяти по-умолчанию - очень мало. При закачке таблиц с миллионами записей, тратилось время на подобное "отрывочное" выделение. Немного модифицировав класс TList, получили расчёт даже самых больших заказов - за 2 мин. Причём половина ( 40-45%) этого времени тратилась на подготовку и вызов процедур на клиентском месте (из них 20% тратилось на обработку процедуры, которая с помощью select'ов загоняла данные в dll), а другая ( 50%) тратилась на вызов функций из dll по вытягиванию результатов и "распихиванию" их в таблицы результатов. Вызов функции расчёта длился 1 секунду МАКСИМУМ !!! Правда, часть подготовки к расчешу производилась ещё и в функциях запихивания данных.
Если изобразить в терминах SQL что производилось, то происходило примерно следующее:
Закачка в DLL:
create procedure eprDenode_Init
(
....
)
returns
(
aSessionID integer
)
as
dummy integer;
begin
aSessionID = gen_ID(...);
insert into Sessions
...
(aSessionID, ....);
dummy = udf...Init (aSessionID,...);
eprDenode_Init_1 (aSessionID);
eprDenode_Init_2 (aSessionID);
....
end
^
create procedure eprDenode_Init_1
(aSessionID integer)
as
dummy integer;
begin
select distinct 1 from .... z
where udf...SaveZData1 ( :aSessionID, z.ID,
z.ChildID, z.Quantity, ....) = 0
and udf...SaveZData2 (....) = 0
into :Dummy;
select distinct 1 from .... y
where udf...SaveYData1 (:aSessionID, y.ID, y.Prise, ....) = 0
and udf...SaveYData2 (....) = 0
into :Dummy;
..... select distinct 1 from .... j
where udf...SaveJData1 ( :aSessionID, j.ID, j.MaterialID,
j.MeasureID, j.Quantity ....) = 0
and udf...SaveJData2 (....) = 0
into :Dummy;
.....
end
^
Выкачка данных произведена, запускаем расчёт
create procedure eprDenode_Calc
(aSessionID integer)
returns
(Res integer)
as
begin
Res = udf...Calc (aSessionID);
end
^
Выкачка данных из DLL и сохранение их в табл. результатов
create procedure eprDenode_Save
(
aSessionID integer
)
as
dummyI integer;
dummyD double precision;
....
i integer;
begin
i = udfGetNextArecID(aSessionID);
while i>0 do
begin
DummyI = udfGetCurrAParamI (aSessionID, i);
DummyD = udfGetCurrAParamD (aSessionID, i);
....
insert into ... /* табл. результатов*/
values
(i, DummyI, DummyD, .....)
.....
i = udfGetNextArecID(aSessionID);
end
.....
i = udfGetNextBrecID(aSessionID);
while i>0 do
begin
DummyI = udfGetCurrBParamI (aSessionID, i);
DummyD = udfGetCurrBParamD (aSessionID, i);
....
insert into ... /* табл. результатов*/
values
(i, DummyI, DummyD, .....)
.....
i = udfGetNextBrecID(aSessionID);
end
.....
end
^
То, что время на загрузку данных в DLL и выгрузку данных их DLL примерно одинаково, объясняется тем, что загрузка проста и быстра, выполняются простыми командами select, но грузить надо очень много данных. Выгрузка обратная - более трудоёмкая операция (т.к. в один момент функция может вернуть только одно значение, кода (процедурного) много и он скомпилирован в псевдокоманды, выполняются операции insert) , но данных намного меньше (количественно).
Limitations: применять только на Classic (использовался IB 4.0/NT). На суперах - проблемы с невозможностью распознать сессию пользователя и одновременный расчёт двумя пользователями невозможен. Вариант решения - применение отдельного сервера приложений, который осуществляет запуск подобного расчёта.
Теперь что я думаю по данному поводу. В целом оно слегка похоже на мой ``обратный'' вариант, но вместо временной таблицы используются структуры данных, доступные UDF. Обычно (при традиционном использовании) вызовы этих функций работают автономно друг от друга, обрабатывая отдельные скалярные данные. Здесь же речь фактически идёт о создании специализированного программного модуля под задачу, имеющего интерфейс к InterBase в виде набора UDF в одной библиотеке. И вполне вероятно, что подобный подход может пригодиться не только по поводу рекурсии.