索引與可擴充性#

索引是主要用來加速資料存取的資料庫物件。它們是輔助結構：任何索引都能被刪除、再依 heap 資料重建。除了加速存取，索引也用來強制某些完整性約束。

PostgreSQL 核心提供六種內建索引存取方法（索引類型）：

=> SELECT amname FROM pg_am WHERE amtype = 'i';
 btree | hash | gist | gin | spgist | brin

PostgreSQL 的可擴充性意味著新的存取方法可以在不修改核心的情況下加入。其中一個這樣的擴充（bloom 方法）就包含在標準模組集合中。

儘管各種索引類型差異甚大，它們最終都是把鍵（例如被索引欄位的值）對應到含有該鍵的 heap 元組。元組以六位元組的元組 ID（TID）指涉。知道鍵或鍵的某些資訊，就能快速讀取可能含有所需資料的元組，而不必掃描整張表。

索引引擎#

為確保新的存取方法能以擴充形式加入，PostgreSQL 實作了一個通用索引引擎。它的主要職責是取得並處理特定存取方法回傳的 TID：

• 從對應的 heap 元組讀取資料
• 依特定快照檢查元組可見性
• 若存取方法的條件求值結果不確定，就重新檢查條件

索引引擎也參與最佳化階段所建計畫的執行。評估各種執行路徑時，最佳化器需要知道所有潛在可用存取方法的屬性：

• 該方法能以所需順序回傳資料嗎？還是需要獨立的排序階段？
• 能立刻回傳前幾個值嗎？還是必須等整個結果集取完？

不只最佳化器需要知道存取方法的細節。索引建立還提出更多問題：該存取方法支援多欄位索引嗎？這個索引能保證唯一性嗎？

存取方法負責處理的任務：

• 實作建立索引、插入與刪除索引項目的演算法
• 在頁面之間分配索引項目（後續交由緩衝快取管理器處理）
• 實作清理演算法
• 取得鎖以確保正確的並行運作
• 產生 WAL 條目
• 依鍵搜尋被索引資料
• 估算索引掃描成本

運算子類別#

可擴充性也體現在新增資料型別的能力上——而存取方法事先對這些型別一無所知。因此存取方法必須定義自己的介面，以便插入任意資料型別。

要讓新資料型別能與特定存取方法搭配使用，你必須實作對應的介面：提供可與索引搭配使用的運算子，以及可能的一些輔助支援函式。這樣一組運算子與函式稱為運算子類別（operator class）。

索引邏輯部分由存取方法本身實作，部分外包給運算子類別。這種分配相當隨意：B-tree 把所有邏輯都寫死在存取方法中，而其他方法可能只提供主要框架，把實作細節全交給特定的運算子類別。

同一種資料型別常由數個運算子類別支援，使用者可挑選行為最合適的那個。

運算子類別與運算子族#

運算子類別#

存取方法介面由運算子類別實作，它是存取方法套用於特定資料型別的一組運算子與支援函式。運算子類別存放在系統目錄的 pg_opclass 表格中。

多數情況我們不必了解運算子類別——只要建立使用預設運算子類別的索引即可。例如支援 text 型別的 B-tree 運算子類別有四個，其中一個永遠被標記為預設：

       opcname       | opcdefault
−−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−
 text_ops            | t
 varchar_ops         | f
 text_pattern_ops    | f
 varchar_pattern_ops | f

因此典型的建立索引指令：

CREATE INDEX ON aircrafts(model, range);

其實只是以下語法的簡寫：

CREATE INDEX ON aircrafts
USING btree -- 預設存取方法
(
   model text_ops, -- text 的預設運算子類別
   range int4_ops -- integer 的預設運算子類別
);

策略編號#

為特定存取方法與資料型別定義的每個運算子類別，都必須含有一組「接受該型別參數、且實作該存取方法語意」的運算子。

例如 btree 存取方法定義了五個必要的比較運算子，任何 btree 運算子類別都必須全部含有：

     opcname      | amopstrategy |     amopopr
−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−
 text_ops         |            1 | <(text,text)
 text_ops         |            2 | <=(text,text)
 text_ops         |            3 | =(text,text)
 text_ops         |            4 | >=(text,text)
 text_ops         |            5 | >(text,text)
 text_pattern_ops |            1 | ~<~(text,text)
 text_pattern_ops |            2 | ~<=~(text,text)
 text_pattern_ops |            3 | =(text,text)
 text_pattern_ops |            4 | ~>=~(text,text)
 text_pattern_ops |            5 | ~>~(text,text)

存取方法所隱含的運算子語意，由 amopstrategy 顯示的策略編號反映。例如 btree 的策略 1 表示「小於」、2 表示「小於或等於」等等——運算子本身可以取任意名稱。

上例顯示了兩種運算子。帶波浪號者不考慮定序（collation），執行字串的逐位元比較；儘管如此，兩者實作的是相同的邏輯比較操作。

text_pattern_ops 的實際價值#

