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

理论上，计算机必须计算所有业务的距离，而实际上只有经度和纬度在一定范围内的业务才需要计算。

那么我怎样才能在 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 支持GiST 索引，比如postgres，那么你应该考虑使用它们。

Answer 2

（披露：我是 Microsoft SQL Server 的人，所以我的答案受此影响。）

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

如果您想扩展，缓存很重要。最快的查询是您从未进行过的查询。每当用户询问离他最近的事物时，您都会将他的位置和结果集存储在 Redis 或 memcached 等缓存中数小时。营业地点在 4 小时内不会更改 - 好吧，如果有人编辑商家，它们可能会更改，但您不一定需要在所有结果集中立即更新。