合併連接#

合併連接（merge join）處理已依連接鍵排序的資料集，並回傳同樣排序的結果。輸入集合可能因索引掃描而已預先排序；否則執行器必須在實際合併開始前先排序它們。

=> EXPLAIN (costs off) SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
ORDER BY t.ticket_no;
 Merge Join
   Merge Cond: (t.ticket_no = tf.ticket_no)
   −> Index Scan using tickets_pkey on tickets t
   −> Index Scan using ticket_flights_pkey on ticket_flights tf

最佳化器偏好這個連接方法，因為它回傳的結果已符合 ORDER BY 的排序要求。

選擇計畫時，最佳化器會留意資料集的排序狀態，非必要就不執行排序。例如某次合併連接產生的資料集若已具備合適的排序，就能原樣用於後續的合併連接。

多層合併連接的例子中，ticket_flights 與 boarding_passes 先連接（兩者都有複合主鍵 (ticket_no, flight_id)，結果依這兩欄排序），產生的列集合再與依 ticket_no 排序的 tickets 連接。

演算法#

它使用兩個指向內外集合當前列（初始為第一列）的指標：

1. 若當前列的鍵不匹配，指向較小鍵那一列的指標往下移，直到找到匹配為止
2. 連接好的列回傳給上層節點，內集合的指標往前移一格
3. 操作持續到其中一個集合結束為止

處理重複：這個演算法能應付內集合的重複，但外集合也可能有重複。為此演算法還須改進——若外側指標移動後鍵維持不變，內側指標就退回第一個匹配的列。如此每個外集合列都能與所有同鍵的內集合列配對。

外連接的演算法再稍作調整，但仍基於相同原理。

成本估算#

啟動成本至少包含所有子節點的啟動成本。

一般而言，可能需要掃描外集合或內集合的一部分才找到第一個匹配。這個比例可依直方圖比較兩集合中最小的連接鍵來估算。上例中兩張表的票號範圍相同，故不需要。

總成本 = 從子節點取得資料的成本 + 計算成本：

• 由於演算法在其中一個集合結束時就停止（外連接除外），另一個集合可能只被部分掃描。掃描部分的大小可透過比較兩集合的最大鍵值估算
• 若有重複，內集合的某些列可能被掃描數次。重複掃描次數的估算 = 連接結果的基數 − 內集合的基數
• 比較操作的成本為 cpu_operator_cost（0.0025），比較次數估算為兩集合列數之和（加上重複所致的重讀次數）
• 每個結果列的處理成本為 cpu_tuple_cost（0.01）

=> SELECT 0.43 + 0.56 AS startup,
  round((139110.29 + 570972.46 + 0.01 * 8391852
         + 0.0025 * (2949857 + 8391852))::numeric, 2) AS total;
 startup |   total
−−−−−−−−−+−−−−−−−−−−−
    0.99 | 822355.54

平行模式#

合併連接沒有平行版本，但仍可用於平行計畫：外集合可由多個工作者平行掃描，但內集合永遠由每個工作者完整掃描一次。

=> SET enable_hashjoin = off;  -- 平行雜湊連接幾乎總是更便宜，先關掉
=> EXPLAIN (costs off)
SELECT count(*), sum(tf.amount)
FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no;
 Finalize Aggregate
   −> Gather
       Workers Planned: 2
       −> Partial Aggregate
           −> Merge Join
               −> Parallel Index Scan using ticket_flights_pkey o...
               −> Index Only Scan using tickets_pkey on tickets t

連接類型的變體#

合併連接演算法可用於任何類型的連接。唯一限制是：全外連接與右外連接的條件必須含有合併相容的運算式（「外側欄位 = 內側欄位」或「欄位 = 常數」）。

內連接與左外連接可以單純用無關條件過濾連接結果，但對全連接與右連接而言這種過濾不適用。

為恢復所需順序，規劃器會引入 Sort 節點——這自然提高了計畫成本，使雜湊連接更具吸引力。

