PostgreSQL 9.4.5文書 | |||
---|---|---|---|
前のページ | 上に戻る | 第 57章SP-GiSTインデックス | 次のページ |
SP-GiSTは高度に抽象化されたインタフェースを提供します。アクセスメソッドの開発者は特定のデータ型専用のメソッドだけを開発する必要があります。 SP-GiSTのコアは効率的なディスクマッピングと木構造の探索を担当します。 また、同時実行制御とログ出力も担当します。
SP-GiSTのツリーのリーフタプルは、インデックスの付けられた列と同じデータ型の値を含んでいます。 ルートレベルにあるリーフタプルは、必ずインデックスが付けられた元のデータの値を含んでいますが、より下のレベルのリーフタプルは、接尾辞など、圧縮された表現しか含んでいないかも知れません。 この場合、演算子クラスのサポート関数が、内部タプルをリーフレベルまでたどりながら集める情報を使って元の値を再構築できる必要があります。
内部タプルは、探索木の分岐点となるため、もっと複雑です。 それぞれの内部タプルは1つ以上のノードの集合を含んでおり、ノードは類似のリーフ値のグループを表現します。 ノードは下向きのリンクを含んでおり、これは下のレベルの別の内部タプルを指すか、あるいはすべて同じインデックスページ上に載っているリーフタプルの短いリストを指しています。 それぞれのノードは、それを記述するlabelを持っています。 例えば、基数木では、ノードのラベルは文字列の値の次の文字にすることができます。 省略可能ですが、内部タプルはそのすべてのメンバーを記述する接頭辞の値を持つことができます。 基数木では、これは表現される文字列に共通の接頭辞とすることができます。 接頭辞の値は、必ずしも本当の接頭辞である必要はなく、演算子クラスが必要とする任意の値で良いです。 例えば四分木では、その中心点を保持し、4つの象限をそこから相対的に測るようにできます。 そうすると、四分木の内部タプルはこの中心点の周りの象限に対応する4つのノードも含むことになるでしょう。
木構造のアルゴリズムには、現在のタプルのレベル(深さ)を知っていることが必要なものがあります。そこで、SP-GiSTのコアは、演算子クラスが木構造をたどって下がるときにレベル数の管理を可能にしています。 また、必要であれば、表現される値を加算的に再構築することもサポートしています。
注意: SP-GiSTのコアのコードはnullエントリについても対応しています。 SP-GiSTのインデックスはインデックス列がnullのエントリについても格納しますが、これはインデックスの演算子クラスのコードからは隠されているので、nullのインデックスエントリや検索条件が演算子クラスのメソッドに渡されることはありません。 (SP-GiSTの演算子は厳格なのでNULL値について成功を返すことはできないと想定されています。) 従って、ここではこれ以上、NULLについて議論しません。
SP-GiSTのインデックス演算子クラスが提供しなければならないユーザ定義メソッドが5つあります。
5つのメソッドはいずれも2つのinternal引数をとり、1番目の引数はサポートメソッドの入力値を含むCの構造体へのポインタ、2番目の引数は出力値が置かれるCの構造体へのポインタという形式に従っています。
メソッドのうち4つは、その結果がすべて出力構造体の中にあるので、単にvoidを返しますが、leaf_consistent
は、さらにbooleanの結果を返します。
メソッドは、その入力構造体のどのフィールドも変更してはいけません。
どんな場合でも、出力構造体はユーザ定義メソッドを呼び出す前にゼロに初期化されます。
5つのユーザ定義メソッドは以下のとおりです。
config
接頭辞とノードラベルのデータ型のデータ型OIDを含め、インデックスの実装に関する静的情報を返します。
関数のSQL宣言は以下のようになります。
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
1番目の引数はCのspgConfigIn構造体へのポインタで、関数の入力データを含みます。 2番目の引数はCのspgConfigOut構造体へのポインタで、関数が結果のデータを入れます。
typedef struct spgConfigIn { Oid attType; /* Data type to be indexed */ } spgConfigIn; typedef struct spgConfigOut { Oid prefixType; /* Data type of inner-tuple prefixes */ Oid labelType; /* Data type of inner-tuple node labels */ bool canReturnData; /* Opclass can reconstruct original data */ bool longValuesOK; /* Opclass can cope with values > 1 page */ } spgConfigOut;
attTypeは多様のインデックス演算子クラスをサポートするために渡されます。 通常の固定データ型の演算子クラスでは、それは常に同じ値を持っているので無視できます。
接頭辞を使わない演算子クラスでは、prefixTypeをVOIDOIDに設定することができます。 同様に、ノードラベルを使わない演算子クラスでは、labelTypeをVOIDOIDに設定することができます。 演算子クラスが、元々提供されていたインデックスの値を再構築できるときは、canReturnDataをtrueにします。 attTypeが可変長で、演算子クラスが接尾辞付けの繰り返しによって長い値を分割できるときにのみ、longValuesOKをtrueにします(項57.4.1参照)。
choose
内部タプルに新しい値を挿入するときのメソッドを選択します。
関数のSQL宣言は以下のようになります。
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
1番目の引数はCのspgChooseIn構造体へのポインタで、関数の入力データを含みます。 2番目の引数はCのspgChooseOut構造体へのポインタで、関数が結果のデータを入れます。
typedef struct spgChooseIn { Datum datum; /* original datum to be indexed */ Datum leafDatum; /* current datum to be stored at leaf */ int level; /* current level (counting from zero) */ /* Data from current inner tuple */ bool allTheSame; /* tuple is marked all-the-same? */ bool hasPrefix; /* tuple has a prefix? */ Datum prefixDatum; /* if so, the prefix value */ int nNodes; /* number of nodes in the inner tuple */ Datum *nodeLabels; /* node label values (NULL if none) */ } spgChooseIn; typedef enum spgChooseResultType { spgMatchNode = 1, /* descend into existing node */ spgAddNode, /* add a node to the inner tuple */ spgSplitTuple /* split inner tuple (change its prefix) */ } spgChooseResultType; typedef struct spgChooseOut { spgChooseResultType resultType; /* action code, see above */ union { struct /* results for spgMatchNode */ { int nodeN; /* descend to this node (index from 0) */ int levelAdd; /* increment level by this much */ Datum restDatum; /* new leaf datum */ } matchNode; struct /* results for spgAddNode */ { Datum nodeLabel; /* new node's label */ int nodeN; /* where to insert it (index from 0) */ } addNode; struct /* results for spgSplitTuple */ { /* Info to form new inner tuple with one node */ bool prefixHasPrefix; /* tuple should have a prefix? */ Datum prefixPrefixDatum; /* if so, its value */ Datum nodeLabel; /* node's label */ /* Info to form new lower-level inner tuple with all old nodes */ bool postfixHasPrefix; /* tuple should have a prefix? */ Datum postfixPrefixDatum; /* if so, its value */ } splitTuple; } result; } spgChooseOut;
datumはインデックスに挿入される元のデータです。
leafDatumは最初はdatumと同じですが、choose
あるいはpicksplit
メソッドがそれを変更すると、ツリーのより低いレベルで変更されることがあります。
挿入の探索がリーフのページに到達したとき、leafDatumの現在値が、新しく作成されるリーフタプルに格納される値となります。
levelは、ルートレベルを0として、現在の内部タプルのレベルを示します。
現在の内部タプルが複数の同等なノードを含むとして印を付けられているとき、allTheSameをtrueにします(項57.4.3参照)。
現在の内部タプルが接頭辞を含むとき、hasPrefixをtrueにします。
このとき、prefixDatumがその値になります。
nNodesは内部タプルが含む子ノードの数で、nodeLabelsはそれらのラベル値の配列、あるいはラベルがなければNULLになります。
choose
関数は、新しい値が既存の子ノードの1つとマッチするか、新しい子ノードを追加する必要があるか、あるいは新しい値がタプルの接頭辞と適合しないので内部タプルを分割してより制限のない接頭辞を作成する必要があるか、を決定することができます。
新しい値が既存の子ノードの1つにマッチしたときは、resultTypeをspgMatchNodeにセットします。 nodeNはノードの配列中のそのノードの番号(0から)にセットします。 levelAddは、そのノードをたどって下がるときに生じたlevelの増分にセットします。あるいは演算子クラスがレベルを使っていなければ0のままにします。 restDatumは、演算子クラスがデータをあるレベルから次のレベルに変更しないのであれば、datumに等しくセットします。そうでなければ、次のレベルでleafDatumとして使われる修正された値にセットします。
新しい子ノードを追加しなければならないときは、resultTypeをspgAddNodeにセットします。
nodeLabelは、新しいノードで使われるラベルにセットし、nodeNはノードの配列中の挿入される場所のノードの番号(0から)にセットします。
ノードを追加した後で、choose
関数を修正された内部タプルを使って再び呼び出しますが、このときは、spgMatchNodeという結果になるはずです。
新しい値がタプルの接頭辞と適合しないときは、resultTypeをspgSplitTupleにセットします。
このアクションは、すべての既存のノードを新しい低位の内部タプルに移動し、新しい低位の内部タプルにリンクする単一のノードを持つ新しいタプルで既存のタプルを置換します。
prefixHasPrefixは新しい上位のタプルが接頭辞を持つかどうかを示し、持つ場合にはprefixPrefixDatumをその接頭辞の値にセットします。
インデックスに追加される新しい値を受け入れるため、新しい接頭辞の値は元のものよりも制限の緩いものになっている必要があり、また元の接頭辞より長くはなりません。
nodeLabelは、新しい低位の内部タプルを指し示すノードで使われるラベルにセットします。
postfixHasPrefixは、新しい低位のタプルが接頭辞を持つかどうかを示し、持つときにはpostfixPrefixDatumを接頭辞の値にセットします。
新しい低位に移動したタプルのノードのラベルを変更する機会も、子のインデックスのエントリを変更する機会もありませんから、これら2つの接頭辞と追加のラベルの組み合わせは、元の接頭辞と同じ意味を持つ必要があります。
ノードが分割された後で、choose
を置換した内部タプルを使って再び呼び出します。
この呼び出しは、通常はspgAddNodeという結果になります。というのは、分割のステップで追加されたノードのラベルは恐らく新しい値とマッチしないからです。
従って、その後、3回目の呼び出しでやっとspgMatchNodeが返り、リーフレベルに下がる挿入が可能となります。
picksplit
リーフタプルの集合に対し、新しい内部タプルをどうやって作るかを決定します。
関数のSQL宣言は以下のようになります。
CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
1番目の引数はCのspgPickSplitIn構造体へのポインタで、関数の入力データを含みます。 2番目の引数はCのspgPickSplitOut構造体へのポインタで、関数が結果のデータを入れます。
typedef struct spgPickSplitIn { int nTuples; /* number of leaf tuples */ Datum *datums; /* their datums (array of length nTuples) */ int level; /* current level (counting from zero) */ } spgPickSplitIn; typedef struct spgPickSplitOut { bool hasPrefix; /* new inner tuple should have a prefix? */ Datum prefixDatum; /* if so, its value */ int nNodes; /* number of nodes for new inner tuple */ Datum *nodeLabels; /* their labels (or NULL for no labels) */ int *mapTuplesToNodes; /* node index for each leaf tuple */ Datum *leafTupleDatums; /* datum to store in each new leaf tuple */ } spgPickSplitOut;
nTuplesは入力されるリーフタプルの個数です。 datumsはデータの値の配列です。 levelはすべてのリーフタプルの現在のレベルで、これが新しい内部タプルのレベルになります。
hasPrefixは新しい内部タプルが接頭辞を持つかどうかを示し、持つ場合はprefixDatumを接頭辞の値にセットします。
nNodesは新しい内部タプルが含むノードの数を示し、nodeLabelsはそのラベル値の配列にセットします。
(ノードがラベルを必要としないときは、nodeLabelsをNULLにセットします。詳細は項57.4.2を参照してください。)
mapTuplesToNodesは、それぞれのリーフタプルが割り当てられるノードの番号(0から)の配列にセットします。
leafTupleDatumsは新しいリーフタプルに格納される値の配列にセットします(演算子クラスがデータをあるレベルから次のレベルに変更しなければこれらは入力のdatumsと同じになります)。
picksplit
関数は、nodeLabels、mapTuplesToNodes、leafTupleDatumsの配列についてpallocしなければならないことに注意してください。
2つ以上のリーフタプルを与えた場合、picksplit
関数はそれらを2つ以上のノードに分類すると予想されます。そうでなければ、リーフタプルを複数のページにまたがって分割するという、この操作の究極の目的を実現できないからです。
従って、picksplit
がすべてのリーフタプルを同じノードに置くことになった場合には、SP-GiSTのコアのコードがその決定を覆して内部タプルを生成し、その中の複数の同一のラベルが付けられたノードに、リーフタプルが無作為に割り当てられます。
そのようなタプルは、このことが発生したことを明示するため、allTheSameと印がつけられます。
choose
関数とinner_consistent
関数は、これらの内部タプルについて、適切な注意をして取り扱わなければなりません。
詳細な情報は項57.4.3を参照してください。
config
関数がlongValuesOKをtrueにセットし、1ページよりも大きな入力値を与える場合にのみ、picksplit
を1つだけのリーフタプルに適用できます。
この場合の操作の重要な点は、接頭辞をはがして、新しい、より短いリーフデータの値を生成することです。
この呼出は、1ページに収まる短さのリーフデータが生成されるまで繰り返されます。
詳細な情報は項57.4.1を参照してください。
inner_consistent
ツリーの探索でたどるべきノード(枝)の集合を返します。
関数のSQL宣言は以下のようになります。
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
1番目の引数はCのspgInnerConsistentIn構造体へのポインタで、関数の入力データを含みます。 2番目の引数はCのspgInnerConsistentOut構造体へのポインタで、関数が結果のデータを入れます。
typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ int level; /* current level (counting from zero) */ bool returnData; /* original data must be returned? */ /* Data from current inner tuple */ bool allTheSame; /* tuple is marked all-the-same? */ bool hasPrefix; /* tuple has a prefix? */ Datum prefixDatum; /* if so, the prefix value */ int nNodes; /* number of nodes in the inner tuple */ Datum *nodeLabels; /* node label values (NULL if none) */ } spgInnerConsistentIn; typedef struct spgInnerConsistentOut { int nNodes; /* number of child nodes to be visited */ int *nodeNumbers; /* their indexes in the node array */ int *levelAdds; /* increment level by this much for each */ Datum *reconstructedValues; /* associated reconstructed values */ } spgInnerConsistentOut;
配列scankeysは長さがnkeysで、インデックス検索の条件を記述します。
複数の条件はANDで結合されます。つまり、条件のすべてを満たすインデックスエントリのみが対象となります。
(nkeysが0ならば、すべてのエントリが検索条件を満たすことになる、ということに注意してください。)
通常、consistent関数では、配列のそれぞれのエントリのsk_strategyおよびsk_argumentフィールドのみが問題となります。これらのフィールドにはそれぞれインデックス付け可能な演算子と比較値が入ります。
なお、比較値がNULLかどうかを確認するためにsk_flagsを検査する必要はありません。なぜならSP-GiSTのコアのコードがそのような条件を除外するからです。
reconstructedValueは親タプルのために再構築された値で、ルートレベルの場合、あるいは親レベルのinner_consistent
関数が値を返さなかった場合は(Datum) 0となります。
levelは現在の内部タプルのレベルを、ルートレベルを0として数えたものです。
returnDataは、この問い合わせで再構築されたデータが必要な場合にtrueとなりますが、これはconfig
関数がcanReturnDataを確認した場合にのみ、そうなります。
allTheSameは、現在の内部タプルに"all-the-same"の印が付いている場合にtrueになります。この場合、すべてのノードは(ラベルがあれば)同じラベルを持っていますから、そのすべてが問い合わせにマッチするか、いずれもマッチしないかのいずれかになります(項57.4.3参照)。
hasPrefixは現在の内部タプルが接頭辞を持っている場合にtrueとなり、このときprefixDatumがその値となります。
nNodesは内部タプルが含む子ノードの数です。nodeLabelsはそれらのラベル値の配列で、ノードにラベルがないときはNULLになります。
nNodesは探索で訪れる必要のある子ノードの数にセットされなければなりません。また、nodeNumbersはそれらの番号の配列にセットされなければなりません。
演算子クラスがレベルを監視しているときは、それぞれのノードへと下って訪れるときに必要なレベルの増分の配列をlevelAddsにセットします。
(この増分はすべてのノードについて同じになることも多いですが、必ずしもそうなるとは限らないので配列が使われます。)
値の再構築が必要なときには、訪れるそれぞれの子ノードについて再構築された値の配列をreconstructedValuesにセットします。再構築が必要でなければ、reconstructedValuesをNULLのままにします。
inner_consistent
関数は、nodeNumbers、levelAdds、reconstructedValuesの配列についてpallocしなければならないことに注意してください。
leaf_consistent
リーフタプルが問い合わせを満たす場合、trueを返します。
関数のSQL宣言は以下のようになります。
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
1番目の引数はCのspgLeafConsistentIn構造体へのポインタで、関数の入力データを含みます。 2番目の引数はCのspgLeafConsistentOut構造体へのポインタで、関数が結果のデータを入れます。
typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ int level; /* current level (counting from zero) */ bool returnData; /* original data must be returned? */ Datum leafDatum; /* datum in leaf tuple */ } spgLeafConsistentIn; typedef struct spgLeafConsistentOut { Datum leafValue; /* reconstructed original data, if any */ bool recheck; /* set true if operator must be rechecked */ } spgLeafConsistentOut;
配列scankeysは長さがnkeysで、インデックス探索の条件を記述します。
複数の条件はANDで結合されます。つまり、条件のすべてを満たすインデックスエントリのみが対象となります。
(nkeysが0ならば、すべてのエントリが検索条件を満たすことになる、ということに注意してください。)
通常、consistent関数では、配列のそれぞれのエントリのsk_strategyおよびsk_argumentフィールドのみが問題となります。これらのフィールドにはそれぞれインデックス付け可能な演算子と比較値が入ります。
なお、比較値がNULLかどうかを確認するためにsk_flagsを検査する必要はありません。なぜならSP-GiSTのコアのコードがそのような条件を除外するからです。
reconstructedValueは親タプルのために再構築された値で、ルートレベルの場合、あるいは親レベルのinner_consistent
関数が値を返さなかった場合は(Datum) 0となります。
levelは現在のリーフタプルのレベルを、ルートレベルを0として数えたものです。
returnDataは、この問い合わせで再構築されたデータが必要な場合にtrueとなりますが、これはconfig
関数がcanReturnDataを確認した場合にのみ、そうなります。
leafDatumは現在のリーフタプルに格納されている鍵の値です。
この関数は、リーフタプルが問い合わせにマッチすればtrueを返し、マッチしなければfalseを返します。 trueの場合、returnDataがtrueであれば、leafValueは、このリーフタプルにインデックス付けするために元々提供された値にセットされなければなりません。 また、マッチするかどうかが不確実で、マッチするかの確認のために実際のヒープタプルに演算子を再適用しなければならないときは、recheckがtrueにセットされることがあります。
SP-GiSTのすべてのサポートメソッドは、通常は短期間有効なメモリコンテキスト内で呼び出されます。つまり、それぞれのタプルについて処理した後でCurrentMemoryContextはリセットされます。
したがって、pallocしたものすべてについてpfreeすることを気にかけることはあまり重要ではありません。
(config
メソッドは例外で、メモリリークを避けるようにする必要があります。
しかし、通常はconfig
メソッドは、パラメータとして渡された構造体に定数を代入する以外、何もする必要がありません。)
インデックス付けされた列が照合可能なデータ型の場合、インデックスの照合は、標準的なPG_GET_COLLATION()
の仕組みを使ってすべてのサポートメソッドに渡されます。