まえがき

この一連の記事では、PostgreSQLのインデックスに焦点を当てます。

質問はさまざまな観点から検討できます。 DBMSを使用するアプリケーション開発者が関心を持たなければならないもの、存在するインデックス、PostgreSQLに非常に多くの異なるインデックスがある理由、それらを使用してクエリを高速化する方法について説明します。 おそらく、このトピックは少数の言葉で明らかにすることができますが、特に内部構造の詳細にも興味がある好奇心developer盛な開発者には、他の誰かの意見を聞くだけでなく、私たち自身の結論を引き出すこともできるため、内部構造の詳細にも興味を持っています。

議論以外では、新しいタイプのインデックスの開発が残ります。 これにはC言語の知識が必要であり、アプリケーション開発者よりもシステムプログラマーの能力に関連しています。 同じ理由で、実際にはソフトウェアインターフェイスを考慮せず、すぐに使用できるインデックスを使用するために重要なことだけに焦点を合わせます。

このパートでは、データベースエンジンに関連する一般的なインデックス作成メカニズムと、PostgreSQLの拡張機能として追加できる個々のインデックスアクセス方法との間の責任の分割について説明します。 次の部分では、アクセス方法のインターフェイスと、クラスや演算子族などの重要な概念を見ていきます 。 このような長いが必要な導入の後、さまざまなタイプのインデックスのデバイスとアプリケーションを詳細に見ていきます： Hash 、 B-tree 、 GiST 、 SP-GiST 、 GINとRUM 、 BRINとBloom 。

指数

PostgreSQLのインデックスは、主にデータへのアクセスを高速化するために設計された特別なデータベースオブジェクトです。 これらは補助構造です。テーブル内の情報からインデックスを削除および復元できます。 DBMSがインデックスなしで、ゆっくりと動作できると聞くことがあります。 ただし、これはそうではありません。これは、インデックスが一部の整合性制約をサポートするためにも役立つためです。

現在、PostgreSQL 9.6には6種類のインデックスが組み込まれていますが、もう1つは拡張機能として利用可能です。これは、バージョン9.6の重要な変更により可能になりました。 そのため、近い将来、他の種類のインデックスの出現を期待する必要があります。

インデックスのタイプ（ アクセス方法とも呼ばれます ）のすべての違いにもかかわらず、最終的にそれらのいずれかがキー（たとえば、インデックス付き列の値）とこのキーが発生するテーブルの行との間の対応を確立します。 行は、ファイルブロック番号とブロック内の行の位置で構成されるTID（タプルID）を使用して識別されます。 次に、キーまたはキーに関する情報を知っていれば、テーブル全体を見なくても、関心のある情報が見つかる行をすばやく読むことができます。

インデックスは、データへのアクセスを加速する代わりに、メンテナンスに特定のコストを必要とすることを理解することが重要です。 テーブル行の挿入、削除、更新など、インデックス付きデータに対する操作では、そのテーブル用に作成されたインデックスは、同じトランザクション内で再構築する必要があります。 インデックスが作成されなかったテーブルフィールドを更新しても、インデックスは再構築されません。 このメカニズムはHOT（ヒープのみのタプル）と呼ばれます。

拡張性にはいくつかの意味があります。 新しいアクセス方法をシステムに簡単に統合できるように、一般的なインデックス作成メカニズムがPostgreSQLに割り当てられています。 その主なタスクは、アクセス方法からTIDを取得し、それらを操作することです。

• テーブル行の対応するバージョンからデータを読み取ります。
• 個別のTIDによるサンプリング、または（ビットマップの構築を伴う）TIDのセットによる即時サンプリング。
• 分離レベルを考慮して、現在のトランザクションの行バージョンの可視性を確認します。

