Как я могу ускорить запросы, которые ищут корневой узел транзитивного замыкания?

Question

У меня есть историческая транзитивная таблица замыканий, которая представляет дерево.

create table TRANSITIVE_CLOSURE
  (
    CHILD_NODE_ID number not null enable,
    ANCESTOR_NODE_ID number not null enable,
    DISTANCE number not null enable,
    FROM_DATE date not null enable,
    TO_DATE date not null enable,
    constraint TRANSITIVE_CLOSURE_PK unique (CHILD_NODE_ID, ANCESTOR_NODE_ID, DISTANCE, FROM_DATE, TO_DATE)
  );

Вот некоторые примеры данных:

CHILD_NODE_ID | ANCESTOR_NODE_ID | DISTANCE 
--------------------------------------------
1             | 1                | 0
2             | 1                | 1
2             | 2                | 0
3             | 1                | 2
3             | 2                | 1
3             | 3                | 0

К сожалению, мой текущий запрос на поиск корневого узла вызывает полное сканирование таблицы:

select *
from transitive_closure tc
where 
  distance = 0
  and not exists (
  select null
  from transitive_closure tci
  where tc.child_node_id = tci.child_node_id
    and tci.distance <> 0
);

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

Есть ли лучший способ найти корневой узел транзитивного замыкания? Я хотел бы переписать весь наш старый унаследованный код, но я не могу ... поэтому мне нужно как-то составить список смежности. Получить все, кроме корневого узла, легко, так есть ли лучший способ? Думаю ли я об этой проблеме неправильно?

План запроса для таблицы с 800 тыс. Строк.

OPERATION                                  OBJECT_NAME        OPTIONS         COST 
SELECT STATEMENT                                                              2301 
  HASH JOIN                                                   RIGHT ANTI      2301 
    Access Predicates
      TC.CHILD_NODE_ID=TCI.CHILD_NODE_ID 
    TABLE ACCESS                           TRANSITIVE_CLOSURE FULL            961 
      Filter Predicates 
        TCI.DISTANCE = 1 
    TABLE ACCESS                           TRANSITIVE_CLOSURE FULL            962 
      Filter Predicates 
        DISTANCE=0

Answer 1

Сколько времени занимает выполнение запроса и как долго вы хотите его занять? (Обычно вы не хотите использовать стоимость для настройки. Мало кто знает, что на самом деле означает стоимость плана объяснения.)

На моем медленном рабочем столе запрос занимал только 1,5 секунды для строк 800К. И затем через 0,5 секунды после того, как данные были в памяти. Вы получаете что-то значительно хуже, или этот запрос будет выполняться очень часто?

Я не знаю, как выглядят ваши данные, но я предполагаю, что полное сканирование таблицы всегда будет лучшим для этого запроса. Предполагая, что ваши иерархические данные является относительно мелким, то есть есть много расстояний 0 и 1, но очень мало расстояний 100, самый важный столбец не будет очень отчетливым. Это означает что любая из записей индекса для расстояния будет указывать на большое количество блоков. Будет намного дешевле читать всю таблицу одновременно, используя многоблочные чтения. чем читать большое количество по одному блоку за раз.

Кроме того, что вы подразумеваете под историческим? Можете ли вы сохранить результаты этого запроса в материализованном представлении?

Другая возможная идея - использовать аналитические функции. Это заменяет второе сканирование таблицы сортировкой. Такой подход обычно быстрее, но для меня это запрос на самом деле занимает больше времени, 5,5 секунды вместо 1,5. Но, возможно, это будет лучше в вашей среде.

select * from
(
    select
        max(case when distance <> 0 then 1 else 0 end)
            over (partition by child_node_id) has_non_zero_distance
        ,transitive_closure.*
    from transitive_closure
)
where distance = 0
    and has_non_zero_distance = 0;

Answer 2

Добавьте ОДИН корневой узел, с которого произошли все ваши текущие корневые узлы.Тогда вы просто запросите детей вашего единственного корня.Проблема решена.

Answer 3

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