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…

Funktionale Ansätze in einer imperativen Programmiersprache

Im Zuge der Vorlesung “Paradigmen der Programmierung” kam ich erstmals mit dem alternativen Programmierkonzept der funktionalen Programmierung in Berührung, das sich von dem der weiter verbreiteteren imperativen Programmiersprachen wie etwa Java und C grundsätzlich unterscheidet. Als Übung auf die Klausur versuchte ich die Ideen der funktionalen Programmiersprache Haskell in einer imperativen Sprache umzusetzen. In Javascript ist die Nutzung von anonymen Funktionen und ihre Übergabe selbst als Parameter einer anderen Funktion bereits verbreitet, womit sie per se bereits einige Konzepte der funktionalen Programmierung umsetzt. Um weitere Dinge wie partielle Funktionsaufrufe ebenfalls zu ermöglichen, habe ich ein Javascript-Modul “functionalJS” geschrieben, das mit dem Konstruktor Functional() ein Äquivalent zum Javascript-eigenen Function() bietet. Der Quellcode sowie einige Beispiele finden sich auf github. Im Folgenden möchte ich die Ideen der funktionalen Programmierung kurz vorstellen und erklären, wie sie in dieser Klasse umgesetzt wurden.

Alles ist eine Funktion

Beim funktionalen Programmierstil besteht das Programm einzig aus Funktionen. Auf den ersten Blick mag das bei imperativen Programmiersprachen kaum anders sein, auch hier bilden Funktionen bzw. Methoden einen wesentlichen Bestandteil. Es gibt jedoch Unterschiede bei der Art der Aufrufe: Imperative Programme führen die Funktionen als eine Folge von Anweisungen aus (“Tu das! Dann tu das solange dies gilt!” – imperativ eben), bei der funktionalen Programmierung treten die Funktionen nur ineinander geschachtelt auf – das Ergebnis einer Funktion ist also zugleich Parameter der nächsten. Dadurch sind Variablen unnötigt, was einen Vorteil der funktionalen Programmiersprachen begründet: Es gibt keine Seiteneffekte! Während in der imperativen Programmierung das Resultat vom Programmzustand abhängt, hängen hier die Rückgabewerte einzig von den Parametern ab und etwa nicht vom Zeitpunkt des Aufrufes.

Für die Umsetzung in Javascript bedeutet dies, dass alle Funktionen ohne lokale Variablen auskommen, sondern stattdessen einzig ein return-Statement beinhalten. In diesem können nach dem eben genannten Konzept Funktionen aufgerufen werden. Dadurch ist Rekursion möglich, die nötig wird, um Schleifen zu vermeiden. Jede Funktion muss zudem mindestens einen Parameter und genau einen Rückgabewert besitzen, um dem funktionalen Anspruch gerecht zu werden.

Beispiel: Durchschnittsfunktion für eine übergebene Liste in Javascript (Ausschnitt der functional.js)

function(l) { return ratio(sum(l), length(l)); }

Mustervergleiche (Stichwort: Pattern matching)

Haskell erlaubt die mehrfache Definition einer Funktion. Dies unterscheidet sich wesentlich vom “Überladen” bei Java, wo die Unterschiede bei der mehrfachen Definition in der Methodensignatur liegen. In funktionalen Programmiersprachen werden dagegen semantische statt syntaktische Muster für die Eingabeparameter angelegt, d.h. es wird quasi eine Musterbasis aufgebaut, die dann beim Aufruf der Funktion von oben nach unten getestet wird. Sobald das erste Muster mit den übergebenen Parametern zusammenpasst, wird dessen Ergebnis oder Funktionsrumpf genutzt. Das Ergebnis hängt also wesentlich von der Reihenfolge der Musterdefinitionen ab. Basisfälle für Rekursionen werden so stets als erstes definiert, der allgemeinste Fall zum Schluss.

Beispiel: (Primitive) Definition der Fibonacci-Funktion in Haskell:

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)

Die beiden Basisfälle der Fibonacci-Funktion werden also vor der allgemeinen Rekursionsvorschrift definiert. In Javascript ist ein Überladen von Funktionen nicht möglich, auch bei der functionalJS-Klasse müssen so die Muster gleich dem Konstuktor übergeben werden. Eine äquivalente Definition der Fibonacci-Funktion mittels der functionalJS-Klasse sieht so aus:

Beispiel: Definition der Fibonacci-Funktion in Javascript (modifizierter Ausschnitt der test.js)

