PostgreSQL 索引掃描
根據直播內容整理而成，錄播地址：https://www.bilibili.com/video/BV13a4y1T7jd
索引概述
數據庫索引，是將一個表的某些字段的數據進行重新組織的數據庫對象，通過使用索引，可以大大加速數據庫的一些操作，其背後的思想也很簡單樸素：空間換時間。
數據庫中的索引，可以類比爲一本書的目錄，當我們在書中查詢某信息的時候，藉助目錄，可以快速定位到對應的章節，從而避免了從整本書中去翻閱，加速了查找的過程。
索引分類
Postgres 中常見的索引大致有下面的這幾種，其中 BTree 索引是使用最廣泛的，也是創建索引時默認的選項。
索引掃描的例子
下面通過一個例子來體會索引對錶掃描的性能的影響。我們首先創建一個測試表，例如叫 articles，並向其中插入一些測試的數據。
CREATE TABLE articles (
id SERIAL8 NOT NULL PRIMARY KEY,
a text,
b text,
c text
);
INSERT INTO articles(a, b, c)
SELECT
md5(random()::text),
md5(random()::text),
md5(random()::text)
from (
SELECT * FROM generate_series(1,1000000) AS id
) AS x;我們從這個表中查詢一條數據，例如查找 a = '65c966eb2be73daf418c126df8dc33b5' 的數據，其查詢計劃如下：
掃描方法
順序掃描
當對無索引的字段進行查詢，或者判斷到查詢將返回大多數數據時，查詢優化器將會使用順序掃描方法。還是以之前的 articles 表爲例，這裏我們查詢了 id > 100 的數據，包含了大部分該表中的數據，所以儘管 id 列上有索引，但還是會使用順序掃描。
索引掃描
如果判斷到查詢將會命中非常少量的數據時，查詢優化器將會選擇索引掃描方法，上面的例子已經有對應的展示了。下面是一個掃描索引範圍的例子，可以看到命中數據佔表數據的少量，選擇索引掃描是最高效的。
位圖索引掃描
儘管索引掃描的數據量一般較少，但是這個掃描需要隨機 IO 操作，因此對比順序掃描使用的順序 IO 操作，它的代價並不總是更小。所以在命中適中數據（少量與多數之間），順序掃描和索引掃描各自都有缺陷。針對這種情況，一般可以採用位圖索引掃描，其原理是將需要訪問的頁面有序化，將隨機 IO 轉爲順序 IO。
-
使用索引掃描到滿足條件的所有 TID
-
用 TID 列表按照頁面的訪問順序構建一個位圖
-
讀取數據記錄時，同一個頁面只需要讀取一次
下圖描述了 Postgres 中幾種表數據掃描的方式，查詢優化器會根據計算的代價選擇最優的掃描方法。
索引物理存儲
postgres 中的索引是一種二級索引，即在物理存儲上，索引數據和對應的表數據是分離開的。每個特定的索引對象都存儲爲了一張獨立的關係表，並且都能夠在 pg_class 系統表中查詢到。
-
樹層級更少：每個內部節點不再存儲數據，因此能存儲的鍵值會更多，於是導致樹的層級更少且查詢數據也更快（減少了隨機 IO）
-
查詢速度更穩定：因爲所有數據都存在葉子節點上，因此每次查找的次數（樹的高度次隨機 IO 操作）都相同，查詢速度也要更穩定
-
遍歷查詢更方便：B+Tree 的葉子節點數據構成了一個有序鏈表，在遍歷查詢時，首先定位第一個鍵值的位置，然後沿着鏈表即可訪問到全部數據
BTree 中的每一個節點在物理結構上存儲爲一個 page，page 的結構和 heap 表的類似，如下：
索引創建
當用戶使用 create index on table (col) 語句後，將會經過語法解析、權限檢查等階段，然後建立索引關係，更新系統元數據，最後使用表中的數據構建一個完整的 B-Tree 索引。
主要的函數調用路徑如下：
ProcessUtility() Utility語句的處理入口
DefineIndex() 定義一個索引（異常判斷，準備index_create()的輸入參數）
index_create() 創建一個索引（建立關係文件並更新系統表數據）
index_build() 構建索引的外層接口
bt_build() B-Tree的索引構建邏輯以 BTree 爲例，使用表中的數據來構建 B-Tree 索引總體分爲兩步，一是將表中的數據排序，二是根據有序的數據元組，遍歷自底向上構建整個 BTree。
這裏主要是會針對不同的索引類型，調用不同的 ambuild 方法，其中 BTree 對應的方法是 btbuild，下圖是索引相關接口的訪問關係，不同的索引訪問方法通過 IndexAM 進行抽象，供上層執行器調用。
索引掃描
索引掃描在執行器中的三個步驟分別是
-
ExecInitIndexScan
-
ExecIndexScan
-
ExecEndIndexScan
ExecInitIndexScan
主要負責初始化索引掃描的狀態結構體 IndexScanState 核心任務是將索引掃描的過濾條件轉換爲各種類型的掃描鍵 ScanKey。
-
ScanKey 主要存儲了索引列的信息，操作函數以及待比較的函數，ScanKey 描述了一個完整的過濾條件，並用於索引掃描
-
但如果過濾條件是一個複雜的表達式，引入了 iss_RuntimeKeys 來處理
IndexScanState 的主要字段：
Init 階段主要關注的是 ExecIndexBuildScanKeys 方法，此方法的作用是將掃描過濾條件轉化爲各種類型的掃描鍵 ScanKey。
索引的過濾條件分爲了以下五種情況：
-
常數或普通運算，直接存入 ScanKey
-
非常數的值表達式運算，此時執行器節點無法在初始階段得到表達式的結果，需要暫時存入 iss_RuntimeKeys
-
RowCompareExpr，比如過濾條件是 “（indexkey1，indexkey2）> （1，2）”，表示多個過濾條件的組合，遍歷所有的子過濾條件，分別存入 iss_ScanKeys 或者 iss_RuntimeKeys
-
ScalarArrayOpExpr，比如過濾條件是 “indexkey1 = ANY（1,10,20）”，如果索引支持處理基於數組的搜索，分別將常數存入 ScanKey 或者 RuntimeKey，如果不支持數組搜索，例如 Hash、GIN、Gist 索引，則將過濾條件存入 arrayKeys
-
NullTest，索引鍵是否爲 NULL，例如_"indexkey IS NULL/IS NOT NULL"，設置 ScanKey 對應的值即可_
ExecIndexScan
負責基於索引讀取元組，並返回給執行器上層節點。函數 IndexNext 不斷進行索引掃描，讀取元組，並將元組封裝進 TupleTableSlot 傳遞給上層節點。
-
此函數的主要參數是 IndexScanDesc，保存了 scan 過程中的狀態信息
-
通過 xs_heap_continue 判斷是否在 HOT 鏈上，如果是的話不做任何操作
-
否則調用 index_getnext_tid 返回一個 TID
-
在 pg_am 表中查找 amgettuple 對應的內層接口函數
-
調用這個函數（例如 BTree 中的 btgettuple），根據具體的索引實現返回一個 TID
-
調用 index_fetch_heap 獲取實際的元組
ExecEndIndexScan
主要負責清理工作，釋放計算 RuntimeKey 的內存上下文，並關閉相關索引表和數據表。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/XuPHVSnLcInMmkXDigDKBQ