投影？ 結構です

カットの下には、空間インデックスの使用に関する小さなメモがあります

zcurveに基づいて、球体にあるポイントデータにインデックスを付けます。 また、PostgreSQLのベンチマークと同じ（ただし完全に異なる）との比較

Rツリーのインデックス。



トピックの開発中（ 1、2、3、4、5、6 ）。

実際、 最初に戻ります-地理座標にインデックスを付けて、それらを球の表面に配置するというアイデアです。 緯度と経度のペアの通常のインデックス付けでは、赤道から遠く離れた歪みが生じますが、投影の操作は普遍的ではありません。 したがって、地理座標を3次元空間に変換するという考え方は非常にエレガントに見えます。



考え方自体は新しいものではなく、同様に機能します。たとえば、PostgreSQL拡張機能-PGSphereは 、インデックス作成に3次元Rツリーを使用します。 彼と比較します。

データ準備。

PGSphere

• 最初に、拡張機能をダウンロード、ビルド、インストールする必要があります（作成者は現在のバージョン1.1.5を使用しました）
  
  
  
  

  gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config sudo gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config install
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• 次にダウンロード（psql）
  
  
  
  

   CREATE EXTENSION pg_sphere;
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• テストデータ用のテーブルを作成する
  
  
  
  

   CREATE TABLE spoint_data (sp spoint);
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• ランダムデータのソースが必要です。
  
  プログラムの最初のパラメーターは半径で、2番目は結果の数です。
  
  唯一の微妙な点は、データが特定の半径のボール内に均等に分散されることです。そうでない場合、球に均等に分散されません。
• ランダムなデータをawkスクリプトに渡して、地理座標に変換します
  
  
  
  

   # --- gendata.awk ------ BEGIN{ pi=3.1415926535897932; degra=pi/180.0; rad=180.0/pi; Grad = 1000000.; } { x = $1; y = $2; z = $3; r3 = sqrt(x*x + y*y + z*z); x *= Grad / r3; y *= Grad / r3; z *= Grad / r3; r2 = sqrt(x*x + y*y); lat = atan2(z, r2) * rad; lon = 180. + atan2(y, x) * rad; printf ("(%14.10fd, %14.10fd)\n", lon, lat); }
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• 実際にデータを作成する場合、ここでは半径は重要ではありません。pgsphereとzcurveが同じデータを取得することが重要です。 索引付けを高速化するには、ソートが非常に望ましいです。
  
  
  
  

   ./random 1000000 100000000 | gawk -f gendata.awk | sort > pgsphere.txt
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• テーブルにデータを注ぎます
  
  
  
  

   COPY spoint_data (sp) FROM '/home/.../pgsphere.txt';
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• 索引付け
  
  
  
  

   CREATE INDEX sp_idx ON spoint_data USING gist (sp);
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

Zorder

• まず、 拡張機能を収縮、組み立て、インストールする必要があります
  
  
  
  

   gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config sudo gmake USE_PGXS=1 PG_CONFIG=/usr/bin/pg_config install
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• テストデータ用のテーブルを作成する
  
  
  
  

   create table test_points_3d (x integer,y integer, z integer);
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• ランダムデータの同じソースが必要になります 。
• ランダムなデータをawkスクリプトに渡して、2,000,000辺のキューブ内に配置します
  
  
  
  

   #--- gendata2.awk ------ BEGIN{ pi=3.1415926535897932; degra=pi/180.0; rad=180.0/pi; Grad = 1000000.; } { x = $1; y = $2; z = $3; r3 = sqrt(x*x + y*y + z*z); x *= Grad / r3; y *= Grad / r3; z *= Grad / r3; ix = int(x+0.5+Grad); iy = int(y+0.5+Grad); iz = int(z+0.5+Grad); print ix"\t"iy"\t"iz; }
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• 実際にデータを作成するには、ここで半径が重要です。 ソートはオプションです。
  
  
  
  

   ./random 1000000 100000000 | gawk -f gendata2.awk > zcurve.txt
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• テーブルにデータを注ぎます
  
  
  
  

   COPY test_points_3d FROM '/home/.../zcurve.txt';
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

• 索引付け
  
  
  
  

   create index zcurve_test_points_3d on test_points_3d(zcurve_num_from_xyz(x,y,z));
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

試験準備

PGSphere

