воскресенье, 13 марта 2011 г.

Работа с n-арными деревьями на PL/SQL

Представьте себе почти классическую ситуацию: есть какие-то данные в БД (одна, две и более таблиц), и надо эти данные обработать хитрым образом, а затем сохранить результат в отдельную таблицу для последующего представления данных пользователю.

Выбирать данные на клиентское приложение, обрабатывать локально, а затем сохранять результат обратно в БД – законом не запрещается, но крайне не рационально. Причём чем больше объём исходных данных, тем больше требуется время на просто выборку данных. Поэтому любые задачи, связанные с обработкой данных лучше решать на стороне сервера.

Допустим, что в процессе обработки данных, нам необходимо построить дерево.

На Delphi структуру узла дерева можно описать так:

type
PNode = ^TNode;
TNode = record
Parent: PNode; // ссылка на родительский узел
Childs: array of PNode; // ссылки на дочерние узлы
// данные в ноде
Data: Integer;
// ...
end;

Процедура создания узла дерева в этом случае может быть такой:


function CreateNode(Parent: PNode; Data: Integer): PNode;
begin
New(Result);
Result^.Parent := Parent;
Result^.Data := Data;
end;

Ну и процедура перебора всех дочерних узлов:


procedure IterateChilds(Parent: PNode);
var
i: Integer;
Child: PNode;
begin
for i := Low(Parent^.Childs) to High(Parent^.Childs) do
begin
Child := Parent^.Childs[i];
// работаем с дочерним узлом:
Child^.Data := 1;
// перебираем дочерние рекурсивно:
IterateChilds(Child);
end;
end;

Думаю, приведённого кода достаточно, чтобы понять, о чём идёт речь.


 


Теперь попробуем сделать что-то подобное на стороне сервера.


Интерпретируемый язык PL/SQL, используемый в СУБД Oracle, очень мощное средство в умелых руках. Однако он имеет ряд неприятных ограничений. Например в PL/SQL нет указателей, а потому и нельзя ссылаться на типы данных, которые ещё не объявлены (или объявлены по коду ниже). Поэтому, если написать так:


  type t_childs is table of t_node index by pls_integer;
type t_node is record (
--parent pointer?
childs t_childs,
data integer
);

то получим ошибку при компиляции. Да и не понятно, как сослаться на родительскую ноду?


Столкнувшись с такой проблемой, я уж было хотел решить поставленную задачу с использованием объектов. Но объект в Oracle – это тип SQL, а логику обработки данных надо реализовывать в PL/SQL, а отсюда есть некоторые неприятные моменты. Например, не все типы данных PL/SQL можно использовать в SQL. Да и работа с объектами  происходит медленнее, чем с PL/SQL массивами (коллекциями).


Думал-думал я, как же можно решить задачу без указателей. А потом вдруг вспомнил, что указатель – это всего лишь число, указывающее на конкретный адрес памяти. Если все узлы дерева хранить в массиве, то адрес узла (указатель на узел) можно заменить простым числом – индексом из массива.


Таким образом, структуру данных на PL/SQL можно описать так:


  type t_childs is table of pls_integer index by pls_integer;
type t_node is record (
self_idx pls_integer, -- индекс из таблицы g_nodes, указывает на себя
parent_idx pls_integer, -- индекс из таблицы g_nodes, указывает на родительский узел
pchild_idx pls_integer, -- индекс из таблицы child_idxs родительского узла
child_idxs t_childs, -- набор индексов из таблицы g_nodes, указывающих на дочерние узлы
-- полезные данные:
some_data pls_integer,
-- ..
);
type t_nodes is table of t_node index by pls_integer;
g_nodes t_nodes; -- хранилище узлов дерева
g_nodes_seq pls_integer; -- счётчик узлов
p_root_node pls_integer; -- указатель на корневой узел

Здесь стоит обратить внимание на:



  • g_nodes – это коллекция узлов, объявленная как index by pls_integer, это означает, что g_nodes отдельно инициализировать не нужно.

  • g_nodes_seq – это счётчик узлов, сохранённых в g_nodes, по большому счёту можно обойтись и без него, но он нужен для удобства.

  • p_root_node – индекс, по которому будет хранится корень дерева.

Теперь для построения дерева, нам понадобятся следующие функции:


function get_next_seq return pls_integer is
begin
g_nodes_seq := nvl(g_pc_nodes_seq, 0) + 1;
return g_nodes_seq;
end;

function create_node(parent_idx_ in pls_integer, pchild_idx_ in pls_integer, data_ in pls_integer) return pls_integer
is
p_node pls_integer;
begin
p_node := get_next_seq;

g_nodes(p_node).self_idx := p_node;
g_nodes(p_node).parent_idx := parent_idx_;
g_nodes(p_node).pchild_idx := pchild_idx_;
if pchild_idx_ is not null then
--if g_nodes(parent_idx_).child_idxs.exists(pchild_idx_) then
-- raise...
--end if;
g_nodes(parent_idx_).child_idx(pchild_idx_) := p_node;
end if;
g_nodes(p_node).data := data_;

