PostgreSQL で独自インデックスを作成する

このページは PostgreSQL でインデックスアクセスメソッド(Index Access Method)を使った独自のインデックスを作成する方法を紹介している。 記事の内容は PostgreSQL 9.5 に基づいており、他のバージョンでは差異がある可能性がある。

PostgreSQL の他の記事へのインデックスはここ。

更新履歴
(2016.12.04) 作成。

目次

• 1. はじめに
• 2. Q & A
  • 2.1 独自インデックスを作成するエクステンションをどのように作成するか
    • 2.1.1 インデックスアクセスメソッド関数の定義
    • 2.1.2 pg_am システムカタログに独自インデックスの挿入
    • 2.1.3 演算子クラスの定義
  • 2.2 独自インデックスを定義したエクステンションを安全に削除するには
  • 2.3 インデックス作成の処理をどのように実装するか
    • 2.3.1 ambuild コールバックは正しい統計情報を必ず返さなくてはならない
    • 2.3.2 IndexBuildHeapScan の返す HeapTuple の t_self は HOT 対応がされている
  • 2.4 空のインデックスはなぜ必要なのか
  • 2.5 ストレージのデザインと Write-Ahead-Log の出し方
  • 2.5 VACUUM 処理の注意点
• 参考文献
• コメント

1. はじめに

PostgreSQL は B-tree、Hash、BRIN と呼ばれるインデックスを持っている。 テーブルに対してこれらのインデックスを貼ると、クエリー実行時にオプティマイザーが自動的にこれらのインデックスを利用してくれる。 他にも GiST、SP-GiST、GIN と呼ばれるインデックスがあり、特殊なデータ型に対するインデックスを拡張することも可能である。

だが PostgreSQL はこれ以外に インデックスアクセスメソッド(Index Access Method) と呼ばれる機構があり、GiST などと異なり完全に独自なインデックスを作成可能である。 インデックスアクセスメソッドを使うと、T-Tree、R-Tree、Bw-Tree のような現代的なアルゴリズムのインデックスを構築することができる。

なお PostgreSQL のインデックスアクセスメソッドの基本情報は [1] の PostgreSQL 9.5.4 文書 第58章 インデックスアクセスメソッドのインタフェース定義 に記載されている。 また [2] に作成の仕掛けだが独自インデックスの雛形を置いた。 以降、説明のための独自インデックスの名前を myindex とする。

2. Q & A

2.1 独自インデックスを作成するエクステンションをどのように作成するか

インデックスアクセスメソッドを使って独自インデックスを作る場合、以下のような操作の流れになる。

1. インデックスアクセスメソッドを定義(CREATE FUNCTION)する。
2. pg_am システムカタログに独自インデックスを挿入する。
3. 演算子クラスを定義(CREATE OPEARATOR CLASS)することで独自インデックスにインデックス可能なデータ型を指定する。

これらの操作をまとめてエクステンションとすべきであろう。 エクステンションのスクリプトは例えば以下のようになる。

CREATE EXTENSION myindex のようにコマンドを打つと、独自インデックスが利用可能になる。 後は CREATE INDEX USING myindex のように USING 句でインデックス名を指定する。

2.1.1 インデックスアクセスメソッド関数の定義

インデックスアクセスメソッドは 58.2. インデックスアクセスメソッド関数 で指定された関数を C 言語関数のユーザー定義関数として定義する。

各インデックスアクセスメソッド関数はシグネチャーさえ合えば名前は自由に付けてよい。 関数のスキーマも自由にしてよいが、pg_catalog か public のスキーマの下に定義するのがよいであろう。

2.1.2 pg_am システムカタログに独自インデックスの挿入

独自インデックスは pg_am システムカタログの下に 1 つの行として挿入するが、これを行う専用のコマンド(CREATE CUSTOM INDEX のような)が準備されていない。 49.3 pg_am を参照しながら、INSERT コマンドで直接挿入する。

