Денормализация деревьев

Очень часто за основу архитектуры приложения берётся дерево. Простой пример: есть страны, в странах — области, в областях — города, в городах — организации, в организациях — работники, товары или что-либо ещё. Использование дерева вполне логично и оправдано. Иерархичность такой системы показывает некая абстрактная таблица. Назовём её object:

CREATE TABLE object (
  id NUMBER(11),
  parent_id NUMBER(11),
  type VARCHAR2(16) NOT NULL,
  name VARCHAR2(255) NOT NULL,
  CONSTRAINT pk_object PRIMARY KEY (id),
  CONSTRAINT fk_object_parent FOREIGN KEY (parent_id) REFERENCES object (id) ON DELETE CASCADE ENABLE
);

Наполним её какими-нибудь данными:

id  |  parent_id  |  type     |  name
------------------------------------------------------
1   |  NULL       |  country  |  Россия
2   |  1          |  region   |  Московская область
3   |  1          |  region   |  Новосибирская область
4   |  2          |  city     |  Москва
5   |  3          |  city     |  Новосибирск

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

-- Выбрать все города России
SELECT *
  FROM object
    WHERE type = 'city'
    START WITH id = 1 CONNECT BY PRIOR id = parent_id;

-- Выбрать страну, в которой находится Новосибирск
SELECT *
  FROM object
    WHERE type = 'country'
    START WITH id = 5 CONNECT BY PRIOR parent_id = id;

Однако проблемы появляются, когда записей в таблице становится на столько много, что любой рекурсивный запрос выполняется минуты две, а то и больше. Менять всю архитектуру как-то поздновато… Тут-то нам на помощь и приходит денормализация дерева. В этой статье я расскажу об одном из способов такой денормализации.

Основная идея заключается в использовании материализованного представления, которое хранит связи в более удобном для запросов виде:

CREATE MATERIALIZED VIEW object_fast
  REFRESH COMPLETE ON DEMAND
  START WITH trunc(sysdate)+4/24 NEXT (trunc(sysdate)+1)+4/24 AS
  SELECT rownum id, tree.* FROM (
  SELECT 
     CONNECT_BY_ROOT id object_id,
     CONNECT_BY_ROOT name object_name,
     CONNECT_BY_ROOT type object_type,
     id parent_id,
     name parent_name,
     type parent_type,
     level-1 nesting_level
   FROM object
   CONNECT BY PRIOR parent_id = id
   ORDER BY object_id, nesting_level
) tree;;

ALTER TABLE object_fast ADD CONSTRAINT pk_object_fast PRIMARY KEY (id);

Теперь мы имеем денормализованную таблицу, которую можем использовать в своих запросах.

id | object_id | object_name           | object_type | parent_id | parent_name           | parent_type | nesting_level
----------------------------------------------------------------------------------------------------------------------
1  | 1         | Россия                | country     | 1         | Россия                | country     | 0
2  | 2         | Московская область    | region      | 2         | Московская область    | region      | 0
3  | 2         | Московская область    | region      | 1         | Россия                | country     | 1
4  | 3         | Новосибирская область | region      | 3         | Новосибирская область | region      | 0
5  | 3         | Новосибирская область | region      | 1         | Россия                | country     | 1
6  | 4         | Москва                | city        | 4         | Москва                | city        | 0
7  | 4         | Москва                | city        | 2         | Московская область    | region      | 1
8  | 4         | Москва                | city        | 1         | Россия                | country     | 2
9  | 5         | Новосибирск           | city        | 5         | Новосибирск           | city        | 0
10 | 5         | Новосибирск           | city        | 3         | Новосибирская область | region      | 1
11 | 5         | Новосибирск           | city        | 1         | Россия                | country     | 2

Как можно увидеть, в таблице есть связи каждого объекта со всеми его родителями, а nesting_level — это число уровней до родителя. Обратите внимание, я добавил поле id, которое не обязательно, но вполне разумно, если вы планируете получать доступ к данным через ORM. Теперь вышеупомянутые запросы будут выглядеть так:

-- Выбрать все города России
SELECT *
  FROM object_fast
    WHERE parent_id = 1 AND object_type = 'city';

-- Выбрать страну, в которой находится Новосибирск
SELECT *
  FROM object_fast
    WHERE object_id = 5 AND parent_type = 'country';

Ну и, по желанию, можно добавить индексы:

CREATE INDEX object_fast_obj_id ON object_fast (object_id);
CREATE INDEX object_fast_par_id ON object_fast (parent_id);
CREATE INDEX object_fast_obj_type ON object_fast (object_type);
CREATE INDEX object_fast_par_type ON object_fast (parent_type);
CREATE INDEX object_fast_nesting ON object_fast (nesting_level);

Вот и всё. От себя скажу, что на нашем проекте этот способ дал прирост скорости запросов примерно в 60 раз. Используйте с умом и не забывайте, что полученные данные будут не всегда актуальными. Рекомендую применять этот способ только к редко добавляющимся и удаляющимся объектам. Ну или тогда стоит реализовать оперативное обновление материализованного представления. Нет предела полёту фантазии…

update: Статья была подправлена и способ существенно упрощен благодаря комментарию xtender.