インデックス作成メカニズムはクエリの実行に関与します。 最適化段階で作成された計画に従って呼び出されます。 クエリ実行のさまざまな方法をソートおよび評価するオプティマイザは、適用される可能性のあるすべてのアクセス方法の機能を理解する必要があります。 アクセス方法は、正しい順序ですぐにデータを提供することができますか、またはソートを個別に提供する必要がありますか？ nullを検索するためにアクセス方法を適用することは可能ですか？ -このような質問はオプティマイザーによって常に解決されます。

アクセス方法に関する情報は、オプティマイザーだけでなく必要です。 インデックスを作成するとき、システムは以下を決定する必要があります。複数の列にわたってインデックスを構築することは可能ですか？ このインデックスは一意性を提供できますか？

そのため、各アクセス方法は、それ自体に関する必要な情報をすべて提供する必要があります。 バージョン9.6より前では、このためにpg_amテーブルが使用されていました。9.6からは、データは特別な関数により深く移行しました。 このインターフェイスについては、後ほど詳しく説明します。

アクセス方法自体のタスクには、他のすべてが含まれます。

• インデックスを構築し、データのページネーションを行うアルゴリズムの実装（すべてのインデックスがバッファキャッシュマネージャによって同じ方法で処理されるように）;
• 式 " indexed-field operator expression "によってインデックス内の情報を検索します。
• インデックスの使用コストの評価。
• プロセスの正しい並列実行に必要なロックを操作します。
• 先行書き込みログ（WAL）の生成。

まず、一般的なインデックス作成メカニズムの可能性を検討し、次にさまざまなアクセス方法を検討します。

インデックス作成メカニズム

インデックス作成メカニズムにより、PostgreSQLはその機能を考慮して、さまざまなアクセス方法で同等に動作できます。

基本的なスキャン方法

インデックススキャン

インデックスによって提供されるTIDを別の方法で使用できます。 例を考えてみましょう：

postgres=# create table t(a integer, b text, c boolean);
CREATE TABLE
postgres=# insert into t(a,b,c)
select s.id, chr((32+random()*94)::integer), random() < 0.01
from generate_series(1,100000) as s(id)
order by random();
INSERT 0 100000
postgres=# create index on t(a);
CREATE INDEX
postgres=# analyze t;
ANALYZE

3つのフィールドを持つテーブルを作成しました。 最初のフィールドには1から100000までの数字が含まれ、その上にインデックスが作成されています（現時点では、どちらが重要ではありません）。 2番目のフィールドには、印刷できない文字を除くさまざまなASCII文字が含まれています。 最後に、3番目のフィールドには論理値が含まれ、約1％の行でtrue、残りの行でfalseです。 行はテーブルにランダムな順序で挿入されます。

条件「a = 1」で値を選択してみましょう。 条件の形式は「 インデックス付きフィールド演算子式 」で、「等しい」が演算子として使用され、 式 （検索キー）が「1」であることに注意してください。 ほとんどの場合、条件はインデックスが使用できるようなものでなければなりません。

postgres=# explain (costs off) select * from t where a = 1;
QUERY PLAN
-------------------------------
Index Scan using t_a_idx on t
Index Cond: (a = 1)
(2 rows)

この場合、オプティマイザーはインデックススキャンを使用することを決定しました。 インデックスが作成されると、アクセス方法は、一致する行が終了するまで、一度に1つずつTID値を返します。 インデックスメカニズムは、TIDが指すテーブルのページを参照し、行のバージョンを受け取り、マルチバージョンルールに従ってその可視性をチェックし、受け取ったデータを返します。

ビットマップスキャン

インデックススキャンは、いくつかの値についてのみ有効です。 ただし、選択範囲が増えると、同じタブページに何度も戻る必要が生じる可能性があります。 したがって、この場合、オプティマイザーはビットマップスキャンを使用したスキャンに切り替えます。

postgres=# explain (costs off) select * from t where a <= 100;
QUERY PLAN
------------------------------------
Bitmap Heap Scan on t
Recheck Cond: (a <= 100)
-> Bitmap Index Scan on t_a_idx
Index Cond: (a <= 100)
(4 rows)

