Wie berechnet Yelp effizient die Entfernung in der Datenbank?

Question

Angenommen, ich habe eine Tabelle:

Business(BusinessID, Lattitude, Longitude)

Alle sind natürlich indiziert.Außerdem gibt es 1 Million Datensätze

Angenommen, ich möchte beispielsweise Unternehmen finden, die 106,5 am nächsten liegen. Wie würde ich das tun?

Wenn ich mache

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

zum Beispiel, oder wenn ich es tue

SELECT *
FROM Business
TOP 20

Theoretisch muss der Computer die Entfernung für alle Unternehmen berechnen, während in der Praxis nur diejenigen berechnet werden sollten, deren Breiten- und Längengrad innerhalb eines bestimmten Bereichs liegen.

Wie kann ich also zum Beispiel in PHP oder SQL machen, was ich will?

Ich bin bisher für die Antwort dankbar.Ich verwende MySQL und es gibt keine effizientere Lösung als die offensichtliche Lösung.MySQL Spatial verfügt auch nicht über eine Funktion zur Berechnung der Distanz.

Answer 1

Wenn ich die Frage richtig verstehe (und ich bin mir nicht sicher, ob ich das tue), machen Sie sich Sorgen um das Computer "(Some formula to compute distance here)" Für jede Zeile in der Tabelle jedes Mal, wenn Sie eine Frage durchführen?

Dies kann bis zu einem gewissen Grad durch Verwendung der Indizes auf gemindert werden latitude und longitude Wir müssen also nur die Entfernung für ein "Kasten" von Punkten berechnen, der den gewünschten Kreis enthält:

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

Wobei 96, 116 usw. so ausgewählt werden, dass sie der Einheit des Wertes '2000' und dem Punkt auf dem Globus entsprechen, von dem Sie Entfernungen berechnen.

Wie genau dieser Indizes verwendet, hängt von Ihrem RDBMS und den Auswahlmöglichkeiten ab, die der Planer trifft.

Im Allgemeinen ist dies eine primitive Methode, um eine Art zu optimieren Suche nach Nachbarn. Wenn Ihre RDBMs unterstützt werden GIST -Indizes, wie Postgres Dann sollten Sie sie stattdessen in Betracht ziehen.

Answer 2

(Offenlegung: Ich bin ein Microsoft SQL Server -Typ, daher werden meine Antworten davon beeinflusst.)

Um es wirklich effizient zu tun, gibt es zwei Dinge, die Sie wollen: Caching und native räumliche Datenunterstützung. Räumungsdatenunterstützung Sie können Geographie- und Geometriedaten direkt in der Datenbank speichern, ohne intensiv/teure Berechnungen im laufenden Fliegen durchzuführen, und können Sie Indizes erstellen, um sehr schnell den nächsten Punkt Ihres aktuellen Standorts (oder effizientesten Route oder was auch immer) zu finden.

Caching ist wichtig, wenn Sie skalieren möchten, Zeitraum. Die schnellste Frage ist die, die Sie nie machen. Immer wenn ein Benutzer ihm nach den nächstgelegenen Dingen fragt, speichern Sie seinen Standort und das Ergebnis in einem Cache wie Redis oder Memcached für einen Zeitraum von Stunden. Geschäftsstandorte werden sich nicht für 4 Stunden ändern - na ja, sie könnten, wenn jemand ein Unternehmen bearbeitet, aber Sie müssen nicht unbedingt in allen Ergebnismengen sofort aktualisiert werden.

Answer 3

Yelp verwendet wahrscheinlich GIS

PostgreSQL verfügt über die Referenzimplementierung für GIS mit PostGIS. Yelp verwendet möglicherweise MySQL, das in jeder Hinsicht minderwertig ist.Im Fall von Yelp speichern sie mit ziemlicher Sicherheit die Koordinaten für:

• Der Benutzer
• Die möglichen Ziele

Diese Koordinaten liegen höchstwahrscheinlich in WGS84 vor und werden als Geografietyp gespeichert.In PostgreSQL und PostGIS würde es ungefähr so ​​aussehen:

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;

Sie würden diesen Tisch füllen.Dann holen sie sich die WGS84-Koordinaten von Ihrem Telefon und generieren eine Abfrage, wie diese mit SQL Alchemy (im Fall von Yelp).

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

Weitere Informationen finden Sie in unserem räumlich, und check out Geografische Informationssysteme @ StackExchange