Come si calcola in modo efficiente Yelp distanza nel database?

Question

Ad esempio, dire che ho una tabella:

Business(BusinessID, Lattitude, Longitude)

Tutti sono indicizzati naturalmente. Inoltre ci sono 1 milione di record

Di 'Voglio trovare le aziende più vicina al 106,5, per esempio, come lo farei?

Se faccio

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

per esempio, o se lo faccio

SELECT *
FROM Business
TOP 20

In teoria il computer dovrà distanza elaborazione per tutti biz mentre in pratica solo quelli con lattitude e longitudine entro un certo intervallo che deve essere calcolato.

Così come posso fare quello che voglio in PHP, SQL o, per esempio?

Sono grato con la risposta finora. Sto usando mysql e non hanno nulla di più efficiente rispetto alla soluzione più ovvia. MySQL spaziali non hanno la funzione di calcolo distanza sia.

Answer 1

Se ho capito correttamente alla domanda (e io non sono sicuro che faccio), siete preoccupati per il calcolo "(Some formula to compute distance here)" per ogni riga della tabella ogni volta che si esegue una query?

Questo può essere attenuato in misura utilizzando gli indici su latitude e longitude quindi non ci resta che calcolare la distanza di una 'scatola' di punti che contengono il cerchio vogliamo davvero:

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

Dove 96, 116 ecc sono scelti per abbinare l'unità del valore di '2000' e il punto del globo si sta calcolando distanze da.

Come proprio questo utilizza gli indici dipenderà dal vostro RDBMS e le scelte sua marche pianificatore.

In termini generali, questo è un modo primitivo di ottimizzare una sorta di più vicino di ricerca prossimo . Se i supporti RDBMS GiST , come postgres allora si dovrebbe considerare l'utilizzo di loro, invece.

Answer 2

(Disclosure:. Sono un ragazzo di Microsoft SQL Server, quindi le mie risposte sono influenzati da questo)

Per davvero fare in modo efficace, ci sono due cose che si desidera: la cache e il supporto nativo dei dati spaziali. spaziale dati supportano consente di memorizzare i dati di geografia e geometria direttamente nel database, senza fare calcoli intensivi / costosi al volo, e consente di creare indici per molto rapidamente trovare il punto più vicino alla posizione corrente (o la maggior parte itinerario efficiente o qualsiasi altra cosa).

Caching è importante se si vuole scalare, punto. La query più veloce è quello che mai fare. Ogni volta che un utente chiede le cose più vicine a lui, di archiviare la sua posizione e il set di risultati in una cache, come Redis o memcached per un periodo di ore. sedi di attività commerciali non stanno andando a cambiare per 4 ore -. beh, potrebbero se qualcuno modifica un business, ma non devono necessariamente che, per essere aggiornato immediatamente in tutti i set di risultati

Answer 3

Yelp probabili usi GIS

PostgreSQL ha l'implementazione di riferimento per GIS con PostGIS . Yelp può essere utilizzando MySQL, che è inferiore in ogni modo . Nel caso di qualcosa come Yelp, che quasi certamente mantenere le coordinate per,

• L'utente
• I potenziali destinazioni

Queste coordinate sono quasi certamente in WGS84 e memorizzata come tipo di Geografia. In PostgreSQL e PostGIS sarebbe simile a questa,

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;

Si sarebbero riempire quel tavolo. Poi si afferrano le coordinate WGS84 dal telefono e generare una query, come questo con SQL Alchemy (nel caso di Yelp),

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

Per ulteriori informazioni, consultare il nostro spaziale , e controllare informazione geografica @ StackExchange