有些查詢非用雜湊連接不可：巢狀迴圈完全不允許全連接，而合併因連接條件不受支援也無法使用。此時不論 enable_hashjoin 為何，都會使用雜湊連接。

排序#

若其中一個集合（或兩者）未依連接鍵排序，就必須在連接前重新排序，計畫中以 Sort 節點表示：

=> EXPLAIN (costs off)
SELECT * FROM flights f
  JOIN airports_data dep ON f.departure_airport = dep.airport_code
ORDER BY dep.airport_code;
 Merge Join
   −> Sort
       Sort Key: f.departure_airport
       −> Seq Scan on flights f
   −> Sort
       Sort Key: dep.airport_code
       −> Seq Scan on airports_data dep

排序也可以出現在連接之外——只要指定 ORDER BY，不論在一般查詢或視窗函式中（WindowAgg 節點會在 Sort 預先排序好的資料集上計算視窗函式）。

規劃器有數種排序方法可用（EXPLAIN ANALYZE 的 Sort Method 會顯示）：

 Merge Join (actual rows=214867 loops=1)
   −> Sort (actual rows=214867 loops=1)
       Sort Method: external merge Disk: 17136kB
   −> Sort (actual rows=104 loops=1)
       Sort Method: quicksort Memory: 52kB

快速排序#

若待排序的資料集塞得進 work_mem（預設 4 MB），就套用經典的快速排序（quicksort）。

就實作而言，排序由一個專責元件執行，它會依可用記憶體與其他因素選擇最合適的演算法。

成本估算：排序 n 個值的計算複雜度為 O(n log₂ n)，單次比較操作估算為 cpu_operator_cost 的兩倍。

由於必須掃描並排序整個資料集才能取得結果，排序的啟動成本包含子節點的總成本與所有比較操作的開銷。

總成本再加上每個待回傳列的處理成本，估算為 cpu_operator_cost（而非通常的 cpu_tuple_cost，因為 Sort 節點造成的開銷微不足道）。

=> WITH costs(startup) AS (
  SELECT 4.04 + round((0.0025 * 2 * 104 * log(2, 104))::numeric, 2)
)
SELECT startup, startup + round((0.0025 * 104)::numeric, 2) AS total
FROM costs;
 startup | total
−−−−−−−−−+−−−−−−−
    7.52 | 7.78

Top-N 堆積排序#

若資料集只需部分排序（由 LIMIT 定義），就可套用堆積排序（計畫中顯示為 top-N heapsort）。

更精確地說，這個演算法在下列情況使用：排序讓列數至少減半，或配置的記憶體容納不下整個輸入集合、但容納得下輸出集合。

=> EXPLAIN (analyze, timing off, summary off)
SELECT * FROM seats ORDER BY seat_no LIMIT 100;
 Limit (cost=72.57..72.82 rows=100 width=15) (actual rows=100 loops=1)
   −> Sort (cost=72.57..75.91 rows=1339 width=15) (actual rows=100 loops=1)
       Sort Key: seat_no
       Sort Method: top−N heapsort Memory: 33kB
       −> Seq Scan on seats ...

演算法：要從 n 個值中找出最大（或最小）的 k 個，執行器先把前 k 列加入一個稱為堆積（heap）的資料結構；接著逐一加入其餘列，每次迭代後從堆積中移除最小（或最大）值。所有列處理完畢後，堆積中就是要找的 k 個值。

此處的 heap 指的是眾所周知的資料結構，與常以同名指稱的資料庫表格毫無關係。

成本估算：演算法的計算複雜度估算為 O(n log₂ k)，但每個操作都比快速排序昂貴，因此公式改用 n log₂ 2k。

外部排序#

若掃描顯示資料集大到無法在記憶體中排序，排序節點就切換到外部合併排序（計畫中標示為 external merge）。

流程：

1. 已掃描的列在記憶體中以快速排序排好，寫入暫存檔

   

2. 後續列讀進釋出的記憶體，重複此程序，直到所有資料被寫入數個預先排序好的檔案

   

3. 接著把這些檔案合併成一個。這項操作使用的演算法與合併連接大致相同，主要差別是它一次可以處理兩個以上的檔案

   

