申し訳ありませんが、これは SQL の回答ではなく、データに対する特定の制約を想定して予測可能なパフォーマンスを得るための方法です。
データはどのくらいの頻度で変更されますか?可能であれば、すべてのエンティティ 5 つの最近傍のグラフを事前に計算し、それを使用して選択を高速化できますか?
このデータがほとんど読み取り専用である場合、...
これらの点はどの程度均等に分布していますか?分布がかなり均等でよくわかっている場合は、ハッシュ テーブル内のすべての座標とインデックスをバケット化して、独自の空間マッピングを作成できますか。
データベースにデータを保持する必要がない場合は、高速なハッシュ ルックアップのために、データをメモリ マップ ファイルに移動します。 (70m のレコードはメモリに簡単に収まるはずです)。
このアーキテクチャを使用して、ディスプレイ広告と検索エンジンの関連性のためにミリ秒未満のルックアップを生成しました。
==詳細==
固定サイズの正方形 (チェス盤のような) のグリッドを作成し、各点をグリッドにマッピングし、各グリッド ボックスに属するオブジェクトのリストを作成します。それぞれのサイズを調整すると、正しくボックスに入れると、平均して、各正方形に 5 ～ 50 個のポイントがあるはずです -- これは原則として四分木ですが、簡単にするために木はありません。
バケット内のすべてのデータを分散させた後に空になったバケットごとに、データを含む最も近いバケットに関する情報を追加します。
各バケットに、座標から計算できる一意の番号が付けられるように、各バケットに左から右の行に番号を付けることができます。また、各バケットをハッシュ テーブルに挿入するか、スペースが許す場合はストレート ルックアップ テーブル。
クエリを取得したら、マップするバケットを計算するだけで、そのバケット内のオブジェクトのリストを取得するか、コンテンツを持つ最も近いバケットへのポインターを含む「空の」バケットを取得します.
これにより、探しているオブジェクトの最初の候補リストが得られます。あとは、実行して最も近いオブジェクトを確認するだけです。
99% のケースではそうです -- しかし、(a) 次のバケツに実際により近いいくつかの候補があることを心配している場合は、周囲の 8 つのバケツをチェックして、できるかどうかを確認してください。
最も近いすべてのオブジェクトのリストも取得したい場合は、オブジェクトごとに 5 つの最近隣の単純なネットワークも計算すると、A->{B,C,D のようなデータ構造になります。 ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....
これにより、Dijkstra のバリエーションでトラバースできる単純なネットワークが形成されます ここで、最も近いポイントに隣接するすべてのポイントを取得します。
データ構造の構築には時間がかかりますが、一度完了すると、適切なルックアップが完了し、データセットを返すことがミリ秒未満で実行できます (http またはオフボックス通信の原因は含まれません)
これがお役に立てば幸いです。