連接的類型與方法#
連接（join）是 SQL 語言的關鍵特性，是其威力與彈性的基礎。列集合（不論直接取自表格或來自其他操作的結果）永遠成對連接。
連接的類型#
內連接（inner join，INNER JOIN 或簡寫 JOIN）：包含兩個集合中滿足特定連接條件的列配對。連接條件把一個集合的某些欄位與另一集合的某些欄位結合，所有涉及的欄位構成連接鍵。
- 若連接條件要求兩集合的連接鍵相等，就稱為等值連接（equi-join）——這是最常見的類型
- 笛卡兒積（
CROSS JOIN）包含兩集合所有可能的列配對，是「條件恆為真」的內連接特例
外連接（outer join）：
- 左外連接（
LEFT OUTER JOIN或LEFT JOIN）在內連接結果之外，額外納入左集合中在右集合找不到匹配的列（對應的右側欄位填入NULL） - 右外連接（
RIGHT JOIN）同理，只是集合對調 - 全外連接（
FULL JOIN）包含左外與右外連接，兩側找不到匹配的列都加入
反連接與半連接：
- 半連接（semi-join）很像內連接，但只包含左集合中在右集合有匹配的列（即使有多個匹配，該列也只納入一次）
- 反連接（anti-join）包含某集合中在另一集合沒有匹配的列
SQL 語言沒有明確的半連接與反連接，但可用
EXISTS與NOT EXISTS之類的謂詞達到相同效果。
連接方法#
PostgreSQL 提供三種連接方法（實作 SQL 連接邏輯操作的演算法）：
- 巢狀迴圈連接（nested loop join）
- 雜湊連接（hash join）
- 合併連接（merge join）
這些基本演算法常有針對特定連接類型量身打造的變體，儘管它們可能只支援其中部分類型。
例如巢狀迴圈支援內連接（計畫中的
Nested Loop節點）與左外連接（Nested Loop Left Join節點），但不能用於全連接。同一演算法的某些變體也能被其他操作（如聚合）使用。不同的連接方法在不同條件下表現最佳，選出最具成本效益者是規劃器的工作。
巢狀迴圈連接#
基本演算法如下：外層迴圈走訪第一個集合（外集合）的所有列；對其中每一列，巢狀迴圈走訪第二個集合（內集合）的列以找出滿足連接條件者。每找到一對就立刻作為查詢結果的一部分回傳。
這個演算法存取內集合的次數 = 外集合的列數。因此巢狀迴圈連接的效率取決於幾個因素：
- 外集合的基數
- 是否有能有效率取得內集合列的存取方法
- 對內集合相同列的重複存取
笛卡兒積#
不論集合中有多少列，巢狀迴圈連接都是求笛卡兒積最有效率的方式：
=> EXPLAIN SELECT * FROM aircrafts_data a1
CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
Nested Loop (cost=0.00..2.78 rows=45 width=144)
−> Seq Scan on aircrafts_data a1 -- 外集合
(cost=0.00..1.09 rows=9 width=72)
−> Materialize (cost=0.00..1.14 rows=5 width=72)
−> Seq Scan on aircrafts_data a2 -- 內集合
(cost=0.00..1.11 rows=5 width=72)
Filter: (range > 5000)Materialize 節點回傳從子節點收到的列，同時把它們存下來供後續使用：
- 列在記憶體中累積，直到總大小達到
work_mem，之後 PostgreSQL 開始把它們溢寫到磁碟上的暫存檔 - 再次被存取時，該節點直接讀取累積的列，不呼叫子節點
因此執行器可以避免重新掃描整張表，只讀取滿足條件的列。
一般的等值連接也可能產生類似的計畫：
=> EXPLAIN SELECT * FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.ticket_no = '0005432000284';
Nested Loop (cost=0.99..25.05 rows=3 width=136)
−> Index Scan using tickets_pkey on tickets t ...
−> Index Scan using ticket_flights_pkey on ticket_flights tf ...
Index Cond: (ticket_no = '0005432000284'::bpchar)規劃器辨識出兩個值相等後，把連接條件
tf.ticket_no = t.ticket_no換成tf.ticket_no = 常數，實質上把等值連接化約成了笛卡兒積。
成本估算#
基數：笛卡兒積的基數估算為兩個資料集基數的乘積（3 = 1 × 3）。
啟動成本 = 所有子節點啟動成本之和。
總成本包含：
- 取得外集合所有列的成本
- 首次取得內集合所有列的成本（期間進行物化）
- 內集合列的重複取得成本 × (N − 1)（N 為外集合列數）
- 每個待回傳列的處理成本（
cpu_tuple_cost）
第一個例子（無重複掃描）：
=> SELECT 0.43 + 0.56 AS startup_cost,
round((8.45 + 16.57 + 3 * 0.01)::numeric, 2) AS total_cost;
startup_cost | total_cost
−−−−−−−−−−−−−−+−−−−−−−−−−−−
0.99 | 25.05笛卡兒積的例子（Materialize 重複掃描 8 次，每次估算 0.0125）：
=> SELECT 0.00 + 0.00 AS startup_cost,
round((1.09 + (1.14 + 8 * 0.0125) + 45 * 0.01)::numeric, 2) AS total_cost;
startup_cost | total_cost
−−−−−−−−−−−−−−+−−−−−−−−−−−−
0.00 | 2.78計畫中顯示的是 Materialize 首次呼叫的成本；後續呼叫的成本不會列出。
參數化連接#
更常見的、不化約為笛卡兒積的例子：
=> EXPLAIN SELECT * FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
Nested Loop (cost=0.99..45.68 rows=6 width=136)
−> Index Scan using tickets_book_ref_idx on tickets t
(cost=0.43..12.46 rows=2 width=104)
Index Cond: (book_ref = '03A76D'::bpchar)
−> Index Scan using ticket_flights_pkey on ticket_flights tf
(cost=0.56..16.58 rows=3 width=32)
Index Cond: (ticket_no = t.ticket_no)這裡
Nested Loop走訪外集合（tickets）的列，並為每一列搜尋內集合的對應列，把票號t.ticket_no作為參數傳入條件。內層節點（Index Scan）被呼叫時，面對的是ticket_no = 常數這個條件。
連接基數的估算#
連接選擇性是兩集合笛卡兒積中連接後留存的比例。顯然必須排除兩集合中連接鍵含 NULL 的列，因為等值條件對它們永不成立。
估算基數 = 笛卡兒積基數（兩集合基數的乘積）× 選擇性
有外鍵時：由於被連接的表格由外鍵相連，選擇性估算依賴「子表格的每一列在父表格中恰有一個匹配列」這項事實。因此選擇性取為「外鍵所參照表格大小的倒數」：
=> SELECT round(2 * tf.reltuples * (1.0 / t.reltuples)) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets' AND tf.relname = 'ticket_flights';
rows
−−−−−−
6無外鍵時：選擇性取為特定連接條件的估算選擇性。假設值分佈均勻時，等值連接的通用公式為：
min( 1/nd₁ , 1/nd₂ )其中 nd₁、nd₂ 分別是兩集合中連接鍵的相異值數量。本例算出的結果與外鍵版本一致。
規劃器會盡可能精修這個基準估算。目前它無法使用直方圖，但若兩張表格的連接鍵都蒐集了 MCV 清單，它就會納入考量：出現在清單中的列其選擇性能被更準確估算，只有剩下的列才需依賴均勻分佈的計算。
一般而言，定義了外鍵，連接選擇性的估算就可能更準確。對複合連接鍵尤其如此——這種情況下選擇性經常被大幅低估。
用 EXPLAIN ANALYZE 觀察迴圈#
=> EXPLAIN (analyze, timing off, summary off) SELECT * ...
Nested Loop (cost=0.99..45.68 rows=6 width=136)
(actual rows=8 loops=1)
−> Index Scan using tickets_book_ref_idx on tickets t
(cost=0.43..12.46 rows=2 width=104) (actual rows=2 loops=1)
−> Index Scan using ticket_flights_pkey on ticket_flights tf
(cost=0.56..16.58 rows=3 width=32) (actual rows=4 loops=2)外集合含兩列（actual rows=2），估算正確。因此 Index Scan 被執行了兩次（loops=2），每次平均選出四列（actual rows=4），總共找到 8 列。
若啟用
TIMING，PostgreSQL 顯示的也是平均值，就像列數一樣。要得到總執行時間，必須把這個值乘以迭代次數（loops）。另外要注意：在某些平台上啟用 timing 的輸出可能顯著拖慢查詢執行。
列快取（Memoization）#
若內集合被以相同的參數值反覆掃描（因而得到相同結果），快取這個集合的列可能很划算。
這種快取由 Memoize 節點執行（PostgreSQL 14 起）。它與 Materialize 相似，但專為參數化連接設計，實作複雜得多：
| Materialize | Memoize | |
|---|---|---|
| 儲存內容 | 單純物化子節點回傳的所有列 | 確保不同參數值回傳的列分開保存 |
| 溢位處理 | 開始把列溢寫到磁碟 | 全部保留在記憶體中（否則快取就沒有意義了） |
=> EXPLAIN SELECT * FROM flights f
JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
Nested Loop (cost=5.44..387.10 rows=113 width=135)
−> Bitmap Heap Scan on flights f ...
−> Memoize (cost=0.15..0.27 rows=1 width=72)
Cache Key: f.aircraft_code
Cache Mode: logical
−> Index Scan using aircrafts_pkey on aircrafts_data a ...運作機制#
- 用於存放快取列的記憶體大小為
work_mem×hash_mem_multiplier（預設 4 MB × 1.0） - 如第二個參數名稱所示，快取列存放在雜湊表（開放定址）中。雜湊鍵（計畫中的
Cache Key）就是參數值（多個參數時為多個值） - 所有雜湊鍵被串成一個清單：一端視為冷端（含長時間未使用的鍵），另一端為熱端（存放最近使用的鍵）
命中：若傳入的參數值對應已快取的列，這些列就直接傳給父節點（Nested Loop），不檢查子節點；使用過的雜湊鍵被移到熱端。
未命中：Memoize 從子節點拉取列、快取後傳給上層節點，對應的雜湊鍵也變熱。
淘汰：新資料填滿可用記憶體時，對應冷端鍵的列被淘汰。這個淘汰演算法與緩衝快取所用的不同，但目的相同。
某些參數值可能有多到塞不進配置記憶體的匹配列，即使其他列都已被淘汰。這類參數會被跳過——只快取部分列毫無意義，因為下次呼叫仍得從子節點取得全部列。
成本估算與診斷#
顯然只有在 Memoize 比其子節點便宜時使用它才有意義。每次後續 Memoize 掃描的成本取決於預期的快取存取樣態與可用於快取的記憶體大小，而算出的值高度依賴「內集合掃描中相異參數值數量」的準確估算。
=> EXPLAIN (analyze, costs off, timing off, summary off) SELECT * ...
−> Memoize (actual rows=1 loops=113)
Cache Key: f.aircraft_code
Cache Mode: logical
Hits: 112 Misses: 1 Evictions: 0 Overflows: 0 Memory Usage: 1kB此查詢選出同一航線、由特定機型執飛的航班，因此所有對 Memoize 的呼叫都使用相同的雜湊鍵：第一列必須從表格取得（Misses: 1），後續全部命中快取（Hits: 112），整個操作只用 1 kB 記憶體。
另兩個顯示值——淘汰次數（
Evictions）與快取溢位次數（Overflows，無法快取某參數集合的全部列）——若數字很大，代表配置的快取太小，可能肇因於相異參數值數量的估算不準確。此時使用 Memoize 節點可能相當昂貴。極端情況下，可關閉
enable_memoize參數（預設 on）禁止規劃器使用快取。
外連接#
巢狀迴圈連接可用於執行左外連接：
=> EXPLAIN SELECT *
FROM ticket_flights tf
LEFT JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no
AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720';
Nested Loop Left Join (cost=1.12..33.35 rows=3 width=57)
Join Filter: ((bp.ticket_no = tf.ticket_no) AND (bp.flight_id = tf.flight_id))
−> Index Scan using ticket_flights_pkey on ticket_flights tf ...
−> Materialize ...此處規劃器選了帶過濾器的非參數化連接：它對內集合執行完全相同的掃描（因此該集合藏在 Materialize 節點後），並回傳滿足 Join Filter 的列。
外連接的基數估算方式與內連接相同，只是算出的估算會與外集合的基數比較，取較大者作為最終結果。
換言之：外連接絕不會減少列數（但可能增加）。
規劃器可能為內連接與外連接選出不同的計畫。即使這個簡單的例子，強制使用巢狀迴圈連接的內連接版本也會有不同的
Join Filter（只剩tf.flight_id = bp.flight_id）。總成本的細微差異，源於外連接還必須檢查票號，才能在外集合找不到匹配時得到正確結果。
全連接因同樣理由也不被支援。
反連接與半連接#
反連接與半連接的相似之處在於：對第一（外）集合的每一列，只需在第二（內）集合找到一個匹配列就夠了。
反連接只回傳在第二集合中沒有匹配的第一集合列：執行器一找到第二集合中的第一個匹配列，就能離開目前迴圈——對應的第一集合列必須被排除在結果之外。
反連接可用來計算 NOT EXISTS 謂詞：
=> EXPLAIN SELECT * FROM aircrafts a
WHERE NOT EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
Nested Loop Anti Join (cost=0.28..4.65 rows=1 width=40)
−> Seq Scan on aircrafts_data ml ...
−> Index Only Scan using seats_pkey on seats s ...不用
NOT EXISTS的等價查詢（LEFT JOIN ... WHERE s.aircraft_code IS NULL）會得到完全相同的計畫。
半連接回傳第一集合中至少有一個匹配的列（同樣不必再檢查其他匹配——結果已經確定）。半連接可用來計算 EXISTS 謂詞（Nested Loop Semi Join 節點）。
半連接與反連接的計畫都顯示
seats表格的基本列數估算（rows=149），儘管實際上只需取出其中一列。實際查詢執行當然會在取得第一列後停止（EXPLAIN ANALYZE顯示actual rows=1 loops=9）。
估算方式：
- 半連接的選擇性以一般方式估算，只是內集合的基數取為 1
- 反連接的估算選擇性則是用 1 減去，就像取否定一樣
- 成本估算反映了「第二集合的掃描一找到第一個匹配列就停止」這項事實
非等值連接#
巢狀迴圈演算法允許依任何連接條件連接列集合。
顯然，若內集合是建有索引的基表、且連接條件使用的運算子屬於該索引的運算子類別，對內集合的存取就能相當有效率。
但總是可以透過「計算被某條件過濾的列的笛卡兒積」來完成連接——此時條件可以完全任意。
例如選出彼此距離接近的機場配對：
=> CREATE EXTENSION earthdistance CASCADE;
=> EXPLAIN (costs off) SELECT *
FROM airports a1
JOIN airports a2 ON a1.airport_code != a2.airport_code
AND a1.coordinates <@> a2.coordinates < 100;
Nested Loop
Join Filter: ((ml.airport_code <> ml_1.airport_code) AND
((ml.coordinates <@> ml_1.coordinates) < '100'::double precisi...
−> Seq Scan on airports_data ml
−> Materialize
−> Seq Scan on airports_data ml_1平行模式#
巢狀迴圈連接可參與平行計畫執行。
=> EXPLAIN (costs off) SELECT t.passenger_name
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
JOIN flights f ON f.flight_id = tf.flight_id
WHERE f.flight_id = 12345;
Nested Loop
−> Index Only Scan using flights_flight_id_status_idx on fligh...
Index Cond: (flight_id = 12345)
−> Gather
Workers Planned: 2
−> Nested Loop
−> Parallel Seq Scan on ticket_flights tf
Filter: (flight_id = 12345)
−> Index Scan using tickets_pkey on tickets t
Index Cond: (ticket_no = tf.ticket_no)- 上層的巢狀迴圈連接是循序執行的。外集合只由
flights表格中依唯一鍵取得的一列構成，因此即使內側列數龐大，使用巢狀迴圈仍屬合理 - 內集合以平行計畫取得：每個工作者掃描自己分到的那份
ticket_flights列，並用巢狀迴圈演算法與tickets連接