Clever Geek Handbook

ZオーダーとRツリーについて

画像






Rツリーと比較したZ次曲線に基づくインデックスには、多くの利点があります。





ただし、Zオーダーに基づくインデックスには欠点があります-比較的低いパフォーマンスです:)。 カットの下で、この欠点が何に関係しているか、そしてそれを使って何かを行うことができるかどうかを理解しようとします。



おおよそ、Z曲線の意味は次のとおりです。結果として、x座標とy座標のビットを1つの値で交互に入れ替えます。 例は（x = 33（ 010 0001 ）、y = 22（ 01 0110 ）、Z = 1577（ 0 1 1 0 0 0 1 0 1 0 0 1 ）。2つのポイントの座標が近い場合、Z-それらの値は近くなります。

3次元（またはそれ以上）バージョンも同様に配置され、3（またはそれ以上）の座標の数字を交互に並べます。



また、特定の範囲で検索するには、この範囲のZ曲線のすべての値を「ラスタライズ」し、連続した間隔を見つけて、それぞれを検索する必要があります。



エクステント[111000 ... 111000] [111400 ... 111400]（675間隔）、右上隅（各連続ポリラインは1間隔）の図です。



画像






また、たとえば、範囲[111000 ... 111000] [112000 ... 112000]の場合、1688の連続した間隔が得られます。明らかに、その数は主に境界の長さに依存します。 将来を見ると、テストデータでは、6間隔で15ポイントがこの範囲に入りました。



はい、これらの間隔のほとんどは、1つの値から縮退するまで小さくなります。 それにもかかわらず、このすべての範囲に値が1つしかない場合でも、その値は任意の間隔にあります。 そして、それが好きかどうかにかかわらず、1688個すべてのサブクエリを実行して、実際にポイントがいくつあるかを調べる必要があります。



左下の値から右上のすべてを表示することはオプションではありません。この場合の角度の違いは3 144 768です。3倍以上のデータを見る必要があり、これは最悪の場合とはほど遠いです。 たとえば、エクステント[499500 ... 499500] [500500 ... 500500]は、135,263,808の値の範囲（エクステント領域の135倍）を提供します。



そして、ここで伝統的な質問をすることができます-



もしも...



一般に空のインデックスがあると仮定すると、これを理解するためにこれらの数百および数千のサブクエリをすべて実行する必要がありますか？ いいえ、1つで十分です-左下から右上へ。



ここで、範囲が十分に小さく、データがまばらで、何かを見つける可能性が小さいとします。 隅から隅まで同じリクエストを実行してみましょう。 何も見つからなかった場合、何もありません。 そうでなければ、チャンスがあります。 しかし、見たように、隅から隅へのリクエストによってスイープされた領域は、検索範囲よりも何倍も大きくなる可能性があり、明らかに不要なデータを読み取る必要はありません。 したがって、カーソル全体を表示するのではなく、そこから最小のZ値のみを取得します。 これを行うには、クエリは（order by）および（top 1）を使用して実行されます。



ですから、何らかの意味があります。 この値が私たちの範囲からではないと仮定すると、それは何を与えることができますか？ [1 ... N]のサブクエリ範囲のソートされた配列があることを思い出してください。 バイナリ検索を実行し、mとm + 1の間であっても、この値が絞り込まれるサブクエリを見つけます。 驚くべきことに、それは1からmまでのリクエストを省略することができることを意味し、明らかにそこには何もない。



値が私たちの範囲に属している場合、それは私たちの範囲の1つに入り、mではありますが、どれであるかを見つけることもできます。 前と同様に、番号1 ... m-1のリクエストは省略できます。 しかし、番号mの間隔は、その中にあるすべてのものを私たちに与える別個の要求に値します。



まあ、まだデータが残っているかもしれないので、続けましょう。 再度、リクエストを実行しますが、コーナーからコーナーではなく、間隔m + 1の開始から右上コーナーまでです。 そして、間隔のリストの最後に達するまでこれを行います。



これが全体の考え方です。大量のデータや大量のデータが範囲内に入った場合でも正常に機能することに注意してください。 一見すると、これはリクエストの数を根本的に減らし、作業を高速化します。



アイデアを実際にテストするときが来ました。 テストサイトとして、 PostgeSQL 9.6.1、 GiSTを使用します。 測定は2つのコアと4 GBのRAMを備えた控えめな仮想マシンで実行されたため、時間には絶対値はありませんが、読み取られたページ数は信頼できます。



