問題タブ [spatial-index]

私は楽しみのためだけに群がるボイドのシミュレーションに取り組んでおり、それを少し最適化したいと考えています。作業が必要な領域は、特定のボイドの近くでボイドを見つけることです。タスクに適したある種の空間データ構造を実現することが最善の策であると考えています (こちらを参照して、少し下にスクロールしてください)。

何をするにしても、Java でゼロから自分自身を実装します。そうすれば、選択したデータ構造について、多数のライブラリ関数を呼び出しただけの場合よりも多くのことを学ぶことができます。

R-Trees、kd trees、およびQuadtreesを認識しています。私の意見では、それらはすべて実行可能なオプションです。しかし、私はこれらのデータ構造の経験がなく、何が私の目的に最も適しているか完全にはわかりません. この規模では何も必要ありません.100万ではなく、おそらく数百のボイド、おそらく最大で1000のボイドを話していますが、最終的にはAndroidフォンで実行する可能性があることを覚えておいてください.

このためのデータ構造（もちろん、上記に限定されません）をお勧めし、代替案よりもそれを選択する正当な理由を教えてください。

はい、この質問を見ました。いいえ、私はその答えに満足していません。理由がまったく示されていません。

ああ、もう1つ-タイトルが言うように、これは厳密に2次元のみです。

バックグラウンド

顧客の地域を表す POLYGONS/MULTIPOLYGONS を含むテーブルがあります。

• テーブルには約 8,000 行が含まれています
• ポリゴンの約 90% が円
• ポリゴンの残りの部分は、1 つ以上の州、県、またはその他の地理的地域を表します。これらのシェイプの生のポリゴン データは、米国の国勢調査データからインポートされました。
• テーブルには、主キーに空間インデックスとクラスター化インデックスがあります。デフォルトの SQL Server 2008 R2 設定は変更されていません。オブジェクトごとに 16 セル、すべてのレベルが中。

私が経験している問題を再現する簡単なクエリを次に示します。

単純で単純なクエリのように見えても、実行に 12 ～ 13 秒かかり、そのような単純なクエリに対して非常に複雑な実行計画のように見えます。

私の調査では、クエリ オプティマイザーが空間インデックスを適切に使用するように、クエリにインデックス ヒントを追加することをいくつかの情報源が提案しています。追加WITH(INDEX(idx_terr_territory))しても効果はなく、実行計画から、ヒントに関係なくインデックスを参照していることは明らかです。

ポリゴンの削減

米国国勢調査データからインポートされた地域ポリゴンが不必要に複雑である可能性があるように思われたため、2 番目の列を作成し、さまざまな許容度で縮小ポリゴン ( Reduce() メソッドを使用) をテストしました。新しい列に対して上記と同じクエリを実行すると、次の結果が得られました。

• 削減なし: 12649ms
• 10 減: 7194ms
• 20 減: 6077ms
• 30 減: 4793ms
• 40 減: 4397ms
• 50 減: 4290ms

明らかに正しい方向に向かっていますが、精度を落とすことは洗練されていない解決策のように思えます。これは、インデックスが想定されているものではありませんか? そして、そのような基本的なクエリの実行計画は、依然として奇妙に複雑に見えます。

空間インデックス

好奇心から、空間インデックスを削除したところ、結果に驚かされました。

1. クエリは、インデックスなしで高速になりました (削減なしで 3 秒未満、削減許容値 >= 30 で 1 秒未満)
2. 実行計画ははるかに単純に見えました。

私の質問

1. 空間インデックスによって速度が低下するのはなぜですか?
2. クエリを高速化するために、ポリゴンの複雑さを軽減することは本当に必要ですか? 精度を落とすと、将来的に問題が発生する可能性があり、うまくスケーリングできないようです。

その他の注意事項

• SQL Server 2008 R2 Service Pack 1 が適用されました
• さらなる調査により、ストアド プロシージャ内でクエリを実行することが提案されました。これを試してみましたが、何も変わらないように見えました。

