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

9

Por exemplo, digamos que eu tenha uma tabela:

Business(BusinessID, Lattitude, Longitude)

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

Digamos que eu queira encontrar empresas mais próximas a 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 calcular a distância para todos os negócios, enquanto na prática apenas aqueles com latitude e longitude dentro de um determinado intervalo que deve ser calculado.

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

Sou grato com a resposta até agora. Estou usando o mysql e eles não têm nada mais eficiente do que a solução óbvia. O MySQL espacial também não possui a função de distância computacional.

user4951
fonte

Respostas:

8

Se eu entendi a pergunta corretamente (e não tenho certeza), você está preocupado com a computação "(Some formula to compute distance here)"de todas as linhas da tabela cada vez que faz uma consulta?

Isso pode ser atenuado até certo ponto usando os índices latitudee, longitudeportanto, 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 em que você está calculando as distâncias.

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

Em termos gerais, essa é uma maneira primitiva de otimizar um tipo de pesquisa de vizinhos mais próximos . Se o seu RDBMS suporta índices GiST , como o postgres , considere usá-los.

Jack diz que tenta topanswers.xyz
fonte
Eu usei o mysql. No entanto, algum mecanismo mysql suporta geopatial, embora não innodb.
user4951
Estou certo de que você não tem opção de mudar do MySQL? Caso em que, por favor marcar a questão mysql
Jack diz tentativa topanswers.xyz
Na verdade, agora adiciono a tabela auxiliar do myisam agora, como faço isso de forma eficiente?
usar o seguinte comando
Bem, eu posso usar mongodb. Eu não decidi isso. No entanto, eu estou mais familiarizado com o mysql.
usar o seguinte comando
11
Meu conselho seria se familiarizar com o postgres, se possível - comparado ao MongoDB, é muito mais parecido com o MySQL e tem uma história sólida com dados espaciais, e seus comentários indicam que você prefere 'grátis'.
Jack diz que tente topanswers.xyz
6

(Divulgação: eu sou do tipo 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 de geografia e geometria diretamente no banco de dados sem fazer cálculos intensos / caros dinamicamente e permite criar índices para encontrar rapidamente o ponto mais próximo da sua localização atual (ou rota mais eficiente ou qualquer outra coisa).

O armazenamento em cache é importante se você deseja dimensionar, período. 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 o Redis ou o cache de memórias por um período de horas. As localizações das empresas não serão alteradas por quatro horas - bem, elas podem ocorrer se alguém editar uma empresa, mas você não precisa necessariamente ser atualizado imediatamente em todos os conjuntos de resultados.

Brent Ozar
fonte
Não consigo descobrir pelo seu link se o SQL Server realmente indexa dados espaciais de uma maneira que é útil para obter uma lista de pontos próximos - não é?
Jack diz que tente topanswers.xyz
Parece que não
Jack diz que tente topanswers.xyz
O problema é que estou usando o mysql e verifiquei que eles não têm nenhum algoritmo mais eficiente do que o prescrito por Jack Douglas. Gostaria de saber se o mysql fará esse tipo de coisa como cache também. Microsoft SQL é pago e mysql é gratuito
user4951 2/11/11
11
A localização da empresa não muda o tempo todo, mas a localização das pessoas muda.
user4951
0

O Yelp provavelmente usa GIS

O PostgreSQL possui a implementação de referência para GIS com PostGIS . O Yelp pode estar usando 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 em potencial

Essas coordenadas estão quase certamente no WGS84 e armazenadas como tipo de Geografia. No PostgreSQL e no PostGIS, seria algo como isto,

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 enchiam a mesa. 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 Sistemas de Informação Geográfica @ StackExchange

Evan Carroll
fonte