ソースデータ



エクステント[0 ... 1 000 000] [0 ... 1 000 000]の1億個のランダムポイントがデータとして使用されました。



2次元のポイントデータのテーブルを取得してみましょう。 



create table test_points (x integer,y integer);


データを作成します。



gawkスクリプト
BEGIN {

for（i = 0; i <100000000; i ++）

{

x = int（1000000 * rand（））;

y = int（1000000 * rand（））;

print x "\ t" z;

}

exit（0）;

}



結果のファイルを並べ替え（以下の説明）、COPY演算子を使用してテーブルに入力します。 



 COPY test_points from '/home/.../data.csv';


テーブルへの入力には数分かかります。 データサイズ（\ dt +）-4358 Mb



Rツリー



対応するインデックスは次のコマンドで作成されます： 



 create index test_gist_idx on test_points using gist ((point(x,y)));


しかし、ニュアンスがあります。 インデックスは非常に長い間ランダムデータに基づいて作成されます（いずれの場合も、作成者には一晩で作成する時間がありませんでした）。 事前に並べ替えられたデータの構築には、約1時間かかりました。



インデックスサイズ（\ di +）-9031 Mb



基本的に、テーブル内のデータの順序は重要ではありませんが、さまざまな方法に共通する必要があるため、ソートされたテーブルを使用する必要がありました。



テストリクエストは次のようになります。 



 select count(1) from test_points where point(x,y) <@ box(point("xmin","ymin"),point("xmax","ymax"));


通常のインデックスの検証



パフォーマンスをテストするために、xとyによって個別のインデックスで空間クエリを実行します。 次のように作成されます。 



 create index x_test_points on test_points (x); create index y_test_points on test_points (y);


数分かかります。



テストリクエスト： 



 select count(1) from test_points where x >= "xmin" and x <= "xmax" and y >= "ymin" and y <= "ymax";


Z-index



ここで、x、y座標をZ値に変換できる関数が必要です。



最初に、 拡張子を作成し、その中に関数を作成します。 



 CREATE FUNCTION zcurve_val_from_xy(bigint, bigint) RETURNS bigint AS 'MODULE_PATHNAME' LANGUAGE C IMMUTABLE STRICT;


彼女の体： 
 static uint32 stoBits[8] = {0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080}; uint64 zcurve_fromXY (uint32 ix, uint32 iy) { uint64 val = 0; int curmask = 0xf; unsigned char *ptr = (unsigned char *)&val; int i; for (i = 0; i < 8; i++) { int xp = (ix & curmask) >> (i<<2); int yp = (iy & curmask) >> (i<<2); int tmp = (xp & stoBits[0]) | ((yp & stoBits[0])<<1) | ((xp & stoBits[1])<<1) | ((yp & stoBits[1])<<2) | ((xp & stoBits[2])<<2) | ((yp & stoBits[2])<<3) | ((xp & stoBits[3])<<3) | ((yp & stoBits[3])<<4); curmask <<= 4; ptr[i] = (unsigned char)tmp; } return val; } Datum zcurve_val_from_xy(PG_FUNCTION_ARGS) { uint64 v1 = PG_GETARG_INT64(0); uint64 v2 = PG_GETARG_INT64(1); PG_RETURN_INT64(zcurve_fromXY(v1, v2)); }




これで（もちろんCREATE EXTENSIONの後）、Z-indexは次のように構築されます： 



 create index zcurve_test_points on test_points(zcurve_val_from_xy(x, y));


これには数分かかります（データの並べ替えは不要です）。



インデックスサイズ（\ di +）-2142 Mb（Rツリーよりも4倍小さい）



Z-Index検索



したがって、最初の（「単純」と呼ぶ）バージョンでは、次のようにします。



  1. サイズdx * dyのエクステントの場合、対応するサイズの識別子の配列を開始します
  2. 範囲内の各ポイントについて、Z値が計算されます
  3. 識別子の配列を並べ替える
  4. 連続間隔を見つける
  5. 間隔ごとに、次の形式のサブクエリを実行します。 



     select * from test_points where zcurve_val_from_xy(x, y) between $1 and $2


  6. 結果を得る


