Início / dba / Perguntas / 4210
Accepted
user4951
Asked: 2011-08-01 06:59:03 +0800 CST

Como o Yelp calcula com eficiência a distância no banco de dados?

  • 772

Por exemplo, digamos que eu tenha uma tabela:

Business(BusinessID, Lattitude, Longitude)

Todos são indexados, é claro. Também há 1 milhão de registros

Digamos que eu queira encontrar empresas mais próximas de 106,5, por exemplo, como eu faria isso?

Se eu fizer

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

por exemplo, ou se eu fizer

SELECT *
FROM Business
TOP 20

Em teoria o computador terá que computar distância para todos os biz enquanto na prática apenas aqueles com latitude e longitude dentro de uma certa faixa que deve ser computada.

Então, como posso fazer o que quero em PhP ou SQL, por exemplo?

Estou grato com a resposta até agora. Estou usando mysql e eles não tem nada mais eficiente que a solução óbvia. O MySQL espacial também não possui função de cálculo de distância.

optimization mysql-5.5

3 respostas

  1. Best Answer

    Se eu entendi a pergunta corretamente (e não tenho certeza), você está preocupado em calcular "(Some formula to compute distance here)"cada linha da tabela toda vez que faz uma consulta?

    Isso pode ser mitigado até certo ponto usando os índices on latitudee longitude, portanto, só precisamos calcular a distância para uma 'caixa' de pontos contendo o círculo que realmente queremos:

    select * from business
where (latitude>96 and latitude<116) and 
      (longitude>-5 and longitude<15) and 
      (Some formula to compute distance here) < 2000

    Onde 96, 116 etc são escolhidos para corresponder à unidade do valor '2000' e ao ponto no globo a partir do qual você está calculando as distâncias.

    A precisão com que isso usa índices dependerá do seu RDBMS e das escolhas feitas por seu planejador.

    Em termos gerais, esta é uma forma primitiva de otimizar uma espécie de busca do vizinho mais próximo . Se o seu RDBMS oferece suporte a índices GiST , como postgres , considere usá-los.

    • 8

  2. (Divulgação: sou um cara do Microsoft SQL Server, então minhas respostas são influenciadas por isso.)

    Para realmente fazer isso com eficiência, há duas coisas que você deseja: armazenamento em cache e suporte a dados espaciais nativos. O suporte a dados espaciais permite armazenar dados geográficos e geométricos diretamente no banco de dados sem fazer cálculos intensivos/caros em tempo real e permite criar índices para encontrar rapidamente o ponto mais próximo de sua localização atual (ou rota mais eficiente ou qualquer outra).

    O armazenamento em cache é importante se você deseja dimensionar, ponto final. A consulta mais rápida é aquela que você nunca faz. Sempre que um usuário pede as coisas mais próximas a ele, você armazena sua localização e o conjunto de resultados em um cache como Redis ou memcached por um período de horas. Os locais das empresas não vão mudar por 4 horas - bem, eles podem mudar se alguém editar uma empresa, mas você não precisa necessariamente que isso seja atualizado imediatamente em todos os conjuntos de resultados.

    • 6

  3. Yelp provavelmente usa GIS

    PostgreSQL tem a implementação de referência para GIS com PostGIS . O Yelp pode estar usando o MySQL, que é inferior em todos os aspectos . No caso de algo como o Yelp, eles quase certamente mantêm as coordenadas para,

    • O usuário
    • Os destinos potenciais

    Essas coordenadas quase certamente estão em WGS84 e armazenadas como tipo Geografia. No PostgreSQL e no PostGIS, seria mais ou menos assim,

    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;

    Eles encheriam aquela mesa. Em seguida, eles pegam as coordenadas WGS84 do seu telefone e geram uma consulta, como esta com o SQL Alchemy (no caso do Yelp),

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

    Para obter mais informações, consulte nosso e confira Geographic Information Systems @ StackExchange

    • 0

relate perguntas