Leapcell: The Best of Serverless Web Hosting
逆インデックスの原理
逆インデックスは検索エンジン技術に由来し、検索エンジンの基盤と見なすことができます。逆インデックス技術のおかげで、検索エンジンはデータベース検索や削除などの操作を効率的に行うことができます。逆インデックスについて詳しく説明する前に、まず関連する順方向インデックスを紹介し、両者を比較します。
順方向インデックス
検索エンジンにおいて、順方向テーブルは文書IDをキーワードとして使用し、テーブルには文書内の各単語の位置情報が記録されます。検索時には、システムはテーブル内の各文書の単語情報をスキャンし、検索キーワードを含むすべての文書を見つけるまで処理を行います。
順方向テーブルの構造は以下のボックス図で表すことができます。
+---------------------+
| 順方向インデックステーブル |
+---------------------+
| 文書ID | 位置情報 |
+---------------------+
| Doc1 | word1@3 |
| | word2@7 |
+---------------------+
| Doc2 | word1@2 |
| | word3@5 |
+---------------------+
| Doc3 | word2@4 |
| | word4@6 |
+---------------------+
この組織方法は、インデックスを作成する際に構造が比較的単純で、作成が容易で保守しやすいです。インデックスは文書に基づいて作成されるため、新しい文書を追加する場合、この文書に対して新しいインデックスブロックを作成し、元のインデックスファイルの末尾に付加するだけです。文書を削除する場合は、文書番号に対応するインデックス情報を直接見つけて削除することができます。ただし、検索時にはすべての文書をスキャンして漏れがないようにする必要があるため、検索時間が大幅に延長され、検索効率が低くなります。
順方向テーブルの仕組みは非常に単純ですが、その検索効率は非常に低く、特定の状況を除いては実用的な価値がありません。
逆インデックス
逆テーブルは単語や用語をキーワードとしてインデックス化し、テーブル内のキーワードに対応するレコードエントリには、この単語や用語が登場するすべての文書が記録されます。
逆テーブルの構造は以下のボックス図で表すことができます。
+---------------------+
| 逆インデックステーブル |
+---------------------+
| キーワード | 文書リスト |
+---------------------+
| word1 | Doc1,Doc2 |
+---------------------+
| word2 | Doc1,Doc3 |
+---------------------+
| word3 | Doc2 |
+---------------------+
| word4 | Doc3 |
+---------------------+
各単語や用語に対応する文書の数は動的に変化するため、逆テーブルの作成と保守は比較的複雑です。ただし、検索時には検索キーワードに対応するすべての文書を一括して取得できるため、順方向テーブルよりも効率が高いです。全文検索において、検索の高速応答は重要な性能です。インデックスの作成はバックグラウンドで行われるため比較的遅いですが、全体的な検索エンジンの効率に影響を与えません。
PostgreSQLにおけるGINインデックス
概要
GINはGeneralized Inverted Indexの略で、いわゆる逆インデックスです。それが処理するデータ型の値は原子的ではなく、要素で構成されており、これを複合型と呼びます。例えば、(hank, 15:3 21:4) は、hankが15:3と21:4の位置に登場することを意味します。以下では、具体的な例を通じてGINインデックスをより明確に理解するために説明します。
GINインデックス構造
物理構造
GINインデックスの物理的な格納には以下の内容が含まれます。
- エントリ：GINインデックス内の要素で、単語の位置と見なすことができ、キーとも理解できます。
- エントリツリー：エントリ上に構築されるBツリー。
- ポスティングリスト：エントリが登場する物理的な位置（ヒープctid、ヒープテーブルの行番号）の連結リスト。
- ポスティングツリー：エントリが登場する物理的な位置（ヒープctid、ヒープテーブルの行番号）の連結リスト上に構築されるBツリー。したがって、ポスティングツリーのKEYはctidで、エントリツリーのKEYはインデックス化された列の値です。
- 保留リスト：インデックスタプルの一時的な格納連結リストで、fastupdateモードの挿入操作に使用されます。
以上から分かるように、GINインデックスは主にエントリツリーとポスティングツリー（またはポスティングリスト）で構成されており、エントリツリーはGINインデックスの主要な構造ツリーで、ポスティングツリーは補助ツリーです。
エントリツリーはb+ツリーに似ており、ポスティングツリーはbツリーに似ています。
また、エントリツリーとポスティングツリーはどちらもKEYに基づいて順序付けされています。
論理構造
論理的には、GINインデックスは関係と見なすことができ、この関係には2つの構造があります。
基盤テーブルの1列のみをインデックス化
| key | value |
|---|---|
| key1 | ポスティングリスト（またはポスティングツリー） |
| key2 | ポスティングリスト（またはポスティングツリー） |
| … | … |
基盤テーブルの複数列をインデックス化（複合、多列インデックス）
| 列ID | key | value |
|---|---|---|
| Column1 num | key1 | ポスティングリスト（またはポスティングツリー） |
| Column2 num | key1 | ポスティングリスト（またはポスティングツリー） |
| Column3 num | key1 | ポスティングリスト（またはポスティングツリー） |
| … | … | … |
これから分かるように、この構造の下では、基盤テーブルの異なる列における同じキーは、GINインデックスでは異なるキーとして扱われます。
全文検索
GINの主な応用分野は全文検索の高速化です。そこで、ここでは全文検索の例を用いてGINインデックスを紹介します。
テーブルを作成し、doc_tsvはテキスト検索型で、自動的に要素をソートして重複を排除します：
pg_study=# create table ts(doc text, doc_tsv tsvector);
CREATE TABLE
pg_study=# insert into ts(doc) values
('Can a sheet slitter slit sheets?'),
('How many sheets could a sheet slitter slit?'),
('I slit a sheet, a sheet I slit.'),
('Upon a slitted sheet I sit.'),
('Whoever slit the sheets is a good sheet slitter.'),
('I am a sheet slitter.'),
('I slit sheets.'),
('I am the sleekest sheet slitter that ever slit sheets.'),
('She slits the sheet she sits on.');
INSERT 0 9
pg_study=# update ts set doc_tsv = to_tsvector(doc);
UPDATE 9
pg_study=# create index on ts using gin(doc_tsv);
CREATE INDEX
このGINインデックスの構造は以下の通りです。黒い四角はTID番号で、白いものは単語です。これは単方向リストで、Bツリーの双方向リストとは異なります：
+--------+ +--------+ +--------+
| sheet |---->| slit |---->| slitter|
+--------+ +--------+ +--------+
| | |
v v v
+--------+ +--------+ +--------+
| (0,10) | | (0,10) | | (0,10) |
+--------+ +--------+ +--------+
| | |
v v v
+--------+ +--------+ +--------+
| (0,11) | | (0,11) | | (0,11) |
+--------+ +--------+ +--------+
| | |
v v v
... ... ...
もう1つの例を見てみましょう：
pg_study=# select ctid,doc, doc_tsv from ts;
ctid | doc | doc_tsv
--------+--------------------------------------------------------+---------------------------------------------------------
(0,10) | Can a sheet slitter slit sheets? | 'sheet':3,6 'slit':5 'slitter':4
(0,11) | How many sheets could a sheet slitter slit? | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7
(0,12) | I slit a sheet, a sheet I slit. | 'sheet':4,6 'slit':2,8
(0,13) | Upon a slitted sheet I sit. | 'sheet':4 'sit':6 'slit':3 'upon':1
(0,14) | Whoever slit the sheets is a good sheet slitter. | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1
(0,15) | I am a sheet slitter. | 'sheet':4 'slitter':5
(0,16) | I slit sheets. | 'sheet':3 'slit':2
(0,17) | I am the sleekest sheet slitter that ever slit sheets. | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6
(0,18) | She slits the sheet she sits on. | 'sheet':4 'sit':6 'slit':2
(9 rows)
以上から分かるように、sheet、slit、slitterは複数列に登場するため、複数のTIDが存在します。この場合、TIDリストが生成され、それに対して個別のBツリーが生成されます。
以下のステートメントでは、単語が何行に登場するかを調べることができます。
pg_study=# select (unnest(doc_tsv)).lexeme, count(*) from ts
group by 1 order by 2 desc;
lexeme | count
----------+-------
sheet | 9
slit | 8
slitter | 5
sit | 2
upon | 1
mani | 1
whoever | 1
sleekest | 1
good | 1
could | 1
ever | 1
(11 rows)
クエリの例
以下のクエリはどのように実行されるでしょうか。
// ここではデータ量が少ないため、全テーブルスキャンを無効にする
pg_study=# set enable_seqscan TO off;
SET
pg_study=# explain(costs off)
select doc from ts where doc_tsv @@ to_tsquery('many & slitter');
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on ts
Recheck Cond: (doc_tsv @@ to_tsquery('many & slitter'::text))
-> Bitmap Index Scan on ts_doc_tsv_idx
Index Cond: (doc_tsv @@ to_tsquery('many & slitter'::text))
(4 rows)
まず、クエリから各単語（検索キー）を抽出します：maniとslitter。これは特殊なAPIによって完了し、データ型と演算子の戦略を考慮します：
pg_study=# select amop.amopopr::regoperator, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'tsvector_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'gin'
and amop.amoplefttype = opc.opcintype;
amopopr | amopstrategy
-----------------------+--------------
@@(tsvector,tsquery) | 1
@@@(tsvector,tsquery) | 2
(2 rows)
単語を含むBツリーで、2つのキーに対応するTIDリストを探します：
mani: (0,2)
slitter: (0,1), (0,2),(1,2), (1,3), (2,2)
最後に、見つけた各TIDに対して、一連の整合性関数を呼び出します。この整合性関数は、TIDが指す行が検索条件を満たすかどうかを判断することができます。検索の単語が「and」で結合されているため、返される行は(0,2)のみです。
| | | 整合性関数
| | | function
TID | mani | slitter | slit & slitter
-------+------+---------+----------------
(0,1) | f | T | f
(0,2) | T | T | T
(1,2) | f | T | f
(1,3) | f | T | f
(2,2) | f | T | f
結果は以下の通りです：
pg_study=# select doc from ts where doc_tsv @@ to_tsquery('many & slitter');
doc
---------------------------------------------
How many sheets could a sheet slitter slit?
(1 row)
更新速度が遅い問題
GINインデックスでのデータの挿入または更新は非常に遅いです。なぜなら、通常1行には多数の単語要素がインデックス化されるからです。したがって、1行を追加または更新する場合、インデックスツリーを多くの場合更新する必要があります。
一方、複数行を同時に更新する場合、それらの単語要素の一部が同じ場合があり、そのため、全体的なコストは1行ずつ文書を更新するコストよりも少なくなります。
GINインデックスにはfastupdateストレージパラメータがあり、インデックスを作成するときに指定し、後で更新することができます：
pg_study=# create index on ts using gin(doc_tsv) with (fastupdate = true);
CREATE INDEX
このパラメータを有効にすると、更新は別の無順序リストに蓄積されます。このリストが十分に大きくなったり、真空操作（ゴミ収集）の際に、蓄積されたすべての更新がインデックスに対して即座に実行されます。「十分に大きい」リストは、「gin_pending_list_limit」構成パラメータまたはインデックスを作成するときの同名のストレージパラメータによって決定されます。
部分一致検索
「slit」で始まるdocを検索します。
pg_study=# select doc from ts where doc_tsv @@ to_tsquery('slit:*');
doc
--------------------------------------------------------
Can a sheet slitter slit sheets?
How many sheets could a sheet slitter slit?
I slit a sheet, a sheet I slit.
Upon a slitted sheet I sit.
Whoever slit the sheets is a good sheet slitter.
I am a sheet slitter.
I slit sheets.
I am the sleekest sheet slitter that ever slit sheets.
She slits the sheet she sits on.
(9 rows)
インデックスを使用して高速化することもできます：
pg_study=# explain (costs off)
select doc from ts where doc_tsv @@ to_tsquery('slit:*');
QUERY PLAN
---------------------------------------------------
Seq Scan on ts
Filter: (doc_tsv @@ to_tsquery('slit:*'::text))
(2 rows)
キーワードの頻度
いくつかのデータを生成します：
fts=# alter table mail_messages add column tsv tsvector;
fts=# update mail_messages set tsv = to_tsvector(body_plain);
fts=# create index on mail_messages using gin(tsv);
fts=# \timing on
-- 合計466125件のデータ
fts=# select count(*) from mail_messages;
count
--------
356125
(1 row)
-- ここでは、unnestを使用して1行内で単語が登場する回数をカウントせず、データ量が比較的多いため、ts_stat関数を使用して計算します
fts=# select word, ndoc
fts-# from ts_stat('select tsv from mail_messages')
fts-# order by ndoc desc limit 3;
word | ndoc
-------+--------
wrote | 231174
use | 173833
would | 157169
(3 rows)
Time: 11556.976 ms
たとえば、メール情報でめったに登場しない単語「tattoo」を検索します：
fts=# select word, ndoc from ts_stat('select tsv from mail_messages') where word = 'tattoo';
word | ndoc
--------+------
tattoo | 2
(1 row)
Time: 11236.340 ms
2つの単語が同じ行に登場する回数を調べます。「wrote」と「tattoo」が同時に登場する行は1行だけです。
fts=# select count(*) from mail_messages where tsv @@ to_tsquery('wrote & tattoo');
count
-------
1
(1 row)
Time: 0.550 ms
どのように実行されるか見てみましょう。上記の通り、2つの単語のTIDリストを取得する場合は、検索効率が明らかに低いです。なぜなら、20万以上の値をトラバースし、1つの値のみを取得する必要があるからです。ただし、統計情報を通じて、「wrote」は頻繁に登場し、「tattoo」はめったに登場しないことが分かります。そのため、めったに使用されない単語の検索が実行され、次に2つの検索された行に「wrote」が存在するかどうかをチェックします。このようにして、クエリ結果をすばやく取得することができます：
fts=# select count(*) from mail_messages where tsv @@ to_tsquery('wrote & tattoo');
count
-------
1
(1 row)
Time: 0.419 ms
クエリ結果の制限
GINインデックスの特徴の1つは、ビットマップを返すだけで、TIDを1つずつ返すことができないことです。したがって、この記事のすべての計画では、ビットマップスキャンを使用します。
圧縮方法
GINの利点の1つは、圧縮機能です。まず、同じ単語が複数列に登場する場合、インデックスには1回だけ格納されます。次に、TIDはインデックス内で順序付けされているため、簡単な圧縮方法を使用することができます：リスト内の次のTIDは、前のTIDと実際に異なります。この数は通常非常に小さく、完全な6バイトのTIDと比較して、必要なビット数ははるかに少なくなります。
異なるインデックスのサイズを比較します：
Bツリーインデックスを作成します：
GINは異なるデータ型（textではなくtsvector）に基づいて構築され、このデータ型は小さいです。
同時に、Bツリーはメッセージを2K以内に切り詰めます。
fts=# create index mail_messages_btree on mail_messages(substring(body_plain for 2048));
CREATE INDEX
Time: 32709.807 ms
gistインデックスを作成します：
fts=# create index mail_messages_gist on mail_messages using gist(tsv);
CREATE INDEX
Time: 14651.884 ms
gin、gist、btreeのそれぞれのサイズを見てみます：
fts=# select pg_size_pretty(pg_relation_size('mail_messages_tsv_idx')) as gin,
fts-# pg_size_pretty(pg_relation_size('mail_messages_gist')) as gist,
fts-# pg_size_pretty(pg_relation_size('mail_messages_btree')) as btree;
gin | gist | btree
--------+--------+--------
189 MB | 111 MB | 526 MB
(1 row)
Time: 2.961 ms
GINインデックスはより多くのスペースを節約するため、OracleからPostgreSQLへの移行のプロセスでは、GINインデックスをビットマップインデックスの代わりに使用することができます。一般的に、ビットマップインデックスはユニークな値が非常に少ないフィールドに使用され、これはGINにとっても非常に有効です。また、PostgreSQLは任意のインデックス（GINを含む）に基づいて動的にビットマップを構築することができます。
Leapcell: The Best of Serverless Web Hosting
最後に、サーバレスWebサービスをデプロイするのに最適なプラットフォームをお勧めします：Leapcell
🚀 好きな言語で開発
JavaScript、Python、Go、またはRustで簡単に開発できます。
🌍 無制限のプロジェクトを無料でデプロイ
使用する分だけ支払います — リクエストがなければ、請求されません。
⚡ 使った分だけ支払い、隠した費用はありません
アイドル料金はなく、シームレスなスケーラビリティを実現します。
🔹 Twitterでフォロー：@LeapcellHQ