IOException.de

Icon

Ausgewählter Nerdkram von Informatikstudenten der Uni Ulm

Optimierung SQL-basierter Umkreissuchen – Teil 1: Lösungsansätze

Wie auch einige Kollegen dieses Blogs nahm ich vor wenigen Wochen am node.js knockout teil, einem 48-Stunden-Hackathon. Ich versuchte mich mit meinem Projekt an einem Mashup, das als zentrales Element eine Umkreissuche beherbergen sollte.

Diesen Anwendungsfall gibt es sehr häufig: In einer SQL-Datenbank sind Geo-Koordinaten von Orten gespeichert und es soll nun ausgehend von einer beliebigen Position eine bestimmte Anzahl der nächstgelegenen gespeicherten Orte gefunden werden. Da ich mit meinem Projekt eine Datenbank für deutsche Vereine realisieren wollte, wäre etwa eine konkrete Fragestellung gewesen: “Hey, ich bin gerade beim Alexanderplatz Berlin. Such mir doch mal die 15 nächstgelegenen Vereine heraus!” Die Ergebnismenge ist hierbei nur in der Anzahl, nicht aber der Entfernung eingeschränkt. Genau umgekehrt wäre es zum Beispiel, wenn nach allen Vereinen im Umkreis von 50km gesucht würde, wo auch mehr oder weniger als 15 Resultate gefunden werden könnten. Dieser Beitrag wird nur die erste Frage behandeln. Der Begriff “Umkreissuche” sollte also in diesem Sinne verstanden werden.

Nehmen wir an, unsere Koordinaten sind in der Tabelle coords in den Spalten lat und lon gespeichert. Die 15 nächstgelegenen Orte zu einem gegebenen Punkt (c.lat, c.lon) zu finden ist gar nicht so schwer, die SQL-Abfrage findet man im Internet:

'SELECT *, (acos(sin('+c.lat+'*Pi()/180)*sin(lat*Pi()/180)+cos('+c.lat+'*Pi()/180)*cos(lat*Pi()/180)*cos(('+c.lon+'-lon)*Pi()/180))) as distance FROM coords ORDER BY distance ASC LIMIT 15'

Die Resultate, die diese Abfrage liefert, sind die 15 nächstgelegenen Orte zum Punkt c. Problem bei diesem Vorgehen ist, dass die Abfrage recht umfangreich und somit auch zeitintensiv ist, wodurch sie etwa im Falle großer Datenmengen oder zusätzlicher Joins zum Flaschenhals wird. So lief die Abfrage bei meinem Projekt mit nur 2600 gespeicherten Orten sehr schleppend und drohte das Scheitern der gesamten Applikation.

Abhilfe sollte folgende Überlegung schaffen: Ist es schneller, nicht direkt von der Tabelle coords abzufragen, sondern eine Auswahl überhaupt in Frage kommender Vereine vorher abzuschätzen? Ziel wäre es also, einen Query in folgender Form zu nutzen:

'SELECT *, (Formel von oben) AS distance FROM (SELECT * FROM coords ORDER BY abschaetzung LIMIT faktor*15) AS shortened ORDER BY distance LIMIT 15'

Es werden also über eine Näherungsformel die 15*faktor besten Datensätze vorausgewählt, aus denen dann die 15 echt nächsten gesucht werden. Die simpelste Idee einer solchen Näherungsformel wäre schlicht die Abschätzung mittels Pythagoras, bei der wir mal außer Acht lassen, dass unsere Erde ja eigentlich ein räumliches Gebilde ist. Die Abschätzungsselektion sieht dann so aus:

'SELECT * FROM coords ORDER BY SQRT(POW(('+c.lat+'-lat), 2)+POW(('+c.lon+'-lon), 2)) LIMIT '+15*faktor

Abmessung Nord-Süd-Ausnehnung Deutschland

Mit dem Google Maps Distance Calculator lässt sich ein Verhältnis Breitengrad / km bestimmen

Entscheidend ist natürlich: Wie groß muss wohl faktor gewählt werden, damit auch wirklich alle der 15 echt nächsten Punkte in der Vorauswahl enthalten sind? Während des 48-Stunden-Hackathons hatte ich keine Zeit, dies näher zu ergründen und probierte es mit dem Faktor 2, der nach meinem Empfinden kaum false-positives lieferte. Ob dem wirklich so ist, wird der zweite Teil dieses Beitrags zeigen.

Die Betrachtung, Längen- und Breitengrade gleich gewichtet in die Pythagoras-Formel einfließen zu lassen, ist der naivste Weg. Die false-positive-Rate ließe sich verbessern, wenn man das Verhältnis Breitengrad zu Längengrad genauer wüsste. Diese lassen sich aber nicht einfach in Kilometer umrechnen – einen konstanten Umrechnungsfaktor kann es aufgrund der Erdkrümmung nicht geben. Da wir aber ohnehin nur eine Näherungsformel zur Vorauswahl suchen, ist das auch gar nicht so schlimm, Näherungswerte reichen für eine Verbesserung der eben genutzten Pythagorasformel vollkommen.

Über den Google Maps Distance Calculator lassen sich Näherungen für Deutschland recht schnell ermitteln: Ein Breitengrad (lat) entspricht bei uns rund 70 Kilometer, Längengrade (lon) erhöhen sich alle 110 Kilometer um eins. Damit lässt sich die obige Pythagoras-Formel verbessern:

