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:

C:\dev\bin\mongodb-2.0.2\bin>mongo
MongoDB shell version: 2.0.2
connecting to: test
> db.createCollection("location")
{ "ok" : 1 }
> db.location.save( {_id: "A", position: [0.001, -0.002]} )
> db.location.save( {_id: "B", position: [1.0, 1.0]} )
> db.location.save( {_id: "C", position: [0.5, 0.5]} )
> db.location.save( {_id: "D", position: [-0.5, -0.5]} )

Zur Geodaten-Suche benötigen wir einen entsprechenden Index auf dem Array position:

> 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:

> db.location.find( {position: { $near: [0,0], $maxDistance: 0.75  } } )
{ "_id" : "A", "position" : [ 0.001, -0.002 ] }
{ "_id" : "D", "position" : [ -0.5, -0.5 ] }
{ "_id" : "C", "position" : [ 0.5, 0.5 ] }
> db.location.find( {position: { $within: { $box: [ [0.25, 0.25], [1.0,1.0] ] }  } } )
{ "_id" : "C", "position" : [ 0.5, 0.5 ] }
{ "_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:

public class Location {
 
   @Id private String id;
 
   private double[] position;
   ...
}

Ein Repository mit unseren Queries sieht in etwa so aus:

public interface LocationRepository extends MongoRepository<Location, String> {
 
   List<Location> findByPositionWithin(Circle c);
 
   List<Location> findByPositionWithin(Box b);
}

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.

public class MongoDBGeoSpatialTest {
 
  @Autowired LocationRepository repo;
 
  @Autowired MongoTemplate template;
 
  @Before public void setUp() {
    // ensure geospatial index
    template.indexOps(Location.class).ensureIndex( new GeospatialIndex("position") );
    // prepare data
    repo.save( new Location("A", 0.001, -0.002) );
    repo.save( new Location("B", 1, 1) );
    repo.save( new Location("C", 0.5, 0.5) );
    repo.save( new Location("D", -0.5, -0.5) );
  }
 
  @Test public void shouldFindAroundOrigin() {
    // when
    List<Location> locations = repo.findByPositionWithin( new Circle(0,0, 0.75) );
 
    // then
    assertLocations( locations, "A", "C", "D" );
  }
 
  @Test public void shouldFindWithinBox() {
    // when
    List<Location> locations = repo.findByPositionWithin( new Box( new Point(0.25, 0.25), new Point(1,1)) );
 
    // then
    assertLocations( locations, "B", "C" );
  }
  ...

Unsere Suchergebnisse über das Spring Data MongoDB API entsprechen denen, die wir auch über die Mongo Shell erreicht haben:

Circle:
A(0.001, -0.002)
D(-0.500, -0.500)
C(0.500, 0.500)
 
Box:
C(0.500, 0.500)
B(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:

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:

Die Koordinaten haben ich mit Hilfe von Google Maps [8] ermittelt. Wir fügen nun zu unserem Repository ein einzige(!) Zeile Code hinzu:

   List<Location> findByPositionNear(Point p, Distance d);

Da Düsseldorf und Köln recht nah beieinander liegen, liefert die folgende Suchanfrage ...

   List<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 ...

   List<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.)