fibonacci = new Functional("fibonacci",
	[0, 0],
	[1, 1],
	["n", function(n) { return fibonacci(n-1)+fibonacci(n-2); }]
);

Die Muster werden als Arrays dem Functional übergeben. Dabei sind für reine Funktionen wie der letzte Fall auch Verkürzungen möglich. Näheres dazu ist in der Dokumentation aufgeführt. Ansonsten gilt: Das letzte Array-Element ist das Resultat oder die aufzurufende Funktion bei Übergabe dieses Musters. Optional kann als einfacher String der Name der Funktion übergeben werden, was für die interne Realisierung der Rekursion nötig ist.

Wird nun die Fibonacci-Funktion aufgerufen, so werden die Muster mittels Pattern matching nacheinander mit den tatsächlichen Parametern verglichen. Dabei sind durchaus auch kompliziertere Muster möglich, die die Haskell-typischen Listen erkennen. So wird die einfache length-Funktion, die die Anzahl der Elemente einer Liste zurückgibt, in beiden Sprachen wie folgt definiert:

Beispiel: Definition der length-Funktion in Haskell

length []	=  0
length (x:xs)	=  1 + length xs

Analog sieht eine solche Definition mittels functionalJS aus, mit dem Unterschied, dass hier für Listen (egal ob leer oder nicht) stets die eckigen Klammern genutzt werden:

Beispiel: Definition der length-Funktion in Javascript (Ausschnitt der functional.js)

length = new Functional("length",
	["[]", 		0],
	["[x:xs]", 	function(x, xs) { return 1+length(xs); }]
);

Über vordefinierte special operators ist es auch nach der Definition eines Functionals möglich, die Musterbasis zu erweitern. Dies könnte in diesem Beispiel etwa wie folgt geschehen, wodurch die Funktion bei Übergabe einer leeren Liste 42 zurückgibt:

Beispiel: Nachträgliche Erweiterung der Musterbasis in Javascript

length('__addOnTop',
	["[]", 42]
);

In Haskell ist ein solches Verhalten nachträglich etwa im GHCi, dem Haskell-Interpreter, nicht möglich. Dort könnten weitere Muster stets nur am Ende das Basis hinzugefügt werden. Ein solches Verhalten lässt sich bei functionalJS mittels des Keywords ‘__add’ realisieren.

Partielle Aufrufe (Stichwort: Currying)

Haskell erlaubt das partielle Aufrufen von definierten Funktionen, d.h. das Übergeben zu weniger Parameter um daraus eine neue Funktion zu erhalten. Dieses Verhalten ist sinnvoll, um eigene und vordefinierte Funktionen mehrfach nutzen zu können und insbesondere in der Verwendung als Funktional (siehe nächsten Punkt). Anders als bei imperativen Programmiersprachen stellen Übergabeparameter einer Funktion also kein Tupel dar (param1, param2, param3), sondern lassen sich eher als Liste param1 -> param2 -> param3 -> result auffassen. Werden alle Parameter übergeben, so wird ganz normal das Funktionsresultat zurückgegeben. Wird die Funktion dagegen nur mit zwei Parametern aufgerufen, so wird ein neue Funktion zurückgegeben, die von einem Parameter abhängt. Man sagt, dass eine Funktion mit einer Stelligkeit von 3 bei Übergabe von zwei Parametern eine Funktion der Stelligkeit 1 zurückliefert.

Das Verhalten, dass die Anzahl der Parameter einer Funktion in Javascript variabel sein kann, kann durch die Nutzung des arguments-Objekts realisiert werden. Schwieriger gestaltet sich die Realisierung der partiellen Auswertung (Ausschnitt). Während bei der normalen Auswertung, also bei Übergabe aller Parameter, einfach das erste Muster gesucht wird, welches zutrifft, müssen bei der partiellen Auswertung alle zutreffenden Muster gesucht werden, da diese in dieser Reihenfolge Teil des zurückzugebenen Functionals werden. Anhand dieser Muster wird ein neues Functional erzeugt, in deren Funktionsrümpfe die gebundenen Variablen durch die gematchten Parameter ersetzt werden. So wird also aus der zweistelligen add-Funktion (Definition), die die Summe zweier Zahlen berechnet, bei Übergabe des Parameters 1 ein einstelliges Functional, das eine Zahl erwartet und als Resultat den Nachfolger der Zahl zurückliefert.

