転置インデックスの原則

転置インデックスは検索エンジン技術に由来し、検索エンジンの基礎と見なすことができます。転置インデックス技術のおかげで、検索エンジンはデータベースの検索や削除などの操作を効率的に実行できます。転置インデックスについて詳しく説明する前に、関連する順方向インデックスを紹介し、両者を比較します。

順方向インデックス

検索エンジンでは、順方向テーブルはドキュメント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はインデックス付きカラムの値です。
保留リスト：高速更新モードでの挿入操作に使用される、インデックスタプルのテンポラリストレージリンクリスト。

上記から、GINインデックスは主にエントリツリーとポスティングツリー（またはポスティングリスト）で構成されており、エントリツリーはGINインデックスの主要な構造ツリーであり、ポスティングツリーは補助ツリーであることがわかります。

エントリツリーはb+treeに似ており、ポスティングツリーはb-treeに似ています。

さらに、エントリツリーとポスティングツリーの両方が、KEYに従って整理されています。

論理構造

論理的には、GINインデックスはリレーションと見なすことができ、このリレーションには2つの構造があります。

ベーステーブルの1つのカラムのみをインデックス

キー	値
key1	ポスティングリスト（またはポスティングツリー）
key2	ポスティングリスト（またはポスティングツリー）
…	…

ベーステーブルの複数カラムをインデックス（複合、複数カラムインデックス）

column_id	キー	値
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
+--------+ +--------+ +--------+
| (0,10) | | (0,10) | | (0,10) |
+--------+ +--------+ +--------+
 |
 v
+--------+ +--------+ +--------+
| (0,11) | | (0,11) | | (0,11) |
+--------+ +--------+ +--------+
 |
 v
 ... ... ...

別の例を見てみましょう。

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)のみです。

 | | | consistency
 | | | 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インデックスでのデータの挿入または更新は非常に遅いです。通常、各行にはインデックスを作成する多くの単語要素が含まれているためです。したがって、行を追加または更新する場合は、インデックスツリーを大幅に更新する必要があります。

一方、複数の行が同時に更新される場合、一部の単語要素が同じである可能性があるため、総コストは行ごとに行を更新するコストよりも低くなります。

GINインデックスには、fastupdateストレージパラメータがあり、インデックスを作成するときに指定し、後で更新できます。

pg_study=# create index on ts using gin(doc_tsv) with (fastupdate = true);
CREATE INDEX

このパラメータを有効にすると、更新は個別の順不同リストに蓄積されます。このリストが十分に大きい場合、またはvacuum（ガベージコレクション）中に、蓄積されたすべての更新がインデックス上で直ちに操作されます。「十分に大きい」リストは、「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を使用する代わりに、データ量が比較的多いため、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は異なるデータ型（テキストではなく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：最高のサーバーレスWebホスティング

最後に、Webサービスのデプロイに最適なプラットフォームをお勧めします：Leapcell

🚀 お気に入りの言語で構築

JavaScript、Python、Go、またはRustで簡単に開発できます。

🌍 無料で無制限のプロジェクトをデプロイ

使用した分だけ支払います。リクエストも料金もありません。

⚡ 従量課金制、隠れたコストなし

アイドル料金はかからず、シームレスなスケーラビリティを実現します。

📖 ドキュメントを見る

🔹 Twitterでフォローしてください：@LeapcellHQ

PostgreSQLを検索エンジンとして？はい、Elasticsearchが必須ではないかも