まず、アクセス方法は条件に一致するすべてのTID（ビットマップインデックススキャンノード）を返し、それらから行バージョンのビットマップが構築されます。 次に、行のバージョンがテーブルから読み取られます（ビットマップヒープスキャン）-この場合、各ページは1回だけ読み取られます。

2番目のステップでは、条件が再確認される場合があることに注意してください（条件の再確認）。 選択が大きすぎて、行バージョンのビットマップがRAMに完全に収まらない場合があります（work_memパラメーターによって制限されます）。 この場合、少なくとも1つの適切なバージョンの文字列を含むページのビットマップのみが構築されます。 このような「大まかな」カードはスペースを取りませんが、ページを読み取るときは、そこに保存されている各行の条件を再確認する必要があります。 サンプルの場合でも（この例のように）、Recheck Condステップはプランに表示されますが、実際には実装されていません。

テーブルの複数のフィールドに条件が課されており、これらのフィールドにインデックスが付けられている場合、ビットマップをスキャンすると（オプティマイザーが有利だと判断した場合）、同時に複数のインデックスを使用できます。 各インデックスについて、行バージョンのビットマップが構築され、ビット単位で論理的に乗算される（式がAND句で接続されている場合）か、論理的に追加されます（式がOR句で接続されている場合）。 例：

postgres=# create index on t(b);
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';
QUERY PLAN
--------------------------------------------------
Bitmap Heap Scan on t
Recheck Cond: ((a <= 100) AND (b = 'a'::text))
-> BitmapAnd
-> Bitmap Index Scan on t_a_idx
Index Cond: (a <= 100)
-> Bitmap Index Scan on t_b_idx
Index Cond: (b = 'a'::text)
(7 rows)

ここで、BitmapAndノードは、ビット操作「and」を使用して2つのビットマップを結合します。

ビットマップを使用したスキャンは、同じデータページへのアクセスの繰り返しを回避します。 しかし、テーブルのページのデータがインデックスエントリとまったく同じ方法で物理的に順序付けられている場合はどうでしょうか。 もちろん、ページ内のデータの物理的な順序に完全に依存することはできません。ソートされたデータが必要な場合は、リクエストでORDER BY句を明示的に指定する必要があります。 しかし、「ほぼすべて」のデータが実際に順序付けられている場合があります。たとえば、行が正しい順序で追加され、その後、またはCLUSTERコマンドの実行後に変更されない場合です。 その後、ビットマップの構築は追加のステップであり、通常のインデックススキャンは悪化しません（複数のインデックスを組み合わせる可能性を考慮しない場合）。 したがって、アクセス方法を選択するとき、スケジューラはデータの順序付けの程度を示す特別な統計を調べます。

postgres=# select attname, correlation from pg_stats where tablename = 't';
attname | correlation
---------+-------------
b | 0.533512
c | 0.942365
a | -0.00768816
(3 rows)

絶対値が1に近い値は高列（列c）を示し、ゼロに近い値はランダム分布（列a）を示します。

シーケンシャルスキャン

完全を期すために、非選択的条件下では、オプティマイザはテーブル全体のインデックスシーケンシャルスキャンを使用することを好みます。

postgres=# explain (costs off) select * from t where a <= 40000;
QUERY PLAN
------------------------
Seq Scan on t
Filter: (a <= 40000)
(2 rows)

そして彼は正しいでしょう。 事実、インデックスは、条件の選択性が高いほど、つまり条件を満たす行が少ないほど、より適切に機能するということです。 選択が増えると、インデックスページの読み取りのオーバーヘッドも増加します。

状況は、シーケンシャル読み取りがページを「ランダムに」読み取るよりも速いという事実によって悪化します。 これは特に、ハードドライブの場合に当てはまります。ハードドライブでは、ヘッドをトラックに移動させる機械的な操作が、データ自体の読み取りよりもかなり長くかかります。 SSDでは、この効果はそれほど顕著ではありません。 アクセスコストの違いを考慮して、seq_page_costとrandom_page_costの2つのパラメーターがあります。これらはグローバルに設定できるだけでなく、テーブルスペースのレベルでも設定でき、異なるディスクサブシステムの特性を考慮に入れます。