このオプションを使用して検索するには、関数（下の本文）を使用します。 



 CREATE FUNCTION zcurve_oids_by_extent(bigint, bigint, bigint, bigint) RETURNS bigint AS 'MODULE_PATHNAME' LANGUAGE C IMMUTABLE STRICT;


この関数を使用した空間クエリは次のようになります。 



 select zcurve_oids_by_extent("xmin","ymin","xmax","ymax") as count;


この関数はヒット数のみを返します。データ自体は、必要に応じて「 elog（INFO ...） 」を使用して表示できます。



2番目の改善された（「サンプル」と呼びましょう）オプションは次のとおりです。



  1. サイズdx * dyのエクステントに対して、対応するサイズの識別子の配列を開始します
  2. 範囲内の各ポイントについて、Z値が計算されます
  3. 識別子の配列をソートします
  4. 連続間隔を見つける
  5. 見つかった最初の間隔から開始します。



    1. 次のタイプの「テスト」リクエストを実行します（パラメーター-間隔の境界）： 



       select * from test_points where zcurve_val_from_xy(x, y) between $1 and $2 order by zcurve_val_from_xy(x, y) limit 1


    2. このクエリは、現在のテスト間隔の開始から検索範囲の終了までのZ値が最小のテーブルの行を提供します。

    3. 要求で何も見つからなかった場合、検索範囲にデータが残っていないため、終了します。

    4. これで、見つかったZ値を分析できます。



      1. いずれかの間隔に収まるかどうかを確認します。
      2. そうでない場合は、次の残りの間隔の番号を見つけて、ステップ5に進みます。
      3. ひどい場合は、このタイプの間隔でクエリを実行します。 



         select * from test_points where zcurve_val_from_xy(x, y) between $1 and $2


      4. 次の間隔を取り、ステップ5に進みます。


このオプションを使用して検索するには、次の関数を使用します。 



 CREATE FUNCTION zcurve_oids_by_extent_ii(bigint, bigint, bigint, bigint) RETURNS bigint AS 'MODULE_PATHNAME' LANGUAGE C IMMUTABLE STRICT;


この関数を使用した空間クエリは次のようになります。 



 select zcurve_oids_by_extent_ii("xmin","ymin","xmax","ymax") as count;


また、この関数はヒット数のみを返します。



ラスタライズ



説明されているアルゴリズムでは、間隔のリストを取得するために、非常に単純で非効率的な「ラスタライズ」アルゴリズムが使用されています。



一方、彼の作品の平均時間を適切なサイズのランダムな範囲で測定することは難しくありません。 ここにあります：

エクステントdx * dy SERPの予想される平均ポイント数 時間、ミリ秒
100X100 1 .96（.37 + .59）
316X316 10 11（3.9 + 7.1）
1000X1000 100 119.7（35 + 84.7）
3162X3162 1000 1298（388 + 910）
10000X10000 10,000 14696（3883 + 10813）
カッコ内に2つのフェーズが個別に示されています-Z値の計算とソート



結果



データを含むピボットテーブルを次に示します。

Nポイント 種類 時間（ミリ秒） 読みます 共有ヒット
1 X＆Y

rtree

Z値

Z値II 		43.6

.5

8.3（9.4）

1.1（2.2） 		59.0173

4.2314

4.0988

4.1984（12.623） 		6.1596

2.6565

803.171

20.1893（57.775）
10 X＆Y

rtree

Z値

Z値II 		83.5

.6

15（26）

4（15） 		182.592

13.7341

14.834

14.832（31.439） 		9.24363

2.72466

2527.56

61.814（186.314）
100 X＆Y

rtree

Z値

Z値II 		220

2.1

80（200）

10（130） 		704.208

95.8179

95.215

96.198（160.443） 		16.528

5.3754

8007.3

208.214（600.049）
1000 X＆Y

rtree

Z値

Z値II 		740

12

500（1800）

200（1500） 		3176.06

746.617

739.32

739.58（912.631） 		55.135

25.439

25816

842.88（2028.81）
10,000 X＆Y

rtree

Z値

Z値II 		2,500

70 ... 1 200

4700（19000）

1300（16000） 		12393.2

4385.64

4284.45

4305.78（4669） 		101.43

121.56

86274.9

5785.06（9188）
Npoints -SERPの平均ポイント数。



タイプ -