text_pattern_ops 運算子類別是為了解決 ~~ 運算子（對應 LIKE）支援上的限制而設計的。在使用 C 以外任何定序的資料庫中，這個運算子無法使用 text 欄位上的一般索引：

=> CREATE INDEX ON tickets(passenger_name);
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE passenger_name LIKE 'ELENA%';
 Seq Scan on tickets
   Filter: (passenger_name ~~ 'ELENA%'::text)

使用 text_pattern_ops 運算子類別的索引行為就不同了：

=> CREATE INDEX tickets_passenger_name_pattern_idx
ON tickets(passenger_name text_pattern_ops);
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE passenger_name LIKE 'ELENA%';
 Bitmap Heap Scan on tickets
   Filter: (passenger_name ~~ 'ELENA%'::text)
   −> Bitmap Index Scan on tickets_passenger_name_pattern_idx
       Index Cond: ((passenger_name ~>=~ 'ELENA'::text) AND
       (passenger_name ~<~ 'ELENB'::text))

注意 Index Cond 中過濾運算式的變化：搜尋現在只使用 % 之前的樣板前綴，偽陽性命中則在 Filter 條件的重新檢查中被濾掉。

btree 存取方法的運算子類別沒有提供比較樣板的運算子，套用 B-tree 的唯一方式就是用比較運算子改寫這個條件。text_pattern_ops 的運算子不考慮定序，這才讓我們有機會改用等價的條件。

索引被使用的兩個前提#

索引要能依過濾條件加速存取，必須滿足：

1. 條件寫成「被索引欄位 運算子 運算式」的形式（若該運算子指定了交換對應運算子，條件也可寫成「運算式 運算子 被索引欄位」）
2. 該運算子屬於索引宣告中為該被索引欄位所指定的運算子類別

=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE 'ELENA BELOVA' = passenger_name;
 Index Scan using tickets_passenger_name_idx on tickets
   Index Cond: (passenger_name = 'ELENA BELOVA'::text)

注意 Index Cond 中參數的位置：執行階段被索引欄位必須在左側。參數被置換時，運算子會被換成交換對應者；本例中因等於關係可交換，所以是同一個運算子。

運算式索引#

以下查詢中，由於條件裡的欄位名稱被函式呼叫取代，技術上無法使用一般索引：

=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE initcap(passenger_name) = 'Elena Belova';
 Seq Scan on tickets

此時可用運算式索引——宣告中以任意運算式取代欄位：

=> CREATE INDEX ON tickets( (initcap(passenger_name)) );
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE initcap(passenger_name) = 'Elena Belova';
 Bitmap Heap Scan on tickets
   −> Bitmap Index Scan on tickets_initcap_idx

換言之，若運算式含有任何函式呼叫，這些函式必須是 IMMUTABLE 且確實遵守該 volatility 類別。否則索引掃描與 heap 掃描對同一查詢可能回傳不同結果。

支援函式#

除了一般運算子，運算子類別還可提供存取方法所需的支援函式。例如 btree 定義了五個支援函式，第一個（比較兩個值）是必要的，其餘皆可缺席：

 amprocnum |       amproc
−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−
         1 | bttextcmp
         2 | bttextsortsupport
         4 | btvarstrequalimage

運算子族#

每個運算子類別永遠屬於某個運算子族（pg_opfamily）。一個族可包含數個「以相同方式處理相似資料型別」的類別。

例如 integer_ops 族包含數個語意相同但大小不同的整數型別類別：

 opcname | opcintype
−−−−−−−−−−+−−−−−−−−−−−
 int2_ops | smallint
 int4_ops | integer
 int8_ops | bigint

datetime_ops 族則包含處理日期的運算子類別（date_ops、timestamptz_ops、timestamp_ops）。

雖然每個運算子類別只支援單一資料型別，但一個族可包含多種資料型別的運算子類別。

拜這種把各種運算子歸入單一族的分組方式之賜，當索引用於涉及不同型別值的條件時，規劃器不必做型別轉換。

索引引擎介面#

與表格存取方法一樣，pg_am 表格的 amhandler 欄位含有實作介面的函式名稱（bthandler、hashhandler、gisthandler、ginhandler、spghandler、brinhandler）。

這個函式把介面結構中的佔位符填入實際值：有些是負責索引存取各項任務的函式（例如執行索引掃描並回傳 heap 元組 ID），有些則是索引引擎必須知道的索引方法屬性。

所有屬性分為三類：

• 存取方法屬性
• 特定索引的屬性
• 索引的欄位層級屬性

區分存取方法屬性與索引層級屬性是著眼於未來：目前基於特定存取方法的所有索引，在這兩個層級上永遠有相同的屬性。

存取方法屬性#

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
  'can_order', 'can_unique', 'can_multi_col',
  'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'btree';

CAN ORDER：要以所需順序取得結果，你總是可以掃描表格再排序（Sort + Seq Scan）；但若有支援此屬性的索引，資料就能直接以所需順序回傳（Index Scan）。

CAN UNIQUE：每次宣告唯一或主鍵約束，PostgreSQL 都會自動建立唯一索引來支援它。