指数のカバー

原則として、アクセス方法の主なタスクは、適切なテーブル行の識別子を返し、インデックス作成メカニズムが必要なデータをそこから読み取ることができるようにすることです。 しかし、クエリに必要なすべてのデータが既にインデックスに含まれている場合はどうでしょうか？ このようなインデックスは、 カバリングと呼ばれます。この場合、オプティマイザはインデックススキャンのみを使用できます。

postgres=# vacuum t;
VACUUM
postgres=# explain (costs off) select a from t where a < 100;
QUERY PLAN
------------------------------------
Index Only Scan using t_a_idx on t
Index Cond: (a < 100)
(2 rows)

この名前は、インデックス作成メカニズムがテーブルをまったく参照せず、アクセス方法から必要なすべての情報を排他的に受け取ることを示唆している場合があります。 ただし、PostgreSQLのインデックスには行の可視性を判断できる情報が含まれていないため、これは完全に真実ではありません。 したがって、アクセス方法は、現在のトランザクションに表示されているかどうかに関係なく、検索条件に該当するすべてのバージョンの行を返します。

ただし、インデックス作成メカニズムが可視性を判断するために毎回テーブルを調べる必要がある場合、このスキャン方法は通常のインデックススキャンと変わりません。

この問題は、PostgreSQLがテーブルのいわゆる可視性マップをサポートするという事実によって解決されます。このマップでは、バキュームプロセスは、開始時間と分離レベルに関係なく、すべてのトランザクションがデータを見るのに十分なほど長く変化していないページをマークします。 インデックスによって返された行の識別子がそのようなページを参照している場合、可視性は確認できません。

したがって、定期的なクリーニングはコーティングインデックスの有効性を高めます。 さらに、オプティマイザーは、未クリーニングの行の数を考慮し、可視性のチェックで大きなオーバーヘッドが予測される場合、インデックススキャンのみの使用を拒否できます。

テーブルへの強制呼び出しの数は、explain analyzeコマンドを使用して見つけることができます。

postgres=# explain (analyze, costs off) select a from t where a < 100;
QUERY PLAN
-------------------------------------------------------------------------------
Index Only Scan using t_a_idx on t (actual time=0.025..0.036 rows=99 loops=1)
Index Cond: (a < 100)
Heap Fetches: 0
Planning time: 0.092 ms
Execution time: 0.059 ms
(5 rows)

この場合、クリーンアップが実行されたばかりなので、テーブルにアクセスする必要はありませんでした（ヒープフェッチ：0）。 一般に、この数値がゼロに近いほど良いです。

すべてのインデックスが、インデックス付きの値自体を行識別子とともに保存するわけではありません。 アクセス方法がデータを返せない場合、インデックススキャン専用に使用することはできません。

ヌル

不確実な値は、値が存在しない、または不明であるという事実を表す便利な方法として、リレーショナルデータベースで重要な役割を果たします。

しかし、特別な意義には、自分自身に対する特別な態度が必要です。 通常のブール論理は3桁になります。 不定値が通常の値よりも小さいか、それとも大きいかが不明です（そのため、NULLS FIRSTおよびNULLS LASTをソートするための特別な構成）。 集計関数で不確実な値を考慮する必要があるかどうかは明らかではありません。 スケジューラには特別な統計が必要です...

不定値を使用したインデックスサポートの観点からは、あいまいさもあります。そのような値にインデックスを付けるべきかどうか。 nullをインデックス化しない場合、インデックスはよりコンパクトになります。 ただし、インデックスを作成すると、「 インデックス付きフィールド IS [NOT] NULL」という形式の条件にインデックスを使用できるようになります。また、テーブルに条件がまったくない場合のカバーインデックスも使用できます（この場合、インデックスはテーブルのすべての行からデータを返す必要があるため数値および未定義の値を含む）。

