一般索引掃描#

索引提供的 TID 存取方式有兩種基本形態，第一種是索引掃描（index scan）。多數（但非全部）索引存取方法具備 INDEX SCAN 屬性以支援此操作。

計畫中以 Index Scan 節點表示：

=> EXPLAIN SELECT * FROM bookings
WHERE book_ref = '9AC0C6' AND total_amount = 48500.00;
 Index Scan using bookings_pkey on bookings
   (cost=0.43..8.45 rows=1 width=21)
   Index Cond: (book_ref = '9AC0C6'::bpchar)
   Filter: (total_amount = 48500.00)

索引掃描期間，存取方法逐一回傳 TID。索引引擎收到 TID 後存取該 TID 所指的 heap 頁面、取得對應元組，若符合可見性規則就回傳所要求的欄位集合。此過程持續到存取方法用盡符合查詢的 TID 為止。

索引與 heap 的存取操作由同一個 Index Scan 節點處理，而非兩個不同節點。但另有獨立的 Tid Scan 節點，用於事先已知元組 ID 時直接從 heap 取元組：

=> EXPLAIN SELECT * FROM bookings WHERE ctid = '(0,1)'::tid;
 Tid Scan on bookings (cost=0.00..4.01 rows=1 width=21)
   TID Cond: (ctid = '(0,1)'::tid)

成本估算的兩個部分#

索引掃描的成本估算由索引存取操作與 heap 頁面讀取兩部分構成。

索引部分完全取決於特定的存取方法。對 B-tree 而言，成本主要來自取得索引頁面與處理其項目：

• 待讀取的頁數與列數由資料總量與過濾條件的選擇性決定
• 索引頁面是隨機存取的（邏輯結構上相鄰的頁面在磁碟上是散落的）
• 估算再加上「從根走到葉節點」與「計算所需運算式」所耗的 CPU 資源

heap 部分包括 heap 頁面存取成本與處理所有取得元組所需的 CPU 時間。

好情境：高相關性#

若元組在磁碟上的實體順序與索引中 TID 的邏輯順序完美相關，每個頁面只會被存取一次：Index Scan 節點循序地一頁接一頁走，逐一讀取元組。

=> SELECT attname, correlation
FROM pg_stats WHERE tablename = 'bookings'
ORDER BY abs(correlation) DESC;
   attname    | correlation
−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
 book_ref     |             1
 total_amount | 0.0026738467
 book_date    | 8.02188e−05

本例中 book_ref 的高相關性當然是因為資料是依該欄位升冪載入表格、且尚未有任何更新。對該欄位上的索引執行 CLUSTER 也會得到同樣的結果。

• 任何列更新都會把產生的元組移到表格末尾
• 依其他欄位做索引掃描的計畫會以不同順序回傳結果
• 甚至循序掃描也可能不是從表格開頭開始的

所以若你需要特定順序，就該在 ORDER BY 子句中明確定義它。

成本計算示範#

=> EXPLAIN SELECT * FROM bookings WHERE book_ref < '100000';
 Index Scan using bookings_pkey on bookings
   (cost=0.43..4638.91 rows=132999 width=21)
   Index Cond: (book_ref < '100000'::bpchar)

該條件的選擇性約為 0.0630（接近 1/16，這可從 book_ref 值域為 000000–FFFFFF 推知）。

索引部分的 I/O：滿足 B-tree 所支援條件的索引項目，存放在被串成有序清單的頁面中，因此待讀索引頁數估算為索引大小 × 選擇性。但由於這些頁面實體上無序，讀取以隨機方式進行（random_page_cost）。

索引部分的 CPU：處理所有讀取的索引項目（每項 cpu_index_tuple_cost = 0.005），並為每項計算條件（cpu_operator_cost = 0.0025）。

表格存取視為循序讀取所需數量的頁面。完美相關時，heap 元組在磁碟上彼此相鄰，因此頁數估算為表格大小 × 選擇性（seq_page_cost），再加上每元組 cpu_tuple_cost = 0.01 的處理成本。

idx_cost | tbl_cost | total
−−−−−−−−−−+−−−−−−−−−−+−−−−−−−
    2457 |     2177 | 4634

