カランのブログ

ソフトウェアエンジニア / 台湾人 / 福岡生活

今のモード ライト

如果想問問題或單純回饋的話可以填寫表單唷

記事のタイトルや概要は自動翻訳であるため（中身は翻訳されてない場合が多い）、変な言葉が出たり、意味伝わらない場合がございます。空いてる時間で翻訳します。

PostgreSQL ノート — インデックス

在資料庫當中，為了改進查詢效率，在資料量大的時候，可以透過建立索引讓資料庫加速查詢效率。本篇文章將會探討 PostgreSQL 的 index。雖然在大部分的情況，直接使用 CREATE INDEX 的語法已經能夠應付常見的開發場景，但是在 PostgreSQL 當中，其實還提供了許多不同的 index types 使用。

前言

最近因為自己的小專案想要做全文搜尋及地點搜尋等功能，發現 postgres 實在太方便了，有全文搜尋，有強大的 GIS 支持（搭配 PostGIS）、trigger function、好用的 window function、hstore 等等。因此在實作功能的同時順便記錄一下。只是畢竟是個自嗨的專案，因此資料量小的下 index 都覺得有點好笑，這邊就沒有太嚴謹的 benchmark 了。

目錄

  • 索引的基本原理
  • 如何在 PostgreSQL 中建立索引
  • 使用索引時的注意事項
  • 如何維護 INDEX
  • PostgreSQL 當中的 index types
    • B Tree
    • GIN
    • GiST
    • BRIN
    • Bloom

索引的基本原理

資料庫最重要的就是查詢資料，當資料存儲在硬碟時就要考慮如何處理 I/O 的效能問題。外接硬碟因為其本身硬體的限制，會比直接在記憶體讀取耗費更多的時間。在資料庫當中，如果沒有對資料表建立索引，將會使用 sequential scans 來查詢資料。在資料數量小的時候並沒有太明顯的效能差異，甚至還比建立索引還快，不過當資料量越來越大，sequential scans 很有可能造成讀取過慢的問題。

索引如何解決 sequential scans 過慢的問題

透過額外在硬碟建立一張索引表，我們可以透過索引表當作目錄，資料庫在查詢時，就會用給定的索引表尋找相對應的索引。再透過由索引指向實體資料，連結到硬碟當中的實體位址。

B Tree

B Tree 是一個專門為硬碟優化的平衡樹，跟一般的二元樹不同，B Tree 的樹可以有很多分支，有效減少樹的深度。B tree 的原理需要比較長的篇幅介紹，所以這邊省略介紹。

PostgreSQL 中的索引

建立索引

在 PostgreSQL 中可以透過 SQL 語法來建立索引。

CREATE INDEX index_name ON table_name (column_name) USING method;

在 PostgreSQL 中，如果沒有特別指定演算法，預設使用 B-Tree 來建立索引。也可以針對某個 column 做索引。也可以一次對多個 column 建立索引。

CREATE INDEX index_name ON table_name (col1, col2);
"Index Scan using index_subscribers_on_email on subscribers  (cost=0.28..8.29 rows=1 width=76)"
"  Index Cond: ((email)::text = 'xxx@yahoo.co.jp'::text)"

"Seq Scan on subscribers  (cost=0.00..37.38 rows=1 width=76)"
"  Filter: ((email)::text = 'xxx@gamil.co.jp'::text)"

我們可以用 EXPLAIN 來觀察 query 的效能。發現透過 B-Tree 的方式成功減少了查詢時間。

注意：

  • 使用 CREATE INDEX 建立索引時會鎖住整張表，在資料量大時可能需要耗費不少時間。
  • 建立索引時我們可以加入 CREATE INDEX CONCURRENTLY 來確保資料表不會被 lock 住。不過為了確保索引表的完整性，CONCURRENTLY 需要花更多的時間來建立索引。

When this option is used, PostgreSQL will build the index without taking any locks that prevent concurrent inserts, updates, or deletes on the table; whereas a standard index build locks out writes (but not reads) on the table until it's done. There are several caveats to be aware of when using this option — see Building Indexes Concurrently.

source

恰如其分的 index

為了解釋資料庫使用 index 的時機，我們先對某個只有兩筆資料的 table 下 index。

CREATE INDEX index_users_on_email ON users (email);
EXPLAIN SELECT email FROM users WHERE email = 'xxx@gmail.com';

"Seq Scan on users  (cost=0.00..1.02 rows=1 width=32)"
"  Filter: ((email)::text = 'xxx@gmail.com'::text)"

對於資料量小的資料，儘管建立了索引，資料庫仍然會使用 sequential scan 查詢。