實務上列是以 32 頁為一批讀取而非逐列，這減少了 I/O 操作次數。單次迭代中合併的檔案數取決於可用記憶體，但永遠不少於 6 個；上限同樣有限制（500），因為檔案太多時效率會下降。

若排好的暫存檔無法一次全部合併，就必須分數趟處理，部分結果寫入新的暫存檔。每次迭代都增加待讀寫的資料量，因此可用的 RAM 越多，外部排序完成得越快。

最後一次合併通常被延後，在上層節點拉取資料時即時執行。

成本估算：一般的比較成本（次數與記憶體內快速排序相同）再加上 I/O 成本。所有輸入資料必須先寫入磁碟暫存檔，合併時再讀出（若無法一次合併完，可能不只讀一次）。

假設磁碟操作（讀寫皆然）四分之三是循序的、四分之一是隨機的。

寫到磁碟的資料量取決於待排序的列數與查詢所用的欄位數。上例查詢顯示 flights 的所有欄位，因此溢寫到磁碟的資料大小與整張表格幾乎相同（2309 頁 vs. 2624 頁，不計元組與頁面中繼資料）。

增量排序（PostgreSQL 13 起）#

若資料集必須依鍵 K₁…Kₘ…Kₙ 排序，而已知它已依前 m 個鍵排序，就不必從頭重排。可以：

1. 依相同的前幾個鍵 K₁…Kₘ 把集合切成群組（群組內的值已符合既定順序）
2. 再依剩餘的 Kₘ₊₁…Kₙ 鍵分別排序每個群組