與規劃器給出的 4638.91 相符（近似）。

壞情境：低相關性#

相關性低時一切都變了。在幾乎零相關的 book_date 欄位上建索引，並查詢與前例選出比例相近的列——索引存取變得如此昂貴，規劃器只有在所有其他選項都被明確禁止時才會選它：

=> CREATE INDEX ON bookings(book_date);
=> SET enable_seqscan = off;
=> SET enable_bitmapscan = off;
=> EXPLAIN SELECT * FROM bookings
WHERE book_date < '2016-08-23 12:00:00+03';
 Index Scan using bookings_book_date_idx on bookings
   (cost=0.43..56957.48 rows=132403 width=21)

原因是：低相關性提高了「存取方法回傳的下一個元組位於不同頁面」的機率。因此 Index Scan 節點必須在頁面之間跳躍而非循序讀取；最壞情況下，頁面存取次數可達取得元組的數量。

快取如何被納入模型#

但我們不能單純把好情境計算中的 seq_page_cost 換成 random_page_cost、relpages 換成 reltuples——那樣算出的 535,787 遠高於計畫顯示的 56,957。

就規劃目的而言，快取大小由 effective_cache_size（預設 4 GB）定義——它的值越小，預期要讀的頁面就越多。

估算落在兩條虛線之間：最佳情境（完美相關時為頁數的一半）與最壞情境（零相關且無快取時為列數的一半）。

把 effective_cache_size 降到最小，計畫估算就接近無快取的低端值（532,745）。規劃器會為最壞與最佳情境分別計算表格 I/O 成本，再依實際相關性取中間值。

• 若 heap 元組與存取方法回傳 ID 的順序相關，這個「一小部分」可以相當大
• 但相關性低時（而這常見得多），對選擇性低的查詢，索引掃描的吸引力就大幅下降

唯索引掃描#

若索引含有查詢所需的全部 heap 資料，它對該特定查詢就稱為覆蓋索引（covering index）。有這樣的索引時就能避免額外的表格存取：存取方法可以直接回傳實際資料而非 TID——這種索引掃描稱為唯索引掃描（index-only scan），可被支援 RETURNABLE 屬性的存取方法使用。

=> EXPLAIN SELECT book_ref FROM bookings WHERE book_ref < '100000';
 Index Only Scan using bookings_pkey on bookings
   (cost=0.43..3791.91 rows=132999 width=7)
   Index Cond: (book_ref < '100000'::bpchar)

在 PostgreSQL 中，索引不含元組可見性資訊，因此存取方法會回傳所有滿足過濾條件的 heap 元組資料，即使目前交易看不到它們；可見性隨後由索引引擎檢查。

然而若這個方法必須存取表格來檢查每個元組的可見性，那它就與一般索引掃描沒有差別了。它改為運用表格的可見性映射——清理行程在其中標記「只含全可見元組」的頁面。若存取方法回傳的 TID 屬於這類頁面，就不需檢查可見性。

唯索引掃描的成本估算取決於 heap 中全可見頁面的比例：

=> SELECT relpages, relallvisible FROM pg_class WHERE relname = 'bookings';
 relpages | relallvisible
−−−−−−−−−−+−−−−−−−−−−−−−−−
    13447 |         13446

與一般索引掃描的差別在於：表格存取相關的 I/O 成本，按「未出現在可見性映射中的頁面比例」計算（元組處理的成本估算則相同）。本例中所有頁面都只含全可見元組，因此 heap I/O 成本實質上被排除（1330 vs. 2177）。

實測：新建的表格必須檢查所有元組的可見性（Heap Fetches: 132109）；一旦執行 VACUUM，只要所有頁面維持全可見，這項檢查就變得多餘、不再執行（Heap Fetches: 0）。

INCLUDE 子句#

並非總能把查詢所需的全部欄位都加進索引：

• 對唯一索引而言，加入新欄位會破壞原本鍵欄位的唯一性
• 索引存取方法可能沒有為待加入欄位的資料型別提供運算子類別

此時仍可把欄位 include 進索引而不使其成為索引鍵的一部分（PostgreSQL 11 起）。當然，無法依被 include 的欄位做索引掃描，但若查詢參照這些欄位，該索引就能作為覆蓋索引運作。