這是因為 Random I/O 的花費會比循序查詢的方式還高，因此如果資料量小時，就算建立 index 也不會增加查詢效能，反而浪費了硬碟空間。

index size

對一個具有 1300 多筆的資料建立 index。

CREATE INDEX index_subscribers_on_email on subscribers (email);
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size;//80K

透過 pg_relation_size 拿取相關 relation 的大小。

  • 刪除 index DROP INDEX IF EXISTS index_name。

為了確保索引的完整性，在建立索引時，PostgreSQL 會將整張表做 exclusive lock，建立完索引後才 release。因此對頻繁查改的資料表來說很有可能造成服務中斷，對於筆數相當多的資料來說，建立索引有可能花上幾分鐘或是幾十分鐘。

維護 index

https://wiki.postgresql.org/wiki/Index_Maintenance

首先先在資料庫刪除幾筆資料，對於資料庫來說，預設刪除的方式並不是真正從硬碟當中釋放空間，而是標上類似「已刪除」的標記。對於索引來說，刪除資料並不會減少索引大小。

DELETE FROM subscribers WHERE id >1350;
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size; // 80K

這時可以透過 REINDEX 的方式重新建立索引。REINDEX INDEX index_name

REINDEX INDEX index_subscibers_on_email;
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size; // 72K

重建索引會把無用的索引刪除，索引表的大小減少了。

從上面我們可以得知，對於增刪頻繁的資料表來說，定期重建索引可以減少索引表的大小，如果需要刪除大量的資料，也盡量重建索引來維護索引表的大小，否則可能造成硬碟空間的浪費。

不過 REINDEX 也會造成鎖表，如果不允許服務維修或暫停的話，可以直接用 CREATE INDEX CONCURRENTLY 的方式重新建立一個全新的索引，再把舊的索引刪除，並且重新命名索引。這會比 REINDEX 耗費更久時間，而且也比較麻煩一些，不過可以確保資料表不會被鎖住。

對特定資料做索引

有些時候我們只會頻繁查詢某些特定條件的資料，這時候就不一定要對所有資料下索引。透過 CREATE INDEX index_name ON table_name WHERE ... 的方式，我們可以針對需要的資料做索引。

索引排序

在建立索引時如果沒有特別宣告排序，預設會使用 ASC 來建立索引。不過在某些使用情境下，我們可能更常用 DESC 的方式來排序，例如排名、文章發佈日期等等，這時使用 DESC 建立索引更有效率。

CREATE INDEX index_articles_on_published_date ON articles (published_date DESC);

重建索引

B-Tree索引只有在全部清空索引 page 才會被重複利用，所以在資料庫刪除某個值並不會減少索引表的大小。原本的資料為 1400 筆，刪除 50 筆，索引大小沒有變化。

DELETE FROM subscribers WHERE id > 1350;

SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size; // 80K

重新建立索引

REINDEX INDEX index_subscibers_on_email;
SELECT pg_relation_size('index_subscibers_on_email')/1024 || 'K' AS size;
72K

讓沒有被利用到的索引刪除，釋放硬碟空間，避免許多無用的索引佔據整個硬碟。但是要注意，REINDEX 也會造成鎖表。如果服務不允許關閉維護的狀況，可以考慮直接建立新的索引，再把原本的索引刪除、重新命名新的索引。

Postgre 當中的 index type

注意：以下的內容都還沒有做 bench mark

上面介紹完了 postgre index 與使用方式，接下來介紹 Postgre 當中常見的 index type。如果在建立 index 時沒有特別指定使用的方法，PostgreSQL 會使用 B Tree 來建立索引。

Btree

B Tree 支援下列幾種查詢操作：

  • <
  • <=
  • =
  • >=
  • >

GIN(Generalized Inverted Index)

GIN is designed for handling cases where the items to be indexed are composite values, and the queries to be handled by the index need to search for element values that appear within the composite items.

GIN 被用在全文搜尋或是或是像 Array 這種可能會被。如同字面上的意思，倒排索引，就是利用 Value 當作索引值，再去找相對應出現的索引。

例如：

this is cat
this is an apple.
cat meows.
// build inverted index
"this": {(0, 0), (1,0)}
"is": {(0,1), (1,1)}
"an": {(1,2)}
"apple: {(1,3)}
"cat": {(0,2), (2,0)}
"meows": {(2,1)}

透過下面的索引表，如果我們想要搜尋 cat 這個關鍵字，就可以從 key 為 cat 的 value 找到對應的索引。發現 cat 出現在第一個句子的第二個字以及第三個句子的第一個字。

