如何在分層數據上使用兩個連接的 CTE 表達式來改善較差的性能？

我有一個分層數據表，我想在其中選擇條目，1）僅包含作為給定父級後代的匹配項，2）返回匹配條目的完整分層路徑。

我正在使用兩個 CTE 執行此操作：一個從指定的父級獲取所有遞歸子級，另一個選擇匹配項並獲取這些匹配項的所有遞歸父級。然後，主查詢將這兩個 CTE 連接並分組。

但是，性能並不好。單獨執行任一 CTE（即僅獲取後代實體或僅獲取路徑層次結構）會立即返回結果，但兩個 CTE 一起（在具有數百萬個條目的表上執行）可能需要幾分鐘到幾小時，具體取決於字元串匹配的數量，甚至是單個匹配。在找到所有條目之前，它也不會返回第一個找到的條目。

是否可以提高以下查詢的性能，或者至少可以讓它立即開始返回找到的結果？

該表具有以下結構：

CREATE TABLE [Files]
(  [fileId]       INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL
,  [name]         TEXT    NOT NULL
,  [parentFileId] INTEGER NULL
,  UNIQUE
  (  [name]
  ,  [parentFileId]
  )
);
CREATE INDEX [Files_parentFileId] ON [Files]([parentFileId]);
CREATE INDEX [Files_name]         ON [Files]([name]);

我能夠產生的最快查詢是：

-- The [@Context] CTE lists all the fileIds that are descendants
--  of the input @rootFileId. The query should only return
--  matches that are in this list of fileIds
WITH           [@Context]
AS             (
  -- Starting with the ID of the root entry..
  SELECT      @rootFileId           [fileId]
  UNION
  -- ..build up all the IDs of the children
  SELECT      [Files].[fileId]
  FROM        [Files]
  JOIN        [@Context]
     ON       [Files].[parentFileId] = [@Context].[fileId]
              )
-- The [@FilePath] CTE selects each entry that matches the given
--  input @name and all entries that are its parents
,              [@FilePath]
AS             (
  -- Starting with the entries that match the given @name..
  SELECT      -1                    [depth]
  ,           [Files].[fileId]
  ,           [Files].[parentFileId]
  ,           [Files].[name]
  FROM        [Files]
  WHERE       [name]                LIKE @name
  UNION
  -- ..build up all the IDs of the parents
  SELECT      [@FilePath].[depth] - 1
  ,           [@FilePath].[fileId]  -- for grouping entries by the matched entry's id
  ,           [Files].[parentFileId]
  ,           [Files].[name]
  FROM        [Files]
  JOIN        [@FilePath]
     ON       [Files].[fileId]      = [@FilePath].[parentFileId]
              )
-- Group all the parent entries into one column with each found entry
--  and exclude any entry that wasn't on the [@Context] list
SELECT         [@FilePath].[fileId]
,              [@FilePath].[name]
, GROUP_CONCAT([@FilePath].[parentFileId]) [pathFileId]
, GROUP_CONCAT([@FilePath].[name], '\')    [pathname]
FROM           [@FilePath]
JOIN           [@Context]
  ON          [@Context].[fileId]   = [@FilePath].[fileId]
GROUP BY       [@FilePath].[fileId]
ORDER BY       [@FilePath].[depth];

歡迎來到論壇，這是一個很好的第一個問題，包含 DDL，可以輕鬆重現場景。對於以後的文章，還包括一些可以使用的範例數據。您甚至可以使用DB<>Fiddle或類似站點。我在Your Fiddle添加了您的問題的略微修改版本。該站點不允許我在樹中添加超過 90000 個節點，但至少在幾秒鐘內會返回該數據量的答案。

我刪除了帶引號的標識符並稍微更改了它們。避免使用引號有幾個原因，它們使程式碼更難閱讀，並且區分大小寫。由於 SQL 不區分大小寫，因此我也避免使用駝峰式大小寫。我也改變了你的索引。足夠了，這裡是解決方案的演練：

CREATE TABLE Files
(  file_id       INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL
,  file_name         TEXT    NOT NULL
,  parent_file_id INTEGER NULL
,  UNIQUE
  (  file_name
  ,  parent_file_id
  )
);

CREATE UNIQUE INDEX files_ix1 ON Files (parent_file_id, file_id, file_name);

第一步，獲取某個節點的後代。與您在查詢中所做的類似：

with rec (depth, file_id, parent_file_id, file_name) as ( 
   select 0, file_id, parent_file_id, file_name 
   from files where file_id = 57
   union all
   select depth+1, f.file_id, r.file_id, f.file_name
   from files f
   join rec r
       on f.parent_file_id = r.file_id
)

其次，從上一個問題中獲取根的祖先。我添加了一個深度屬性，可以輕鬆辨識此節點：

), root_path (depth, file_id, parent_file_id, file_name) as (
   select depth, file_id, parent_file_id, file_name 
   from rec where depth = 0
   union all
   select r.depth-1, f.file_id, f.parent_file_id, f.file_name
   from root_path r
   join files f
       on r.parent_file_id = f.file_id
)

由於您遍歷了整個樹，然後您必須加入，因此您的對方可能會為性能問題負責。

第三步，我們將祖先與後代結合起來。我已經使用聯合來擺脫兩者中存在的節點，您可以通過過濾其中一條腿並使用聯合全部來提高效率：

tree (depth, file_id, parent_file_id, file_name) as (        
   select depth, file_id, parent_file_id, file_name from root_path
   union
   select depth, file_id, parent_file_id, file_name from rec
)

現在樹包含所有相關節點，因此我們可以遞歸地構造樹的傳遞閉包：

closure (file_id, parent_file_id, file_name, file_path) as (
   select file_id, parent_file_id, file_name, '/'||file_name 
   from tree
   where depth = (select min(depth) from tree)
   union all
   select t.file_id, t.parent_file_id, t.file_name
        , c.file_path || '/' || t.file_name 
   from tree t
   join closure c
       on t.parent_file_id = c.file_id
)
select * from closure

如果在樹上遍歷和聚合資訊是您經常做的事情，您可以考慮使用某種增量評估系統 (IES)。這個想法是上面的遞歸部分已經在你需要時預先計算好了。基本上有 3 個不同的版本，你可以用Google搜尋更多資訊

1. Nested Sets，雖然不是發明者，但 Joe Celko 寫了很多關於它的文章和書籍。基本思想是每個節點都有一個上限和下限，任何包含另一個節點的節點都是該節點的祖先。該方法的主要批評是樹的小變化可能會很昂貴，因為它可能導致樹的大部分重新編號。
2. 物化路徑，您基本上將祖先部分儲存在每個節點中，並使用 like 謂詞來查找祖先/後代。明智地選擇標記分隔符，否則您可能會得到錯誤的結果。
3. 使用單獨的祖先表，通常稱為傳遞閉包 (TC) 表。您可以使用樹表上的觸發器來維護祖先的表。我已經將它用於數百萬行沒有問題的樹。您需要注意，祖先表通常是樹表基數的 5-10 倍。

編輯：FWIW 我嘗試對我的本地 Db2 11.5.5 進行 900 萬行的查詢。完全相同的查詢在約 20 秒內返回 29529 行。如果我通過在樹的下方選擇一個開始來減少結果，我會得到：

file_id = 57      -> 29529 rows, 20 seconds
file_id = 5703    -> 1106 rows,  0.38 seconds
file_id = 57036   -> 132 rows,   0.15 seconds
file_id = 571036  -> 30 rows,    0.08 seconds

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