return p_node;
end;

function create_root(data_ in pls_integer) return pls_integer is
begin
p_root_node := create_node(null, null, data_);
return p_root_node;
end;

Думаю, тут всё понятно: дерево начинаем строить с корня (create_root), затем создаём узлы (create_node).


Итерация дерева делается так:


procedure iterate_tree(p_node in pls_integer)
is
i pls_integer;
p_child pls_integer;
begin
-- goto first child
i := g_nodes(p_node).child_idxs.first;
while i is not null
loop
p_child := g_nodes(p_node).child_idxs(i);
-- do something
g_nodes(p_child).data := 1;
-- iterate childs
iterate_tree(p_child);
-- goto next child
i := g_nodes(p_node).child_idxs.next(i);
end loop;
end;

Ну, в общем, примерно так. Немного громоздко получилось, но работает и работает достаточно быстро.


Если навигация “вверх” от узла не требуется, то можно упростить описание структуры t_node.

7 коммент.:

Юрий комментирует...

Для чего такой гемор...?
Не проще, в процессе обработки, сохранять данные во временную таблицу #TEMP(ID, ParID, ...). И на сервере проще (у тогоже оракла есть SQL для бега по деревьям) и на клиенте (если использовать гриды типа EhLib или DevEx они сами деревья строят)

Николай Зверев комментирует...

Проще-то оно проще. Только вот кэширование иерархической структуры в оперативной памяти для последующей обработки повышает скорость обработки данных на 1-2 порядка (это зависит от объёма обрабатываемых данных, чем больше данных - тем заметнее разница).

Тут фокус в том, что вставки в таблицы, да и вообще SQL операторы работают медленнее, чем вся манипуляция с данными в оперативной памяти.

Николай Зверев комментирует...

Наверное, всё-таки, надо живой пример... я подумаю над примером (не хочется брать пример из коммерческого проекта). Тогда будет понятно, что загружать данные на клиент для обработки - крайне расточительно...

Когда я писал про прирост производительности на 1-2 порядка -- я делал тесты с относительно небольшими объёмами данных (отрабатывало за 22 секунды против ~25 минут).

Сейчас я получил результат по всем данным.
Вот конкретные цифры:
- дерево строится по 80666 записям одной таблицы
- дальше запускается цикл (на сейчас - 65 итераций), в каждой итерации цикла строится второе дерево (тут уже записей может быть меньше, но с узлами второго дерева сохраняются дополнительные данные из других таблиц), и дальше идёт совместная работа с двумя деревьями
- результат работы итерации сохраняется в таблицу (т.к. боюсь, что ОП может просто не хватить и начнёт использоваться файл подкачки), делается commit (чтобы RBS не переполнился), второе дерево убивается -> следующая итерация
- снова прохожу по первому дереву... ну вобщем там ещё три этапа.

После всего этого пользователю доступен результат -- кросс таблица, в БД это 2 411 695 записей, на экране - 37 103 строк и (65*2 + 2=) 132 столбца.

Алгоритм с деревьями в памяти отработал за 113 минут (причём самыми медленными операциями оказались вставки в таблицы; дерево в памяти разворачивается за пару секунд).
А до этого была версия с использованием select и update -- поставив работать на ночь, утром придя на работу я увидел, что оно ещё работает.

Юрий комментирует...

В вашем конкретном случае, ваши конструкции одназначно лучше.
Но если ваш сервак используют не только Вы один, а куча народу и каждый оперирует такими объёмами..
Ведь память не резиновая а диск наверно можно сказать что "резиновый".

Николай Зверев комментирует...

Юрий, такими объёмами оперируют не "куча народу", а один сервер. А вот "куча народу" уже работает с результатами проведённых вычислений, делая запросы к этому результату с дополнительными условиями (чтобы не вытаскивать на клиент все 2.5 млн. записей.... хотя никто им этого не запрещает).

Может быть я не очень понятно излагаю свои мысли, зачем это всё делалось... почитайте литературу по поводу OLAP.

Анонимный комментирует...

а аналитика чем не угадила?
select .. start with .. connect by ..

Николай Зверев комментирует...

start with - штука классная. Но тут фишка в том, что если открыть курсор и, двигаясь по нему, делать подзапросы (ну такая у меня задача, причём подзапросы работают с теми же данными, по которым строится основной селект) - это будет работать очень медленно.
Без подзапросов тоже можно, т.е. с использованием аналитических функций. Только практика показала, что аналитика не на много быстрее работает, т.к. по сути всё сводится к тем же подзапросам, которые отрабатывают за кадром.

А вот если сделать select BULK COLLECT INTO , а потом по этому массиву построить дерево - это работает в разы быстрее.

Отправить комментарий

.

.