前回、 Zオーダーに基づく空間インデックスが効果的に機能するためには、2つのことを行う必要があるという結論に達しました。
- サブインターバルを取得するための効率的なアルゴリズム
- Bツリーでの低レベルの作業
それはまさに私たちがカットの下で行うことです。
より興味深いアルゴリズムから始めましょう。
サブクエリの分割
比較的単純なため、2次元アルゴリズム（インデックスポイント）を検討します。 ただし、アルゴリズムは簡単に大規模に一般化できます。
ここで（簡単にするために）非負の整数座標を使用します。 座標は32ビットに制限されているため、インデックスキーの値はuint64に格納できます。
Zナンバリングの次の単純なプロパティが必要です。
- 長方形を平面上にマークしてみましょう。 次に、長方形のすべてのポイントの中で、最小のz番号は長方形の左下隅（「z」と呼びます）、最大の-右上隅（「Z」と呼びます）を持ちます。 この特性は、明らかにZ番号を構築する方法から得られます。
- 各長方形は、最初の長方形のすべてのz番号が2番目の長方形のすべてのz番号よりも小さくなるように、2つの長方形（垂直または水平セクション）に一意に分割できます。 これは、Z曲線の自己相似性から生じます。 4つのセルのユニットセルは半分に分割され、さらに2つのセクションが半分に分割されます。階層のすべてのレベルで同じことが起こります。
サブインターバルの連続性を維持するために、範囲をどの程度正確にカットする必要がありますか？
曲線の自己相似性から、格子に沿って2のべき乗のステップと原点での結び目のみを切断することができます。
しかし、64から選択できる特定の格子はどれですか？ とても簡単です。 カットする範囲は、目的のラティスの複数のセルを占有する必要があります。そうでない場合は、カットするものがまったくありません。 一方、どの座標でも、サイズは2セルを超えることはできません。少なくとも1つのセルは厳密に2セルでなければなりません。 カット範囲が両方の次元で2つのセルを占める場合、Z値の構築における放電が最も高い座標でカットします。
そのようなグリッドを見つける方法は？ これも簡単です。 角度zとZのZ値を比較するだけで十分です。上位桁との比較を開始し、値が発散した放電を見つけます。 これが目的のグリッドです。
カットする方法は？ ここで、Z値を作成する方法、つまり、x座標とy座標が放電を通じて交互に変わることを思い出す必要があります。 したがって：
- zとZの差を放電mから始めましょう
- xがthisであるかyであるかに関係なく、mが必要な1つの座標に沿ってカットします。ただし、この場合はxとしますが、yの場合はすべて同じように機能します
- エクステント（x0、y0、x1、y1）から、2つを取得する必要があります：（x0、y0、x2-1、y1）、（x2、y0、x1、y1）
- そして、x2を取得するには、すべての桁のx座標をm未満にリセットするだけで十分です。 通して
- x2-1は、ビットmをリセットし、すべての最下位xビットに1を割り当てることにより取得されます。
それでは、サブクエリ生成アルゴリズムはどのように見えますか？ とても簡単です：
- サブクエリのキューを開始します。最初はこのキューに1つの要素があります-目的の範囲
- キューが空ではない間：
- キューの先頭からアイテムを取得します
- このリクエストの停止基準が失敗した場合
- zおよびZ-角度の値を取得します
- zとZを比較-放電mを見つけます。
- 上記の方法で、2つのサブクエリを取得します
- それらをキューに入れます。最初に大きなZ値を持つもの、次に2番目の
このメソッドは、サブクエリの生成を保証します。サブクエリでは、最終（つまり、停止基準が機能した）サブクエリのZ値が増加するだけで、後方クエリはありません。
停止基準
非常に重要です。これを無視すると、すべてが単一の正方形に分割されるまで、サブクエリの生成が継続されます。
このような基準を作成する場合、クエリパラメータ、エリア、幾何学的プロパティだけに依存することはできないことに注意してください。実際のデータでは、ポイントの分布は非常に不均一になる場合があります。 事前に地域の人口は不明です。
そのため、インデックスツリーでの検索との統合が必要です。これは、思い出していただけるように、Bツリーです。
インデックスに関してサブクエリはどのように見えますか？ これは、いくつかのページにあるデータのコレクションです。 サブクエリが空の場合、データ間隔は空ですが、まだどこかに見えます。 データがないことを理解するには、それらを読み取って、ツリーの最上部からリーフページに移動する必要があります。 空のクエリもツリーの外に見えることがあります。
一般に、サブクエリデータの読み取りプロセスは2つのフェーズで構成されます-
- 響きのある木。 ルートページから開始して、サブクエリ（z）の左下隅のZ値以下のキーを探し、リーフページに移動します。 出力は、ページのスタックと「空中」のシートページです。 このページでは、目的の要素以上の要素を探しています。
- サブクエリの最後まで読んでください。 PostgreSQLでは、Bツリーリーフページはリストでリンクされています（リンクされていない場合）。次のページを取得するには、ページのスタックを上に移動してから下に移動する必要があります。
したがって、調査要求の後、データが開始されるはずのシートページが手元にあります。 さまざまな状況が考えられます。
- 見つかったページ要素は、サブクエリの右上隅（Z）よりも大きくなっています。 つまり データなし。
- 見つかったページ要素はZ未満で、最後のページ要素はZ未満です。つまり、 サブクエリはこのページで始まり、さらにどこかで終わります。
- 見つかったページ要素はZより小さく、最後のページ要素はZより大きくなります。 サブクエリ全体がこのページにあります。
- 見つかったページ要素はZより小さく、最後のページ要素はZです。つまり、 サブクエリはこのページから始まりますが、次のページ（同じ座標を持ついくつかの要素）で終わることもあります。 さらに多くの重複がある場合は、さらにはるかに。
オプションN1にはアクションは不要です。 N2の場合、次の停止基準（サブクエリの分割）は自然に見えます。オプション3または4が得られるまでそれらをカットします。オプションN3では、すべてが明らかです。N4の場合、複数のデータページがあります。 次のページでは、Zに等しいキーを持つデータのみが存在する可能性があります。カット後、同じ状況にいることがわかります。 これに対処するには、次のページから、Zに等しいキーを持つすべてのデータを単純に考慮するだけで十分です。一般に、N4はかなりエキゾチックなケースではありません。
Bツリーを使用する
Bツリーでの低レベルの作業は特に難しくありません。 ただし、 拡張機能を作成する必要があります。 一般的なロジックは次のとおりです-SRF関数を登録します。
CREATE TYPE __ret_2d_lookup AS (c_tid TID, x integer, y integer); CREATE FUNCTION zcurve_2d_lookup(text, integer, integer, integer, integer) RETURNS SETOF __ret_2d_lookup AS 'MODULE_PATHNAME' LANGUAGE C IMMUTABLE STRICT;
入力でインデックス名とエクステントを受け取ります。 は要素のセットを返します。各要素には、テーブルの行と座標へのポインタがあります。
ツリー自体へのアクセスは次のとおりです。
const char *relname; /* */ ... List *relname_list; RangeVar *relvar; Relation rel; ... relname_list = stringToQualifiedNameList(relname); relvar = makeRangeVarFromNameList(relname_list); rel = indexOpen(rel); ... indexClose(rel);
ルートページの取得：
int access = BT_READ; Buffer buf; ... buf = _bt_getroot(rel, access);
一般に、インデックス内の検索は、Bツリー内の通常の検索と同様に行われます（postgresql / src / backend / access / nbtree / nbtsearch.cを参照）。 変更はキーの詳細に関連しているため、少し遅くなる場合でも、キーなしで実行できます。
ページ内の検索は次のようになります。
Page page; BTPageOpaque opaque; OffsetNumber low, high; int32 result, cmpval; Datum datum; bool isNull; ... page = BufferGetPage(buf); opaque = (BTPageOpaque) PageGetSpecialPointer(page); low = P_FIRSTDATAKEY(opaque); high = PageGetMaxOffsetNumber(page); ... ... /* */ if (P_ISLEAF(opaque)) return low; /* - */ return OffsetNumberPrev(low);
ページ要素の取得：
OffsetNumber offnum; Page page; Relation rel; TupleDesc itupdesc = RelationGetDescr(rel); IndexTuple itup; Datum datum; bool isNull; uint64 val; ... itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); datum = index_getattr(itup, 1, itupdesc, &isNull); val = DatumGetInt64(datum);
最終的なアルゴリズム
- サブクエリのキューを開始します。最初はこのキューに1つの要素があります-目的の範囲
- キューが空ではない間：
- キューの先頭からアイテムを取得します
- zのインデックス（左下隅）でプローブクエリを実行します。 お金を節約するために、毎回ではなく、最後に見つかった値（最初は0）がz以上である場合にのみサウンドを鳴らすことができます
- 見つかった最小値がZ（右上隅）を超える場合、このサブクエリの処理を終了し、A.2に進みます。
- プローブ要求が停止したBツリーリーフページの最後の要素を確認します
- Z以上の場合は、ページ要素を選択し、検索範囲のメンバーシップにフィルターをかけ、結果のポイントを記憶します。
- Zに等しい場合、Zに等しい値を持つキーが完全に使い果たされるまでインデックスを前方に読み取り、それらを記憶します
- それ以外の場合、最後のページの値はZより小さい
- zとZを比較-放電mを見つけます。
- 上記の方法で、2つのサブクエリを取得します
- それらをキューに入れます。最初に大きなZ値を持つもの、次に2番目の
予備結果
記事のタイトルの図では、実際のクエリをサブクエリと結果ポイントに分類しています。 Rツリーで見つかった結果と上記のアルゴリズムで得られた結果の比較を示します。 デバッグ時間の図であり、1つのポイントでは不十分であることは明らかです。
しかし、写真は写真ですが、パフォーマンスの比較を見たいです。 私たちの側は同じテーブルになります：
create table test_points (x integer,y integer); COPY test_points from '/home/.../data.csv'; create index zcurve_test_points on test_points(zcurve_val_from_xy(x, y));
次のようなリクエスト：
select count(1) from zcurve_2d_lookup('zcurve_test_points', 500000,500000,501000,501000);
事実上の標準と同様に、Rツリーと比較します。 さらに、前の記事とは異なり、Rツリーで「インデックスのみのスキャン」が必要です。 Z-indexはテーブルにアクセスしなくなりました。
create table test_pt as (select point(x,y) from test_points); create index test_pt_idx on test_pt using gist (point); vacuum test_pt;
そのようなデータでは、リクエストは次のようになります。
explain (analyze, buffers) select * from test_pt where point <@ box( point(500000, 500000), point(510000, 510000));
配る：
QUERY PLAN --------------------------------------------------------------------------------------------- Index Only Scan using test_pt_idx on test_pt (cost=0.42..539.42 rows=10000 width=16) (actual time=0.075..0.531 rows=968 loops=1) Index Cond: (point <@ '(510000,510000),(500000,500000)'::box) Heap Fetches: 0 Buffers: shared hit=20 Planning time: 0.088 ms Execution time: 0.648 ms (6 rows)
必要に応じて。
実際の比較：
| リクエストタイプ | インデックスの種類 | 時間です。 | 共有読み取り | 共有ヒット |
|---|---|---|---|---|
| 100X100
〜1ポイント | Rツリー
Zカーブ | 0.4 *
0.34 * | 1.8
1.2 | 3.8
3.8 |
| 1000X1000
〜100ポイント | Rツリー
Zカーブ | 0.5 ... 7 **
0.41 * | 6.2
2.8 | 4.9
37 |
| 10000X10000
〜10,000ポイント | Rツリー
Zカーブ | 4 ... 150 ***
6.6 **** | 150
43.7 | 27
2900 |
**-一連の異なる長さの平均化によって取得されたデータ、10,000対100,000
***-データは、一連の異なる長さ、1,000対10,000を平均することによって取得されました
****-一連の長さ10 000を平均化して得られたデータ
測定は2つのコアと4 GBのRAMを備えた控えめな仮想マシンで実行されたため、時間には絶対値はありませんが、読み取られたページ数は信頼できます。
ホットサーバーと仮想マシンでの2回目の実行で時間が表示されます。 読み取られたバッファーの数は、新しく生成されたサーバー上にあります。
結論
- いずれにせよ、小さなクエリでは、ZインデックスはRツリーよりも高速です
- 著しく少ないページを読み取ります
- Rツリーは、かなり早くキャッシュをミスし始めます。
- 同時に、Zインデックス自体は4倍コンパクトなので、キャッシュはより効率的に動作します
- さらに、ミスがホストマシンのディスクキャッシュを通過する可能性があります。そうしないと、そのような違いを説明することが困難になります。
次は何ですか
考慮される2次元ポイントインデックスは、概念を検証することのみを目的としており、人生ではほとんど役に立たない。
3次元インデックスの場合でも、64ビットキーでは有用な解決策として十分ではありません（エンドツーエンド）。
今後の予定は次のとおりです。
- 別のキーに切り替える、数値
- 球上の点を含む3Dオプション
- ヒルベルト曲線を扱う可能性の確認
- 完全な測定
- 4Dオプション-長方形
- 6Dオプション-球体上の長方形
- ...
PS：ソースはBSDライセンスでここに投稿されています。この記事の説明は「raw-2D」ブランチに対応しています
PPS：アルゴリズム自体は、Alexander Artyushinと共同で古代（2004〜2005年）に開発されました。
PPPS：このアルゴリズムをPostgreSQLに実装することを奨励してくれたPostgresProの スタッフに感謝します。
PPPPS： ここから続きます