2016/1/18

Geospatial Index in MongoDB

MongoDB 自 2.6 版開始就支援儲存座標點的欄位,並能為該欄位建立 Geospatial Indexes,提供使用者快速搜尋附近的座標點資料的資料查詢功能。例如最簡單的應用:找到我附近的夥伴或是找到家裡附近的餐廳。


座標點 [longitude, latitude]


座標點的資料是兩個浮點數字組成的,先寫 longitude 經度,再寫 latitude 緯度,在思考座標點資料時,必須要用平面座標來看,原點在正中央,x軸往右為正數,y軸往上為正數,這跟跟矩陣的元素表示方法不同,先列後行。


[longitude, latitude]

基本 2d 平面查詢


要測試最基本的平面查詢,我們先產生 100 個座標點的測試資料,其實座標點資料就只是單純的兩個數字而已,重要的是,在建立 index 時,要指定用 2d 的 index:


db.ex.drop()
for( var i=0; i<100; i++ ) {
    db.ex.insert({pos:[i%10, Math.floor(i/10)]})
}

db.ex.ensureIndex({pos:"2d"})

用 $near 查詢時,回傳的資料點會依照距離遠近的順序傳送回來。


> db.ex.find({pos:{$near:[5,5]}})
{ "_id" : ObjectId("565e634fbd3fd37d48c0a691"), "pos" : [ 5, 5 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a690"), "pos" : [ 4, 5 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a69b"), "pos" : [ 5, 6 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a687"), "pos" : [ 5, 4 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a692"), "pos" : [ 6, 5 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a686"), "pos" : [ 4, 4 ] }
.....

以下這個圖形將所有座標點都以一個圓點表示,原點[0,0]位於左下角。


以下是有距離範圍的查詢,但回傳的資料點,並不保證依照距離由小到大排列


position:{$within:[$center, $box, $ploygon, $centerSphere]}

首先是 $center 的測試,我們測試一個半徑為 2 的圓形涵蓋的範圍:


> db.ex.find( {pos:{$within:{$center:[[5,5],2]}}} , {_id:0} )
{ "pos" : [ 4, 4 ] }
{ "pos" : [ 3, 5 ] }
{ "pos" : [ 4, 5 ] }
{ "pos" : [ 5, 3 ] }
{ "pos" : [ 5, 4 ] }
{ "pos" : [ 5, 5 ] }
{ "pos" : [ 4, 6 ] }
{ "pos" : [ 5, 6 ] }
{ "pos" : [ 5, 7 ] }
{ "pos" : [ 6, 4 ] }
{ "pos" : [ 6, 5 ] }
{ "pos" : [ 7, 5 ] }
{ "pos" : [ 6, 6 ] }


$box 是一個矩形


> db.ex.find( {pos:{$within:{$box:[[5,5],[6,6]]}}} , {_id:0} )
{ "pos" : [ 5, 5 ] }
{ "pos" : [ 5, 6 ] }
{ "pos" : [ 6, 5 ] }
{ "pos" : [ 6, 6 ] }


$polygon 則是一個多邊形


> db.ex.find( {pos:{$within:{$polygon:[[3,4],[5,7], [7,3]]}}} , {_id:0} )
{ "pos" : [ 3, 4 ] }
{ "pos" : [ 4, 4 ] }
{ "pos" : [ 4, 5 ] }
{ "pos" : [ 5, 4 ] }
{ "pos" : [ 5, 5 ] }
{ "pos" : [ 5, 6 ] }
{ "pos" : [ 5, 7 ] }
{ "pos" : [ 6, 4 ] }
{ "pos" : [ 7, 3 ] }
{ "pos" : [ 6, 5 ] }


Geospatial Indexes


剛剛的 2d 查詢,看起來還蠻簡單的,但 MongoDB 的 Geospatial Indexes 不光只支援這個功能而已。


MongoDB 支援兩種平面的模型 surface type
1. Spherical: 2dsphere index
座標點是放在像地球一樣的球面上,由於是球面的關係,距離跟相對關係的計算,跟一般的平面座標是不同的
2. Flat: 2d index
傳統的平面座標


如果是一般的 2d index,座標點的儲存只支援 legacy coordinate pairs的表示方式,也就是 [x,y],前面是 longitude 經度,後面是 latitude 緯度。


但如果是 2dsphere index,除了支援 legacy coordinate pairs 的資料外,還可以用 GeoJSON object 的表示方式儲存,預設是以 WGS84 datum,也就是 Degrees, Minutes, Seconds 的地理位置表示方式。


WGS 84 座標點表示系統有五種,可以用 PGC Coordinate Converter 進行轉換的計算,比較常見的有兩種 DMS 及 DD,但要注意的是 GeoJSON 預設是先寫緯度,再寫經度,但 MongoDB 卻是前面是 longitude 經度,後面是 latitude 緯度。


  1. DMS (Degrees, Minutes, Seconds)
    ex: 24° 15' 28.0800" N, 120° 53' 36.6000" E
  2. DD (Decimal Degrees)
    ex: 24.2578, 120.8935

GeoJSON 是以 JSON 表示地理資料結構的格式,由兩個部份組成:


  1. type:
    有以下這些類型 Point, LineString, Polygon, MultiPoint, MultiLineString, and MultiPolygon, GeometryCollection

  2. coordinates
    是這個類型資料的座標點的集合


我們可以透過 http://geojsonlint.com/ 測試 GeoJSON,並將結果顯示在地圖上。


// Point
{
  "type": "Point",
  "coordinates": [
    120.8935,  
    24.2578 
  ]
}

// LineString
{
  "type": "LineString",
  "coordinates": [
    [120.7000,24.2000],
    [120.6900,24.1900],
    [120.6815,24.1833],
    [120.5900,24.1500]
  ]
}


透過 GeoJSON Editor 用線跟多邊形,把文心森林公園框起來:


{
  "type" : "GeometryCollection",
  "geometries" : [
    {
      "type" : "Polygon",
      "coordinates": [
          [
            [
              120.64390238374472,
              24.146822125175643
            ],
            [
              120.64660605043173,
              24.146743804632557
            ],
            [
              120.64653094857931,
              24.14385570109112
            ],
            [
              120.64319428056479,
              24.144188570589225
            ],
            [
              120.64390238374472,
              24.146822125175643
            ]
          ]
        ]
    },
    {
      "type" : "LineString",
      "coordinates": [
          [
            120.64390238374472,
            24.14681233511038
          ],
          [
            120.64656313508749,
            24.146753594703075
          ],
          [
            120.64652021974325,
            24.14385570109112
          ],
          [
            120.64322646707296,
            24.144188570589225
          ],
          [
            120.64390238374472,
            24.14681233511038
          ]
        ]
     }
  ]
}


geospatial query operators


geospatial index 有兩種,geospatial index 不能當作 shard key index,而且在 sharded collection 中,不能使用 $near, $nearSphere,可以用 $geoNear aggregation 取代。


  • 2d
    支援平面幾何的計算
    legacy coordinate pairs [longitude, latitude]

  • 2dsphere
    支援球面的計算
    可儲存 GeoJSON 或是 legacy coordinate pairs


MongoDB 的 Query Selectors 有以下這4種


  1. $geoWithin
    Inclusion
    在 GeoJSON geomerty 的裡面的圖形,2d 及 2dsphere indexes 都有支援

  2. $geoIntersects
    Intersect
    跟 GeoJSON geomerty 的相交的圖形, 只有 2dsphere index 支援

  3. $near
    Proximity
    接近某個點的 geospatial objects,2d 及 2dsphere indexes 都有支援

  4. $nearSphere
    Proximity
    在球面上,接近某個點的 geospatial objects,2d 及 2dsphere 都支援


Geometry Specifiers 有以下這幾種


  1. $geometry
    以 GeoJSON 格式指定的 geometry
  2. $minDistance
    最短距離,用在 $near, $nearSphere,只能用在 2dsphere index
  3. $maxDistance
    最長距離,用在 $near, $nearSphere, 2d 及 2dsphere 都支援
  4. $center
    圓形,用在 $geoWithin queries 裡面, 2d 支援
  5. $centerSphere
    圓形,用在 $geoWithin queries 裡面,可用 [x,y] 或 GeoJSON 格式,2d 及 2dsphere 都支援
  6. $box
    矩形,用在 $geoWithin queries 裡面, 2d 支援
  7. $polygon
    用 [x,y] 描述的多邊形,用在 $geoWithin queries 裡面, 2d 支援

References


Geospatial Indexes and Queries
Geospatial Index Tutorials
Geospatial Indexing with MongoDB Presentation


如何基於mongodb來實現用戶當前位置距離顯示順序功能


MongoDB – Geospatial Queries


Spring Data – Part 4: Geospatial Queries with MongoDB