GIN代表通用倒排索引。GIN旨在處理要索引的專案是複合值的情況,並且索引需要處理的查詢需要搜尋複合專案中出現的元素值。例如,專案可以是文件,查詢可以是搜尋包含特定單詞的文件。
我們使用單詞專案來指代要索引的複合值,使用單詞鍵來指代元素值。GIN始終儲存和搜尋鍵,而不是專案值本身。
一個GIN索引儲存一組(鍵,倒排列表)對,其中倒排列表是鍵出現的行 ID 集合。相同的行 ID 可以出現在多個倒排列表中,因為一個專案可以包含多個鍵。每個鍵值只儲存一次,因此一個GIN索引對於同一鍵多次出現的情況非常緊湊。
GIN的通用性在於GIN訪問方法程式碼不需要知道它加速的具體操作。相反,它使用為特定資料型別定義的自定義策略。該策略定義瞭如何從索引項和查詢條件中提取鍵,以及如何確定包含查詢中某些鍵值的行是否實際滿足查詢。
的優點之一是GIN它允許資料型別領域的專家而不是資料庫專家開發具有適當訪問方法的自定義資料型別。這與使用GiST.
該GIN在PostgreSQL中的實現主要由 Teodor Sigaev 和 Oleg Bartunov 維護。有關GIN的更多資訊,請訪問他們的網站。
核心 PostgreSQL 發行版包含GIN運算子類如表 65.3所示。(附錄 F中描述的一些可選模組提供了額外的GIN運算子類。)
表 65.3。內建GIN運算子類
名稱 | 可索引運算子 |
---|---|
array_ops |
&& (anyarray,anyarray) |
@> (anyarray,anyarray) |
|
<@ (anyarray,anyarray) |
|
= (anyarray,anyarray) |
|
jsonb_ops |
@> (jsonb,jsonb) |
@? (jsonb,jsonpath) |
|
@@ (jsonb,jsonpath) |
|
? (jsonb,text) |
|
?| (jsonb,text[]) |
|
?& (jsonb,text[]) |
|
jsonb_path_ops |
@> (jsonb,jsonb) |
@? (jsonb,jsonpath) |
|
@@ (jsonb,jsonpath) |
|
tsvector_ops |
@@ (tsvector,tsquery) |
對於jsonb
型別的兩個運算子類,jsonb_ops
是預設的。jsonb_path_ops
支援較少的運算子,但對這些運算子提供了更好的效能。有關詳細資訊,請參閱第 8.14.4 節。
該GIN介面具有高度抽象性,要求訪問方法實現者只需實現被訪問資料型別的語義。該GIN層本身負責併發、日誌記錄和搜尋樹結構。
要使GIN訪問方法的工作是實現一些使用者定義的方法,這些方法定義了樹中鍵的行為以及鍵、索引項和可索引查詢之間的關係。簡而言之,GIN將可擴充套件性與通用性、程式碼重用和簡潔的介面相結合。
運算子類必須提供兩種方法:GIN必須提供
Datum *extractValue(Datum itemValue, int32 *nkeys, bool **nullFlags)
給定要索引的專案,返回一個 palloc 分配的鍵陣列。返回的鍵的數量必須儲存在*nkeys
中。如果任何鍵可以為空,則還要 palloc 分配一個包含*nkeys
個bool
欄位的陣列,將其地址儲存在*nullFlags
中,並根據需要設定這些空標誌。*nullFlags
可以保留為NULL
(其初始值),如果所有鍵都非空。如果專案不包含鍵,則返回值可以為NULL
。
Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data, bool **nullFlags, int32 *searchMode)
給定要查詢的值,返回一個 palloc 分配的鍵陣列;也就是說,query
是可索引運算子的右側值,其左側是索引列。n
是運算子類中運算子的策略編號(請參閱第 36.16.2 節)。通常,extractQuery
需要查閱n
以確定query
的資料型別以及它應該用於提取鍵值的方法。返回的鍵的數量必須儲存在*nkeys
中。如果任何鍵可以為空,則還要 palloc 分配一個包含*nkeys
個bool
欄位的陣列,將其地址儲存在*nullFlags
中,並根據需要設定這些空標誌。*nullFlags
可以保留為NULL
(其初始值),如果所有鍵都非空。如果query
不包含鍵,則返回值可以為NULL
。
searchMode
是一個輸出引數,允許extractQuery
指定搜尋的詳細資訊。如果*searchMode
設定為GIN_SEARCH_MODE_DEFAULT
(這是呼叫前初始化的值),則只有與至少一個返回鍵匹配的專案才被視為候選匹配。如果*searchMode
設定為GIN_SEARCH_MODE_INCLUDE_EMPTY
,則除了包含至少一個匹配鍵的專案外,不包含任何鍵的專案也被視為候選匹配。(此模式對於實現子集運算子等非常有用。)如果*searchMode
設定為GIN_SEARCH_MODE_ALL
,則索引中所有非空專案都被視為候選匹配,無論它們是否與任何返回鍵匹配。(此模式比其他兩種選擇慢得多,因為它需要掃描幾乎整個索引,但可能需要正確實現邊緣情況。在大多數情況下需要此模式的運算子可能不適合作為 GIN 運算子類。)用於設定此模式的符號在access/gin.h
中定義。
pmatch
是一個輸出引數,用於支援部分匹配。要使用它,extractQuery
必須分配一個包含*nkeys
個bool
的陣列,並將其地址儲存在*pmatch
中。陣列的每個元素應設定為 true,如果相應的鍵需要部分匹配,否則設定為 false。如果*pmatch
設定為NULL
,則 GIN 假定不需要部分匹配。該變數在呼叫前初始化為NULL
,因此不支援部分匹配的運算子類可以簡單地忽略此引數。
extra_data
是一個輸出引數,允許extractQuery
將附加資料傳遞給consistent
和comparePartial
方法。要使用它,extractQuery
必須分配一個包含*nkeys
個指標的陣列,並將其地址儲存在*extra_data
中,然後將它想要的任何內容儲存到各個指標中。該變數在呼叫前初始化為NULL
,因此不需要額外資料的運算子類可以簡單地忽略此引數。如果設定了*extra_data
,則整個陣列將傳遞給consistent
方法,並將相應的元素傳遞給comparePartial
方法。
運算子類還必須提供一個函式來檢查索引項是否與查詢匹配。它有兩種形式,一個布林型consistent
函式和一個三元triConsistent
函式。triConsistent
涵蓋了兩者的功能,因此只提供triConsistent
就足夠了。但是,如果布林型變體計算成本顯著較低,則提供兩者可能是有利的。如果只提供布林型變體,則某些依賴於在獲取所有鍵之前否定索引項的最佳化將被停用。
bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool nullFlags[])
如果索引項滿足策略編號為n
的查詢運算子(或者如果返回重新檢查指示,則可能滿足),則返回 true。此函式無法直接訪問索引項的值,因為GIN不顯式儲存項。相反,可用的是關於從查詢中提取的哪些鍵值出現在給定索引項中的知識。check
陣列的長度為nkeys
,與之前為該query
資料項由extractQuery
返回的鍵數相同。如果索引項包含相應的查詢鍵,則check
陣列的每個元素都為 true,即如果 (check[i] == true) 則extractQuery
結果陣列的第 i 個鍵存在於索引項中。原始query
資料項被傳入,以防consistent
方法需要查閱它,同時傳入的還有之前由extractQuery
返回的queryKeys[]
和nullFlags[]
陣列。extra_data
是extractQuery
返回的附加資料陣列,如果沒有則為NULL
。
當extractQuery
在queryKeys[]
中返回空鍵時,如果索引項包含空鍵,則相應的check[]
元素為真;也就是說,check[]
的語義類似於IS NOT DISTINCT FROM
。如果需要區分常規值匹配和空匹配,consistent
函式可以檢查相應的nullFlags[]
元素。
成功時,如果需要根據查詢運算子重新檢查堆元組,則應將*recheck
設定為 true,如果索引測試是精確的,則設定為 false。也就是說,返回 false 值保證堆元組不匹配查詢;返回 true 值且*recheck
設定為 false 保證堆元組匹配查詢;返回 true 值且*recheck
設定為 true 表示堆元組可能匹配查詢,因此需要透過直接針對原始索引項評估查詢運算子來獲取和重新檢查它。
GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], Datum queryKeys[], bool nullFlags[])
triConsistent
類似於consistent
,但在check
向量中,每個鍵有三個可能的值:GIN_TRUE
、GIN_FALSE
和GIN_MAYBE
。GIN_FALSE
和GIN_TRUE
與常規布林值具有相同的含義,而GIN_MAYBE
表示該鍵的存在未知。當存在GIN_MAYBE
值時,如果專案肯定匹配,無論索引項是否包含相應的查詢鍵,函式才應返回GIN_TRUE
。同樣,函式只有在專案肯定不匹配時才必須返回GIN_FALSE
,無論它是否包含GIN_MAYBE
鍵。如果結果取決於GIN_MAYBE
條目,即基於已知查詢鍵無法確認或否定匹配,則函式必須返回GIN_MAYBE
。
當check
向量中沒有GIN_MAYBE
值時,GIN_MAYBE
返回值等同於在布林型consistent
函式中設定recheck
標誌。
此外,GIN 必須有一種方法來對索引中儲存的鍵值進行排序。運算子類可以透過指定比較方法來定義排序順序
int compare(Datum a, Datum b)
比較兩個鍵(而不是索引項!),並返回一個小於零、等於零或大於零的整數,指示第一個鍵是小於、等於還是大於第二個鍵。空鍵永遠不會傳遞給此函式。
或者,如果運算子類不提供compare
方法,GIN 將查詢索引鍵資料型別的預設 B 樹運算子類,並使用其比較函式。建議在僅用於一種資料型別的 GIN 運算子類中指定比較函式,因為查詢 B 樹運算子類會花費一些週期。然而,多型 GIN 運算子類(如array_ops
)通常無法指定單個比較函式。
運算子類GIN可以選擇提供以下方法
int comparePartial(Datum partial_key, Datum key, StrategyNumber n, Pointer extra_data)
比較部分匹配查詢鍵與索引鍵。返回一個整數,其符號表示結果:小於零表示索引鍵與查詢不匹配,但索引掃描應繼續;零表示索引鍵與查詢匹配;大於零表示索引掃描應停止,因為不再可能匹配。提供了生成部分匹配查詢的運算子的策略編號n
,以防需要其語義來確定何時結束掃描。此外,extra_data
是extractQuery
建立的附加資料陣列的相應元素,如果沒有則為NULL
。空鍵永遠不會傳遞給此函式。
void options(local_relopts *relopts)
定義一組使用者可見的引數,用於控制運算子類的行為。
options
函式傳遞一個指向local_relopts
結構的指標,該結構需要填充一組運算子類特定選項。可以使用PG_HAS_OPCLASS_OPTIONS()
和PG_GET_OPCLASS_OPTIONS()
宏從其他支援函式訪問這些選項。
由於索引值的鍵提取和鍵在GIN中的表示都是靈活的,它們可能取決於使用者指定的引數。
為了支援“部分匹配”查詢,運算子類必須提供comparePartial
方法,並且其extractQuery
方法在遇到部分匹配查詢時必須設定pmatch
引數。有關詳細資訊,請參閱第 65.4.4.2 節。
上面提到的各種Datum
值的實際資料型別因運算子類而異。傳遞給extractValue
的項值始終是運算子類的輸入型別,並且所有鍵值都必須是該類的STORAGE
型別。傳遞給extractQuery
、consistent
和triConsistent
的query
引數的型別是策略編號標識的類成員運算子的右側輸入型別。這不必與索引型別相同,只要可以從中提取正確型別的鍵值即可。但是,建議這些三個支援函式的 SQL 宣告為query
引數使用運算子類的索引資料型別,即使實際型別可能根據運算子而有所不同。
在內部,一個GIN索引包含一個在鍵上構建的 B 樹索引,其中每個鍵是一個或多個索引項的元素(例如,陣列的成員),並且葉頁面中的每個元組都包含一個指向堆指標 B 樹的指標(“釋出樹”),或者當列表足夠小以適應單個索引元組和鍵值時,它包含一個簡單的堆指標列表(“釋出列表”)。圖 65.1說明了 GIN 索引的這些組成部分。
從PostgreSQL 9.1 開始,索引中可以包含空鍵值。此外,對於根據extractValue
為空或不包含任何鍵的索引項,索引中還包含佔位符空值。這允許搜尋應該找到空項。
多列GIN索引是透過在複合值(列號,鍵值)上構建單個 B 樹來實現的。不同列的鍵值可以具有不同的型別。
圖 65.1。GIN 內部結構
更新一個GIN索引往往很慢,因為倒排索引的內在特性:插入或更新一行堆表可能會導致索引中插入許多條目(每個從索引項中提取的鍵插入一個)。GIN能夠透過將新元組插入到臨時、未排序的待處理條目列表中來推遲大部分工作。當表被清理或自動分析時,或者當呼叫gin_clean_pending_list
函式時,或者如果待處理列表變得大於gin_pending_list_limit,這些條目將使用在初始索引建立期間使用的相同批次插入技術移動到主GIN資料結構。這大大提高了GIN索引更新速度,即使考慮到額外的清理開銷。此外,開銷工作可以通過後臺程序而不是在前臺查詢處理中完成。
這種方法的主要缺點是搜尋除了掃描常規索引外還必須掃描待處理條目列表,因此大量的待處理條目列表會顯著減慢搜尋速度。另一個缺點是,雖然大多數更新都很快,但導致待處理列表變得“太大”的更新將立即觸發清理週期,因此比其他更新慢得多。正確使用自動清理可以最大程度地減少這兩個問題。
如果一致的響應時間比更新速度更重要,可以透過關閉fastupdate
儲存引數來停用待處理條目的使用。GIN索引。有關詳細資訊,請參閱CREATE INDEX。
GIN 可以支援“部分匹配”查詢,其中查詢不確定一個或多個鍵的精確匹配,但可能的匹配落在相當窄的鍵值範圍內(在由compare
支援方法確定的鍵排序順序內)。extractQuery
方法不是返回要精確匹配的鍵值,而是返回要搜尋範圍的下限鍵值,並將pmatch
標誌設定為 true。然後使用comparePartial
方法掃描鍵範圍。comparePartial
必須對匹配的索引鍵返回零,對仍在搜尋範圍內的不匹配返回小於零,或者如果索引鍵超出可能匹配的範圍則返回大於零。
插入到GIN索引可能很慢,因為每個專案可能會插入許多鍵。因此,對於批次插入表,建議在完成批次插入後刪除 GIN 索引並重新建立它。
當為GIN啟用fastupdate
時(有關詳細資訊,請參閱第 65.4.4.1 節),開銷會小於未啟用時。但對於非常大的更新,最好還是刪除並重新建立索引。
構建時間GIN索引對maintenance_work_mem
設定非常敏感;在索引建立期間節省工作記憶體是得不償失的。
在對已啟用fastupdate
的現有GIN索引進行一系列插入期間,系統將在待處理條目列表大於gin_pending_list_limit
時清理該列表。為避免觀察到的響應時間波動,最好讓待處理列表清理在後臺(即透過自動清理)進行。可以透過增加gin_pending_list_limit
或使自動清理更積極地避免前臺清理操作。但是,增加清理操作的閾值意味著,如果確實發生前臺清理,則需要更長時間。
gin_pending_list_limit
可以透過更改儲存引數來覆蓋單個 GIN 索引,這允許每個 GIN 索引擁有自己的清理閾值。例如,可以僅為可能被大量更新的 GIN 索引增加閾值,並否則降低它。
開發的主要目標GIN索引是為了在PostgreSQL中建立對高度可擴充套件的全文字搜尋的支援,並且通常情況下,全文字搜尋會返回非常大的結果集。此外,當查詢包含非常頻繁的單詞時,這通常會發生,因此大型結果集甚至沒有用。由於從磁碟讀取許多元組並對其進行排序可能需要很長時間,這對於生產來說是不可接受的。(請注意,索引搜尋本身非常快。)
為了方便對此類查詢進行受控執行,GIN對返回的行數有一個可配置的軟上限:gin_fuzzy_search_limit
配置引數。它預設設定為 0(表示無限制)。如果設定了非零限制,則返回的結果集是整個結果集的子集,隨機選擇。
“軟”意味著實際返回的結果數量可能與指定限制略有不同,具體取決於查詢和系統隨機數生成器的質量。
根據經驗,數千個值(例如,5000 — 20000)效果很好。
GIN假設可索引運算子是嚴格的。這意味著extractValue
根本不會在空項值上呼叫(相反,會自動建立一個佔位符索引條目),並且extractQuery
也不會在空查詢值上呼叫(相反,查詢被假定為不可滿足的)。但請注意,支援包含在非空複合項或查詢值中的空鍵值。
如果您在文件中發現任何不正確、與您使用特定功能的經驗不符或需要進一步澄清的內容,請使用此表格報告文件問題。