時間（ミリ秒） -リクエスト実行の平均時間。 これらの条件下では、値は非常に不安定で、DBMSキャッシュ、仮想マシンのディスクキャッシュ、およびホストシステムのディスクキャッシュに依存します。 ここで参照する可能性が高くなります。 Z-valueおよびZ-value-iiには、2つの数値が与えられます。 括弧内は実際の時間です。 括弧なし-時間から「ラスタライズ」のコストを引いたもの。



読み取り -要求ごとの読み取りの平均数（EXPLAIN（ANALYZE、BUFFERS）を介して受信）



共有ヒット -バッファの呼び出し回数（...）

Z-value-iiの場合、読み取りと共有のヒット列に2つの数値が表示されます。 括弧内は測定値の総数です。 括弧なし-order byおよびlimit 1を使用したクエリの調査を除く したがって、そのような要求に関する統計は不要と見なされましたが、参照用に提供されました。



ホットサーバーと仮想マシンでの2回目の実行で時間が表示されます。 読み取られたバッファーの数は、新しく生成されたサーバー上にあります。



すべてのタイプのクエリで、テーブル自体のデータはインデックスに属していませんでした。 ただし、これは同じテーブルからの同じデータであるため、すべての種類のクエリで定数値を取得しました。



結論



  1. Rツリーは静的な状態では依然として非常に優れており、ページ読み取りの効率は非常に高くなっています。
  2. ただし、Zオーダーインデックスは、必要なデータがないページを読み取る必要がある場合があります。 これは、テストカーソルが間隔の間にある場合に発生し、この間隔には多くの外部ポイントが存在する可能性があり、特定のページには集計データが含まれません。
  3. それにもかかわらず、より高密度のパッケージングにより、Zオーダーは実際に読み取られるページ数においてRツリーに近くなります 。 これは、 潜在的に Zオーダーが同様のパフォーマンスを生成できることを示唆しています。

  4. Zオーダーインデックスは、キャッシュから膨大な数のページを読み取ります。 要求は同じ場所で何度も行われます。 一方、これらの測定値は比較的安価です。
  5. 大規模なクエリでは、Zオーダーの速度がRツリーよりも大幅に低下します。 これは、サブクエリを実行するために高レベルで高速ではない機構であるSPIを使用するという事実によって説明されます。 そして、もちろん「ラスタライズ」では、何かをする必要があります。
  6. 一見、間隔サンプルを使用しても作業が大幅に加速されることはありませんでしたが、正式にはページ読み取りの統計がさらに悪化しました。 ただし、これは使用する必要があった高レベルの資金のコストであることを理解する必要があります。 潜在的に、Zオーダーベースのインデックスは、パフォーマンスの点ではRツリーより悪くなく、他の戦術的および技術的特性の点でははるかに優れています。


見込み



同等の条件でRツリーと競合できるZオーダーに基づいた本格的な空間インデックスを作成するには、次の問題を解決する必要があります。





幸いなことに、これらの両方は不可能とは思えません。



