Как Yelp эффективно вычисляет расстояние в базе данных?

Question

Например, скажем, у меня есть таблица:

Business(BusinessID, Lattitude, Longitude)

Все, конечно, индексируются. Также есть 1 миллион записей

Скажем, я хочу найти бизнес, ближайший к 106,5, например, как бы я это сделал?

Если я сделаю

SELECT *
FROM Business
WHERE (Some formula to compute distance here) < 2000

например, или если я сделаю

SELECT *
FROM Business
TOP 20

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

Итак, как я могу сделать то, что я хочу, например, в PHP или SQL?

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

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, как постгрес Тогда вам следует рассмотреть возможность их использования.

Answer 2

(Раскрытие: я парень Microsoft SQL Server, поэтому на меня влияют ответы.)

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

Кэширование важно, если вы хотите масштабировать, точка. Самый быстрый запрос - это тот, который вы никогда не делаете. Всякий раз, когда пользователь просит для него самые близкие вещи, вы храните его местоположение и результат, установленную в кэше, таком как Redis или Memcached в течение нескольких часов. Бизнес -точки не будут меняться в течение 4 часов - ну, они могут, если кто -то будет редактировать бизнес, но вам не обязательно нужно немедленно обновлять во всех наборах результатов.

Answer 3

Yelp, вероятно, использует ГИС

PostgreSQL имеет справочную реализацию для ГИС с Постгис. 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 с вашего телефона и генерируют запрос, как этот с Alchemy SQL (в случае Yelp),

SELECT *
FROM businesses AS b
WHERE ST_DWithin( b.geog, ST_MakePoint(userLong,userLat) );

Для получения дополнительной информации см. Наш пространственный, и проверить Географические информационные системы @ stackexchange