sql - 闭表 Root Nodes 10s 百万节点查询性能

Question

我目前有一个用于分层数据的闭包表，它有 500 万个节点，这导致闭包表中有大约 7500 万行。由于闭包表的大小，使用 Sqlite 我的查询时间呈指数增长。

CREATE TABLE `Closure` (`Ancestor` INTEGER NOT NULL ,`Descendant` INTEGER NOT NULL ,`Depth` INTEGER, PRIMARY KEY (`Ancestor`,`Descendant`) )
CREATE INDEX `Closure_AncestorDescendant` ON `Closure` (`Ancestor` ASC, `Descendant` ASC);
CREATE INDEX `Closure_DescendantAncestor` ON `Closure` (`Descendant` ASC, `Ancestor` ASC);
CREATE TABLE `Nodes` (`Node` INTEGER PRIMARY KEY NOT NULL, `Root` BOOLEAN NOT NULL, `Descendants` INTEGER NOT NULL);

即使只有大约 5 或 6 个节点满足查询，我查找根节点的查询需要大约 20 分钟的时间。

SELECT `Closure`.`Ancestor` FROM `Closure` 
LEFT OUTER JOIN `Closure` AS `Anc` ON `Anc`.`Descendant` = `Closure`.`Descendant` 
AND `Anc`.`Ancestor` <> `Closure`.`Ancestor` WHERE `Anc`.`Ancestor` IS NULL;

20 分钟太长了，所以现在我正在存储一个 bool 值，如果节点是根节点并修改 Nodes . Root移动节点时的列.. 我对重复数据并不完全满意，但我的查询时间现在每个查询的个位数毫秒。

我也有很多查询需要知道给定节点有多少后代(主要是如果后代 > 1 来知道这个对象是否可以在树 View 中虚拟化/扩展)。我曾经在每次需要时都查询它，但是在像我这样的巨大数据库中，即使使用索引，查询似乎也需要很长时间(超过 1 秒)，所以我也将它们减少到 Nodes . Descendants每次移动节点时我也会更新该列。不幸的是，这是我想避免的另一个数据重复。

我曾经使用的查询如下所示。如果有人能解释如何提高性能(考虑到我已经有一个以 Ancestor 开头的索引)，我将不胜感激。

SELECT COUNT(*) FROM `Closure` WHERE `Ancestor`=@Node

Answer 1

您正在开发的 SQLite 版本是否支持外键？如果是这样，您的闭包表设计应该有一个 FK 引用您使用闭包表支持的层次结构表。在 TSQL 中:

constraint fk_a FOREIGN KEY (ancestor) REFERENCES <hierarchy_tablename> (nodeid)
constraint fk_d FOREIGN KEY (descendant) REFERENCES <hierarchy_tablename> (nodeid)

抱歉，您必须查找相关的 SQLite 语法。

由于您已经在维护一个深度域，即后代与其祖先之间的距离，您可以利用它来判断给定节点是否有子节点。

select top 1 'EXPANDABLE' as whatever
from closure C
where exists (select ancestor from closure where depth > 0 and ancestor = C.ancestor)
and ancestor = @Node

无论关闭表的大小如何，这都应该很快恢复。如果你从中得到一个空集，那么你的给定节点就不能再扩展了，因为它没有子节点。一旦 Exists 找到一个符合您的条件的实例，它就会返回 true，并且您只取前 1 个实例，因此您不会为传递的 @Node 的闭包表中的每一行都返回一行。

至于提高寻根性能，请尝试以下操作。这是我用来寻找根的方法，但我的闭包表只有 ~200,000 行。我比较了为每个生成的计划，并且您的代码使用了哈希，这可能会由于设备上的处理器要求而影响性能(我在这里假设 SQLite 适用于 iPhone/iPad 或某种类型的小型设备发行版)。下面在其计划中使用较少的处理能力和更多的索引读取，并利用层次结构与闭包表的关系。我不能确定它会改善你的表现问题，但值得一试。

select a.node_name, a.node_id
from test.hier a left outer join 
                 (select coo.descendant /* coo = CHILD OF OTHER */
                  from test.closure_tree coo right outer join test.closure_tree ro
                        on coo.ancestor <> ro.descendant /* ignore its self reference */
                        and coo.descendant = ro.descendant /* belongs to another node besides itself */)lo 
    on a.node_id = lo.descendant
where lo.descendant is null