Найти расстояние между более чем 100K мест

Question

Найти расстояние между более чем 100K мест

У меня есть две таблицы MySQL с местами, table1 а также table2 (увидеть ниже). В каждой таблице более 100 тысяч строк. Я хотел бы найти расстояние между каждым местоположением в этих двух таблицах, используя их геолокации.

Вот запрос MySQL, чтобы найти расстояние между одной геолокацией, например, (-37.22, 88.88) и всеми местоположениями в table1,

$lat = -37.22;
$long = 88.88;

SELECT id, latitude, longitude, name
((2 * 3960 *
ATAN2(
SQRT(
POWER(SIN((RADIANS($lat - latitude))/2), 2) +
COS(RADIANS(latitude)) *
COS(RADIANS($long)) *
POWER(SIN((RADIANS($long - longitude))/2), 2)
),
SQRT(1-(
POWER(SIN((RADIANS($lat - latitude))/2), 2) +
COS(RADIANS(latitude)) *
COS(RADIANS($long)) *
POWER(SIN((RADIANS($long - longitude))/2), 2)
))
)
)) AS distance FROM table1 ORDER BY distance;

Table1
id name latitude longitude
1   foo1    -37.12   62.34
2   foo2    -47.12   72.34
3   foo3    -57.12   82.34

Table2
id name latitude longitude
1   bar1    -38.22   66.11
2   bar2    -48.22   76.11
3   bar3    -58.22   86.11

Учитывая, что это тоже большие данные, я не уверен, с чего начать. Мысли?

1

bigdata geolocation mysql php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Если вы хотите оптимизировать путешествие или приблизиться к местоположению, вы должны использовать пространственные функции. http://dev.mysql.com/doc/refman/5.7/en/spatial-extensions.html
Но похоже, что вы хотите каждый расчет, так что да, вам нужно будет сделать 10 миллиардов операций.
- Я думаю, время здесь не проблема. Потому что, если у вас есть, вы можете использовать его. А если появятся новые локации, просто рассчитайте расстояние от этой локации.
- Но вы должны оптимизировать. Самая затратная часть запроса — это расчет SIN() а также COS() поэтому создайте дополнительное поле для каждой строки с этим значением. Таким образом, вы должны сделать это только один раз, а не 100 000 раз для каждой строки
- Наконец, запустите цикл, чтобы создать данные в блоках.

РЕДАКТИРОВАТЬ:

После прочтения вашего последнего комментария. Вам нужен пространственный индекс. Так же, как при поиске одного идентификатора в вашей базе данных, пространственный индекс оптимизирует поиск поблизости.

Также вы можете сделать поиск коробки. Вместо того, чтобы искать всю вселенную, вы создаете рамку вокруг своей точки и ищите внутри этой рамки. Используя обычный индекс с плавающей точкой, вы делаете что-то вроде этого

  SELECT t1.name, t2.name,  mysql.Distancefunction(t1,t2) as distance
from t1
cross join t2
WHERE t2.x between (t1.x - 0.001) and (t1.x + 0.001)   -- use x float index
and t2.y between (t1.y - 0.001) and (t1.y + 0.001)   -- use y float index
and mysql.Distancefunction(t1,t2) < 100 km           -- use spatial index

Вы можете играть с дельтой 0,001. Если вы получаете слишком много результатов, вы используете 0,0001. Если вы получаете мало результатов, вы делаете второй шаг с 0,01 только для тех мест без 100 соседей.

1