適用場景：

  • 全文搜尋
  • 陣列

在 PostgreSQL 中使用 GIN：

CREATE INDEX index_on_document on sentences using gin(document);

GiST(Generalized Search Tree)

GiST 其實更算是一種通用的 interface，我們可以使用 GiST 來定義自己的 index 實現方式（B-Tree, R-Tree 等）。一般來說比較少使用到。但像是空間結構的資料，用 B-Tree 可能較難加速像是包含、相鄰、相交的搜索， 因此像是 PostGIS 就是使用 GiST 來建立對空間結構查詢效能較好的索引。

適用場景：

  • 自己實現 index 接口
  • 空間結構
  • 使用 B-Tree 可能無法符合使用場景的資料結構

BRIN(Block Range Indexes)

跟 B-Tree 對每一行做索引不同，BRIN 會對一段 range 做索引，雖然性能方面上仍然是 B-TREE 勝，但是 size 比 B-Tree 小很多。

如果資料常常是以範圍查詢，例如 log 檔，某個範圍的交易訂單、出帳資料等等，這些資料量通常相當驚人，用 B-Tree 建立索引可能會耗費不小的硬碟空間。不過這些資料通常比較少使用精確搜尋，而是用像範圍搜尋的方式來批次處理這些資料，這時候使用 BRIN 可以得到還不錯的效能，同時節省了相當大的空間。

適用場景：

  • Log 檔分析
  • 交易訂單分析
  • 資料量大，常用範圍搜尋

Bloom

Bloom Filter 是為了解決 Hash table 的空間以及查詢時間，算法本身的原理可以相當快速地判斷某個元素是否有出現在集合，但會有 false positive 的情形出現，因此在 PostgreSQL 當中需要做二次檢查。

CREATE INDEX bloom_index_event ON events USING bloom (startTime, endTime, name, gifts)
 WITH (length=80, startTime=2, endTime=2, name=4, gifts=2);

length 為每個 signature 的長度，預設為 80，最長為 4096。後面的參數為對應的 column name 會被 mapped 到幾個 bits，最少為 2，最多為 4096。

適用場景：

  • 對多個 column 的精確搜尋 SELECT * FROM events WHERE startTime=20171111 and endTime=20171231 and name=christmas and gifts="gift_special"，透過 bloom filter 可以快速濾掉不在集合裡的結果。

總結

一般來說，B-Tree 幾乎能夠處理大部分的使用情境。但 PostgreSQL 有豐富的 index 類型可供使用，讓資料能夠更容易地被查詢、索引，也給開發者更高的彈性。這是我相當喜歡 PostgreSQL 的一大原因之一。

  1. 在 PostgreSQL 中有數種下 index 的演算法可供使用，每個演算法都有適合的使用情景。
  2. 使用 CREATE INDEX 時會鎖住整張表，在為大量資料建立索引時很可能會造成影響。可以用 CREATE INDEX CONCURRENTLY 解決，但需要花更多時間建立索引。
  3. 若資料頻繁地更新、刪除，會導致冗餘的 index。盡可能地固定使用 REINDEX 重新建立索引減少硬碟空間的使用。同時注意 REINDEX 會造成鎖表。可以再次建立 index，再把原本的 index 名稱刪除來避免鎖表
  4. CREATE UNIQUE INDEX 可透過 unique 來確保值的唯一性
  5. INDEX 可以透過 WHERE 條件來對特定的 column 下索引，針對特定使用情景。
  6. INDEX 可以透過排序（預設為 ASC），來符合特定的使用情景（文章發佈日期等等）
  7. index 並不是銀彈，可以發現在小資料當中就算下 index 仍然會使用 seq scan，這是因為 Random I/O 的代價遠高於 seq can。因此對於固定且數量不多的資料（ex: 縣市、郵遞區號），建立索引並不一定能增加查詢時間，反而佔據了不必要的硬碟空間。

次の記事

ユーザーフレンドリーなテーブルの設計方法

前の記事

配列.sort の分析

この文章が役に立つと思うなら、下のリンクで応援してくれると大変嬉しいです✨

Buy me a coffee

作者

Kalan 頭像照片，在淡水拍攝，淺藍背景

愷開 | Kalan

Kalan です。台湾出身で、2019年に日本へ転職し、福岡に住んでいます。フロントエンド開発に精通しているだけでなく、IoT、アプリ開発、バックエンド、電子工作などの分野にも挑戦しています。 最近、エレキギターを始めました。ブログを通じて、より多くの人と交流できればと思っています。気軽に絡んでください

お問合せNOW