SQL-запрос для общего количества точек в радиусе местоположения

Question

У меня есть таблица базы данных всех почтовых индексов в США, которая включает город, штат, широту и долготу для каждого почтового индекса. У меня также есть таблица точек базы данных, каждая из которых имеет широту и долготу, связанные с ними. Я хотел бы иметь возможность использовать 1 запрос MySQL, чтобы предоставить мне список всех уникальных комбинаций городов / штатов из таблицы почтовых индексов с общим количеством точек в данном радиусе этого города / штата. Я могу получить уникальный список городов / штатов, используя следующий запрос:

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

Я могу получить количество точек в радиусе 100 миль от конкретного города с широтой '$ lat' и долготой '$ lon', используя следующий запрос:

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, вот вывод:

+----+--------------------+----------+------+------------------------+------------------------+---------+-------+-------+---------------------------------+
| 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        | 
+----+--------------------+----------+------+------------------------+------------------------+---------+-------+-------+---------------------------------+

Я знаю, что мог бы перебрать все почтовые индексы и вычислить количество совпадающих точек в пределах данного радиуса, но таблица точек будет расти все время, и я бы предпочел, чтобы в базе данных почтовых индексов не было итогов устаревших точек. Я надеюсь, что гуру MySQL там покажет мне ошибку моего пути. Заранее спасибо за помощь!

Answer 1

MySQL Guru или нет, проблема в том, что, если вы не найдете способ отфильтровать различные строки, расстояние должно быть рассчитано между каждой точкой и каждым городом ...

Есть два основных подхода, которые могут помочь ситуации

• упростить формулу расстояния
• отфильтровывает маловероятных кандидатов на радиус 100к от данного города

Прежде чем перейти к этим двум направлениям совершенствования, вам следует определиться с желаемым уровнем точности в отношении этого расстояния в 100 миль, а также указать, какой географический район охватывается базой данных (это только континентальная часть США и т. Д.

Причина этого в том, что, хотя более точная численная формула Великого круга очень затратна в вычислительном отношении. Другим способом улучшения производительности было бы сохранение «координат сетки» в виде дополнения (или вместо) координат широты / долготы.

Редактировать
Несколько идей о более простой (но менее точной) формуле :
Поскольку мы имеем дело с относительно небольшими расстояниями (и я предполагаю, что между 30 и 48 градусами северной широты), мы можем использовать евклидово расстояние (или, что еще лучше, квадрат евклидового расстояния), а не более сложные формулы сферической тригонометрии. .
в зависимости от ожидаемого уровня точности, может быть даже приемлемым иметь один единственный параметр для линейного расстояния для полной степени долготы, принимая среднее значение по рассматриваемой области (скажем, около 46 статут миль). Формула тогда станет

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

По идее столбцы с информацией сетки для фильтрации для ограничения количества строк , учитываемой для расчета расстояния.
Каждой «точке» в системе, будь то город или другая точка («места доставки», «места хранения» и т. Д.), Присваиваются две целочисленные координаты, которые определяют квадрат, скажем, 25 миль * 25 миль, где находится точка. Координаты любой точки в пределах 100 миль от контрольной точки (данного города) будут максимум +/- 4 в направлении x и +/- 4 в направлении y. Затем мы можем написать запрос, подобный следующему

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 может быть жестко задан (то же самое для всех местоположений в континентальной части США) или получен из соответствующей записи в таблице почтовых индексов. Аналогично, LatDegInMi может быть жестко закодирован (нет необходимости изменять его, поскольку в отличие от других он относительно постоянен).

Причина, по которой это происходит быстрее, заключается в том, что для большинства записей в декартовом произведении между таблицей почтовых индексов и таблицей точек мы вообще не вычисляем расстояние. Мы исключаем их на основе значения индекса (GridX и GridY).

Это подводит нас к вопросу о том, какие индексы SQL создавать. Конечно, мы можем захотеть: - GridX + GridY + Status (в таблице очков) - статус GridY + GridX + (возможно) - Город + Штат + широта + долгота + GridX + GridY в таблице почтовых индексов

Альтернативой сеткам является «привязка» границ широты и долготы, которые мы рассмотрим, на основе широты и долготы данного города. то есть условие 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)) 

Answer 2

Когда я выполняю поиск такого типа, мои потребности допускают некоторое приближение. Поэтому я использую формулу, которая у вас есть во втором запросе, чтобы сначала вычислить «границы» - четыре значения широты / долготы в крайних значениях допустимого радиуса, затем взять эти границы и выполнить простой запрос, чтобы найти совпадения внутри них ( меньше чем максимальный лат, длинный, больше чем минимальный лат, длинный). Итак, в итоге я получаю все, что находится в квадрате внутри круга, определенного радиусом.

Answer 3

SELECT * FROM tblLocation 
    WHERE 2 > POWER(POWER(Latitude - 40, 2) + POWER(Longitude - -90, 2), .5)

, где часть 2> будет количеством параллелей, а 40 и -90 - широта / долгота контрольной точки

Извините, я не использовал ваши имена таблиц или структуры, я просто скопировал это из одной из моих хранимых процедур, которые есть в одной из моих баз данных.

Если бы я хотел увидеть количество точек в почтовом индексе, я бы сделал что-то вроде этого:

SELECT 
    ParcelZip, COUNT(LocationID) AS LocCount 
FROM 
    tblLocation 
WHERE 
    2 > POWER(POWER(Latitude - 40, 2) + POWER(Longitude - -90, 2), .5)
GROUP BY 
    ParcelZip

Получение общего количества всех местоположений в диапазоне будет выглядеть так:

SELECT 
    COUNT(LocationID) AS LocCount 
FROM 
    tblLocation 
WHERE 
    2 > POWER(POWER(Latitude - 40, 2) + POWER(Longitude - -90, 2), .5)

В данном случае перекрестное соединение может быть неэффективным, поскольку речь идет о большом количестве записей, но это должно выполнить работу в одном запросе:

SELECT 
    ZipCodes.ZipCode, COUNT(PointID) AS LocCount 
FROM
    Points
CROSS JOIN 
    ZipCodes
WHERE 
    2 > POWER(POWER(Points.Latitude - ZipCodes.Latitude, 2) + POWER(Points.Longitude - ZipCodes.Longitude, 2), .5)
GROUP BY 
    ZipCodeTable.ZipCode