INSERT INTO pg_am VALUES ('myindex',
       1, 0,
       false, false, false, false, true, false, false, false, false, false, false, 0,
       'pg_catalog.myindex_insert'::regproc,
       'pg_catalog.myindex_beginscan'::regproc,
       'pg_catalog.myindex_gettuple'::regproc,
       'pg_catalog.myindex_getbitmap'::regproc,
       'pg_catalog.myindex_rescan'::regproc,
       'pg_catalog.myindex_endscan'::regproc,
       'pg_catalog.myindex_markpos'::regproc,
       'pg_catalog.myindex_restrpos'::regproc,
       'pg_catalog.myindex_build'::regproc,
       'pg_catalog.myindex_buildempty'::regproc,
       'pg_catalog.myindex_bulkdelete'::regproc,
       'pg_catalog.myindex_vacuumcleanup'::regproc,
       'pg_catalog.myindex_canreturn'::regproc,
       'pg_catalog.myindex_costestimate'::regproc,
       'pg_catalog.myindex_options'::regproc);

2.1.3 演算子クラスの定義

次に myindex でインデックス可能なデータ型に対する演算子クラスを定義する。 これはCREATE OPEARATOR CLASS コマンドを使う。

• 演算子クラスを定義していないデータ型はインデックス対象にならない。 ただしユーザー定義型(User Defined Type)が入出力変換操作を定義している場合、直接に演算子クラスを定義しなくてもインデックス可能になる。
• 特定のデータ型をインデックス対象禁止にする明示的な方法は存在しない。 ユーザーが CREATE OPERATOR CLASS USING myindex を実行すれば、追加でインデックス可能なデータ型を増やせるからである。 これを禁止するには ProcessUtility_hook あたりで、CREATE OPERATOR CLASS をフックして処理するしかない。
• PostgreSQL には -128〜+127 を格納する char 型(Oid 18番)が存在するが、SQL 中に char と書くとそれは char(1) とみなされる。 これは CHAR(n) 型 (Oid 1042 番)である。 明示的に char 型(Oid 18 番)を呼び出したい場合には、CREATE OPERATOR CLASS char_ops DEFAULT FOR TYPE "char" USING myindex AS ... のようにダブルクォーテーションで囲うこと。

2.2 独自インデックスを定義したエクステンションを安全に削除するには

独自インデックスは CREATE EXTENSION myindex で導入されるが、DROP EXTENSION myindex では完全で安全な削除にならない。

理想的には DROP EXTENSION 時には、CREATE INDEX USING myindex が自動的に DROP INDEX され、pg_am システムカタログの myindex の該当行が消えるのが望ましい。 しかしそのようには動作しない。

• pg_am システムカタログへの登録を 2.2.2 のように INSERT コマンドで強引に行っているので、DROP EXTENSION では pg_am システムカタログの該当行が削除されない。
• しかし CREATE FUNCTION コマンドで登録したインデックスアクセスメソッド関数は DROP EXTENSION で削除される。このため pg_am システムカタログの myindex 行は不正な状態になる。
• DROP EXTENSION 後に手動で pg_am システムカタログの行を DELETE することはできる。しかし myindex のインデックスが存在した場合、不正な状態のインデックスの残骸が残ることになる。

この問題は pg_depend システムカタログへ、インデックスアクセスメソッドとインデックス、エクステンションとインデックスアクセスメソッドの依存関係を追加しても解決しない。 現在、pg_depend システムカタログは pg_am システムカタログ上の行を含んだ依存関係を設定できないためである。

結論として独自インデックスはインストールできるが、アンインストールできない。

2.3 インデックス作成の処理をどのように実装するか

インデックスの作成は ambuild コールバックによって行われるが、いくつか注意事項がある。

2.3.1 ambuild コールバックは正しい統計情報を必ず返さなくてはならない

58.2. インデックスアクセスメソッド関数 の ambuild には、この関数は、新しいインデックスに関する統計情報を含むpallocされた構造体を返さなければなりません。 としか書いていないが、少なくとも IndexBuildResult 構造体の heap_tuples にインデックス対象テーブルの行数を正しく設定する必要がある。