テストには、このawkスクリプトが必要です

 #--- gentest.awk ------- BEGIN{ pi=3.1415926535897932; degra=pi/180.0; rad=180.0/pi; Grad = 1000000.; } { x = $1; y = $2; z = $3; r3 = sqrt(x*x + y*y + z*z); x *= Grad / r3; y *= Grad / r3; z *= Grad / r3; r2 = sqrt(x*x + y*y); lat = atan2(z, r2) * rad; lon = 180. + atan2(y, x) * rad; # EXPLAIN (ANALYZE,BUFFERS) printf ("select count(1) from spoint_data where sp @'<(%14.10fd,%14.10fd),.316d>'::scircle;\n", lon, lat); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このスクリプトは、データを準備したスクリプトと完全に対称です。 数値.316に注意する価値があります。これは、データを探している計算されたランダムなポイントを中心とする球体の半径です



一連のクエリの準備は次のように行われます。

 ./random 1000000 100 1023 | gawk -f gentest.awk >tests1.sql
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、100はテストシリーズのサイズ、1023はランダマイザーのシードです。

ズカーブ

テストには、awkスクリプトも必要です。

 #--- gentest2.awk ------- BEGIN{ pi=3.1415926535897932; degra=pi/180.0; rad=180.0/pi; Grad = 1000000.; } { x = $1; y = $2; z = $3; r3 = sqrt(x*x + y*y + z*z); x *= Grad / r3; y *= Grad / r3; z *= Grad / r3; ix = int(x+0.5+Grad); iy = int(y+0.5+Grad); iz = int(z+0.5+Grad); # EXPLAIN (ANALYZE,BUFFERS) lrad = int(0.5 + Grad * sin(.316 * degra)); print "select count(1) from zcurve_3d_lookup_tidonly('zcurve_test_points_3d', "ix-lrad","iy-lrad","iz-lrad","ix+lrad","iy+lrad","iz+lrad");"; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このスクリプトは、データを準備したスクリプトと完全に対称です。 繰り返しますが、数値.316に注意してください。これは、データを探している計算されたランダムなポイントを中心とする立方体の半分の辺です。



一連のクエリの準備は次のように行われます。

 ./random 1000000 100 1023 | gawk -f gentest2.awk >tests2.sql
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、100はテストシリーズのサイズ、1023はランダマイザーのシードです。pgsphereのサイズと一致する方が良いでしょう。

ベンチマーク

前と同様に、2つのコアと4 GBのRAMを備えた控えめな仮想マシンで測定が実行されたため、時間に絶対値はありませんが、読み取られたページ数は信頼できます。



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

半径	AVG NPoints	Nreq	種類	時間（ミリ秒）	読みます	ヒット数
.01°	1.17 0.7631 （0.7615）	10,000	zcurve rtree	.37 .46	1.4397 2.1165	9.5647 3.087
.0316°	11.6 7.6392 （7.6045）	10,000	zcurve rtree	.39 .67	2.0466 3.0944	20.9707 2.7769
.1°	115.22 76.193 （76.15）	1,000	zcurve rtree	.44 2.75 *	4.4184 6.073	82.8572 2.469
.316°	1145.3 758.37 （760.45）	1,000	zcurve rtree	.59 18.3 *	15.2719 21.706	401.791 1.62
1.°	11310 7602 （7615）	100	zcurve rtree	7.2 94.5 *	74.9544 132.15	1651.45 1.12

どこで

半径 -検索エリアのサイズ（度）

Npoints- 括弧内の出力の平均ポイント数-理論的に予想される数

（41252.96平方度、1億ポイント、1平方度あたり〜2424ポイントの範囲内）

Nreq-シリーズ内のクエリの数

タイプ -

「zcurve」-それは

「rtree」-PGSphere

時間（ミリ秒） -平均クエリ実行時間

読み取り -要求ごとの読み取りの平均数

ヒット -バッファアクセスの数



*ある時点で、Rツリーのパフォーマンスが突然開始される

サグ、これは、このツリーがより顕著に読むという事実による

ページとそのワーキングセットがキャッシュに収まらなくなります（明らかに）。



zcurveはより多くのデータを見つけることに注意してください。 PGSphereのような球ではなく、キューブ内を検索します。 したがって、 HAVERSINEスタイルのポストフィルタリングが必要です 。 ただし、ここではインデックスのパフォーマンスのみを比較しています。



違いを評価してみましょう。 一般に、立方体の内部にある球の一部の面積を見つけるタスクは簡単ではありません。 評価を試みてみましょう。

• 私たちの立方体が、平均して、球から同じ体積の球と同じ領域を切り取ると仮定します
• 単一球の体積1.33 * 3.14 = 4.19
• 辺2 = 8の立方体の体積。
• 次に、8 / 4.19 = 1.24からの3次の根は、仮想球体の半径と実際の球体の比率です。
• 虚球の面積と実際の面積の比1.24 * 1.24 = 1.54
• 実験データから1.17 / 0.7631 = 1.5332
  
  ビンゴ！