CREATE TABLE building (buildid VARCHAR(15) PRIMARY KEY, buildname VARCHAR(50),numpoint NUMBER,points SDO_GEOMETRY);

CREATE INDEX building_spatial_idx ON building(points) INDEXTYPE IS MDSYS.SPATIAL_INDEX;

INSERT INTO USER_SDO_GEOM_METADATA(TABLE_NAME,COLUMN_NAME,DIMINFO,SRID) VALUES ( '建物', 'ポイント', SDO_DIM_ARRAY( --820*580 グリッド SDO_DIM_ELEMENT('X', 0, 820, 1), SDO_DIM_ELEMENT('Y', 0) 、580、1) )、NULL --SRID );

初めて実行したときはエラーは発生しませんでしたが、あとがきはエラーが発生しています

それとも他に理由があるのでしょうか。すべてのインデックス、メタデータ、テーブルを一度に削除して、このエラーを取り除くにはどうすればよいですか。

WiX インストーラーを更新して、SQL Server 2008 R2 をインストールしようとしています。通常の 2008 はほとんどのマシンに正常にインストールされるように見えましたが、 R2 のインストールでは SQLSysClrTypes のインストールに失敗したようです。そのため、SQLServerSpatial.dll と呼ばれる dll が見つからないというエラーが発生しました。

これを正しくインストールするために SQL インストーラーを取得する方法はありますか? この問題についてオンラインでいくつかの議論を見つけましたが、SQL Server の後に SQLSysClrTypes.msi を手動でインストールする以外に解決策はありません。

インストールをサイレントにし、ユーザーの操作を最小限に抑えたいと考えています。

WiX 3.5 と VS2010 を使用しています。

編集

さらに読んで考えてみると、SQL 2008 SP1 では SQLServerSpatial.dll もインストールされていないことがわかりました。コードを変更した結果、これが必要になったのです。だから私の質問はより簡単になりました：

SqlServerSpatial を含めてインストールするように SqlServer インストールを構成できますか?

また

WiX を使用して SQLSysClrTypes.msi をインストールできますか (package.xml と product.xml が必要です)? 誰かがこれをしましたか？

各行に Point (経度と緯度) が含まれる ~40k 行のサンプル セットを含むテーブルがあります。MySQL の空間拡張機能を使用して、境界内に存在するポイントを見つけています。

結果がほとんどないことがわかっている境界内で検索すると、インデックスがそのまま使用されます。ただし、私のテスト データセットは、主に英国周辺の場所で構成されています (より大きなライブ データセットは、パーセンテージで類似している可能性があります)。この境界ボックス内で検索すると、インデックスは使用されず、代わりに完全なテーブル スキャンが実行されます。

そのため、MySQL が検出すると予想される行数が合計行数に近い場合、インデックスを無視することを決定しているように見えます。

その場合、強制的にインデックスを使用するか、テーブル全体のスキャンを確実に回避できますか?

以下を使用する

134行（56秒）では実行速度が非常に遅くなりますが、インデックスヒントがコメント化されていない場合は、次のようになります。

メッセージ8635、レベル16、状態4、行3
クエリプロセッサは、空間インデックスヒントを含むクエリのクエリプランを作成できませんでした。理由：空間索引は、述部で提供されたコンパレーターをサポートしていません。インデックスヒントを削除するか、SETFORCEPLANを削除してみてください。

実行プランでは、フィルターコストが98％であることが示されています。これは、他のテーブルの1400行に対してクエリを実行しているため、合計コストは134 * 1400の個別シークであり、これが遅延の原因です。各テーブルの空間インデックスは、それ自体で、断片化がなく、99％のページフルネスで優れたパフォーマンスを発揮し、オブジェクトごとに16個のセルを持つ4つのグリッドレベルすべてにメディアを使用します。いずれかのテーブルの空間インデックスプロパティを変更しても、パフォーマンスには影響しませんでした。