PG_FUNCTION_INFO_V1(myindex_build);
Datum
myindex_build(PG_FUNCTION_ARGS)
{
    Relation    heapRel = (Relation) PG_GETARG_POINTER(0);
    Relation    indexRel = (Relation) PG_GETARG_POINTER(1);
    IndexInfo  *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
    IndexBuildResult *result;

    /* snip */ 

    result = (IndexBuildResult *) palloc0(sizeof(IndexBuildResult));
    result->heap_tuples  = heap_tuples;
    result->index_tuples = index_tuples;

    return result;
}

というのも、ambuild の結果によって pg_class システムカタログのテーブル内の行数を保持する reltuples が上書きされてしまうからである。 heap_tuples に適当な値を入れると、過去の ANALYZE の結果が棄損されることになる。

2.3.2 IndexBuildHeapScan の返す HeapTuple の t_self は HOT 対応がされている

ambuild コールバックは、内部で IndexBuildHeapScan 関数を呼ぶことになる。 これは対象となるテーブルを 1 行づつスキャンしてコールバックに渡す処理を実施する。 コールバックは IndexBuildCallback 型となる。

typedef void (*IndexBuildCallback)(Relation index, HeapTuple htup, Datum *values, bool *isnull, bool tupleIsAlive, void *state);

この中で HeapTuple 型の htup は「PostgreSQL の基本データ型とタプルの扱い」の4.1 Heap Tupleで説明した、ヒープ(テーブル)内のタプル(レコード)のポインタのように見えるが、微妙に違う。 HeapTuple は通常 htup->t_self が自分のタプルの TID を指しているのだが、IndexBuildHeapScan のコールバック経由で渡ってくるものは HOT(Heap-Only-Tuple) のチェインを手繰ってルートになっているタプルの TID を指している。

つまり CREATE INDEX i1 → INSERT → UPDATE → CREATE INDEX i2 の順でコマンドが挿入されたとする。 最初の INSERT で挿入された行の TID が (0, 1) で、次の UPDATE は (0, 2) だとする。 UPDATE は i1 のインデックスに対して HOT であった。 次に CREATE INDEX i2 が実行されると、(0, 2) の行だけを生きていると判断して IndexBuildHeapScan のコールバックに渡すが、その際に htup->t_self は (0, 2) ではなく (0, 1) と偽装される。

実際の偽装は src/backend/catalog/index.c の IndexBuildHeapRangeScan 関数の中で行われている。

/*
 * You'd think we should go ahead and build the index tuple here, but
 * some index AMs want to do further processing on the data first.  So
 * pass the values[] and isnull[] arrays, instead.
 */

if (HeapTupleIsHeapOnly(heapTuple))
{
    /*
     * For a heap-only tuple, pretend its TID is that of the root. See
     * src/backend/access/heap/README.HOT for discussion.
     */
    HeapTupleData rootTuple;
    OffsetNumber offnum;

    rootTuple = *heapTuple;
    offnum = ItemPointerGetOffsetNumber(&heapTuple->t_self);

    if (!OffsetNumberIsValid(root_offsets[offnum - 1]))
    elog(ERROR, "failed to find parent tuple for heap-only tuple at (%u,%u) in table \"%s\"",
         ItemPointerGetBlockNumber(&heapTuple->t_self),
         offnum, RelationGetRelationName(heapRelation));

    ItemPointerSetOffsetNumber(&rootTuple.t_self,
                              root_offsets[offnum - 1]);

    /* Call the AM's callback routine to process the tuple */
    callback(indexRelation, &rootTuple, values, isnull, tupleIsAlive,
             callback_state);
}
else
{
    /* Call the AM's callback routine to process the tuple */
    callback(indexRelation, heapTuple, values, isnull, tupleIsAlive,
             callback_state);
}

2.4 空のインデックスはなぜ必要なのか

58.2. インデックスアクセスメソッド関数 の ambuildempty コールバックには以下の記述がある。

空のインデックスを構築し、それを指定されたリレーションの初期フォーク(INIT_FORKNUM)に書き出します。 このメソッドはログを取らないテーブルに対してのみ呼び出されます。 初期フォークに書き出された空のインデックスは、サーバの再起動の度に主リレーションフォークにコピーされます。