=> CREATE UNIQUE INDEX ON bookings(book_ref) INCLUDE (book_date);
-- 替換掉自動建立的主鍵索引後
=> EXPLAIN SELECT book_ref, book_date
FROM bookings WHERE book_ref < '100000';
 Index Only Scan using bookings_pkey on bookings (cost=0.43..437...

這類索引常被稱為 covering index，但這並不完全正確。索引是否為覆蓋索引，取決於它的欄位集合是否涵蓋某特定查詢所需的全部欄位——與是否用到 INCLUDE 子句加入的欄位無關。

而且同一個索引可能對某個查詢是覆蓋的，對另一個則不是。

點陣圖掃描#

索引掃描的效率有其限制：相關性下降時，heap 頁面的存取次數上升，掃描從循序變成隨機。

為突破這個限制，PostgreSQL 可以在存取表格之前先取得所有 TID，並依其頁碼升冪排序——這正是點陣圖掃描（bitmap scan）的運作方式，可被支援 BITMAP SCAN 屬性的存取方法使用。

與一般索引掃描不同，這個操作在計畫中由兩個節點表示：

=> EXPLAIN SELECT * FROM bookings WHERE total_amount = 48500.00;
 Bitmap Heap Scan on bookings (cost=54.63..7040.42 rows=2865 wid...
   Recheck Cond: (total_amount = 48500.00)
   −> Bitmap Index Scan on bookings_total_amount_idx
       (cost=0.00..53.92 rows=2865 width=0)
       Index Cond: (total_amount = 48500.00)

Bitmap Index Scan 節點從存取方法取得所有 TID 的點陣圖。

點陣圖由多個區段（segment）構成，每個對應一個 heap 頁面。所有區段大小相同，足以容納該頁面的所有元組——這個數量是有上限的，因為元組標頭相當大，標準大小的頁面最多容納 291 個元組，剛好塞進 37 位元組。

Bitmap Heap Scan 逐區段走訪點陣圖、讀取對應頁面，並檢查所有被標記為全可見的元組。

因此頁面依頁碼升冪讀取，每頁剛好只讀一次。

非同步預取#

這個過程與循序掃描仍然不同，因為被存取的頁面很少彼此相鄰，作業系統的一般預取幫不上忙。

因此 Bitmap Heap Scan 節點實作了自己的預取機制，以非同步方式讀取 effective_io_concurrency（預設 1）個頁面——它是唯一這麼做的節點。這個機制依賴某些作業系統實作的 posix_fadvise 函式；若你的系統支援，依硬體能力在表空間層級設定 effective_io_concurrency 是合理的。

非同步預取也被其他內部程序使用：

• heap 列被刪除時的索引頁面（PostgreSQL 14 起）
• 分析（ANALYZE）期間的 heap 頁面（PostgreSQL 14 起）

這些的預取深度由 maintenance_io_concurrency（預設 10）定義。

點陣圖的精確度#

滿足查詢過濾條件的元組所在頁面越多，點陣圖就越大。它建立在 backend 的本地記憶體中，大小受 work_mem（預設 4 MB）限制。

一旦達到允許的最大大小，某些點陣圖區段會變成「有損」（lossy）：有損區段的每個位元對應整個頁面，該區段本身則涵蓋一段頁面範圍。結果是點陣圖變小，代價是精確度下降。

EXPLAIN ANALYZE 會顯示所建點陣圖的精確度：

-- work_mem 足夠：精確點陣圖
 Bitmap Heap Scan on bookings (actual rows=242691 loops=1)
   Recheck Cond: (total_amount > 150000.00)
   Heap Blocks: exact=13447

-- SET work_mem = '512kB' 之後
 Bitmap Heap Scan on bookings (actual rows=242691 loops=1)
   Recheck Cond: (total_amount > 150000.00)
   Rows Removed by Index Recheck: 1145721
   Heap Blocks: exact=5178 lossy=8269

讀取對應有損區段的 heap 頁面時，PostgreSQL 必須為該頁每個元組重新檢查過濾條件。

待重新檢查的條件永遠顯示為 Recheck Cond，即使實際上沒有執行這項重新檢查。重新檢查期間被濾掉的元組數另外顯示為 Rows Removed by Index Recheck。

若結果集太大，即使所有區段都變成有損，點陣圖仍可能塞不進 work_mem。此時這個限制會被忽略，點陣圖佔用所需的空間——PostgreSQL 既不會進一步降低精確度，也不會把任何區段刷到磁碟。

點陣圖上的操作#

若查詢對多個各有索引的表格欄位施加條件，點陣圖掃描可同時使用多個索引：各索引即時建立自己的點陣圖，再逐位元合併——AND 連接用邏輯合取，OR 連接用邏輯析取。

=> EXPLAIN (costs off)
SELECT * FROM bookings
WHERE book_date < '2016-08-28' AND total_amount > 250000;
 Bitmap Heap Scan on bookings
   Recheck Cond: ((total_amount > '250000'::numeric) AND (book_da...
   −> BitmapAnd
       −> Bitmap Index Scan on bookings_total_amount_idx
       −> Bitmap Index Scan on bookings_book_date_idx

兩個點陣圖合併時：精確區段兩兩合併後仍精確（若新點陣圖塞得進 work_mem），但只要配對中任一區段有損，結果區段就有損。

成本估算#

Bitmap Index Scan 的總成本估算方式與「不考慮 heap 存取的一般索引掃描」相同。

Bitmap Heap Scan 的 I/O 估算則與「完美相關的一般索引掃描」不同：點陣圖讓 heap 頁面能依頁碼升冪讀取、不必回頭；但滿足過濾條件的元組不再彼此相鄰——PostgreSQL 讀的不是一段緊湊的循序頁面範圍，而很可能存取多得多的頁面。

待讀頁數的估算公式：

min( 2 × relpages × reltuples × sel / (2 × relpages + reltuples × sel),  relpages )

I/O 估算再加上每個取得元組的處理成本：

• 精確點陣圖 → 元組數估算為表格總元組數 × 過濾條件選擇性
• 有損區段 → PostgreSQL 必須存取對應頁面以重新檢查其所有元組

因此估算會納入預期的有損區段比例（PostgreSQL 13 起），可依選出的總列數與 work_mem 所定義的點陣圖大小上限推算。條件重新檢查的總成本也會提高估算（不論點陣圖精確度如何）。

Bitmap Heap Scan 的啟動成本基於 Bitmap Index Scan 的總成本，再加上點陣圖處理的成本。

平行索引掃描#

三種索引掃描模式——一般索引掃描、唯索引掃描、點陣圖掃描——都有各自的平行計畫版本。

平行執行的成本估算方式與循序相同，但（就像平行循序掃描一樣）CPU 資源分攤到所有平行行程，從而降低總成本；I/O 分量不分攤，因為行程被同步以循序方式存取頁面。

平行索引掃描（Parallel Index Scan）的運作方式：

B-tree 的平行掃描進行時，目前索引頁面的 ID 保存在伺服器共享記憶體中。初始值由啟動掃描的行程設定：它從根走到第一個合適的葉頁面並存下其 ID。

工作者依需要存取後續索引頁面並替換保存的 ID。取得頁面後，工作者迭代其中所有合適的項目並讀取對應的 heap 元組。當工作者讀完滿足查詢過濾條件的整個值域，掃描即完成。

平行唯索引掃描（Parallel Index Only Scan）：唯一的差別是對全可見頁面跳過 heap 存取。

平行點陣圖掃描：

點陣圖永遠由單一領導行程循序建立——正因如此，Bitmap Index Scan 節點的名稱不含 Parallel 字樣。

點陣圖就緒後，Parallel Bitmap Heap Scan 節點才啟動平行的 heap 掃描，工作者存取後續 heap 頁面並並行處理。

各存取方法的比較#

各存取方法的成本如何隨過濾條件選擇性變化（定性描述，實際數字當然取決於特定表格與伺服器組態）：

規劃器必須做大量計算，才能估算每種方法在每個特定情況下的效率。顯然，這些估算的準確度高度取決於所蒐集統計的準確度。