如何加速查找传递闭包根节点的查询？

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
);

表面上看起来这并不是很贵，但当我接近100万行时，这个特定的查询开始变得棘手起来...特别是当它是一个抓取遗留支持的邻接树的视图的一部分时。

有没有更好的方法来查找传递闭包的根节点？我想重新编写我们所有旧的遗留代码，但我不能...所以我需要以某种方式建立邻接表。获取除根节点之外的所有内容很容易，那么有没有更好的方法？我的思考方式是否有问题？

在具有800k行的表上的查询计划。

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

- Jon Bristow

---

你认为使用 tci.distance = tc.distance + 1 会有帮助吗？ - Jordão

那个和tci.distance <> tc.distance对查询计划没有影响（其成本为3178）。 - Jon Bristow

这使我们降到了2363，这是一个改进...但当与100万行表连接时，仍然会很恶劣。它仍在进行全表扫描。 - Jon Bristow

查询计划可能会有所帮助。您是否考虑过仅在child_node_id上创建较小的索引？分区是否是一个选项 - 您可以根据距离进行分区，这可能有助于外部查询。只是一些想法。 - Jeffrey Kemp

Answer 1

查询需要执行多长时间，你希望它执行多长时间？（通常不建议使用成本进行调优。很少有人知道解释计划成本的真正含义。）

在我较慢的桌面上，查询800K行只需1.5秒。当数据在内存中时，仅需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;

- Jon Heller

Answer 2

你可以尝试在 distance 和 child_node_id 上添加索引，或者改变现有唯一索引中这些列的顺序吗？我认为这样外部查询应该可以通过距离索引访问表格，而内部查询仅需要访问索引。

- Jörn Horstmann

Answer 3

添加一个根节点，所有当前的根节点都是从它派生出来的。然后你只需要查询这个根节点的子节点即可。问题解决。

- l33t