'SELECT * FROM coords ORDER BY SQRT(POW(('+c.lat+'-lat)/70, 2)+POW(('+c.lon+'-lon)/110, 2)) ASC LIMIT '+15*faktor2

Der Preis einer solchen Verbesserung der Näherungsformel ist freilich, dass die Abfrage wieder rechenintensiver wird. Interessant dürfte also sein, ob sich das ganze dann überhaupt noch lohnt. Eigentlich ist es auch gar nicht nötig, die Breiten- und Längengrade auf Kilometer runter zu rechnen, da ja eigentlich nur das Verhältnis als Gewichtung eingehen soll. Statt beide zu dividieren würde also auch ein (lonDiff)*1.57 genügen – wieder eine Operation gespart!

Noch immer wissen wir jedoch nicht, wie groß der jeweilige Faktor bei den beiden Abschätzungen sein sollte, sodass man eine möglichst geringe Fehlerquote erhält (trivialerweise sollte er natürlich wenigstens 1 sein). Wieviel weniger darf der Faktor wohl angesetzt werden, wenn man die Pythagorasformel wie oben beschrieben verbessert? Ein Stochastiker würde das wohl in dieser Form fragen: Wie groß muss der Faktor wenigstens sein, dass nur in maximal 5 Prozent aller Abfragen nicht alle 15 nächsten Vereine enthalten sind?

Im nächsten Teil wird versucht, diese Fragen durch eine Vielzahl an Tests an den Vereinsdaten zu beantworten, und geklärt werden, ob sich die Vorauswahl denn wirklich in einer Steigerung der Perfomance ausdrückt. Ohne zu viel vorweg nehmen zu wollen: Bei meinem node.js knockout Projekt betrug der Performancegewinn über 80 Prozent. Da wusste ich aber auch noch nicht, dass die einfache Pythagorasabschätzung mit Faktor 2 in jedem fünften Fall nicht alle der 15 nächstgelegenen Vereine lieferte…

Kategorie: datenbanken, theoretische informatik

Tags: , ,

Diese Icons verlinken auf Bookmark Dienste bei denen Nutzer neue Inhalte finden und mit anderen teilen können.
  • MisterWong
  • Y!GG
  • Webnews
  • Digg
  • del.icio.us
  • StumbleUpon
  • Reddit
  • Facebook

7 Kommentare

  1. Oli H. sagt:

    Meiner Meinung nach ist die erste Abfrage bereits eine Annäherung. Hier wird als Grundlage eine Kugel benutzt, dabei stimmt das gar nicht. Dem WGS84 Koordinatensystem liegt ein bestimmtes Ellipsoid zu Grunde. Was die Berechnung aber wirklich komplex macht.

    Mein Lösungsvorschlag wäre eher die Datenbank vorher in ein sinnvolles Koordinatensystem umzuwandeln: UTM unterteilt die Erde in kartesische Abschnitte.

  2. Falco Nogatz sagt:

    Klar, auch die erste Formel geht von einer Kugel aus. Die von Dir angesprochene Berechnung im WGS84-System findet sich als Javascript zum Beispiel hier: http://www.movable-type.co.uk/scripts/latlong-vincenty.html#code Das per SQL umzusetzen dürfte ziemlich aufwendig werden.

    Durch Deine Vorschläge habe ich nochmal ein wenig gegoogelt und bin dabei zufällig auf die Spatial Extensions von MySQL gestoßen, deren GIS Modell bereits Geometrieklassen für Punkte und andere Formen bereitstellt. Vielleicht hat ja jemand bereits damit Erfahrungen sammeln können?

  3. David sagt:

    Was mir nicht ganz so in den Sinn kommt ist, warum SQRT groß und sin, cos klein geschrieben sind. Hat das einen Grund?

  4. Falco Nogatz sagt:

    Kurz: Nein :)
    Vervollständigt wird das ganze durch Pi() ^^ Werd das beim nächsten Mal alles groß schreiben, danke für den Hinweis!

  5. Daniel sagt:

    Alexanderplatz, Berlin: 52.52194,13.410981

    SELECT * FROM coords ORDER BY geom ST_SetSRID(ST_Point(13.410981, 52.52194),4326) LIMIT 15;

    Das wäre eine Möglichkeit unter PostGIS (Spatial Extension von PostgreSQL), welches ich jederzeit MySQL Spatial vorziehen würde.
    Der “distance”-Operator sortiert die Einträge nach Index (welcher auf der geom Spalte liegt). Der Index ist hierbei räumlich und gibt eine BoundingBox zurück. Da wir hier Punktdaten haben entspricht der Index den Punktdaten und wir erhalten exakte Ergebnisse. Bei Polygonen oder Linien müssten wird andere Verfahren anwenden, für eine Näherung greift diese Abfrage trotzdem.

    Räumliche Referenzsysteme lassen sich auch ohne weiteres on-the-fly von solchen Datenbanken umrechnen. Hier mal eine Dokumentation zu PostGIS: http://postgis.org/docs/reference.html

  6. Daniel sagt:

    Der “distance”-Operator steht zwischen “geom” und “ST_SetSRID”. Das Formular mag halt keine spitzen Klammern :/ (eine Vorschau vor dem Absenden wäre wünschenswert)

  7. [...] ersten Teil haben wir zwei einfache Lösungsstrategien entwickelt, wie sich Umkreissuchen der Form “Suche [...]

Kommentar