單趟雜湊連接#

雜湊連接（hash join）以事先建好的雜湊表搜尋匹配列：

=> EXPLAIN (costs off) SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no;
 Hash Join
   Hash Cond: (tf.ticket_no = t.ticket_no)
   −> Seq Scan on ticket_flights tf
   −> Hash
       −> Seq Scan on tickets t

第一階段：建立雜湊表#

Hash Join 節點呼叫 Hash 節點，後者從其子節點拉取整個內集合並放進雜湊表。

雜湊表存放「雜湊鍵—值」配對，能依鍵快速存取值；搜尋時間與雜湊表大小無關，因為雜湊鍵會或多或少均勻地分佈在有限數量的桶（bucket）中。

給定鍵落入哪個桶，由該雜湊鍵的雜湊函式決定；由於桶數永遠是 2 的次方，只要取計算結果的所需位元數即可。

與緩衝快取一樣，這個實作使用可動態擴充、以鏈結解決雜湊碰撞的雜湊表。

掃描內集合時為每一列計算雜湊函式：

• 連接條件中所參照的欄位（Hash Cond）作為雜湊鍵
• 雜湊表本身存放內集合中所有被查詢的欄位

實測（work_mem = 256MB）：

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
 Hash Join (actual rows=2949857 loops=1)
   Hash Cond: (t.book_ref = b.book_ref)
   −> Seq Scan on tickets t (actual rows=2949857 loops=1)
   −> Hash (actual rows=2111110 loops=1)
       Buckets: 4194304 Batches: 1 Memory Usage: 145986kB
       −> Seq Scan on bookings b (actual rows=2111110 loops=1)

與對內外集合處理方式不同的巢狀迴圈連接不同，雜湊連接可以把兩個集合對調。較小的集合通常被用作內集合，因為那樣雜湊表較小。

若查詢只參照一個欄位，同樣的雜湊表只需 113 MB（而非 146 MB）——這是「避免在查詢中參照多餘欄位」（例如使用星號）的又一個理由。

桶數的選擇#

選定的桶數應保證：雜湊表被資料完全填滿時，每個桶平均只放一列。

• 密度更高會提高雜湊碰撞率，使搜尋效率降低
• 雜湊表更鬆散則佔用過多記憶體

估算出的桶數會被進位到最近的 2 的次方。若依單列平均寬度估算出的雜湊表大小超過記憶體限制，就會套用雙趟雜湊。

第二階段：探測#

第二階段中，Hash Join 呼叫第二個子節點取得外集合。對每個掃描到的列，在雜湊表中搜尋匹配——這需要為外集合中被納入連接條件的欄位計算雜湊鍵。找到的匹配回傳給父節點。

成本估算#

啟動成本主要反映雜湊表建立的成本，包含：

• 取得內集合的總成本（建立雜湊表所需）
• 為內集合每一列計算連接鍵所有欄位的雜湊函式（每次操作 cpu_operator_cost = 0.0025）
• 把所有內側列插入雜湊表（每列 cpu_tuple_cost = 0.01）
• 取得外集合的啟動成本

總成本 = 啟動成本 + 連接本身的成本：

• 為外集合每一列計算連接鍵所有欄位的雜湊函式（cpu_operator_cost）
• 連接條件的重新檢查（處理可能的雜湊碰撞，每個被檢查的運算子 cpu_operator_cost）
• 每個結果列的處理成本（cpu_tuple_cost）

雙趟雜湊連接#

若規劃器估算顯示雜湊表塞不進配置的記憶體，內集合就會被切分成批次（batch）分別處理。

• 批次數（與桶數一樣）永遠是 2 的次方，使用哪個批次由雜湊鍵對應的位元決定
• 任何兩個匹配的列必屬於同一批次：被放進不同批次的列不可能有相同的雜湊碼
• 所有批次持有相等數量的雜湊鍵；資料分佈均勻時，批次大小也大致相同
• 規劃器透過選擇適當的批次數來控制記憶體消耗

執行流程#

第一階段：執行器掃描內集合以建立雜湊表。