ソースコード 
 #include "postgres.h" #include "catalog/pg_type.h" #include "fmgr.h" #include <string.h> #include "executor/spi.h" PG_MODULE_MAGIC; uint64 zcurve_fromXY (uint32 ix, uint32 iy); void zcurve_toXY (uint64 al, uint32 *px, uint32 *py); static uint32 stoBits[8] = {0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080}; uint64 zcurve_fromXY (uint32 ix, uint32 iy) { uint64 val = 0; int curmask = 0xf; unsigned char *ptr = (unsigned char *)&val; int i; for (i = 0; i < 8; i++) { int xp = (ix & curmask) >> (i<<2); int yp = (iy & curmask) >> (i<<2); int tmp = (xp & stoBits[0]) | ((yp & stoBits[0])<<1) | ((xp & stoBits[1])<<1) | ((yp & stoBits[1])<<2) | ((xp & stoBits[2])<<2) | ((yp & stoBits[2])<<3) | ((xp & stoBits[3])<<3) | ((yp & stoBits[3])<<4); curmask <<= 4; ptr[i] = (unsigned char)tmp; } return val; } void zcurve_toXY (uint64 al, uint32 *px, uint32 *py) { unsigned char *ptr = (unsigned char *)&al; int ix = 0; int iy = 0; int i; if (!px || !py) return; for (i = 0; i < 8; i++) { int tmp = ptr[i]; int tmpx = (tmp & stoBits[0]) + ((tmp & stoBits[2])>>1) + ((tmp & stoBits[4])>>2) + ((tmp & stoBits[6])>>3); int tmpy = ((tmp & stoBits[1])>>1) + ((tmp & stoBits[3])>>2) + ((tmp & stoBits[5])>>3) + ((tmp & stoBits[7])>>4); ix |= tmpx << (i << 2); iy |= tmpy << (i << 2); } *px = ix; *py = iy; } PG_FUNCTION_INFO_V1(zcurve_val_from_xy); Datum zcurve_val_from_xy(PG_FUNCTION_ARGS) { uint64 v1 = PG_GETARG_INT64(0); uint64 v2 = PG_GETARG_INT64(1); PG_RETURN_INT64(zcurve_fromXY(v1, v2)); } static const int s_maxx = 1000000; static const int s_maxy = 1000000; #ifndef MIN #define MIN(a,b) ((a)<(b)?(a):(b)) #endif static int compare_uint64( const void *arg1, const void *arg2 ) { const uint64 *a = (const uint64 *)arg1; const uint64 *b = (const uint64 *)arg2; if (*a == *b) return 0; return *a > *b ? 1: -1; } SPIPlanPtr prep_interval_request(); int fin_interval_request(SPIPlanPtr pplan); int run_interval_request(SPIPlanPtr pplan, uint64 v0, uint64 v1); SPIPlanPtr prep_interval_request() { SPIPlanPtr pplan; char sql[8192]; int nkeys = 2; Oid argtypes[2] = {INT8OID, INT8OID}; /* key types to prepare execution plan */ int ret =0; if ((ret = SPI_connect()) < 0) /* internal error */ elog(ERROR, "check_primary_key: SPI_connect returned %d", ret); snprintf(sql, sizeof(sql), "select * from test_points where zcurve_val_from_xy(x, y) between $1 and $2"); /* Prepare plan for query */ pplan = SPI_prepare(sql, nkeys, argtypes); if (pplan == NULL) /* internal error */ elog(ERROR, "check_primary_key: SPI_prepare returned %d", SPI_result); return pplan; } int fin_interval_request(SPIPlanPtr pplan) { SPI_finish(); return 0; } int run_interval_request(SPIPlanPtr pplan, uint64 v0, uint64 v1) { Datum values[2]; /* key types to prepare execution plan */ Portal portal; int cnt = 0, i; values[0] = Int64GetDatum(v0); values[1] = Int64GetDatum(v1); portal = SPI_cursor_open(NULL, pplan, values, NULL, true); if (NULL == portal) /* internal error */ elog(ERROR, "check_primary_key: SPI_cursor_open"); for (;;) { SPI_cursor_fetch(portal, true, 8); if (0 == SPI_processed || NULL == SPI_tuptable) break; { TupleDesc tupdesc = SPI_tuptable->tupdesc; for (i = 0; i < SPI_processed; i++) { HeapTuple tuple = SPI_tuptable->vals[i]; //elog(INFO, "%s, %s", SPI_getvalue(tuple, tupdesc, 1), SPI_getvalue(tuple, tupdesc, 2)); cnt++; } } } SPI_cursor_close(portal); return cnt; } PG_FUNCTION_INFO_V1(zcurve_oids_by_extent); Datum zcurve_oids_by_extent(PG_FUNCTION_ARGS) { SPIPlanPtr pplan; uint64 x0 = PG_GETARG_INT64(0); uint64 y0 = PG_GETARG_INT64(1); uint64 x1 = PG_GETARG_INT64(2); uint64 y1 = PG_GETARG_INT64(3); uint64 *ids = NULL; int cnt = 0; int sz = 0, ix, iy; x0 = MIN(x0, s_maxx); y0 = MIN(y0, s_maxy); x1 = MIN(x1, s_maxx); y1 = MIN(y1, s_maxy); if (x0 > x1) elog(ERROR, "xmin > xmax"); if (y0 > y1) elog(ERROR, "ymin > ymax"); sz = (x1 - x0 + 1) * (y1 - y0 + 1); ids = (uint64*)palloc(sz * sizeof(uint64)); if (NULL == ids) /* internal error */ elog(ERROR, "cant alloc %d bytes in zcurve_oids_by_extent", sz); for (ix = x0; ix <= x1; ix++) for (iy = y0; iy <= y1; iy++) { ids[cnt++] = zcurve_fromXY(ix, iy); } qsort (ids, sz, sizeof(*ids), compare_uint64); cnt = 0; pplan = prep_interval_request(); { // FILE *fl = fopen("/tmp/ttt.sql", "w"); int cur_start = 0; int ix; for (ix = cur_start + 1; ix < sz; ix++) { if (ids[ix] != ids[ix - 1] + 1) { cnt += run_interval_request(pplan, ids[cur_start], ids[ix - 1]); // fprintf(fl, "EXPLAIN (ANALYZE,BUFFERS) select * from test_points where zcurve_val_from_xy(x, y) between %ld and %ld;\n", ids[cur_start], ids[ix - 1]); // elog(INFO, "%d -> %d (%ld -> %ld)", cur_start, ix - 1, ids[cur_start], ids[ix - 1]); // cnt++; cur_start = ix; } } if (cur_start != ix) { cnt += run_interval_request(pplan, ids[cur_start], ids[ix - 1]); // fprintf(fl, "EXPLAIN (ANALYZE,BUFFERS) select * from test_points where zcurve_val_from_xy(x, y) between %ld and %ld;\n", ids[cur_start], ids[ix - 1]); // elog(INFO, "%d -> %d (%ld -> %ld)", cur_start, ix - 1, ids[cur_start], ids[ix - 1]); } // fclose(fl); } fin_interval_request(pplan); pfree(ids); PG_RETURN_INT64(cnt); } //------------------------------------------------------------------------------------------------ struct interval_ctx_s { SPIPlanPtr cr_; SPIPlanPtr probe_cr_; uint64 cur_val_; uint64 top_val_; FILE * fl_; }; typedef struct interval_ctx_s interval_ctx_t; int prep_interval_request_ii(interval_ctx_t *ctx); int run_interval_request_ii(interval_ctx_t *ctx, uint64 v0, uint64 v1); int probe_interval_request_ii(interval_ctx_t *ctx, uint64 v0); int fin_interval_request_ii(interval_ctx_t *ctx); int prep_interval_request_ii(interval_ctx_t *ctx) { char sql[8192]; int nkeys = 2; Oid argtypes[2] = {INT8OID, INT8OID}; /* key types to prepare execution plan */ int ret =0; if ((ret = SPI_connect()) < 0) /* internal error */ elog(ERROR, "check_primary_key: SPI_connect returned %d", ret); snprintf(sql, sizeof(sql), "select * from test_points where zcurve_val_from_xy(x, y) between $1 and $2"); ctx->cr_ = SPI_prepare(sql, nkeys, argtypes); if (ctx->cr_ == NULL) /* internal error */ elog(ERROR, "check_primary_key: SPI_prepare returned %d", SPI_result); snprintf(sql, sizeof(sql), "select * from test_points where zcurve_val_from_xy(x, y) between $1 and %ld order by zcurve_val_from_xy(x::int4, y::int4) limit 1", ctx->top_val_); ctx->probe_cr_ = SPI_prepare(sql, 1, argtypes); if (ctx->probe_cr_ == NULL) /* internal error */ elog(ERROR, "check_primary_key: SPI_prepare returned %d", SPI_result); return 1; } int probe_interval_request_ii(interval_ctx_t *ctx, uint64 v0) { Datum values[1]; /* key types to prepare execution plan */ Portal portal; values[0] = Int64GetDatum(v0); { // uint32 lx, ly; // zcurve_toXY (v0, &lx, &ly); // // elog(INFO, "probe(%ld:%d,%d)", v0, lx, ly); } if (ctx->fl_) fprintf(ctx->fl_, "EXPLAIN (ANALYZE,BUFFERS) select * from test_points where zcurve_val_from_xy(x, y) between %ld and %ld order by zcurve_val_from_xy(x::int4, y::int4) limit 1;\n", v0, ctx->top_val_); portal = SPI_cursor_open(NULL, ctx->probe_cr_, values, NULL, true); if (NULL == portal) /* internal error */ elog(ERROR, "check_primary_key: SPI_cursor_open"); { SPI_cursor_fetch(portal, true, 1); if (0 != SPI_processed && NULL != SPI_tuptable) { TupleDesc tupdesc = SPI_tuptable->tupdesc; bool isnull; HeapTuple tuple = SPI_tuptable->vals[0]; Datum dx, dy; uint64 zv = 0; dx = SPI_getbinval(tuple, tupdesc, 1, &isnull); dy = SPI_getbinval(tuple, tupdesc, 2, &isnull); zv = zcurve_fromXY(DatumGetInt64(dx), DatumGetInt64(dy)); // elog(INFO, "%ld %ld -> %ld", DatumGetInt64(dx), DatumGetInt64(dy), zv); ctx->cur_val_ = zv; SPI_cursor_close(portal); return 1; } SPI_cursor_close(portal); } return 0; } int run_interval_request_ii(interval_ctx_t *ctx, uint64 v0, uint64 v1) { Datum values[2]; /* key types to prepare execution plan */ Portal portal; int cnt = 0, i; values[0] = Int64GetDatum(v0); values[1] = Int64GetDatum(v1); // elog(INFO, "[%ld %ld]", v0, v1); if (ctx->fl_) fprintf(ctx->fl_, "EXPLAIN (ANALYZE,BUFFERS) select * from test_points where zcurve_val_from_xy(x, y) between %ld and %ld;\n", v0, v1); portal = SPI_cursor_open(NULL, ctx->cr_, values, NULL, true); if (NULL == portal) /* internal error */ elog(ERROR, "check_primary_key: SPI_cursor_open"); for (;;) { SPI_cursor_fetch(portal, true, 8); if (0 == SPI_processed || NULL == SPI_tuptable) break; { TupleDesc tupdesc = SPI_tuptable->tupdesc; for (i = 0; i < SPI_processed; i++) { HeapTuple tuple = SPI_tuptable->vals[i]; // elog(INFO, "%s, %s", SPI_getvalue(tuple, tupdesc, 1), SPI_getvalue(tuple, tupdesc, 2)); cnt++; } } } SPI_cursor_close(portal); return cnt; } PG_FUNCTION_INFO_V1(zcurve_oids_by_extent_ii); Datum zcurve_oids_by_extent_ii(PG_FUNCTION_ARGS) { uint64 x0 = PG_GETARG_INT64(0); uint64 y0 = PG_GETARG_INT64(1); uint64 x1 = PG_GETARG_INT64(2); uint64 y1 = PG_GETARG_INT64(3); uint64 *ids = NULL; int cnt = 0; int sz = 0, ix, iy; interval_ctx_t ctx; x0 = MIN(x0, s_maxx); y0 = MIN(y0, s_maxy); x1 = MIN(x1, s_maxx); y1 = MIN(y1, s_maxy); if (x0 > x1) elog(ERROR, "xmin > xmax"); if (y0 > y1) elog(ERROR, "ymin > ymax"); sz = (x1 - x0 + 1) * (y1 - y0 + 1); ids = (uint64*)palloc(sz * sizeof(uint64)); if (NULL == ids) /* internal error */ elog(ERROR, "can't alloc %d bytes in zcurve_oids_by_extent_ii", sz); for (ix = x0; ix <= x1; ix++) for (iy = y0; iy <= y1; iy++) { ids[cnt++] = zcurve_fromXY(ix, iy); } qsort (ids, sz, sizeof(*ids), compare_uint64); ctx.top_val_ = ids[sz - 1]; ctx.cur_val_ = 0; ctx.cr_ = NULL; ctx.probe_cr_ = NULL; ctx.fl_ = NULL;//fopen("/tmp/ttt.sql", "w"); cnt = 0; prep_interval_request_ii(&ctx); { int cur_start = 0; int ix; for (ix = cur_start + 1; ix < sz; ix++) { if (0 == probe_interval_request_ii(&ctx, ids[cur_start])) break; for (; cur_start < sz && ids[cur_start] < ctx.cur_val_; cur_start++); // if (ctx.cur_val_ != ids[cur_start]) // { // cur_start++; // continue; // } ix = cur_start + 1; if (ix >= sz) break; for (; ix < sz && ids[ix] == ids[ix - 1] + 1; ix++); //elog(INFO, "%d %d %d", ix, cur_start, sz); cnt += run_interval_request_ii(&ctx, ids[cur_start], ids[ix - 1]); cur_start = ix; } } if (ctx.fl_) fclose(ctx.fl_); fin_interval_request(NULL); pfree(ids); PG_RETURN_INT64(cnt); }


私はここに投稿しましたが、githubには投稿していません コードは純粋に実験的なものであり、実用的な価値はありません。



PPS：この仕事をするよう私を励ましてくれたPostgresProの皆さんに感謝します。



PPPS： こことここで続きます


More articles:


All Articles