Einleitung
Jeder Location-based Service [1 ] muss mehr oder weniger das folgende Problem lösen: finde alle interessanten Orte innerhalb einer gewissen Distanz zum aktuellen Standort des Anwenders. Lange vor dem Zeitalter der Smartphones und Tablets haben sich Geografische Informationssysteme (GIS) [2 ] mit diesem (und anderen) Problem(en) beschäftigt.
Die NoSQL-Datenbank [3 ] MongoDB [4 ] unterstützt solche sog. Geodaten-Abfragen [5 ] (also Suchen nach 2-dimensionalen Koordinatensätzen) out-of-the-box. Zum besseren Verständnis der folgenden Dinge empfehle ich diesen Artikel über Spring Data Mongo DB , der eine gute Einführung in MongoDB und das entsprechende Spring Data API gibt.
Planare Karten
Fangen wir mit einem einfachen Beispiel an, das aus vier Punkte in einer Ebene besteht. Die Einheiten des Koordinatensystems können beliebig interpretiert werden, z.B. als Kilometer, Meilen oder sonstwas.
Fügen wir diese Punkte in eine Collection namens location ein:
1C:\dev\bin\mongodb-2.0.2\bin>mongo 2MongoDB shell version: 2.0.2 3connecting to: test 4> db.createCollection("location") 5{ "ok" : 1 } 6> db.location.save( {_id: "A", position: [0.001, -0.002]} ) 7> db.location.save( {_id: "B", position: [1.0, 1.0]} ) 8> db.location.save( {_id: "C", position: [0.5, 0.5]} ) 9> db.location.save( {_id: "D", position: [-0.5, -0.5]} )
Zur Geodaten-Suche benötigen wir einen entsprechenden Index auf dem Array position:
1> db.location.ensureIndex( {position: "2d"} )
Das war’s schon. Nun können wir folgende Abfragen (blauer Kreis und rote Box aus der vorstehenden Abbildungen) mit Hilfe spezieller MongoDB Operatoren ausführen:
1> db.location.find( {position: { $near: [0,0], $maxDistance: 0.75 } } ) 2{ "_id" : "A", "position" : [ 0.001, -0.002 ] } 3{ "_id" : "D", "position" : [ -0.5, -0.5 ] } 4{ "_id" : "C", "position" : [ 0.5, 0.5 ] } 5> db.location.find( {position: { $within: { $box: [ [0.25, 0.25], [1.0,1.0] ] } } } ) 6{ "_id" : "C", "position" : [ 0.5, 0.5 ] } 7{ "_id" : "B", "position" : [ 1, 1 ] }
Versuchen Sie das mal mit Ihrer relationalen Datenbank ohne selbstdefinierte Typen und Funktionen!
Spring Data MongoDB API
Mit Spring Data MongoDB können genau diese Abfragen mit nur sehr wenig Code-Zeilen implementiert werden. Zunächst definieren wir ein POJO, dass einen Punkt in der Ebene repräsentiert:
1public class Location {
2
3 @Id private String id;
4
5 private double[] position;
6 ...
7}
Ein Repository mit unseren Queries sieht in etwa so aus:
1public interface LocationRepository extends MongoRepository<Location, String> { 2 3 List<Location> findByPositionWithin(Circle c); 4 5 List<Location> findByPositionWithin(Box b); 6}
Spring Data leitet zur Laufzeit eine passende Implementierung aus diesen Interface-Methoden ab. Die Klassen Circle, Point und Box sind Abstraktionen, die zum MongoDB API gehören.
1public class MongoDBGeoSpatialTest { 2 3 @Autowired LocationRepository repo; 4 5 @Autowired MongoTemplate template; 6 7 @Before public void setUp() { 8 // ensure geospatial index 9 template.indexOps(Location.class).ensureIndex( new GeospatialIndex("position") ); 10 // prepare data 11 repo.save( new Location("A", 0.001, -0.002) ); 12 repo.save( new Location("B", 1, 1) ); 13 repo.save( new Location("C", 0.5, 0.5) ); 14 repo.save( new Location("D", -0.5, -0.5) ); 15 } 16 17 @Test public void shouldFindAroundOrigin() { 18 // when 19 List<Location> locations = repo.findByPositionWithin( new Circle(0,0, 0.75) ); 20 21 // then 22 assertLocations( locations, "A", "C", "D" ); 23 } 24 25 @Test public void shouldFindWithinBox() { 26 // when 27 List<Location> locations = repo.findByPositionWithin( new Box( new Point(0.25, 0.25), new Point(1,1)) ); 28 29 // then 30 assertLocations( locations, "B", "C" ); 31 } 32 ...
Unsere Suchergebnisse über das Spring Data MongoDB API entsprechen denen, die wir auch über die Mongo Shell erreicht haben:
1Circle: 2A(0.001, -0.002) 3D(-0.500, -0.500) 4C(0.500, 0.500) 5 6Box: 7C(0.500, 0.500) 8B(1.000, 1.000)
Den vollständigen Quellcode dieses Beipiels gibt’s auf github . Am besten mit mongodb.MongoDBGeoSpatialTest anfangen.
Performance-Betrachtungen
MongoDB indiziert Geodaten sehr gut. Ich habe einen kleinen Vergleich zwischen Suchanfragen mit Kreis- und Rechtecksflächen gemacht. Bei der Suche über eine Rechtecksfläche habe ich schnellere Antwortzeiten erwartet (da man hier nur geschichkt die Koordinaten vergleichen muss, bei einer Umkreissuche aber Abstände berechnen muss) – dem war aber nicht so. Mein Testszenario sieht aus wie folgt:
- Lege 100.000 Punkte an mit zufälligen Koordinaten in
(-1,1) x (-1,1) - Führe 10.000 Suchanfragen aus an zufällig ausgewählten Punkten
(x,y)mit Koordinaten in(-1,1) x (-1,1)in einer- Kreisfläche mit Mittelpunkt
(x,y)und Radiusr = 0.1 - Rechtecksfläche mit Mittelpunkt
(x,y)undwidth = sqrt(pi) * r(die dann den gleichen Flächeninhalt wie der Kreis hat)
- Kreisfläche mit Mittelpunkt
Das sind die Ergebnisse:
| Circle | Box | |
|---|---|---|
| Durchschnittl. Zeit pro Suchanfrage [ms] | 47.6592 | 47.2629 |
| Durchschnittl. Treffer pro Suche | 750 | 749 |
Es gibt also praktisch keinen messbaren Unterschied. Das ist natürlich kein Beweis – aber ein guter Hinweis. Es zeigt sich auch, dass die Annäherung der Kreisfläche durch eine inhaltsgleiche Rechtecksfläche gut ist – zumindest ist die Anzahl der gefundenen Treffer in etwa gleich (wenn auch die Mengen der gefundenen Punkte nicht identisch sind). Aber mit MongoDB ist die Annäherung durch die Rechtsecksfläche überflüssig, weil die Kreissuche ähnlich performant ist!
Wer das ganze selbst bewerten will, sollte einen Blick auf diesen Unit-Test werfen: mongodb.MongoDBMassTest.
Spherische Karten
Das die Erde eine Kugel ist [6 ], ist das Arbeiten mit planaren Karten nur dann eine gute Annäherung, wenn hinreichend kleine Distanzen im Spiel sind. Darüber hinaus werden in der Regel Längen- und Breitengrade als Koordinaten verwendet, um einen Punkt auf dem Globus zu identifizieren, und Distanzen werden stets in Meilen oder Kilometern angegeben. Weiterhin variiert der Abstand zwischen zwei Längengraden in Abhängigkeit vom Breitengrad [7 ].
MongoDB berücksichtigt dies seit Version 1.8 und stellt spezielle Such-Operatoren für das spherische Modell zur Verfügung. Standardmäßig deckt das Interval für Geodaten-Indexe den Bereich von [-180,180) ab, da Breiten- und Längengrade diesen Wertebereich verwenden. Ein solches Koordinaten-Paar besteht in MongoDB aus [longitude, latitude], wobei die Reihenfolge wichtig ist.
Ich werde ein Beispiel mit dem Spring Data MongoDB vorstellen, da das API automagisch eine Skalierung hinsichtlich der Maßeinheiten Meilen und Kilometer vornimmt. In einem Low-Level MongoDB-Beispiel müsste diese Skalierung händisch vorgenommen werden. Unser Beispiel dreht sich um die folgenden Städte:
| Stadt | Länge | Breite |
|---|---|---|
| Berlin | 13.405838 | 52.531261 |
| Köln | 6.921272 | 50.960157 |
| Düsseldorf | 6.810036 | 51.224088 |
Die Koordinaten haben ich mit Hilfe von Google Maps [8 ] ermittelt. Wir fügen nun zu unserem Repository ein einzige(!) Zeile Code hinzu:
1List<Location> findByPositionNear(Point p, Distance d);
Da Düsseldorf und Köln recht nah beieinander liegen, liefert die folgende Suchanfrage …
1List<Location> locations = repo.findByPositionNear(DUS , new Distance(70, Metrics.KILOMETERS) );
… auch beide Städte. Ausschlaggebend ist die Verwendung des Enums Metrics. Der Wert KILOMETERS oder MILES löst intern folgendes aus:
- es wird der spherische Suchmodus verwendet
- es findet eine automatische Skalierung der Abstände gemäß der Maßeinheit statt
Wenn wir unsere Suche nun etwas ausweiten …
1List<Location> locations = repo.findByPositionNear(DUS , new Distance(350, Metrics.MILES) );
… finden wir auch alle drei Städte: Düsseldorf, Köln und Berlin. Dieses Beispiel gibt’s auch auf github.
Zusammenfassung
Ich habe gezeigt, wie einfach Geodaten und deren Abfrage in MongoDB sind. Mit Hilfe von Spring Data MongoDB wird diese Einfachheit in die Java-Welt übertragen. Wir haben mit einfachen planaren Karten gearbeitet, haben eine grobe Performance-Analyse geamcht und uns ebenso das realistischerere spherische Modell angeschaut.
Spring Data Project
Dies sind meine anderen Blog-Beiträge zum Spring Data-Projekt:
Teil 1: Spring Data Commons
Teil 2: Spring Data JPA
Teil 3: Spring Data Mongo DB
Referenzen
[1] Location-based service
[2] GIS – Geografisches Informationssystem
[3] NoSQL databases (engl.)
[4] MongoDB (engl.)
[5] MongoDB – Geospatial Indexing (engl.)
[6] Projections and Coordinate Systems (engl.)
[7] Längengrad
[8] Finding longitude and latitude on Google Maps (engl.)
War dieser Beitrag hilfreich?
Weitere Beiträge
von Tobias Trelle
17.12.2018 Dein Job bei codecentric?
Jobs
Agile Developer und Consultant (w/d/m)
Alle Standorte
Weitere Artikel in diesem Themenbereich
Entdecke spannende weiterführende Themen und lass dich von der codecentric Welt inspirieren.
Gemeinsam bessere Projekte umsetzen.
Wir helfen deinem Unternehmen.
Du stehst vor einer großen IT-Herausforderung? Wir sorgen für eine maßgeschneiderte Unterstützung. Informiere dich jetzt.
Hilf uns, noch besser zu werden.
Wir sind immer auf der Suche nach neuen Talenten. Auch für dich ist die passende Stelle dabei.
Blog-Autor*in
Tobias Trelle
Software Architect
Du hast noch Fragen zu diesem Thema? Dann sprich mich einfach an.
Du hast noch Fragen zu diesem Thema? Dann sprich mich einfach an.