鄰接表模型與嵌套集

我偶然發現了一篇描述用於儲存分層數據的嵌套集模型的文章，並且對所謂的性能提升非常感興趣。

在我們的數據庫中實現此功能後，我發現鄰接列表模型的性能要好得多。儘管我讀過的文章和幾篇 SA 文章（一、二）表明任何樹遍歷都應該受益，但我的測試證明了相反的情況。

我錯過了什麼嗎？

下表中大約有 110 萬個條目：

SQL> show table tax_nodes;
TAX_ID                          INTEGER Not Null
PARENT_TAX_ID                   INTEGER Nullable
RANK                            VARCHAR(50) Nullable
DIVISION_ID                     INTEGER Nullable
TREE_RIGHT                      INTEGER Nullable
TREE_LEFT                       INTEGER Nullable
CONSTRAINT INTEG_202:
 Primary key (TAX_ID)

獲取父母的鄰接列表查詢

with recursive lineage as 
(select tax_id, parent_tax_id 
from tax_nodes 
where tax_id = 365612
union ALL 
select tax_id, parent_tax_id 
from tax_nodes t 
join lineage l on l.parent_tax_id = t.tax_id
) 
select l.tax_id
from lineage l

嵌套集查詢以獲取父母

select
 p2.tax_id from tax_nodes as p1,
 tax_nodes as p2
where
   p1.tree_left between p2.tree_left and p2.tree_right
   and p1.tax_id = 365612

結果

365612 336487 10260 10241 10240 35237 10239 1  //1 is the root

為什麼 Adjecency List 的表現更好，儘管大多數資源表明並非如此？

順便說一句，我正在執行 Firebird 2.5 超級伺服器。

更新

在@MarkRotteveel 的提示下，我查看了執行計劃，我懷疑這NATURAL是罪魁禍首。現在的問題是，我該如何擺脫它？

鄰接表執行計劃

PLAN (LINEAGE TAX_NODES INDEX (RDB$PRIMARY108))
PLAN (LINEAGE T INDEX (RDB$PRIMARY108))

嵌套集執行計劃

PLAN JOIN (P1 INDEX (RDB$PRIMARY108), P2 NATURAL)

您的鄰接列表範例的執行計劃表明它能夠將主鍵索引 ( RDB$PRIMARY108) 用於UNION. 這非常有效，主要是因為您從單個值開始，然後遞歸查找其後代（這可能只是整個記錄集的一小部分）。

對於嵌套集執行計劃，它不能使用索引，因為它必須掃描所有記錄以查找 和 的p2.tree_left值p2.tree_right。它只能使用主鍵索引進行查找p1.tax_id = 365612。

如果tax_nodes.tree_left為 . 添加降序索引和tax_nodes.tree_right. 您可能需要交換升序/降序，因為我最初通常會做錯，即使我通常會做錯。但是，您可能還需要更改查詢條件，以便優化器為tree_leftand選擇索引tree_right：

p2.tree_left <= p1.tree_left AND p2.tree_right >= p1.tree_left

引用自：https://dba.stackexchange.com/questions/69983