蒼時弦也
蒼時弦也
資深軟體工程師
發表於

在 PostgreSQL 中使用遞迴查詢來找尋父節點

老爸的公司在去年設計了一個紅利積點的消費回饋機制，裡面採用了樹狀的結構。用來改善傳統多層次傳銷造成的下線提供好處給上線，而下線卻需要去找更多下線來獲取回饋的異常機制。

不過這個設計有一個問題，就是他比傳統的樹成長的速度還會再更快些。也就表示在 Rails 裡面現有用來解決樹狀結構的一些套件並不適合使用。

建構一個樹狀結構，一般在資料庫中會這樣設計。

idnameparent_id
1Jimmy
2John1
3Alice1
4Alex2

在指查詢一代的情況下，可以直接使用 Rails 的 belongs_to 和 has_many 來解決。

但是如果想知道 Alex 的父代有哪些，就必須先找到 John 再繼續往回找。

1def ancestors(user, path = [])
2  return path if user.parent.nil?
3  path << user.parent
4  ancestors(user.parent, path)
5end
6
7ancestors(User.find_by(name: 'Alex'))
8# => [User<@name="John">, User<@name="Jimmy">]

很明顯的，這會執行 N 次的 SQL 查詢，稍微有經驗就會注意到這樣是非常沒有效率的。

於是，就會出現幾種常見的解法。

  • Adjacency List
  • Path Enumeration
  • Nested Sets
  • Closure Table

關於上述這幾種解法的說明，可以參考 Percona 這這份簡報。

Closure Table

在 Rails 中，速度最快的是 Closure table 這個解法，可以使用 closure_tree gem 來實作，不過在文章一開始描述的情境，卻是一個噩夢。

  • 每個交易是一個節點
  • 回饋會往上追溯（但不往下）
  • 節點的世代增長會很快
  • 樹可以無限成長

而 Closure table 是空間換時間的方法，所以假設當發展到 300,00 代的時候，因為 Closure Tree 會把每一個節點跟所有父代做一次關聯來加速查詢，所以在第 300,00 代基本上是需要插入 300,00 - 1 條紀錄的。

所以，這個解法會在後期出現效能貧頸。

Path Enumeration

在 PostgreSQL 內，有一個叫做 ltree 的 Extension 可以使用。

因為紅利回饋的往回追溯會有極限制，畢竟是基於交易的金額來計算可用的回饋，所以受到影響的父代是有限的。

在 Path Enumeration 的特性中，是利用建立「路徑」來記錄的。

idnamepath
1Jimmy
2JohnJimmy
3AliceJimmy
4AlexJimmy.John

也就是說，當 Alex 想知道有多少父代只需要從 path 這個 ltree 類型的欄位下查詢就可以了！

這個解法看起來一切完美，但是卻有一個問題。

欄位的內容有上限，也就是說當發展到一定的世代到達極限後，就無法再繼續下去。

這很適合用來儲存多層的文章分類，但是卻不適合無限成長的樹。

限制世代數

不論是 Closure Table 或者 Path Enumeration 的情況，其實只要限制紀錄的世代數就可以解決這個問題。

畢竟追訴的世代有上限，只要存需要的部分就好了！

這個方法聽起來不錯，不過對 Path Enumeration 來說，當 Path 不完整的時候，查詢就會失去準確度（無法用標準的 Path 查詢去問路徑）

至於 Closure Table 看似這樣做是沒有問題的，但是一樣會失去關於深度的正確數值。

在考慮一些細節之後，發現這並不是恰當的方法。

Adjacency List

回到 Adjacency List 的方法上，在 Rails 中使用會產生類似下面的 SQL 查詢。

1SELECT * FROM users WHERE id = 4;
2SELECT * FROM users WHERE id = 2;
3SELECT * FROM users WHERE id = 1;
4...

一般來說我們應該用 WHERE id IN(1, 2, 3) 來查詢才對。

在這邊 PostgreSQL 提供了叫做 Recursive Query 的功能，官網的範例長這樣。

1WITH RECURSIVE t(n) AS (
2    VALUES(1)
3  UNION ALL
4    SELECT n+1 FROM t
5    WHERE n < 100
6)
7SELECT sum(n) FROM t;

然後就可以做出 1 + 2 + … + 100 的效果。

在 Ruby, PHP, JavaScript 等語言中，遞迴已經不容易理解，在 SQL 中實現這件事情，其實也並不容易。

