關閉表根節點用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