Beispiel: Definition der Nachfolger-Funktion durch partiellen Aufruf in Javascript

succ = add(1); // add :: a -> a -> a

Anders als in Haskell können Funktionsnamen in functionalJS nur aus Buchstaben und Zahlen bestehen, eine Funktionsdefinition als “<” ist so etwa nicht möglich, stattdessen gibt es eine lessthan-Funktion. Dies erschwert partielle Aufrufe von nicht-kommutativen Funktionen.

Beispiel: Falsche Definition der negative-Funktion durch partiellen Aufruf in Javascript

negative = lessthan(0);

Die oben genannte Definition der negative-Funktion liefert eben nicht true zurück für Zahlen kleiner null, sondern genau das Gegenteil. Dies liegt an der Definition von lessthan:

Beispiel: Definition der standardmäßigen lessthan-Funktion (Ausschnitt der functional.js)

lessthan = new Functional("lessthan",
	function(a, b) { return a < b; }
);

Der partielle Aufruf lessthan(0) liefert also ein neues einstelliges Functional zurück, dass stets 0<x prüft. Dies entspricht also nicht dem gewünschten Verhalten. In Haskell sind dagegen auch partielle Aufrufe wie oben gewünscht möglich:

Beispiel: Definition der negative-Funktion in Haskell

negative = (<0)

Daher sind in den standardmäßigen Funktionen der functionalJS-Klasse zu jeder zweistelligen nicht-kommutativen Funktion auch eine entsprechende mit verdrehten Parametern definiert, die den gleichen Namen endend auf “Re” trägt. Unser obiges Beispiel müsste also korrekt lauten:

Beispiel: Korrekte Definition der negative-Funktion durch partiellen Aufruf in Javascript

negative = lessthanRe(0);

Funktionen als Parameter (Stichwort: Funktionale)

Die Möglichkeit des partiellen Aufrufs einer Funktion ist bereits ein mächtiges Instrument. Seine volle Wirkung können solche Funktionen aber bei Übergabe an andere entfalten. Anders als in vielen anderen imperativen Programmiersprachen ist die Übergabe von Funktionen als Parameter in Javascript möglich und ein häufiger Einsatzzweck, insbesondere als Callbacks für Events. Javascript-Anhängern ist ein solches Verhalten also bereits bekannt. In der funktionalen Programmierung bezeichnen wir Funktionen, die als Eingabe oder Ausgabe selbst Funktionen aufnehmen, als Funktionen höherer Ordnung oder Funktionale. So ist es etwa bei der Map-Funktion:

Beispiel: Definition der map-Funktion in Javascript (Ausschnitt der functional.js)

map = new Functional("map",
	["f", 	"[]", 		function(f) { return []; }],
	["f", 	"[x:xs]", 	function(f, x, xs) { return unshift(f(x), map(f, xs)); }]
);

Wie wir sehen, erwartet die map-Funktion also zwei Parameter: Zum einen eine Funktion f, zum anderen eine Liste. Das erste Muster beschreibt den Basisfall der leeren Liste, während der zweite den Rekursionsfall nennt. Kurz gesagt: Im Falle der leeren Liste wird eine leere Liste zurückgegeben, ansonsten wird das Kopfelement genommen, die Funktion f darauf angewendet, und das ganze mit dem Rest der Liste wiederholt und zusammengefügt. Die map-Funktion führt also eine Funktion f auf alle Elemente einer Liste aus. Bekannte Haskell-Beispiele der Funktionale sind auch die fold-Funktionen, die ebenfalls in dem Modul definiert wurden.

Unter Anwendung der Funktionen höherer Ordnung sowie partieller Aufrufe lassen sich so sehr schnell nette Funktionen zusammenstellen:

Beispiel: Anwendungen (Ausschnitt der test.js)

foldr(mult, 1, [1,2,3,4]); // 24, berechnet das Produkt aller Listenelemente

all(lessthanRe(5), [1,2,3,4]); // true, da alle Elemente kleiner 5

until(greaterthanRe(80), mult(2), 1); /* 128, da der Initialwert 1 solange mit 2 multiplitziert wird, bis der Schwellenwert 80 erreicht ist */

Fazit