先來理解一下範例的意思。

1WITH RECURSIVE 遞迴結果表(回傳欄位) AS (
2    初始值
3  UNION ALL
4    遞迴查詢
5)
6SELECT * FROM 遞迴結果表;

也就是說，官網範例的 SQL 是給了初始值 1 並且不斷的 SELECT n + 1 後重新呼叫自己，直到 n < 100 才停止。

建構 SQL 查詢

接下來，以這張表來建構查詢。

idnameparent_id
1Jimmy
2John1
3Alice1
4Alex2

按照前面的原則，撰寫下面這張表。

 1WITH RECURSIVE ancestors(id, parent_id, name) AS (
 2    SELECT users.id, users.parent_id, users.name
 3    FROM users
 4    WHERE id = 4
 5  UNION ALL
 6    SELECT users.id, users.parent_id, users.name
 7    FROM users
 8    JOIN ancestors ON ancestors.parent_id = users.id
 9)
10SELECT * FROM ancestors;

如此一來我們就會得到如下的結果

idparent_idname
42Alex
21John
1Jimmy

首先，我們將 id = 4 的 Alex 選出來，作為第一筆資料。

實務上，應該是將 John (id = 2) 直接帶入（父代預設不包含自己）

接下來，我們的下一筆資料的 users.id 必須等於上一筆資料的 users.parent_id 才行。

這邊簡單的使用 JOIN 將 ancestors 跟現有的 users 連接起來。

JOIN ancestors ON ancestors.parent_id = users.id 可能會讓你有點疑惑。 這邊的 ancestors 是指「上一個找到的父代」也就是說上面這句 JOIN 查詢，是找下一個父代的查詢，用上一個的父代 id 去比對是意思正確的。

至於效能上，目前在 800,00 rows 狀態下，用 JOIN 還是單純 FROM users, ancestors 是差不多的耗時跟解析 SQL 之後可能還需要多觀察是否有改進空間。

相對於 Closure Table 還是慢上不少。

轉換成 Model

既然是使用 Rails 的專案，那麼就需要封裝成 Model 的方法才行。

在這之前，我們要先知道幾個前提。

  • WITH RECURSIVE ancestors(...) AS (...) 裡面給的欄位，是回傳的欄位。
  • UNION 所 SELECT 的欄位必須一至，不可使用 * 符號。

因為有以上的限制，我們的 Model 會呈現這樣的狀態。

 1class User < ApplicationRecord
 2
 3  def ancestors(max_depth: 10)
 4    return_columns = User.column_names.join(', ')
 5    select_columns = column_names_for_recursive_query.join(', ')
 6    table_name = User.table_name
 7
 8    query = <<-SQL
 9      WITH RECURSIVE ancestors(#{return_columns}, depth) AS (
10        SELECT #{select_columns}, 1
11        FROM #{table_name}
12        WHERE #{table_name.id} = #{parent_id}
13      UNION ALL
14        SELECT #{select_columns}, depth + 1
15        FROM #{table_name}
16        JOIN ancestors ON ancestors.parent_id = #{table_name}.id
17        WHERE depth < #{max_depth}
18      )
19      SELECT * FROM ancestors ORDER BY depth
20    SQL
21    User.find_by_sql(query)
22  end
23
24  private
25
26  def column_names_for_recursive_query
27    @column_names ||= User.column_names.map |name|
28      [User.table_name, name].join('.')
29    end
30  end
31end

如此一來，我們就可以用 User.last.ancestors 取得對應的 Model 物件回傳。

不過，上面的查詢也還有不少限制，像是無法繼續加上 order limit 等其他透過 ORM 產生的 SQL 查詢。

總結

其實整體看下來，所謂樹狀的結構解法，是要看當時的情境。

以文章一開始的案例來看，選用 Adjacency List by SQL 的方式最為適合，理由如下。

  • 產生節點要快
  • 世代只會不斷成長
  • 樹狀結構的追溯有上限
    • 每個節點只會運行一次追溯

以這個案例來看，耗費在 Recursive Query 的成本每個節點只有一次，相比 Closure Table 會因為世代成長造成的消耗，或者 Path Enumeration 的儲存限制，這個成本是很低的。

下一步是封裝成 Concern 方便取用，畢竟這類型的系統有時候很仰賴樹狀結構的查詢。

另外，樹狀結構比較常拿去查詢子代，畢竟子代數量不確定的時候非常難以管理。