SQL查询位置半径内的总点数

Question

我有一个美国所有邮政编码的数据库表,其中包括每个邮政编码的城市,州,纬度和经度.我还有一个点数据库表,每个点都有与之关联的纬度和经度.我希望能够使用1个MySQL查询为我提供zipcodes表中所有唯一城市/州组合的列表,以及该城市/州的给定半径内的总点数.我可以使用以下查询获取唯一的城市/州名单:

select city,state,latitude,longitude
from zipcodes 
group by city,state order by state,city;

我可以使用以下查询获得纬度为"$ lat"和经度为"$ lon"的特定城市100英里范围内的点数:

select count(*) 
from points 
where (3959 * acos(cos(radians($lat)) * cos(radians(latitude)) * cos(radians(longitude) - radians($lon)) + sin(radians($lat)) * sin(radians(latitude)))) < 100;

我无法做的是弄清楚如何以不杀死我的数据库的方式组合这些查询.这是我悲伤的尝试之一:

select city,state,latitude,longitude,
    (select count(*) from points
     where status="A" AND 
          (3959 * acos(cos(radians(zipcodes.latitude)) * cos(radians(latitude)) * cos(radians(longitude) - radians(zipcodes.longitude)) + sin(radians(zipcodes.latitude)) * sin(radians(latitude)))) < 100) as 'points' 
from zipcodes 
group by city,state order by state,city;

表格目前有以下索引:

Zipcodes - `zip` (zip)
Zipcodes - `location` (state,city)
Points - `status_length_location` (status,length,longitude,latitude)

当我在前一个MySQL查询之前运行explain时,这里是输出:

+----+--------------------+----------+------+------------------------+------------------------+---------+-------+-------+---------------------------------+
| id | select_type        | table    | type | possible_keys          | key                    | key_len | ref   | rows  | Extra                           |
+----+--------------------+----------+------+------------------------+------------------------+---------+-------+-------+---------------------------------+
|  1 | PRIMARY            | zipcodes | ALL  | NULL                   | NULL                   | NULL    | NULL  | 43187 | Using temporary; Using filesort | 
|  2 | DEPENDENT SUBQUERY | points   | ref  | status_length_location | status_length_location | 2       | const | 16473 | Using where; Using index        | 
+----+--------------------+----------+------+------------------------+------------------------+---------+-------+-------+---------------------------------+

我知道我可以循环遍历所有的zipcode并计算给定半径内的匹配点的数量但是点表将一直在增长,而我宁愿在zipcodes数据库中没有过时的总点数.我希望那里的MySQL大师可以向我展示我的方式的错误.在此先感谢您的帮助!

Answer 1

MySQL大师与否,问题是除非你找到一种过滤各行的方法,否则需要在每个点和每个城市之间计算距离......

有两种可能有助于这种情况的一般方法

• 使距离公式更简单
• 将不太可能的候选人过滤到给定城市的100k半径

在进入这两条改进途径之前,你应该决定这100英里距离所需的精度水平,你也应该指出数据库涵盖哪个地理区域(这只是美国大陆等等).

这样做的原因是,虽然数字更精确,但大圆公式在计算上非常昂贵.性能改进的另一个途径是将"网格坐标"存储在附加(或代替)Lat/Long坐标中.

编辑:
关于一个更简单(但不太精确)的公式的一些想法:
由于我们处理的距离相对较小,(我猜测在Lat和30之间有48到48度),我们可以使用欧氏距离(或更好)欧氏距离的平方而不是更复杂的球形三角公式.
根据预期的精度水平,对于完全经度的线性距离,可以接受一个单一参数,在所考虑的区域内取平均值(例如大约46 法定英里).那么公式就会变成

  LatDegInMi = 69.0
  LongDegInMi = 46.0
  DistSquared = ((Lat1 - Lat2) * LatDegInMi) ^2 + ((Long1 - Long2) * LongDegInMi) ^2

关于具有网格信息的列的想法,以过滤以限制考虑用于距离计算的行数.
系统中的每个"点",无论是城市,还是其他点(？交付地点,商店位置......等等)都会被分配两个整数坐标,这些坐标定义了点所在的25英里*25英里的平方.距参考点(给定城市)100英里内的任何点的坐标在x方向上最多+/- 4,在y方向上最多+/- 4.然后我们可以编写类似于以下内容的查询

SELECT city, state, latitude, longitude, COUNT(*)
FROM zipcodes Z
JOIN points P 
  ON P.GridX IN (
    SELECT GridX - 4, GridX - 3, GridX - 2, GridX - 1, GridX, GridX +1, GridX + 2 GridX + 3, GridX +4
   FROM zipcode ZX WHERE Z.id = ZX.id)
  AND
   P.GridY IN (
    SELECT GridY - 4, GridY - 3, GridY - 2, GridY - 1, GridY, GridY +1, GridY + 2 GridY + 3, GridY +4
   FROM zipcode ZY WHERE Z.id = ZY.id)
WHERE P.Status = A
   AND ((Z.latitude - P.latitude) * LatDegInMi) ^2 
      + ((Z.longitude - P.longitude) * LongDegInMi) ^2 < (100^2)
GROUP BY city,state,latitude,longitude;

请注意,LongDegInMi可以是硬编码的(对于美国大陆的所有位置都相同),或者来自zipcodes表中的相应记录.类似地,LatDegInMi可以是硬编码的(几乎不需要使它变化,因为它不同于它相对恒定).

这个更快的原因是对于zipcodes表和points表之间的笛卡尔积中的大多数记录,我们根本不计算距离.我们根据索引值(GridX和GridY)消除它们.

这让我们想到了要生成哪些SQL索引的问题.当然,我们可能需要: - GridX + GridY + Status(在点表上) - GridY + GridX +状态(可能) - City + State +纬度+经度+ GridX + GridY在zipcodes表上

网格的替代方案是根据给定城市的纬度和经度"约束"我们将考虑的纬度和经度的界限.即JOIN条件变为范围而不是IN:

JOIN points P 
  ON    P.latitude > (Z.Latitude - (100 / LatDegInMi)) 
    AND P.latitude < (Z.Latitude + (100 / LatDegInMi)) 
    AND P.longitude > (Z.longitude - (100 / LongDegInMi)) 
    AND P.longitude < (Z.longitude + (100 / LongDegInMi))