Den funktionalen und imperativen Programmierstil zu vereinen ist schwierig und mag in der Frage münden: Warum? Zum einen beschneidet man die mächtigen Instrumente von Javascript, indem etwa Variablen und Schleifen komplett verboten werden, zum anderen kann man nicht aus den vollen Vorteilen von Haskell schöpfen, etwa bei der Nutzung unendlicher Listen. Und dennoch bieten die Functionals einige Vorteile, allen voran die partiellen Aufrufe. Ob durch die strikte Nutzung des funktionalen Stils tatsächlich auch in Javascript Seiteneffekte ausbleiben, wäre noch zu testen. Insbesondere, da sich einige Funktionen derzeit nicht atomar realisieren lassen (es gibt etwa keinen “(x:xs)”-Operator zur Listenerzeugung), darf in der aktuellen Fassung nicht davon ausgegangen werden. Prinzipien wie anonyme Funktionen und Funktionale sind in Javascript bereits enthalten, wodurch es sich zum Teil bereits ähnlich anfühlt. Das oben geführte until-Beispiel würde man mit normalen Javascript-Mitteln vermutlich wie folgt lösen:

Beispiel: Aufruf einer herkömmlichen until-Funktion in Javascript

until(function condition(x) { return x > 80; }, function do(x) { return x*2; }, 1);

Während ein solches Verhalten nicht in allen imperativen Programmiersprachen möglich ist, bietet Javascript offensichtlich bereits etwas ähnliches an. Auf partielle Aufrufe und die einfache Funktionsdefinition mittels Pattern matching muss man dennoch verzichten.

In der vorgestellten Klasse fehlen noch Haskell-typische Elemente, allen voran die Implementierung von Tupeln. So ist derzeit die bekannte zip-Funktion noch nicht eingebaut. Daneben ist die Implementierung der Mengendefinition, also das einfache Erzeugen einer Liste anhand einer Bildungsvorschrift, umsetzbar. Komplizierter wird es bei der Realisierung von unendlichen Listen, wo Haskell etwa in der Berechnung großer Fibonacci-Zahlen imperativen Programmiersprachen überlegen ist. Schlussendlich lassen sich dann auch ganz grundsätzliche Dinge, wie etwa die Nachbildung der lazy-evaluation als Auswertungsstrategie nicht nachträglich in Javascript umsetzen.

ioexception.de

Benjamin Erb [] studiert seit 2006 Medieninformatik und interessiert sich insbesondere für Java, Web-Technologien, Ubiquitous Computing, Cloud Computing, verteilte Systeme und Informationsdesign.


Raimar Wagner studiert seit 2005 Informatik mit Anwendungsfach Medizin und interessiert sich für C++ stl, boost & Qt Programmierung, Scientific Visualization, Computer Vision und parallele Rechenkonzepte.


David Langer studiert seit 2006 Medieninformatik und interessiert sich für Web-Entwicklung, jQuery, Business Process Management und Java.


Sebastian Schimmel studiert seit 2006 Informatik mit Anwendungsfach Medizin und interessiert sich für hardwarenahe Aspekte, Robotik, webOs, C/C++ und UNIX/Linux.


Timo Müller studiert seit 2006 Medieninformatik. Er interessiert sich allen voran für Mobile and Ubiquitous Computing, systemnahe Enwticklung und verteilte Systeme, sowie Computer Vision.


Achim Strauß studiert seit 2006 Medieninformatik. Seine Interessen liegen in Themen der Mensch-Computer Interaktion sowie Webentwicklung und UNIX/Linux.


Tobias Schlecht studiert seit 2006 Medieninformatik und interessiert sich vor allem für Software Engineering, Model Driven Architecture, Requirements Engineering, Usability Engineering, Web-Technologien, UML2 und Java.


Fabian Groh studiert seit 2006 Medieninformatik. Seine Interessengebiete sind Computer Graphics, Computer Vision, Computational Photography sowie Ubiquitos Computing.


Matthias Matousek studiert seit 2007 Medieninformatik und interessiert sich besonders für Skriptsprachen, Echtzeitsysteme und Kommunikation.


Michael Müller [] studiert seit 2009 Medieninformatik. Er interessiert sich vor allem für Web-Technologien, Ubiquitous Computing, User-Interfaces, UNIX und Creative Coding.


Falco Nogatz [] studiert seit 2010 Informatik mit Anwendungsfach Mathematik. Er interessiert sich für Web-Technologien, Programmierparadigmen und theoretische Grundlagen.

Archiv

Februar 2015
M D M D F S S
« Mrz    
 1
2345678
9101112131415
16171819202122
232425262728