Beliebte Suchanfragen

Cloud Native

DevOps

IT-Security

Agile Methoden

Java

|
//

Spring Data – Teil 4: Geodaten-Suche mit MongoDB

15.3.2012 | 6 Minuten Lesezeit

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:

  1. Lege 100.000 Punkte an mit zufälligen Koordinaten in (-1,1) x (-1,1)
  2. 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 Radius r = 0.1
    • Rechtecksfläche mit Mittelpunkt (x,y) und width = sqrt(pi) * r (die dann den gleichen Flächeninhalt wie der Kreis hat)

Das sind die Ergebnisse:

CircleBox
Durchschnittl. Zeit pro Suchanfrage [ms]47.659247.2629
Durchschnittl. Treffer pro Suche750749

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:

StadtLängeBreite
Berlin13.40583852.531261
Köln6.92127250.960157
Düsseldorf6.81003651.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.)

|

Beitrag teilen

Gefällt mir

0

//

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.