Yelp如何有效地计算数据库中的距离?
-
16-10-2019 - |
题
例如,说我有一张桌子:
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空间也没有计算距离函数。
解决方案
如果我正确理解这个问题(而且我不确定我这样做),那么您担心计算 "(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 然后,您应该考虑使用它们。
其他提示
(披露:我是Microsoft SQL Server的家伙,所以我的答案受到了影响。)
为了真正有效地做到这一点,您需要两件事:缓存和本机空间数据支持。 空间数据支持 可让您直接将地理和几何数据存储在数据库中,而无需进行密集/昂贵的计算,并让您构建索引以非常快速地找到离当前位置的最接近点(或最有效的路线或其他任何位置)。
如果您想扩展时期,缓存很重要。最快的查询是您从未做过的查询。每当用户要求最接近他的东西时,您就可以存储他的位置,结果将结果设置在诸如Redis或Memcache的缓存中。业务地点不会在4个小时内变化 - 好吧,如果有人编辑业务,他们可能会在所有结果集中立即对其进行更新。
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