В стиле SQL - 6 (иерархии)

[egorius]

Иерархии традиционно вызывают много вопросов. Обычно довольно простых, например, связанных с порядком выполнения частей запроса, особенно когда иерархия строится над несколькими таблицами. Но встречаются задачи и поинтереснее.

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

      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? Добавятся ровно три строчки, и это никак не скажется на производительности.

Вопрос со звездочкой состоит в том, что в ряде случаев надо получить ровно одно значение адреса, например, чтобы вывести его на форму. Очевидно, что один раз подняться по иерархии проще и быстрее, чем обойти все дерево. Но ведь поддерживать два способа сделать одно и то же — нехорошо?