ドキュメントによると、空間インデックスのヒントはSQL Server 2012のクエリでのみ使用できますが、これには確実に回避策がありますか？

MongoDB を使用して空間レコードを保存しています。一部のレコードはポリゴンであり、その他はポイントです。データは継続的に挿入されています。

ポリゴンにポイントが含まれるすべてのレコードにアクセスできる必要があります。Mongo の空間クエリでは、ポリゴン内のすべてのポイントを見つけることができますが、ポイントを含むすべてのポリゴンを見つけることはできません。MongoDB の別のデータベース システムでこれを行う良い方法はありますか?

重要な要素と組み合わせた3Dポイントが多数あります。

各ユーザーには6つのポイントがあります。例：Person Charlieには6つのポイントがあります：（22,44,55）は重要度係数3の最初のポイントです（10,0,0）は重要度係数2.8の2番目のベクトルです6番目のポイントは（100,300,200）で、重要度は0.4です。

私がやりたいのは、他のすべての人を繰り返すことなく、チャーリーに最も似ている人を見つけることです。基本的に、すべてのユーザーに対してこの機能を最小限に抑えます（つまり、そのユーザーからチャーリーに適切な6つのポイントを一致させます）。

次に、コストが最も低いユーザーを選択して、全体的にチャーリーに最も類似しているユーザーを見つけます。私は今のところ（たくさんのループを行うことによって）ばかげた方法でコードを書いていますが、複数のポイントと重要な要素があるという事実を適切に処理する方法を探しています。

空間インデックスを調べ始めましたが、複数のポイントがあるため、機能しないと思いますが、ポイントをより高次元のポイントに展開できるのではないでしょうか。では、3次元で6ポイントの代わりに、18次元で1ポイントを持つことができますか？それでも重要度を処理することはできませんが、何もないよりはましです。

残念ながら、（1,1,1）と（400,400,400）は非常に反対であるため、ここではベクトルと余弦定理を使用できません。

何か案は？

2D空間にさまざまなサイズの長方形のセットがあります。長方形の数は10から100000に動的に変更でき、それらの位置とサイズは頻繁に更新されます。

与えられた点（x、y）で長方形を見つけるためにどの空間構造をお勧めしますか？検索操作も非常に頻繁に実行されたと仮定します（たとえば、マウスの移動）。さまざまな空間インデックスアルゴリズムの比較への参照を提供したり、ここでそれらの検索/ビルド/更新のパフォーマンスを比較したりできれば、それは素晴らしいことです。

重心を内部に収まるポリゴンと一致させようとする大規模なクエリがあります。ブロックとポリゴンのZ値で制約しますが、それでも多くのポイントインポリ計算を実行し、実行に長い時間がかかります。

いくつかの背景について：

• 図心を含むテーブルには250万行あります
• 表のすべての空間データは世界の非常に小さな領域にあり、全体の境界ボックスはわずか7643x2351メートルです。
• それらの行のうち、660KフィットはZ基準に一致します
• ポリゴンを含むテーブルには10K行があります
• 表のすべての空間データは、世界のさらに小さな領域にあります
• それらの行のうち、2366は名前の基準に一致します
• インデックスなしでクエリを実行すると11時間かかり、91Kの一致が返されます

クエリは次のようなものです。

したがって、このクエリを高速化するために、に空間インデックスを追加しblocks.WGS84Centroid、に1つ追加しましたpolygons.Shape。
クエリアナライザは、blocks.Idとblocks.WGS84Centroidを含むblocks.ZCentreの非クラスタ化インデックスも提案しました。

その後、クエリプランは次のようになります。

そしてフィルターコスト：

ただし、これら3つのインデックスを追加した後でも、クエリの実行には同じくらいの時間がかかります。
私は今何ができますか？