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

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

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

Основная идея заключается в использовании материализованного представления, которое хранит связи в более удобном для запросов виде. Для начала добавим пакет objects с функцией get_object_fast_table, которая будет возвращать нам денормализованные связи:

CREATE OR REPLACE PACKAGE objects AS        TYPE object_fast_type     IS RECORD (       object_id object.id%TYPE,       object_name object.name%TYPE,       object_type object.type%TYPE,       parent_id object.id%TYPE,       parent_name object.name%TYPE,       parent_type object.type%TYPE,       nesting_level NUMBER(20)     );    TYPE object_fast_table     IS TABLE OF objects.object_fast_type;      FUNCTION get_object_fast_table     RETURN objects.object_fast_table PIPELINED;      END objects; /  CREATE OR REPLACE PACKAGE BODY objects AS    FUNCTION get_object_fast_table     RETURN objects.object_fast_table PIPELINED IS      CURSOR objs IS       SELECT id         FROM object;          CURSOR parents(obid object.id%TYPE) IS       SELECT         obid  object_id,         obj.name object_name,         obj.type object_type,         par.id parent_id,         par.name parent_name,         par.type parent_type,         level - 1 nesting_level       FROM object par       LEFT JOIN object obj ON obj.id = obid          START WITH par.id = obid  CONNECT BY PRIOR par.parent_id = par.id;    BEGIN      FOR obj IN objs LOOP       FOR object_fast IN parents(obj.id) LOOP         PIPE ROW (object_fast);       END LOOP;     END LOOP;      RETURN;   END get_object_fast_table;  END objects; /  

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

SELECT * FROM TABLE(objects.get_object_fast_table()); 

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

Как можно увидеть, в таблице есть связи каждого объекта со всеми его родителями, а nesting_level — это число уровней до родителя. Чтоб постоянно не дёргать эту функцию, сохраним связи в материализованное представление:

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, objs.* FROM TABLE(objects.get_object_fast_table()) objs;  ALTER TABLE object_fast ADD CONSTRAINT pk_object_fast PRIMARY KEY (id); 

Теперь вышеупомянутые запросы будут выглядеть так:

-- Выбрать все города России 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 раз. Используйте с умом и не забывайте, что полученные данные будут не всегда актуальными. Рекомендую применять этот способ только к редко добавляющимся и удаляющимся объектам. Ну или тогда стоит реализовать оперативное обновление материализованного представления. Нет предела полёту фантазии…