PostgreSQL：在查詢計劃中實現為 Merge Join 的內部節點
我正在學習 PostgreSQL EXPLAIN 計劃節點。目前，我正在研究 Materialize 節點。這是我在博文（https://www.depesz.com/2013/05/09/explaining-the-unexplainable-part-3/）中找到的一個查詢和我自己獲得的一個計劃（從結構上講，它是與部落格文章中的相同）：
set work_mem= '1GB'; explain analyze select * from (select * from pg_class order by oid) as c join (select * from pg_attribute a order by attrelid) as a on c.oid = a.attrelid; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- Merge Join (cost=34.27..333.37 rows=2913 width=504) (actual time=0.823..28.413 rows=2913 loops=1) Merge Cond: (pg_class.oid = a.attrelid) -> Sort (cost=33.99..34.97 rows=395 width=265) (actual time=0.739..1.084 rows=395 loops=1) Sort Key: pg_class.oid Sort Method: quicksort Memory: 130kB -> Seq Scan on pg_class (cost=0.00..16.95 rows=395 width=265) (actual time=0.038..0.285 rows=395 loops=1) -> Materialize (cost=0.28..257.05 rows=2913 width=239) (actual time=0.060..11.702 rows=2913 loops=1) -> Index Scan using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.28..220.63 rows=2913 width=239) (actual time=0.050..6.827 rows=2913 loops=1) Planning Time: 1.472 ms Execution Time: 29.617 ms (10 rows)我無法理解部落格作者關於 Postgres 為何在這裡使用 Materialize 的論點。
…合併連接必須匹配幾個條件。有些是顯而易見的（必須對數據進行排序），有些則不那麼明顯，因為技術性更強（數據必須可以來回滾動）。
正因為如此（這些不是那麼明顯的標準），有時 Pg 必須將來自源的數據（在我們的例子中是索引掃描）具體化，以便在使用時具有所有必要的功能。
為什麼 Merge Join 需要數據可以來回滾動？根據我對 Merge Join 的理解，它使用兩個指針同時迭代兩個數據集。Merge Join 算法在向後退時沒有案例。無論如何，據我了解，索引掃描實際上是“可前後滾動”的。我多次看到“Index Scan Backward”。那麼為什麼 Postgres 必須實現它呢？
我在其他來源，即Korry Douglas 和 Susan Douglas的舊書“ PostgreSQL：建構、程式和管理 PostgreSQL 數據庫的綜合指南”，第 2 版中找到了部落格作者觀點的確認：
Materialize 也將用於一些合併連接操作。特別是，如果 Merge Join 運算符的內部輸入集不是由 Seq Scan、Index Scan、Sort 或 Materialize 運算符生成的，則計劃器/優化器將在計劃中插入 Materialize 運算符。這條規則背後的原因並不明顯，它更多地與其他操作員的能力有關，而不是與您的數據的性能或結構有關。Merge Join 運算符很複雜；Merge Join 的一項要求是輸入集必須按連接列排序。第二個要求是內部輸入集必須是可重新定位的；也就是說，Merge Join 需要在輸入集中前後移動。並非所有有序運算符都可以前後移動。如果內部輸入集是由一個不可重定位的運算元產生的，
在我的例子中，內部輸入集是由 Index Scan 產生的，所以根據本書，這個計劃中應該沒有 Materialize 節點。
然後我決定修改查詢，使規劃器不會使用 Materialize，但 Merge Join 仍然存在。這就是我想出的：
set enable_hashjoin = off; set work_mem= '1GB'; explain analyze select * from (select * from pg_class order by oid) as c join (select * from pg_attribute a) as a on c.oid = a.attrelid; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------------- Merge Join (cost=34.27..296.96 rows=2913 width=504) (actual time=0.554..10.103 rows=2913 loops=1) Merge Cond: (pg_class.oid = a.attrelid) -> Sort (cost=33.99..34.97 rows=395 width=265) (actual time=0.491..0.645 rows=395 loops=1) Sort Key: pg_class.oid Sort Method: quicksort Memory: 130kB -> Seq Scan on pg_class (cost=0.00..16.95 rows=395 width=265) (actual time=0.021..0.177 rows=395 loops=1) -> Index Scan using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.28..220.63 rows=2913 width=239) (actual time=0.041..2.296 rows=2913 loops=1) Planning Time: 1.188 ms Execution Time: 10.731 ms (9 rows)我從第二個子查詢中刪除
order by attrelid並強行禁用了 Hash Join。除了 Materialize 節點外，此計劃與上一個計劃相同。因此，我得出結論，Merge Join 不是規劃器在上一個中使用 Materialize 的原因。這個計劃比較便宜，但我想結果是一樣的。如果您能幫助我解決其中的一些難題，我將不勝感激：
- Merge Join 真的需要能夠向後迭代內部數據集嗎？在哪些情況下？就 Merge Join 要求而言，Index Scan 的結果是否“向後迭代”？
- 為什麼 Postgres 計劃器在第一個計劃中使用 Materialize，即使它成本更高？它在這裡服務的目的是什麼？為什麼 Postgres planner 在第二個計劃中不使用 Materialize？
你的分析是對的；實現合併連接的內部關係的決定是在
final_cost_mergejoin.如果它更便宜或者內部路徑的排序會溢出到磁碟，PostgreSQL 將考慮實現。這可以通過關閉來禁用
enable_material，所以這是一個有用的測試。在我們的例子中，禁用它仍然會實現索引掃描，因此必須需要實現。此源註釋描述了何時需要：
/* * Even if materializing doesn't look cheaper, we *must* do it if the * inner path is to be used directly (without sorting) and it doesn't * support mark/restore. * * Since the inner side must be ordered, and only Sorts and IndexScans can * create order to begin with, and they both support mark/restore, you * might think there's no problem --- but you'd be wrong. Nestloop and * merge joins can *preserve* the order of their inputs, so they can be * selected as the input of a mergejoin, and they don't support * mark/restore at present. * * We don't test the value of enable_material here, because * materialization is required for correctness in this case, and turning * it off does not entitle us to deliver an invalid plan. */ else if (innersortkeys == NIL && !ExecSupportsMarkRestore(inner_path)) path->materialize_inner = true;
ExecSupportsMarkRestore做這個：bool ExecSupportsMarkRestore(Path *pathnode) { /* * For consistency with the routines above, we do not examine the nodeTag * but rather the pathtype, which is the Plan node type the Path would * produce. */ switch (pathnode->pathtype) { case T_IndexScan: case T_IndexOnlyScan: /* * Not all index types support mark/restore. */ return castNode(IndexPath, pathnode)->indexinfo->amcanmarkpos; [...] default: break; } return false; }現在 B-tree 索引確實支持標記/恢復，那是怎麼回事呢？
問題是您不是
pg_attribute直接加入，而是使用子查詢。現在這在最終的執行計劃中是看不到的，但是在生成路徑的階段，路徑類型不是T_IndexScan，而是T_SubqueryScan，所以ExecSupportsMarkRestore得出結論，我們必須實現。您可以通過省略
ORDER BY和禁用雜湊連接來進行測試：SET enable_hashjoin = off; explain (costs off) select * from (select * from pg_class order by oid) as c join (select * from pg_attribute a) as a on c.oid = a.attrelid; QUERY PLAN ══════════════════════════════════════════════════════════════════════════ Merge Join Merge Cond: (pg_class.oid = a.attrelid) -> Sort Sort Key: pg_class.oid -> Seq Scan on pg_class -> Index Scan using pg_attribute_relid_attnum_index on pg_attribute a (6 rows)瞧——不
Materialize。這可以優化，但我不太了解程式碼是否可行。