PostgreSQL 的實作更細膩一些：相對較大的群組分別處理，較小的群組則被合併起來完整排序——這減少了反覆呼叫排序程序的開銷。

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM bookings ORDER BY total_amount, book_date;
 Incremental Sort (actual rows=2111110 loops=1)
   Sort Key: total_amount, book_date
   Presorted Key: total_amount
   Full−sort Groups: 2823 Sort Method: quicksort Average
   Memory: 30kB Peak Memory: 30kB
   Pre−sorted Groups: 2624 Sort Method: quicksort Average
   Memory: 3152kB Peak Memory: 3259kB
   −> Index Scan using bookings_total_amount_idx on bookings (ac...

• 資料集因對 total_amount 的索引掃描而預先排序（Presorted Key）
• Full-sort Groups 是被合併起來完整排序的小群組
• Pre-sorted Groups 是資料部分有序的大群組，只需依 book_date 做增量排序
• 兩者都套用記憶體內快速排序；群組大小的差異源於訂位金額分佈不均

增量排序也可用於計算視窗函式（PostgreSQL 14 起）。

成本估算基於預期的群組數與平均大小群組的排序成本估算：啟動成本反映排序第一個群組的成本（讓節點能開始回傳有序列），總成本則包含所有群組的排序成本。

平行模式（PostgreSQL 10 起）#

排序也可並行執行。

但儘管平行工作者確實會預先排序自己那份資料，Gather 節點對它們的排序順序一無所知，只能以先到先服務的方式累積它們。

要保留排序順序，執行器必須改用 Gather Merge 節點。

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM flights ORDER BY scheduled_departure LIMIT 10;
 Limit (actual rows=10 loops=1)
   −> Gather Merge (actual rows=10 loops=1)
       Workers Planned: 1
       Workers Launched: 1
       −> Sort (actual rows=7 loops=2)
           Sort Method: top−N heapsort Memory: 27kB
           Worker 0: Sort Method: top−N heapsort Memory: 27kB
           −> Parallel Seq Scan on flights ...

成本估算：

• 啟動成本 = 子節點的啟動成本 + 啟動平行行程的成本（parallel_setup_cost = 1000）+ 建立二元堆積的成本（排序 n 個值，n 為平行工作者數，即 n log₂ n；單次比較估為 cpu_operator_cost 的兩倍，由於 n 很小這部分通常可忽略）
• 總成本 = 多個行程取得全部資料的開銷 + 把資料傳給領導行程的成本（單列傳輸估為 parallel_tuple_cost 增加 5%，以補償等待下一個值可能的耗時）+ 二元堆積更新的開銷（每個輸入列需 log₂ n 次比較操作與若干額外動作）

相異值與分組#

如前所述，用於聚合分組（與去除重複）的操作不只能靠雜湊，也能靠排序——在已排序的清單中，重複值的群組可以一趟掃描就分辨出來。

從已排序清單取得相異值，計畫中以非常簡單的 Unique 節點表示：

=> EXPLAIN (costs off)
SELECT DISTINCT book_ref FROM bookings ORDER BY book_ref;
 Result
   −> Unique
        −> Index Only Scan using bookings_pkey on bookings

聚合則在 GroupAggregate 節點執行：

=> EXPLAIN (costs off) SELECT book_ref, count(*)
FROM bookings GROUP BY book_ref ORDER BY book_ref;
 GroupAggregate
   Group Key: book_ref
   −> Index Only Scan using bookings_pkey on bookings

平行計畫中，這個節點稱為 Partial GroupAggregate，完成聚合的節點則稱為 Finalize GroupAggregate。

MixedAggregate：雜湊與排序並用#

若分組依多組欄位進行（由 GROUPING SETS、CUBE 或 ROLLUP 指定），兩種策略可以在同一個節點中結合：

=> SET work_mem = '64kB';
=> EXPLAIN (costs off) SELECT count(*)
FROM flights
GROUP BY GROUPING SETS (aircraft_code, flight_no, departure_airport);
 MixedAggregate
   Hash Key: departure_airport
   Group Key: aircraft_code
   Sort Key: flight_no
     Group Key: flight_no
   −> Sort
       Sort Key: aircraft_code
       −> Seq Scan on flights

執行過程：

1. MixedAggregate 收到依 aircraft_code 排序的資料集，掃描並依該欄位分組（Group Key）
2. 掃描的同時，列被依 flight_no 重新排序（如同一般 Sort 節點：記憶體夠就快速排序，否則用磁碟外部排序）；與此同時執行器把這些列放進以 departure_airport 為鍵的雜湊表（如同雜湊聚合：在記憶體中或使用暫存檔）
3. 第二階段掃描剛依 flight_no 排好的資料集，依同一欄位分組（Sort Key 與其下的 Group Key）
4. 最後掃描第一階段備妥的雜湊表，依 departure_airport 分組（Hash Key）

若列還需依另一個欄位分組，它們會再被重新排序一次。

三種連接方法的比較#

對笛卡兒積而言它是二次複雜度，但笛卡兒積實務上並不常見；通常執行器為外集合的每一列透過索引存取一定數量的內側列，而這個平均數不隨資料集總大小改變（例如一筆訂位的平均機票數不會因訂位與售票總數增長而改變）。因此巢狀迴圈的複雜度往往呈線性成長而非二次，即使線性係數很高。

巢狀迴圈有時能藉由在 Memoize 節點快取內集合的列而勝過雜湊連接：雜湊連接總是完整掃描內集合，巢狀迴圈則不必。

若沒有合適的索引，集合就必須被排序——這項操作耗記憶體，複雜度也高於線性 O(n log₂ n)。此時雜湊連接幾乎總是比合併連接便宜——除非結果必須排序。

成本隨選擇性變化的定性圖像：

• 巢狀迴圈：選擇性高時對兩張表都用索引存取；之後規劃器切換到外表格的完整掃描（圖形的線性段）
• 雜湊連接：兩張表都用完整掃描。圖上的「階梯」對應雜湊表填滿整個記憶體、批次開始溢寫到磁碟的時刻
• 合併連接 + 索引：呈小幅線性成長。work_mem 夠大時雜湊連接通常更有效率，但一旦動用暫存檔，合併連接就勝出
• 合併連接 + 排序：無索引可用、必須排序時成本上升；圖上的「階梯」同樣由記憶體不足、排序改用暫存檔所致

這只是示意；各案例中成本的比值都會不同。