問題タブ [spatial-index]

私はMySqlでGrails 1.3.2に取り組んでいます。特定の場所の緯度と経度をデータベースに保存する必要があり、ユーザーの現在の場所に基づいて、その場所の特定の半径内にあるアイテムを返す必要があります。したがって、基本的に次の要件があります。

1. ユーザーの現在の座標の指定された半径内にある場所を検索します
2. 全文検索を提供します。現在、これには検索可能を使用しています
3. ユーザーの現在の座標の指定された半径内で全文検索を組み合わせて実行します。

ここにあるさまざまなオプションを検討しており、これを実装するためのあなたの意見/提案を知りたいと思っていました. ここにあるさまざまなオプションは次のとおりです。

1. Lucene Spatial Search ( http://wiki.apache.org/lucene-java/SpatialSearch ) を検索して、検索可能で使用する方法を調べます

2. Grails Solr プラグイン ( http://www.grails.org/plugin/solr )。ただし、これはドメイン オブジェクトを返しません。

3. Grails スティッチ プラグイン ( http://www.grails.org/plugin/stitches )。著者のサイト ( http://www.philliprhodes.com/content/stitches-30-seconds ) を除いて、多くのドキュメントはありません。

4. ドメイン クラスのすべてのフィールドの全文インデックスに加えて、MySql 空間拡張。このルートに進むと、 searchable をまったく使用しなくなります。

5. Postgres/PostGIS と hibernate-spatial の統合 ( http://blog.mollusca.ch/2008/10/4/grails-spatial-data-postgis )

これは、マップと統合するすべてのアプリケーションにおける非常に基本的な要件であると考えています。

したがって、この機能を実装するための最も適切な方法を知りたいと思っています。

ありがとう

私が持っているのは（私が思うに）単純なSQLServer空間クエリです：

いくつかの4辺のポリゴン（つまり、Webページのグーグル/ビングマップのビューポート/バウンディングボックス）内に存在するすべての米国の州を取得します。

実行には6秒かかります:(

これが実行計画です。

削除

そして、フィルター操作の統計...

削除

さて、これをデバッグする方法がわかりません..微調整する必要があるものを理解するためなど。空間インデックスはありますか？そう信じる ...

GEOGRAPHY返されるデータについてさらに情報を提供する必要がありますか？例えば。ポイント数など？または、実行profilerしてそこからいくつかの統計を提供する必要がありますか？

または、Cells_per_object / Gridsが正しく設定されていません（これらの値をTBHに設定する必要があるかどうかは本当にわかりません）。

誰か助けてもらえますか？お願いします？

更新/編集：

以下の@Bobsからの最初の応答の後、主キー（クラスター化インデックス）が50の奇数行を持つテーブルの非クラスター化インデックスよりも高速であるため、空間インデックスが使用されていないことを確認しました...次に、強制的に空間インデックス（shits-n-giggles用）：-

...そして..クエリが即座に実行されるものを推測します。

WTF？他の誰かが理由を知っていますか？また、理由/内容を説明するために、そのクエリプランを投稿する必要がありますか？

次のような記事を読みました。

(x-min,y-min) および (x-max,y-max) 座標は、境界ボックスの配置と寸法を決定します。境界ボックスの外側のスペースは、0 の番号が付けられた単一のセルとして扱われます。

これは、インデックスの「外側」にあるものはすべて、実際には特別な場所にインデックスが作成されていることを意味すると解釈しました。

が完全にバウンディング ボックスの外側にある場合@MyShape、バウンディング ボックスの外側にあるものだけをチェックする必要があります (したがって、引き続きインデックスを使用します)。

しかしその後、記事には次のように書かれています。

バウンディング ボックスの内側に完全にあるオブジェクトに対して計算された操作だけが、空間インデックスの恩恵を受けます。

反対のことを言っているようです-@MyShapeバウンディングボックスの外側にある場合、完全なテーブルスキャンが実行されます。

それはどれですか？

いくつかの空間検索機能をPostGISを使用したPostgresからSQLServerに移行する作業を行っていますが、インデックスを使用した場合でも、かなりひどいパフォーマンスが見られます。

私のデータは約100万ポイントであり、それらのポイントのどれが特定の形状内にあるかを知りたいので、クエリは次のようになります。

かなり小さい形状を選択すると、1秒未満の時間が得られる場合がありますが、形状がかなり大きい場合（場合によってはそうです）、5分を超える時間が得られます。Postgresで同じ検索を実行すると、常に1秒未満になります（実際、ほとんどすべてが200ミリ秒未満です）。

インデックスでいくつかの異なるグリッドサイズ（すべて高、すべて中、すべて低）、オブジェクトごとに異なるセル（16、64、256）を試しましたが、何をしても時間はかなり一定に保たれます。もっと組み合わせてみたいのですが、どういう方向に行けばいいのかわからないです。オブジェクトごとにより多くのセル？以下？グリッドサイズの奇妙な組み合わせ？

私は自分のクエリプランを調べましたが、それらは常にインデックスを使用していますが、まったく役に立たないだけです。インデックスなしで試してみましたが、それほど悪くはありません。

これについて誰かがアドバイスできることはありますか？私が見つけたものはすべて、「インデックスに関するアドバイスを提供することはできません。すべてを試してみればうまくいくかもしれません」と示唆していますが、インデックスの作成には10分かかるため、これを盲目的に行うのは時間の無駄です。

編集：私はこれをMicrosoftフォーラムにも投稿しました。ここに彼らがそこで求めたいくつかの情報があります：

私が得ることができた最高の実用的なインデックスはこれでした：

インデックスを使用する際に問題が発生しましたが、これは異なります。

これらのテストでは、インデックスごとにWITH（INDEX（...））句を使用してテスト検索（元の投稿にリストされているもの）を実行しました（グリッドサイズとオブジェクトごとのセルのさまざまな設定をテストします）。ヒント。また、各インデックスと同じ検索形状を使用してsp_help_spatial_geometry_indexを実行しました。上記のインデックスは最も速く実行され、sp_help_spatial_geometry_indexで最も効率的であるとリストされました。

検索を実行すると、次の統計が得られます。

また、ランダムポイントをデータとして使用してみましたが（実際のデータを提供できないため）、この検索はランダムデータを使用すると非常に高速であることがわかりました。これにより、私たちの問題はグリッドシステムがデータをどのように処理するかであると私たちは信じるようになりました。

私たちのデータは州全体のアドレスであるため、非常に高密度の領域がいくつかありますが、ほとんどの場合、データはまばらです。問題は、グリッドサイズの設定が両方でうまく機能しないことだと思います。グリッドをに設定するHIGHと、インデックスは低密度領域で返されるセルが多すぎます。グリッドをに設定するLOWと、グリッドは高密度領域では役に立ちません（でMEDIUM、それほど悪くはありませんが、どちらも得意ではありません）。

インデックスを使用することができますが、役に立たないだけです。すべてのテストは「実際の実行プランの表示」をオンにして実行され、常にインデックスが表示されます。

私はPostgreSQLが初めてです。

PostgreSQL のデフォルト インストール (PostGIS のような拡張機能なし) で、テーブルに地理フィールドが定義されている場合、PostgreSQL はどのような種類のインデックスをサポートしていますか?

マニュアルに空間インデックスに関する情報が見つかりませんでした。

MYSQL の POINT データ型を使用して格納されている緯度と経度の座標を使用してテーブルをクエリする必要があるアプリケーションがあります。

特定の GPS 位置の特定の半径内で近くの緯度と経度を検索するストアド関数があります。ただし、私のテーブルには数十万のエントリが含まれるため、パフォーマンスを最適化する必要があります。

次のストアド関数を作成しましたが、800,000 行以上の可能性がある中、約 9,000 行を返すのに約 4.01 秒かかります。近くの GPS 座標を見つけるより良い方法はありますか?

これが私の保存された関数です：

関数に対する私のインスピレーションの多くは、http ://www.movable-type.co.uk/scripts/latlong-db.html から得ました。

タイプgeographyの列があります。空間インデックスを作成しましたが、使用されていません。

インデックスは次のように作成されます。

さまざまなレベルでのグリッド密度の値は、意図的に中程度に設定されていないためのものです。設定内容に違いはありません。推定実行プランを表示すると、インデックスは使用されません。

[http://blogs.msdn.com/b/isaac/archive/2008/08/29/is-my-spatial-index-being-used.aspx] [1]

クエリオプティマイザにヒントを追加しようとすると

このエラーが発生します：

クエリプロセッサは、空間インデックスヒントを含むクエリのクエリプランを作成できませんでした。理由：空間インデックスは、述部で提供されたコンパレータをサポートしていません

私のデータベースはSQLServer2008（100）互換性レベルで実行されています。

。

クエリでこのSQL空間インデックスヒントをどこで/どのように指定するかわかりません：-

クエリを実行すると、空間ヒントが使用されていません。はい、最新バージョンのSQL Server 2008 r2（v 10.5.1600.1）を使用しています。

そこで、ヒントを強制してクエリ速度を比較するために、私は試してみました...

それはうまくいきましたが、パフォーマンスは本当に悪かったです。ヒントを使用して結合を実行しようとしていたのではないかと思っていましたa.Id = b.Id（ヒントを使用したくないためです）。

助言がありますか？

アップデート：

クエリプランを追加しました。コストの大部分は、2つのテーブル間の結合です。Filter（where句）は2番目にコストのかかる部分を占めます。

Perl で RTree を操作するための良いヒントはありますか? パフォーマンスの高い純粋な RTree 実装か、GIS プロジェクトからハイジャックできるものか? それとも、SQLite の空間インデックス サポートのようなものを使用する方が簡単でしょうか?

乾杯

粒子相互作用のシミュレーションに取り組んでいるときに、効率的な最近傍セル検索を提供すると見なされているMorton オーダー (Z オーダー) ( Wikipedia リンク)のグリッド インデックス付けに出くわしました。私が読んだ主な理由は、メモリ内の空間的に近いセルのほぼ連続した順序付けです。

最初の実装の途中であるため、特に基本的な均一グリッドと比較して、最近傍のアルゴリズムを効率的に実装する方法について頭を悩ませることはできません。

1. セル (x,y) が与えられた場合、8 つの隣接セル インデックスを取得し、それぞれの z インデックスを計算するのは簡単です。これにより、要素への一定のアクセス時間が提供されますが、z-index を計算するか、事前定義されたテーブルで検索する必要があります (軸ごとに分離し、OR を計算します)。どうすればこれがより効率的になるでしょうか? 配列 A の要素に A[0] -> A 1 -> A[3] -> A[4] -> ... という順序でアクセスすると、A[1023 の順序よりも効率的です。 ] -> A[12] -> A[456] -> A[56] -> ...?

2. Z オーダーで最近傍を見つけるためのより単純なアルゴリズムが存在することを期待していました。線に沿った何か: 隣接セルの最初のセルを見つけて、反復します。しかし、これは 2^4 サイズのブロック内でのみうまく機能するため、そうではありません。ただし、2 つの問題があります。セルが境界上にない場合、ブロックの最初のセルを簡単に特定してブロック内のセルを反復処理できますが、セルが最近傍セルであるかどうかを確認する必要があります。セルが境界上にある場合は、2^5 個のセルを考慮する必要がある場合よりも悪いことになります。ここで何が欠けていますか？私が必要とすることを行う比較的単純で効率的なアルゴリズムはありますか?

ポイント 1. の質問は簡単にテストできますが、記述されたアクセス パターンが生成する基本的な命令についてはあまり詳しくなく、舞台裏で何が起こっているのかを本当に理解したいと思っています。

ヘルプ、参考文献など、事前に感謝します...

---

編集：
ポイント1を明確にしていただきありがとうございます！ということで、Z-orderingを使うと隣接セルのキャッシュヒット率が平均的に上がるというのは興味深いですね。キャッシュのヒット/ミス率をプロファイリングする方法はありますか?

ポイント2に関して：インデックスi = f（x1、x2、...、xd）がビットごとのインターレースなどから取得されるR ^ dの点群のモートン順序配列を構築する方法を理解していることを追加する必要があります.私が理解しようとしているのは、次の単純な ansatz よりも、最近傍を取得するためのより良い方法があるかどうかです (ここでは d=2、「疑似コード」)。