Yelpはデータベースの距離をどのように効率的に計算しますか？

dba.stackexchange https://dba.stackexchange.com/questions/4210

質問

たとえば、私がテーブルを持っているとします：

Business(BusinessID, Lattitude, Longitude)

もちろん、すべてインデックスが付けられています。また、100万のレコードがあります

たとえば、106,5に最も近いビジネスを見つけたいとしますか？

私が行った場合 

SELECT *
FROM Business
WHERE (Some formula to compute distance here) < 2000

たとえば、または私がそうする場合

SELECT *
FROM Business
TOP 20

理論的には、コンピューターはすべてのbizの距離を計算する必要がありますが、実際には、計算する必要がある特定の範囲内で格子と経度の距離のみを計算する必要があります。

それでは、たとえば、PHPやSQLでやりたいことをどのように行うことができますか？

私はこれまでのところ答えに感謝しています。私はMySQLを使用していますが、明らかなソリューションよりも効率的なものはありません。 MySQL Spatialには、計算距離関数もありません。

役に立ちましたか？

解決

質問を正しく理解している場合（そして私がそうするかどうかはわかりません）、あなたはコンピューティングが心配です "(Some formula to compute distance here)" クエリを行うたびにテーブル内のすべての行について？

これは、でインデックスを使用することにより、ある程度緩和できます latitude と longitude したがって、実際に必要な円を含むポイントの「ボックス」の距離を計算する必要があります。

select * from business
where (latitude>96 and latitude<116) and 
      (longitude>-5 and longitude<15) and 
      (Some formula to compute distance here) < 2000

ここで、96、116などが、値「2000」の単位と距離を計算する世界のポイントに一致するように選択されます。

これがインデックスを正確に使用する方法は、RDBMSとそのプランナーが行う選択に依存します。

一般的に、これは一種の最適化の原始的な方法です 最近隣の検索. 。 RDBMSがサポートしている場合 GISTインデックス, 、 お気に入り ポストグレス その後、代わりにそれらを使用することを検討する必要があります。

他のヒント

（開示：私はMicrosoft SQL Serverの男なので、私の答えはそれに影響されます。）

本当に効率的に行うには、キャッシュとネイティブの空間データサポートの2つのことがあります。 空間データサポート 地理とジオメトリデータをその場で集中的/高価な計算を行わずにデータベースに直接保存し、インデックスを構築して、現在の場所（または最も効率的なルートなど）に最も近いポイントを非常に迅速に見つけることができます。

拡張したい場合、キャッシュは重要です。最速のクエリは、あなたが決して作ることのないクエリです。ユーザーが彼に最も近いものを要求するたびに、あなたは彼の場所を保存し、結果はRedisのようなキャッシュに設定したり、何時間もMemcachedに設定したりします。ビジネスの場所は4時間変更されません。まあ、誰かがビジネスを編集する場合は、必ずしもすべての結果セットですぐに更新する必要はありません。

YelpはGISを使用する可能性があります

PostgreSQLには、GISの参照実装があります ポストギス. Yelpはあらゆる点で劣っているmysqlを使用している可能性があります. 。 Yelpのようなものの場合、彼らはほぼ確実に座標を維持します、

  • ユーザー
  • 潜在的な目的地

これらの座標はほぼ間違いなくWGS84で、地理タイプとして保存されます。 PostgreSqlとPostgisでは、このようなものになります。

CREATE TABLE businesses (
  id   int               GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
  name text,
  geog geography(point)
);
CREATE INDEX ON businesses USING gist(geog);
.... fill table
ANALYZE businesses;

彼らはそのテーブルを埋めます。その後、彼らはあなたの携帯電話からWGS84座標をつかみ、このようなSQL Alchemy（Yelpの場合）でクエリを生成します。

SELECT *
FROM businesses AS b
WHERE ST_DWithin( b.geog, ST_MakePoint(userLong,userLat) );

詳細については、私たちを参照してください , 、そしてチェックしてください 地理情報システム @ stackexchange

ライセンス： CC-BY-SA と 帰属
所属していません dba.stackexchange
scroll top