Yelp如何有效地计算数据库中的距离？

Question

例如，说我有一张桌子：

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空间也没有计算距离函数。

Answer 1

如果我正确理解这个问题（而且我不确定我这样做），那么您担心计算 "(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支持 要点索引, ， 喜欢 Postgres 然后，您应该考虑使用它们。

Answer 2

（披露：我是Microsoft SQL Server的家伙，所以我的答案受到了影响。）

为了真正有效地做到这一点，您需要两件事：缓存和本机空间数据支持。 空间数据支持 可让您直接将地理和几何数据存储在数据库中，而无需进行密集/昂贵的计算，并让您构建索引以非常快速地找到离当前位置的最接近点（或最有效的路线或其他任何位置）。

如果您想扩展时期，缓存很重要。最快的查询是您从未做过的查询。每当用户要求最接近他的东西时，您就可以存储他的位置，结果将结果设置在诸如Redis或Memcache的缓存中。业务地点不会在4个小时内变化 - 好吧，如果有人编辑业务，他们可能会在所有结果集中立即对其进行更新。

Answer 3

Yelp可能使用GIS

PostgreSQL具有GIS的参考实现 Postgis. 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