• 掃描到的列屬於第一批次 → 加入雜湊表、保留在 RAM 中
• 否則 → 寫入暫存檔（每個批次一個獨立檔案）

第二階段：掃描外集合。

• 列屬於第一批次 → 與雜湊表（含內集合第一批次的列）比對
• 屬於其他批次 → 存入暫存檔（同樣每批次一個）

因此 N 個批次最多用 2(N − 1) 個檔案（若某些批次為空則更少）。

第二階段完成後，雜湊表所用記憶體被釋放，此時我們已得到其中一個批次的連接結果。

後續：兩個階段對每個存在磁碟上的批次重複——內集合的列從暫存檔轉入雜湊表，接著從另一個暫存檔讀取同批次的外集合列並比對。處理完畢後暫存檔即被刪除。

單一 session 能在磁碟上存放的暫存檔總量受 temp_file_limit 參數限制（暫存表格不計入）。session 一達到這個值，查詢就會被中止。

=> EXPLAIN (analyze, buffers, costs off, timing off, summary off)
SELECT * FROM bookings b JOIN tickets t ON b.book_ref = t.book_ref;
 Hash Join (actual rows=2949857 loops=1)
   Buffers: shared hit=7236 read=55626, temp read=55126 written=55126
   −> Seq Scan on tickets t (actual rows=2949857 loops=1)
   −> Hash (actual rows=2111110 loops=1)
       Buckets: 65536 Batches: 64 Memory Usage: 2277kB
       Buffers: shared hit=7236 read=6211, temp written=10858
       −> Seq Scan on bookings b (actual rows=2111110 loops=1)

預設 4 MB 的 work_mem 太小，資料被切成 64 個批次，雜湊表用 65,536 個桶。建表期間（Hash 節點）資料被寫入暫存檔（temp written）；連接階段（Hash Join 節點）暫存檔被讀也被寫。

把 log_temp_files 設為零可蒐集更多暫存檔統計——伺服器日誌會列出所有暫存檔及其（刪除時的）大小。

成本估算#

啟動成本 = 單趟連接的啟動成本 + 「寫出足以存放內集合所有列所需欄位的頁數」的估算成本。

儘管建立雜湊表時第一批次並未寫入磁碟，估算並未把這點納入考量，因此不依賴批次數。

總成本 = 單趟連接的總成本 + 讀取先前存於磁碟的內集合列 + 讀寫外集合列的估算成本。讀寫都以每頁 seq_page_cost 估算，因為 I/O 操作被假定為循序的。

• 查詢的寫法要把多餘欄位排除在雜湊表之外
• 規劃器必須選擇兩個集合中較小者來建立雜湊表

動態調整#

有兩個問題可能打亂原定計畫：統計不準確與資料分佈非均勻。

連接鍵欄位的值分佈非均勻時，各批次大小會不同。

skew 最佳化：若某個批次（第一個除外）太大，它的所有列都得寫入磁碟再讀出。外集合造成的麻煩最大，因為它通常較大。因此若外集合的 MCV 有一般（非多變量）統計——即外集合是表格、且以單一欄位連接——雜湊碼對應 MCV 的列會被視為第一批次的一部分，這能在一定程度上降低雙趟連接的 I/O 開銷。

動態增加批次數#

由於上述兩個因素，某些（或全部）批次的大小可能超出估算，導致雜湊表塞不進配置的記憶體區塊。

這種切分甚至可能發生在原本規劃為單趟連接的情況。事實上單趟與雙趟連接使用同一套演算法、同一份程式碼；此處分開敘述純粹是為了行文順暢。

而在分佈非均勻的情況下，增加批次數可能無濟於事。例如鍵欄位所有列都是同一個值時，它們會被放進同一批次（雜湊函式一再回傳相同的值）——雜湊表會不顧一切限制持續增長。理論上這可用「對批次做部分掃描」的多趟連接解決，但目前不支援。

實測（刻意讓規劃器低估列數十倍）：

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM bookings_copy b JOIN tickets t ON b.book_ref = t.book_ref;
 Hash Join (actual rows=2949857 loops=1)
   −> Hash (actual rows=2111110 loops=1)
       Buckets: 65536 (originally 65536) Batches: 32 (originally 8)
         Memory Usage: 4040kB

