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

    Очень часто за основу архитектуры приложения берётся дерево. Простой пример: есть страны, в странах — области, в областях — города, в городах — организации, в организациях — работники, товары или что-либо ещё. Использование дерева вполне логично и оправдано. Иерархичность такой системы показывает некая абстрактная таблица. Назовём её 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.
    • +10
    • 11.6k
    • 9
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 9

      0
      А планы запросов можно увидеть?
        0
        EXPLAIN PLAN FOR
        SELECT *
          FROM object
            WHERE type = 'city'
            START WITH id = 1 CONNECT BY PRIOR id = parent_id;
        
        ---------------------------------------------------------------------------------------------------
        | Id  | Operation                                | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
        ---------------------------------------------------------------------------------------------------
        |   0 | SELECT STATEMENT                         |        |     5 |   825 |     4  (25)| 00:00:01 |
        |*  1 |  FILTER                                  |        |       |       |            |          |
        |*  2 |   CONNECT BY NO FILTERING WITH START-WITH|        |       |       |            |          |
        |   3 |    TABLE ACCESS FULL                     | OBJECT |     5 |   825 |     3   (0)| 00:00:01 |
        ---------------------------------------------------------------------------------------------------
        
        EXPLAIN PLAN FOR
        SELECT *
          FROM object
            WHERE type = 'country'
            START WITH id = 5 CONNECT BY PRIOR parent_id = id;
        
        --------------------------------------------------------------------------------------------
        | Id  | Operation                      | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
        --------------------------------------------------------------------------------------------
        |   0 | SELECT STATEMENT               |           |     2 |   330 |     7  (29)| 00:00:01 |
        |*  1 |  FILTER                        |           |       |       |            |          |
        |*  2 |   CONNECT BY WITH FILTERING    |           |       |       |            |          |
        |   3 |    TABLE ACCESS BY INDEX ROWID | OBJECT    |     1 |   165 |     2   (0)| 00:00:01 |
        |*  4 |     INDEX UNIQUE SCAN          | PK_OBJECT |     1 |       |     1   (0)| 00:00:01 |
        |   5 |    NESTED LOOPS                |           |     1 |   178 |     3   (0)| 00:00:01 |
        |   6 |     CONNECT BY PUMP            |           |       |       |            |          |
        |   7 |     TABLE ACCESS BY INDEX ROWID| OBJECT    |     1 |   165 |     1   (0)| 00:00:01 |
        |*  8 |      INDEX UNIQUE SCAN         | PK_OBJECT |     1 |       |     0   (0)| 00:00:01 |
        --------------------------------------------------------------------------------------------
        
        EXPLAIN PLAN FOR
        SELECT *
          FROM object_fast
            WHERE parent_id = 1 AND object_type = 'city';
        
        -------------------------------------------------------------------------------------------------------
        | Id  | Operation                      | Name                 | Rows  | Bytes | Cost (%CPU)| Time     |
        -------------------------------------------------------------------------------------------------------
        |   0 | SELECT STATEMENT               |                      |     2 |   660 |     2   (0)| 00:00:01 |
        |*  1 |  MAT_VIEW ACCESS BY INDEX ROWID| OBJECT_FAST          |     2 |   660 |     2   (0)| 00:00:01 |
        |*  2 |   INDEX RANGE SCAN             | OBJECT_FAST_OBJ_TYPE |     6 |       |     1   (0)| 00:00:01 |
        -------------------------------------------------------------------------------------------------------
         
        EXPLAIN PLAN FOR
        SELECT *
          FROM object_fast
            WHERE object_id = 5 AND parent_type = 'country';
        
        -----------------------------------------------------------------------------------------------------
        | Id  | Operation                      | Name               | Rows  | Bytes | Cost (%CPU)| Time     |
        -----------------------------------------------------------------------------------------------------
        |   0 | SELECT STATEMENT               |                    |     1 |   330 |     2   (0)| 00:00:01 |
        |*  1 |  MAT_VIEW ACCESS BY INDEX ROWID| OBJECT_FAST        |     1 |   330 |     2   (0)| 00:00:01 |
        |*  2 |   INDEX RANGE SCAN             | OBJECT_FAST_OBJ_ID |     3 |       |     1   (0)| 00:00:01 |
        -----------------------------------------------------------------------------------------------------
        
          0
          Но это для этого примера. Тут простое дерево. Обычно деревья более мудрёные… Таблицы нормализованные, данные разбиты на несколько таблиц… Поэтому и эффект такой оптимизации чувствуется ещё сильней.
          0
          Насколько я помню, то, что у вас называется object_fast_table, обычно называется таблицей транзитивных замыканий. В принципе, достаточно удобный способ работы с древовидными структурами в SQL. Если CONNECT BY PRIOR или аналоги в диалекте SQL не поддерживается, то без такой или подобной структуры трудно обойтись.
            –1
            пакет-то зачем создавать?
            Мвьюху можно было создать на основе простого запроса:
            select 
               id
              ,type
              ,name
              ,parent_id
              ,prior type parent_type
              ,prior name parent_name
              ,level nesting_level
            from object o
            start with parent_id is null
            connect by PRIOR id = parent_id;
            
              0
              а, все поглядел внимательнее и заметил. Это чуток по другому надо тогда через connect_by_root
                +1
                Забавный минус :)
                Удаляй пакет и делаю мвью просто по запросу:
                         select 
                            connect_by_root id   as object_id
                           ,connect_by_root name as object_name
                           ,connect_by_root type as object_type
                           ,id                   as parent_id
                           ,name                 as parent_name
                           ,type                 as parent_type
                           ,level-1              as nesting_level
                         from object o
                         connect by PRIOR parent_id = id
                         order by id, nesting_level
                
                  0
                  Удаляй пакет и делаю делай мвью просто по запросу:
                    0
                    Большое спасибо! Статья была переработана.

                Only users with full accounts can post comments. Log in, please.