Wie berechnet Yelp die Entfernung in der Datenbank effizient?

9

Angenommen, ich habe eine Tabelle:

Business(BusinessID, Lattitude, Longitude)

Alle sind natürlich indiziert. Es gibt auch 1 Million Datensätze

Angenommen, ich möchte 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 Geschäfte berechnen, während in der Praxis nur diejenigen mit Längen- und Breitengraden innerhalb eines bestimmten Bereichs berechnet werden sollten.

Wie kann ich beispielsweise in PhP oder SQL tun, was ich will?

Ich bin dankbar für die bisherige Antwort. Ich benutze MySQL und sie haben nichts effizienter als die offensichtliche Lösung. MySQL räumlich hat auch keine Funktion zum Berechnen der Entfernung.

user4951
quelle

Antworten:

8

Wenn ich die Frage richtig verstehe (und ich bin mir nicht sicher, ob ich das tue), haben Sie Angst, "(Some formula to compute distance here)"bei jeder Abfrage für jede Zeile in der Tabelle zu rechnen?

Dies kann zu einem gewissen Grad verringert werden , indem die Indizes auf latitudeund longitudeso müssen wir nur die Entfernung für eine ‚Box‘ berechnen Punkte den Kreis enthalten wir eigentlich wollen:

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 gewählt werden, dass sie mit der Einheit des Werts '2000' und dem Punkt auf dem Globus übereinstimmen, von dem Sie Entfernungen berechnen.

Wie genau dies Indizes verwendet, hängt von Ihrem RDBMS und den Entscheidungen des Planers ab.

Im Allgemeinen ist dies eine primitive Methode zur Optimierung einer Art Suche nach nächsten Nachbarn . Wenn Ihr RDBMS GiST-Indizes wie Postgres unterstützt , sollten Sie diese stattdessen verwenden.

Jack sagt, versuchen Sie es mit topanswers.xyz
quelle
Ich habe MySQL verwendet. Einige MySQL-Engines unterstützen jedoch Geopatial, jedoch nicht Innodb.
user4951
Habe ich recht, dass Sie keine Möglichkeit haben, von MySQL zu wechseln? In diesem Fall markieren Sie bitte die Frage mysql
Jack sagt, versuchen Sie topanswers.xyz
Eigentlich füge ich jetzt eine Hilfstabelle von myisam hinzu. Wie mache ich das dann effizient?
user4951
Nun, ich kann Mongodb benutzen. Das habe ich nicht entschieden. Am vertrautesten bin ich jedoch mit MySQL.
user4951
1
Mein Rat wäre, sich mit Postgres vertraut zu machen, wenn dies überhaupt möglich ist - im Vergleich zu MongoDB ist es MySQL viel ähnlicher und hat eine solide Historie mit räumlichen Daten, und Ihre Kommentare an anderer Stelle zeigen, dass Sie "kostenlos" bevorzugen.
Jack sagt, versuchen Sie es mit topanswers.xyz
6

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

Um es wirklich effizient zu machen, möchten Sie zwei Dinge: Caching und Unterstützung für native Geodaten. Mit der Unterstützung von Geodaten können Sie Geografie- und Geometriedaten direkt in der Datenbank speichern, ohne im laufenden Betrieb intensive / teure Berechnungen durchführen zu müssen, und Sie können Indizes erstellen, um sehr schnell den nächstgelegenen Punkt zu Ihrem aktuellen Standort (oder der effizientesten Route oder was auch immer) zu finden.

Das Caching ist wichtig, wenn Sie skalieren möchten. Die schnellste Abfrage ist die, die Sie nie stellen. Wenn ein Benutzer nach den ihm am nächsten liegenden Dingen fragt, speichern Sie seinen Standort und die Ergebnismenge für einen Zeitraum von Stunden in einem Cache wie Redis oder zwischengespeichert. Die Geschäftsstandorte werden sich 4 Stunden lang nicht ändern. Wenn jemand ein Unternehmen bearbeitet, muss dies jedoch nicht unbedingt in allen Ergebnismengen sofort aktualisiert werden.

Brent Ozar
quelle
Ich kann anhand Ihres Links nicht herausfinden, ob SQL Server räumliche Daten wirklich so indiziert, dass eine Liste der Punkte in der Nähe abgerufen werden kann - oder?
Jack sagt, versuchen Sie es mit topanswers.xyz
Es sieht
so aus, als ob
Die Sache ist, ich benutze MySQL und ich habe überprüft, dass sie keinen Algorithmus haben, der effizienter ist als das, was Jack Douglas vorgeschrieben hat. Ich frage mich, ob MySQL auch so etwas wie Caching machen wird. Microsoft SQL ist bezahlt und MySQL ist kostenlos
user4951
1
Der Unternehmensstandort wird sich nicht ständig ändern, der Standort der Mitarbeiter jedoch.
user4951
0

Yelp verwendet wahrscheinlich GIS

PostgreSQL hat die Referenzimplementierung für GIS mit PostGIS . Yelp verwendet möglicherweise MySQL, das in jeder Hinsicht minderwertig ist . Bei so etwas wie Yelp behalten sie mit ziemlicher Sicherheit die Koordinaten für,

  • Der Benutzer
  • Die möglichen Ziele

Diese Koordinaten befinden sich mit ziemlicher Sicherheit in WGS84 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 diese Tabelle 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 und unter Geographic Information Systems @ StackExchange

Evan Carroll
quelle