無料スクリプト配布のPHP.TO   PHPの実用的なtips PHPマニュアル MySQLマニュアル Apacheマニュアル PostgreSQLマニュアル マニュアル検索    

56.2. 拡張性

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

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

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

config 関数が longValuesOK をtrueにセットし、1ページよりも大きな入力値を与える場合にのみ、 picksplit を1つだけのリーフタプルに適用できます。 この場合の操作の重要な点は、接頭辞をはがして、新しい、より短いリーフデータの値を生成することです。 この呼出は、1ページに収まる短さのリーフデータが生成されるまで繰り返されます。 詳細な情報は 項56.3.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になります。この場合、すべてのノードは(ラベルがあれば)同じラベルを持っていますから、そのすべてが問い合わせにマッチするか、いずれもマッチしないかのいずれかになります( 項56.3.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() の仕組みを使ってすべてのサポートメソッドに渡されます。


powered by SEO.CUG.NET