Max Breite für x Abstand von Länge - Max Länge für x Entfernung von Breitengrad - SQL

Question

Im Moment habe ich eine Tabelle von 100 Millionen Einsätze:

CREATE TABLE o (
    id   int UNIQUE, 
    latitude FLOAT(10, 8), 
    longitude FLOAT(11, 8) 

); 

Auf meinem hinteren Ende erhalte ich einen Benutzer lat/long und versuche alles innerhalb von x Entfernung davon zurückzugeben.

Anstatt die Entfernungsformel für jedes einzelne Ergebnis zu machen, dachte ich, ich könnte möglicherweise den maximalen Lat/Long für X Abstand berechnen.

Also erstellen wir ein Quadrat, indem wir das Maximum Lat/Min Lat, Max Long/Min Long finden.

Sobald wir diese maximalen Werte haben, würden wir die Abfrage auf diesem Bereich von Werten tun, wodurch unsere Teilmenge deutlich kleiner wird, als dann die tatsächliche Distanzformel zu machen (d. H. Die Werte innerhalb der X-Distanz zu finden).

Also meine Frage an Sie ist: Was macht mich schneller laufen?

Option 1)

• Entfernung Formel auf 100 Millionen Einträge um das Set zu bekommen.

Option 2)

• Statt die Abstandsformel auf dem Satz von 100 Millionen Einträge zu tun, berechnen wir die min/max lat/long.
• Wählen Sie die Werte in diesem Bereich aus der Tabelle der 100 Millionen Einträge
• Führen Sie die Entfernungsformel auf unserem neuen kleineren Satz aus.

Option 3)

• Etwas existiert hierfür bereits in SQL

Wenn Option 2 schneller ist das nächste Problem, das mathematische Problem tatsächlich zu lösen.

Wenn Sie an diesen weiter lesen aussehen:

Lat/Langstrecken Formel

dlon = lon2 - lon1 
dlat = lat2 - lat1 
a = (sin(dlat/2))^2 + cos(lat1) * cos(lat2) * (sin(dlon/2))^2 
c = 2 * atan2(sqrt(a), sqrt(1-a)) 
d = R * c 

Natürlich können wir diese neu anordnen, da D (1 Meile übernehmen) und R (der Radius die Erde) ist ein gesetzter Wert, so erhalten wir D/R = C.

Das Problem kommt dann in, wie berechnen wir C/2 = atan2 (sqrt (a), sqrt (1-a))?

Answer 1

1 - 100M Reihen ist viel zu scannen und zu testen. Es ist in Ordnung, tun Sie es hin und wieder, aber es ist zu langsam, um viel zu tun.

2 - ein pseudo-quadratischen Begrenzungsrahmen und

WHERE latitude BETWEEN ... 
    AND longitude BETWEEN ... 

tun, ist ein guter erster Schritt. Der Breitengradbereich ist eine einfache Konstante mal X; der Längengrad teilt sich auch durch cos(latitude).

Aber das Problem kommt, wenn Sie versuchen, nur diese Zeilen im Quadrat zu finden. Jede Kombination von Index auf latitude und/oder longitude, entweder separat oder zusammen, wird nur teilweise filtern. Das heißt, es ignoriert den Längengrad und gibt Ihnen alles innerhalb des Breitenbereichs oder umgekehrt. Das könnte Sie auf 100.000 Zeilen reduzieren, um die Entfernung zu überprüfen. Das ist viel besser als 100.000.000, aber nicht so gut, wie Sie es sich wünschen.

3 - http://mysql.rjweb.org/doc.php/latlng Geht auf den Platz, oder ganz in der Nähe. Es ist entworfen, um zu skalieren. Ich habe nur 3M Reihen getestet, nicht 100M, aber es sollte gut funktionieren.

Der Haupttrick ist, auf Breitengrad zu partitionieren, dann muss Länge die erste Spalte in PRIMARY KEY sein, damit InnoDB die nahe gelegenen Reihen in der Partition (en) gruppiert. Wenn Sie nach allen Zeilen innerhalb von X Meilen (oder km) suchen, kann es sich die ungefähre Anzahl der Zeilen anzeigen lassen (und die Großkreis-Entfernung berechnen), und nicht etwa 100K. Wenn Sie die nächsten 100 Elemente finden möchten, könnte es etwa 400 (4x) berühren.

Was SPATIAL Index, könnten Sie auf 5.7.6 aktualisieren möchten, das heißt, wenn ST_Distance_Sphere() und ST_MakeEnvelope() hinzugefügt wurden. (MakeEnvelope ist nur geringfügig praktischer als ein Polygon selbst aufzubauen - es hat ein Flat-Earth-Syndrom.)