批次數從規劃的 8 個在執行期成長到 32 個。

類似情況也可能發生在「雜湊表是為另一個連接操作的結果集建立」時——此時沒有可靠的統計可用。

平行計畫中的雜湊連接#

上述雜湊連接演算法也可用於平行計畫：多個平行行程各自建立自己的（完全相同的）內集合雜湊表，然後並行處理外集合。效能提升來自每個行程只掃描自己那份外側列。

=> SET enable_parallel_hash = off;
=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT count(*) FROM bookings b JOIN tickets t ON t.book_ref = b.book_ref;
 ...
                   −> Hash Join (actual rows=983286 loops=3)
                       −> Parallel Index Only Scan using tickets_book_ref...
                       −> Hash (actual rows=2111110 loops=3)
                           Buckets: 4194304 Batches: 1 Memory Usage: 113172kB
                           −> Seq Scan on bookings b (actual rows=2111110...

平行單趟雜湊連接#

儘管一般的雜湊連接在平行計畫中也能相當有效率（尤其對「平行處理沒什麼意義」的小內集合），較大的資料集用專用的平行雜湊連接演算法處理更好。

平行版本的重要區別是：雜湊表建立在共享記憶體中，該記憶體動態配置、可被所有參與連接的平行行程存取。

不是建立數個獨立的雜湊表，而是建立單一共用的雜湊表，它使用所有參與行程專用記憶體的總和——這提高了單趟完成連接的機會。

第一階段（計畫中的 Parallel Hash 節點）：所有平行行程共同建立一個雜湊表，善用對內集合的平行存取。要往下走，每個平行行程都必須完成自己那份第一階段的處理。

第二階段（Parallel Hash Join 節點）：行程再度平行運行，把各自那份外集合列與已建好的雜湊表比對。

=> SET work_mem = '64MB';
 ...
                   −> Parallel Hash Join (actual rows=983286 loops=3)
                       −> Parallel Index Only Scan using tickets_book_ref...
                       −> Parallel Hash (actual rows=703703 loops=3)
                           Buckets: 4194304 Batches: 1 Memory Usage: 115392kB
                           −> Parallel Seq Scan on bookings b ...

儘管可用記憶體比前面示範的一般雜湊連接少了一半，操作仍以單趟完成，因為它使用了所有平行行程配置的記憶體。雜湊表稍微大了一點，但由於現在只有這一個，記憶體總用量反而下降了。

平行雙趟雜湊連接#

所有平行行程的合併記憶體仍可能不足以容納整個雜湊表。這可能在規劃階段就明朗，也可能在查詢執行期間才發現。此時套用的雙趟演算法與前面所見大不相同。

這個演算法的關鍵區別是：它建立數個較小的雜湊表，而非單一大表。每個行程拿到自己的表、獨立處理自己的批次。（但由於這些獨立的雜湊表仍位於共享記憶體中，任何行程都能存取任何一張表。）

若規劃顯示需要多於一個批次，就立刻為每個行程建立獨立的雜湊表；若是在執行階段才做的決定，則重建雜湊表。

第一階段：行程平行掃描內集合，把它切成批次並寫入暫存檔。

由於每個行程只讀取自己那份內集合，沒有任何行程能為任何批次（連第一個也是）建立完整的雜湊表。任一批次的完整列集合只在「由所有平行行程以同步方式寫入的檔案」中累積。

因此與非平行版本及平行單趟版本不同，平行雙趟雜湊連接把所有批次都寫到磁碟，包括第一個。

第二階段：先平行掃描外集合，把其列分配到各批次，每個批次寫入獨立的暫存檔。

掃描到的列不會被插入雜湊表（不像第一階段），因此批次數不會再增加。

所有行程完成外集合掃描後，磁碟上會有 2N 個暫存檔，含內外集合的批次。

最後：每個行程挑一個批次執行連接——把內集合列載入記憶體中的雜湊表，掃描外集合列並比對。批次連接完成後，該行程再挑下一個尚未處理的批次。

若沒有未處理的批次了，已完成自己批次的行程會開始處理另一個行程正在處理的批次——這種並行處理之所以可能，正是因為所有雜湊表都位於共享記憶體中。

這種做法比「所有行程共用一個大雜湊表」更有效率：平行處理更容易安排，同步也更便宜。

連接類型的變體#

雜湊連接演算法支援所有類型的連接：除了內連接，還能處理左、右、全外連接，以及半連接與反連接。

一個值得注意的現象——SQL 中的邏輯左連接，在執行計畫中被轉換成實體的右連接操作：

=> EXPLAIN (costs off)
SELECT * FROM bookings b
  LEFT OUTER JOIN tickets t ON t.book_ref = b.book_ref;
 Hash Right Join
   Hash Cond: (t.book_ref = b.book_ref)
   −> Seq Scan on tickets t
   −> Hash
       −> Seq Scan on bookings b

實體層級：內外集合的指派依連接成本而非查詢文字中的位置決定，通常意味著雜湊表較小的集合會被當作內集合。此處 bookings 被用作內集合，左連接因而變成右連接。

反之，查詢若指定右外連接，執行計畫就會使用左連接（Hash Left Join）。

相異值與分組#

用於聚合分組與去除重複的演算法，與連接演算法非常相似。其中一種做法是在所需欄位上建立雜湊表：只有雜湊表中尚無該值時才把值加入——結果雜湊表就累積了所有相異值。

執行雜湊聚合的節點稱為 HashAggregate。它出現在幾種情境中：

-- GROUP BY
=> EXPLAIN (costs off) SELECT fare_conditions, count(*)
FROM seats GROUP BY fare_conditions;
 HashAggregate
   Group Key: fare_conditions
   −> Seq Scan on seats

-- DISTINCT
=> EXPLAIN (costs off) SELECT DISTINCT fare_conditions FROM seats;
 HashAggregate
   Group Key: fare_conditions
   −> Seq Scan on seats

-- UNION
=> EXPLAIN (costs off) SELECT fare_conditions FROM seats
UNION SELECT NULL;
 HashAggregate
   Group Key: seats.fare_conditions
   −> Append
       −> Seq Scan on seats
       −> Result

雜湊表所用記憶體同樣受 work_mem × hash_mem_multiplier 限制。

單批次（雜湊表塞得進）：

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT DISTINCT amount FROM ticket_flights;
 HashAggregate (actual rows=338 loops=1)
   Group Key: amount
   Batches: 1 Memory Usage: 61kB
   −> Seq Scan on ticket_flights (actual rows=8391852 loops=1)

多批次（PostgreSQL 13 起）：

雜湊表一填滿配置的記憶體，後續所有值就被溢寫到暫存檔，並依其雜湊值的若干位元分組成分區（partition）。

分區數是 2 的次方，選擇原則是讓每個分區的雜湊表都塞得進配置的記憶體。估算準確度當然取決於所蒐集統計的品質，因此算出的數字還會乘以 1.5，以進一步縮小分區、提高單趟處理每個分區的機會。

流程是：整個集合掃描完畢後，節點先回傳「已進入雜湊表之值」的聚合結果；接著清空雜湊表，逐一掃描並處理前一階段存入暫存檔的各分區，就像處理任何其他列集合一樣。若雜湊表仍超出配置的記憶體，溢出的列會再次被分區並寫到磁碟。

雙趟雜湊連接會把 MCV 移進第一批次以避免過多 I/O，但聚合不需要這項最佳化：塞得進配置記憶體的列不會被切分成分區，而 MCV 很可能夠早出現、剛好進得了 RAM。

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT DISTINCT flight_id FROM ticket_flights;
 HashAggregate (actual rows=150588 loops=1)
   Group Key: flight_id
   Batches: 5 Memory Usage: 4145kB Disk Usage: 98184kB
   −> Seq Scan on ticket_flights (actual rows=8391852 loops=1)

此例中相異 ID 數量相對多，雜湊表塞不進配置的記憶體，共需 5 個批次：1 個處理初始資料集，4 個處理寫到磁碟的分區。