上記の文章を読んでも理解できないと思われるが、以下のような理由のために ambuildempty コールバックは存在する。

CREATE UNLOGGED TABLE で作成したログを取らないテーブルに対するインデックスはやはりログを取らないインデックスになる。 ログを取らないテーブルであっても、正常終了した場合はテーブルの内容はディスクに書き出され、次回起動時は前回操作されたデータが見えることになる。 これはログを取らないテーブルも同様である。 しかし異常終了によってサーバーが再起動した場合には、ログを取らないテーブルは過去のデータを失い空のテーブルに戻る。 TRUNCATE コマンドを実行したのと同様に、テーブルの実体となるデータファイルは 0 ブロックになる。

一方、ログを取る・取らないに関わらず空のテーブルに対するインデックスは空(0ブロック)ではない点が重要である。 通常、インデックスの先頭ページにはその重要なデータが書かれたメタページになっている。 これは ambuild コールバックが構築したものである。 しかし PostgreSQL は異常終了からのサーバー再起動後にログを取らないインデックスに対して ambuild コールバックを再実行しない。 しないというより(起動シーケンスの関係上)できない。 そこでサーバー再起動後には、既に作成済みのメタページをコピーして空のインデックスを作成する。 このメタページ作成のために ambuildempty コールバックが存在するのである。

2.5 ストレージのデザインと Write-Ahead-Log の出し方

2.5 VACUUM 処理の注意点

VACUUM コマンドが呼ばれた場合、58.2. インデックスアクセスメソッド関数 の ambulkdelete コールバックと amvacuumcleanup コールバックが呼ばれる。

• amvacuumcleanup コールバックは VACUUM コマンド以外に ANALYZE コマンドが実行された場合でも呼ばれる。 引数として渡される IndexVacuumInfo 構造体の analyze_only でチェックする必要がある。
• 1 回の VACUUM に対して ambulkdelete コールバックは複数回呼ばれることがあるが、インデックス内に削除すべきデータがないと判断された場合 1 回も呼ばれないこともある。ambulkdelete コールバックが 1 度も呼ばれない場合でも、amvacuumcleanup コールバックは呼ばれることもがある。

独自インデックスを作った場合、VACUUM 処理の中でガーベージ・コレクション的な整理がしたくなる。 しかし PostgreSQL のフレームワーク的に大きな制限が存在する。 VACUUM 処理もトランザクションを作成しその中で処理を行うが、VACUUM トランザクションは通常のトランザクションとは異なる MVCC が適用されているためである。 一般セッションのトランザクションは、VACUUM 処理のトランザクションが生存中かどうかの判定ができない。 VACUUM 処理内で自身のトランザクションID(XID)を DB ページに書き込んだ場合、同時に走行しているトランザクションが DB ページからその情報を拾って XID の可視性の判定を行うと、VACUUM トランザクションが生存中だと判断できずコミット済みでもないのでアボートしたトランザクションの書き込みだと誤判定してしまう。 そのためトランザクションの中で MVCC を期待したデータ書き込みはできないことになる。

また VACUUM 処理自体も異常終了することがある。 この場合、VACUUM が行っていた処理が MVCC 的に補償されることがない。 そのため VACUUM が DB ページに対して行ってよい書き込みは冪当性のある処理、つまり同じ書き込みを何度実行しても問題ないものに限られる。 通常の VACUUM は xmin/xmax の凍結を行うが、VACUUM が異常終了した場合 xmin/xmax が凍結されてディスクに書き込まれた DB ページと未凍結の DB ページが混ざることになる。 このような場合でも xmin/xmax が凍結された DB ページに問題なくアクセスできるし、xmin/max が未凍結な DB ページには再 VACUUM 時に同じ処理をもう一度適用すればよい。

参考文献

• [1] PostgreSQL 9.5.4 文書 第58章 インデックスアクセスメソッドのインタフェース定義
• [2] myindex … 独自インデックスの雛形

コメント