完整性約束定義的是絕不可被違反的性質，而索引只是保證它的機制。 理論上約束可以用其他手段施加。

例如 PostgreSQL 不支援分割表格的全域索引，但你仍可在這類表格上建立唯一約束（只要它包含分割鍵）。此時全域唯一性由各分割區的本地唯一索引確保，因為不同分割區不可能有相同的分割鍵。

CAN MULTI COL：多欄位索引能加速依多個欄位條件的搜尋。

一般而言，即使過濾條件只涉及其中部分欄位，多欄位索引仍能加速搜尋。以 B-tree 而言，若過濾條件涵蓋索引宣告中最前面的一段欄位，搜尋就會有效率。

其他所有情況下（例如條件只含 flight_id），搜尋實質上只受限於前導欄位（若查詢含對應條件），其餘條件只用來過濾回傳結果。不過其他類型的索引行為可能不同。

CAN EXCLUDE：EXCLUDE 約束保證由某運算子定義的條件對表格中任何一對列都不成立。

通常擔任此角色的是交集運算子 &&。例如可以用它明確宣告：同一時段的會議室不能被預訂兩次，或地圖上的建築物不可重疊。

若用等於運算子，排除約束就帶有唯一性的意涵：禁止表格中有兩列鍵值相同。但這與 UNIQUE 約束不同——排除約束的鍵不能被外鍵參照，也不能用於 ON CONFLICT 子句。

CAN INCLUDE：可用此屬性以額外欄位擴充唯一索引。這種索引仍保證所有鍵欄位的值唯一，而從被 include 的欄位取資料則不需存取 heap：

=> CREATE UNIQUE INDEX ON flights(flight_id) INCLUDE (status);
=> EXPLAIN (costs off)
SELECT status FROM flights WHERE flight_id = 51618;
 Index Only Scan using flights_flight_id_status_idx on flights

索引層級屬性#

=> SELECT p.name, pg_index_has_property('seats_pkey', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);

欄位層級屬性#

=> SELECT p.name,
  pg_index_column_has_property('seats_pkey', 1, p.name)
FROM unnest(array[
  'asc', 'desc', 'nulls_first', 'nulls_last', 'orderable',
  'distance_orderable', 'returnable', 'search_array', 'search_nulls'
]) p(name);

DISTANCE ORDERABLE：與回傳邏輯值的一般索引運算子不同，排序運算子回傳一個表示兩個參數之間「距離」的實數。索引支援在查詢的 ORDER BY 子句中指定這類運算子：

=> CREATE INDEX ON airports_data USING gist(coordinates);
=> EXPLAIN (costs off)
SELECT * FROM airports
ORDER BY coordinates <-> point (43.578,57.593)
LIMIT 3;
 Limit
   −> Index Scan using airports_data_coordinates_idx on airpo...
       Order By: (coordinates <−> '(43.578,57.593)'::point)

RETURNABLE：這個屬性定義索引結構是否允許取回被索引的值。

SEARCH ARRAY：明確使用陣列並非唯一需要它的情況。例如規劃器會把 IN (list) 運算式轉換成陣列掃描：

=> EXPLAIN (costs off)
SELECT * FROM bookings
WHERE book_ref IN ('C7C821', 'A5D060', 'DDE1BB');
 Index Scan using bookings_pkey on bookings
   Index Cond: (book_ref = ANY ('{C7C821,A5D060,DDE1BB}'::bpchar[]))

若索引方法不支援這類運算子，執行器可能得執行多次迭代才能找出各個值——這會使索引掃描效率降低。

SEARCH NULLS：該不該把 NULL 值加入索引？

• 加入的好處：能對 IS [NOT] NULL 條件執行索引掃描；未提供過濾條件時也能把索引當作覆蓋索引使用（此時索引必須回傳所有 heap 元組的資料，包含含 NULL 者）
• 不加入的好處：跳過 NULL 值可縮小索引大小

決定權留給存取方法的開發者，但多數情況下 NULL 值確實會被索引。

部分索引#

若你不需要索引中的 NULL 值，可建立部分索引（partial index），只涵蓋所需的列：

=> CREATE INDEX ON flights(actual_arrival)
WHERE actual_arrival IS NOT NULL;
=> EXPLAIN (costs off)
SELECT * FROM flights
WHERE actual_arrival = '2017-06-13 10:33:00+03';
 Index Scan using flights_actual_arrival_idx on flights

部分索引比完整索引小，而且只有在被修改的列確實被索引時才需更新——這有時能帶來可觀的效能提升。

顯然除了 NULL 檢查，WHERE 子句可提供任何條件（只要能與 immutable 函式搭配使用）。

建立部分索引的能力由索引引擎提供，因此不依賴存取方法。

自然地，這個介面只包含「必須事先知道才能做出正確決策」的索引方法屬性。例如它並未列出支援謂詞鎖或非阻塞索引建立（CONCURRENTLY）之類的屬性——這些性質定義在實作介面的函式程式碼中。