关闭表根节点用10几百万个节点查询性能

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

我查询发现，有根需要用这么多节点约20分钟，尽管只有约5或6个节点满足查询的节点。

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，以了解此对象是否可以在树视图中虚拟化/扩展）。我以前每次需要时都会询问这个问题，但是在一个巨大的数据库中，就像我甚至用索引查询似乎需要很长时间（超过1秒）一样，所以我也将它们减少到了Nodes。 Descendants列，我每次移动节点时也会更新。不幸的是，这是我想避免的另一个重复数据。

我以前使用的查询如下所示。如果任何人都可以解释如何提高性能（考虑到我已经有一个以祖先为起点的索引），我将不胜感激。

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行。我比较了每个产生的计划，并且你的代码使用了一个Hash，由于设备上的处理器需求（我假设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