開発者は、アクセス方法ごとに、不定値にインデックスを付けるかどうかを決定します。 しかし、原則として、それらはまだインデックス化されています。

複数のフィールドインデックス

複数列のインデックスを使用して、複数のフィールド条件をサポートできます 。 たとえば、テーブルの2つのフィールドにインデックスを作成できます。

postgres=# create index on t(a,b);
CREATE INDEX
postgres=# analyze t;
ANALYZE

オプティマイザは、ビットマップの組み合わせよりもこのようなインデックスを好む可能性が高いでしょう。なぜなら、ここでは、補助アクションなしで必要なTIDをすぐに取得できるからです。

postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';
QUERY PLAN
------------------------------------------------
Index Scan using t_a_b_idx on t
Index Cond: ((a <= 100) AND (b = 'a'::text))
(2 rows)

複数列インデックスを使用して、一部のフィールドの条件によってサンプリングを高速化することもできます-最初から開始：

postgres=# explain (costs off) select * from t where a <= 100;
QUERY PLAN
--------------------------------------
Bitmap Heap Scan on t
Recheck Cond: (a <= 100)
-> Bitmap Index Scan on t_a_b_idx
Index Cond: (a <= 100)
(4 rows)

原則として、最初のフィールドに条件が課されていない場合、インデックスは使用されません。 ただし、場合によっては、オプティマイザーは、シーケンシャルスキャンよりも収益性が高いと考える場合があります。 このトピックについては、btreeインデックスを見るときに詳しく説明します。

すべてのアクセス方法が複数の列にわたるインデックスの作成をサポートするわけではありません。

式インデックス

検索条件は「 インデックス付きフィールド演算子式 」の形式にする必要があるという事実について説明しました。 以下の例では、インデックスは使用されません。これは、フィールド名自体の代わりに、それを含む式が使用されるためです。

postgres=# explain (costs off) select * from t where lower(b) = 'a';
QUERY PLAN
------------------------------------------
Seq Scan on t
Filter: (lower((b)::text) = 'a'::text)
(2 rows)

フィールド名のみが演算子の左側にあるように、この特定のクエリを書き換えることは難しくありません。 ただし、これが不可能な場合は、 式のインデックス（関数インデックス）が役立ちます。

postgres=# create index on t(lower(b));
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where lower(b) = 'a';
QUERY PLAN
----------------------------------------------------
Bitmap Heap Scan on t
Recheck Cond: (lower((b)::text) = 'a'::text)
-> Bitmap Index Scan on t_lower_idx
Index Cond: (lower((b)::text) = 'a'::text)
(4 rows)

関数インデックスは、テーブルフィールドではなく、任意の式によって作成されます。 オプティマイザーは、「 indexed-expression operator expression 」 という形式の条件のインデックスを考慮します。 インデックス付き式の計算がコストのかかる操作である場合、インデックスの更新にはかなりの計算リソースが必要になります。

また、インデックス付きの式について個別の統計が収集されることにも留意してください。 インデックス名ごとにpg_statsビューで見ることができます：

postgres=# \dt
Table "public.t"
Column | Type | Modifiers
--------+---------+-----------
a | integer |
b | text |
c | boolean |
Indexes:
"t_a_b_idx" btree (a, b)
"t_a_idx" btree (a)
"t_b_idx" btree (b)
"t_lower_idx" btree (lower(b))

postgres=# select * from pg_stats where tablename = 't_lower_idx';
...

必要に応じて、通常のテーブルフィールドの場合と同じ方法でヒストグラムバスケットの数を制御できます（列名がインデックス式によって異なる場合があることを考慮して）。

postgres=# \d t_lower_idx
Index "public.t_lower_idx"
Column | Type | Definition
--------+------+------------
lower | text | lower(b)
btree, for table "public.t"

postgres=# alter index t_lower_idx alter column "lower" set statistics 69;
ALTER INDEX


部分インデックス

