В стиле SQL - 6 (иерархии)
Иерархии традиционно вызывают много вопросов. Обычно довольно простых, например, связанных с порядком выполнения частей запроса, особенно когда иерархия строится над несколькими таблицами. Но встречаются задачи и поинтереснее.
Предметная область состоит из сотрудников, каждый из которых работает в некотором отделе. Отделы образуют оргструктуру, то есть иерархию. Некоторым (но не всем) отделам приписан адрес.
1 <-- адрес A / \ 2 3 <-- адрес B / \ 4 5 <-- адрес C
Чтобы найти расположение отдела, у которого нет своего адреса, надо пройтись вверх по иерархии до тех пор, пока не будет обнаружен вышестоящий отдел с адресом.
Например, для картинки выше, адреса отделов должны быть такими:
DEP_ID ADDRESS ------ ------- 1 A 2 A 3 B 4 B 5 C
Задача состоит в написании запроса, который выведет всех сотрудников с указанием их отделов и адресов.
Вот тестовые данные.
create table dep( id number primary key, address varchar2(1000) ); create table dep_hier( parent_id references dep(id), child_id references dep(id) ); create table emp( id number primary key, dep_id number references dep(id) ); insert into dep values(1, 'A'); insert into dep values(2, ''); insert into dep values(3, 'B'); insert into dep values(4, ''); insert into dep values(5, 'C'); insert into dep_hier values(1, 2); insert into dep_hier values(1, 3); insert into dep_hier values(3, 4); insert into dep_hier values(3, 5); insert into emp values(101, 1); insert into emp values(102, 2); insert into emp values(103, 3); insert into emp values(104, 4); insert into emp values(105, 5); commit;
Возможное решение состоит в написании функции, возвращающей адрес указанного отдела (по сути, простой иерархический запрос, поднимающийся вверх по иерархии):
create or replace package hier as function get_address( p_dep_id number ) return varchar2; end; / create or replace package body hier as function get_address( p_dep_id number ) return varchar2 is l_address varchar2(1000); begin select min(dep.address) keep (dense_rank first order by level) into l_address from dep left join dep_hier on dep.id = dep_hier.child_id where dep.address is not null start with dep.id = p_dep_id connect by dep.id = prior dep_hier.parent_id ; return l_address; end; end; /
С такой функцией запрос выглядит тривиально:
select emp.id, emp.dep_id, hier.get_address(emp.dep_id) address from emp order by emp.id;
Есть ли минусы у такого решения? Разумеется, и один из них - производительность.
Дело в том, что функция вызывается каждый раз для каждого сотрудника; следовательно, чем больше сотрудников, тем дольше выполняется запрос. Посмотрим на график:
Красная линия - это то, как наш запрос ведет себя при увеличении числа сотрудников. А зеленая - как мог бы вести, если бы был написан в стиле SQL. Не обманитесь экспоненциальной шкалой: в реальном масштабе разглядеть зеленый график просто не получится.
Разумеется, процедурное решение можно ускорить, добавив волшебное слово result_cache, чтобы функция вызывалась не для каждого сотрудника, а для каждого уникального отдела. Но хорошего результата достичь все равно не получится, потому что неэффективность вылезет при росте иерархии:
Тут уместна аналогия с доступом к таблице по индексу. Для нескольких значений это эффективно, но для всех - катастрофа.
Так каково же «зеленое» решение? Оно состоит в том, чтобы заранее вычислить адреса всех отделов, обойдя дерево иерархии сверху вниз ровно один раз. Удобнее всего использовать для этого ANSI-синтаксис.
with adr(dep_id, address) as ( -- сверху... select dep.id, dep.address from dep where not exists ( -- опредеяем вершину как узел, не имеющий предка select null from dep_hier where dep_hier.child_id = dep.id ) union all -- ...вниз select dep.id, nvl(dep.address, adr.address) -- спускаем адрес сверху, если не указан from adr, dep, dep_hier where dep_hier.parent_id = adr.dep_id and dep.id = dep_hier.child_id ) select emp.id, emp.dep_id, adr.address from emp, adr where adr.dep_id = emp.dep_id order by emp.id;
Есть ли еще минусы у процедурного решения? Да, и это масштабируемость.
Представим себе, что помимо адреса для некоторых отделов аналогичным образом указана и другая информация, например, куратор.
Как изменится процедурное решение для вывода и адреса, и куратора? Очевидно, придется написать еще одну функцию, get_curator, во всем аналогичную get_address, кроме названия поля. Дублируем код, умножаем время на два и получаем минус в карму.
Как изменится решение в стиле SQL? Добавятся ровно три строчки, и это никак не скажется на производительности.
Вопрос со звездочкой состоит в том, что в ряде случаев надо получить ровно одно значение адреса, например, чтобы вывести его на форму. Очевидно, что один раз подняться по иерархии проще и быстрее, чем обойти все дерево. Но ведь поддерживать два способа сделать одно и то же - нехорошо?