54.2. 拡張性

接頭辞とノードラベルのデータ型のデータ型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にします(項54.3.1参照)。

内部タプルに新しい値を挿入するときのメソッドを選択します。

関数の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にします(項54.3.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が返り、リーフレベルに下がる挿入が可能となります。

リーフタプルの集合に対し、新しい内部タプルをどうやって作るかを決定します。

関数の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にセットします。詳細は項54.3.2を参照してください。) mapTuplesToNodesは、それぞれのリーフタプルが割り当てられるノードの番号(0から)の配列にセットします。 leafTupleDatumsは新しいリーフタプルに格納される値の配列にセットします(演算子クラスがデータをあるレベルから次のレベルに変更しなければこれらは入力のdatumsと同じになります)。 picksplit関数は、nodeLabels、mapTuplesToNodes、leafTupleDatumsの配列についてpallocしなければならないことに注意してください。

2つ以上のリーフタプルを与えた場合、picksplit関数はそれらを2つ以上のノードに分類すると予想されます。そうでなければ、リーフタプルを複数のページにまたがって分割するという、この操作の究極の目的を実現できないからです。 従って、picksplitがすべてのリーフタプルを同じノードに置くことになった場合には、SP-GiSTのコアのコードがその決定を覆して内部タプルを生成し、その中の複数の同一のラベルが付けられたノードに、リーフタプルが無作為に割り当てられます。 そのようなタプルは、このことが発生したことを明示するため、allTheSameと印がつけられます。 choose関数とinner_consistent関数は、これらの内部タプルについて、適切な注意をして取り扱わなければなりません。 詳細な情報は項54.3.3を参照してください。

config関数がlongValuesOKをtrueにセットし、1ページよりも大きな入力値を与える場合にのみ、picksplitを1つだけのリーフタプルに適用できます。 この場合の操作の重要な点は、接頭辞をはがして、新しい、より短いリーフデータの値を生成することです。 この呼出は、1ページに収まる短さのリーフデータが生成されるまで繰り返されます。 詳細な情報は項54.3.1を参照してください。

ツリーの探索でたどるべきノード(枝)の集合を返します。

関数の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になります。この場合、すべてのノードは(ラベルがあれば)同じラベルを持っていますから、そのすべてが問い合わせにマッチするか、いずれもマッチしないかのいずれかになります(項54.3.3参照)。 hasPrefixは現在の内部タプルが接頭辞を持っている場合にtrueとなり、このときprefixDatumがその値となります。 nNodesは内部タプルが含む子ノードの数です。nodeLabelsはそれらのラベル値の配列で、ノードにラベルがないときはNULLになります。

nNodesは探索で訪れる必要のある子ノードの数にセットされなければなりません。また、nodeNumbersはそれらの番号の配列にセットされなければなりません。 演算子クラスがレベルを監視しているときは、それぞれのノードへと下って訪れるときに必要なレベルの増分の配列をlevelAddsにセットします。 (この増分はすべてのノードについて同じになることも多いですが、必ずしもそうなるとは限らないので配列が使われます。) 値の再構築が必要なときには、訪れるそれぞれの子ノードについて再構築された値の配列をreconstructedValuesにセットします。再構築が必要でなければ、reconstructedValuesをNULLのままにします。 inner_consistent関数は、nodeNumbers、levelAdds、reconstructedValuesの配列についてpallocしなければならないことに注意してください。

リーフタプルが問い合わせを満たす場合、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にセットされることがあります。