場合によっては、テーブル行の一部のみにインデックスを付ける必要があります。 通常、これは強い不均一な分布によるものです。インデックスでレアな値を検索するのは理にかなっていますが、フルテーブルスキャンで頻繁な値を見つける方が簡単です。

もちろん、「c」列に通常のインデックスを作成することができ、期待どおりに機能します。

postgres=# create index on t(c);
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where c;
QUERY PLAN
-------------------------------
Index Scan using t_c_idx on t
Index Cond: (c = true)
Filter: c
(3 rows)

postgres=# explain (costs off) select * from t where not c;
QUERY PLAN
-------------------
Seq Scan on t
Filter: (NOT c)
(2 rows)

インデックスの長さは276ページです。

postgres=# select relpages from pg_class where relname='t_c_idx';
relpages
----------
276
(1 row)

ただし、「c」列は行の1％のみに当てはまるため、インデックスの99％は使用されません。 この場合、部分インデックスを作成できます。

postgres=# create index on t(c) where c;
CREATE INDEX
postgres=# analyze t;
ANALYZE

このインデックスのサイズは5ページに減少しました。

postgres=# select relpages from pg_class where relname='t_c_idx1';
relpages
----------
5
(1 row)

場合によっては、ボリュームとパフォーマンスの違いが非常に大きくなることがあります。

仕分け

アクセス方法がソート順に行識別子を返す場合、オプティマイザーにクエリを実行するための追加オプションが与えられます。

テーブルをスキャンしてから、データを並べ替えることができます。

postgres=# set enable_indexscan=off;
SET
postgres=# explain (costs off) select * from t order by a;
QUERY PLAN
---------------------
Sort
Sort Key: a
-> Seq Scan on t
(3 rows)

また、インデックスを使用して、ソート順ですぐにデータを読み取ることができます。

postgres=# set enable_indexscan=on;
SET
postgres=# explain (costs off) select * from t order by a;
QUERY PLAN
-------------------------------
Index Scan using t_a_idx on t
(1 row)

すべてのアクセス方法のうち、btreeのみがソートされた形式でデータを返すことができるため、このタイプのインデックスを検討するまで、より詳細な議論を延期します。

並列構造

通常、インデックスを作成するには、テーブルにSHAREロックを設定する必要があります。 このようなロックを使用すると、テーブルからデータを読み取ることができますが、インデックスの構築中の変更は禁止されます。

これを確認するには、インデックスを作成するときに、たとえばテーブルtで、別のセッションでクエリを実行します。

postgres=# select mode, granted from pg_locks where relation = 't'::regclass;
mode | granted
-----------+---------
ShareLock | t
(1 row)

テーブルが十分に大きく、挿入、更新、または削除モードでアクティブに使用されている場合、これは受け入れられないことがあります-セッションの変更は、ロックが長時間解除されるのを待ちます。

この場合、インデックスの並列作成を使用できます。

postgres=# create index concurrently on t(a);
CREATE INDEX

このようなコマンドは、SHARE UPDATE EXCLUSIVEタイプのロックを確立し、データの読み取りと変更の両方を許可します（テーブルの構造の変更、および同じテーブルの別のインデックスのクリーニング、分析、または構築のみが禁止されています）。

ただし、欠点もあります。 まず、テーブルを1回通過する代わりに2回実行されるため、インデックスの構築が通常より遅くなります。また、データを変更する並列トランザクションの完了を待つ必要があります。

第二に、インデックスの並列構築中に、デッドロックまたは一意性制約違反が発生する場合があります。 それでもインデックスは作成されますが、「機能しない」状態です。 この場合、削除してから再作成する必要があります。 非稼働インデックスは、psql \ dコマンドの出力でINVALIDという単語でマークされ、クエリによって完全なリストを取得できます。

postgres=# select indexrelid::regclass index_name, indrelid::regclass table_name from pg_index where not indisvalid;
index_name | table_name
------------+------------
t_a_idx | t
(1 row)

継続する 。