Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-20843

$geoIntersects performs poorly on polygons with lots of coordinates

    XMLWordPrintable

Details

    • Bug
    • Status: Backlog
    • Major - P3
    • Resolution: Unresolved
    • 3.0.6
    • None
    • Geo
    • ALL
    • Hide

      Import the attached database and run the query:

      db.PolygonDescription.find({
          $query: {
              geo: {
                  $geoIntersects: {
                      $geometry: {
                          type: "Point",
                          coordinates: [
                              10.5891,
                              49.77997
                          ]
                      }
                  }
              }
          },
          $explain: true
      },
      {
          _id: 1
      }) 
      

      Delete the last document (id=56179fa25495b1184924b03e) and rerun the query. You'll see a marginal speedup, by just removing this one document.

      Show
      Import the attached database and run the query: db.PolygonDescription.find({ $query: { geo: { $geoIntersects: { $geometry: { type: "Point", coordinates: [ 10.5891, 49.77997 ] } } } }, $explain: true }, { _id: 1 }) Delete the last document (id=56179fa25495b1184924b03e) and rerun the query. You'll see a marginal speedup, by just removing this one document.

    Description

      Test Environment: Windows 10 x64, MongoDB 3.0.6

      I have a very small database with 9999 Polygons (their coordinate consists of just 5 Points).

      Querying the set with geointersects (using a geosphere index) is fast, until I add one more polygon (which covers all others and has a large coordinate set > 130000 points).

      I'll add the mongoexport of my database.

      Explain without the last "huge" polygon:

      { 
          "queryPlanner" : {
              "plannerVersion" : NumberInt(1), 
              "namespace" : "test.PolygonDescription", 
              "indexFilterSet" : false, 
              "parsedQuery" : {
                  "geo" : {
                      "$geoIntersects" : {
                          "$geometry" : {
                              "type" : "Point", 
                              "coordinates" : [
                                  10.5891, 
                                  49.77997
                              ]
                          }
                      }
                  }
              }, 
              "winningPlan" : {
                  "stage" : "PROJECTION", 
                  "transformBy" : {
                      "_id" : NumberInt(1)
                  }, 
                  "inputStage" : {
                      "stage" : "FETCH", 
                      "filter" : {
                          "geo" : {
                              "$geoIntersects" : {
                                  "$geometry" : {
                                      "type" : "Point", 
                                      "coordinates" : [
                                          10.5891, 
                                          49.77997
                                      ]
                                  }
                              }
                          }
                      }, 
                      "inputStage" : {
                          "stage" : "IXSCAN", 
                          "keyPattern" : {
                              "geo" : "2dsphere"
                          }, 
                          "indexName" : "geo_2dsphere", 
                          "isMultiKey" : true, 
                          "isUnique" : false, 
                          "isSparse" : false, 
                          "isPartial" : false, 
                          "indexVersion" : NumberInt(1), 
                          "direction" : "forward", 
                          "indexBounds" : {
                              "geo" : [
                                  "[5116089176692883456, 5116089176692883456]", 
                                  "[5161758491664187392, 5161758491664187392]", 
                                  "[5161806870175809536, 5161806870175809536]", 
                                  "[5161807601393991680, 5161807601393991680]", 
                                  "[5161807601943445504, 5161807601943445504]", 
                                  "[5161807601946329088, 5161807601946329088]", 
                                  "[5161807601946525696, 5161807601946525696]", 
                                  "[5161807601946525697, 5161807601946558463]", 
                                  "[5161807601946591232, 5161807601946591232]", 
                                  "[5161807601947639808, 5161807601947639808]", 
                                  "[5161807601997971456, 5161807601997971456]", 
                                  "[5161807602199298048, 5161807602199298048]", 
                                  "[5161807604615217152, 5161807604615217152]", 
                                  "[5161807608910184448, 5161807608910184448]", 
                                  "[5161807626090053632, 5161807626090053632]", 
                                  "[5161807694809530368, 5161807694809530368]", 
                                  "[5161807969687437312, 5161807969687437312]", 
                                  "[5161811268222320640, 5161811268222320640]", 
                                  "[5161969597896720384, 5161969597896720384]", 
                                  "[5162251072873431040, 5162251072873431040]", 
                                  "[5165628772593958912, 5165628772593958912]", 
                                  "[5170132372221329408, 5170132372221329408]"
                              ]
                          }
                      }
                  }
              }, 
              "rejectedPlans" : [
       
              ]
          }, 
          "executionStats" : {
              "executionSuccess" : true, 
              "nReturned" : NumberInt(4), 
              "executionTimeMillis" : NumberInt(1), 
              "totalKeysExamined" : NumberInt(239), 
              "totalDocsExamined" : NumberInt(233), 
              "executionStages" : {
                  "stage" : "PROJECTION", 
                  "nReturned" : NumberInt(4), 
                  "executionTimeMillisEstimate" : NumberInt(0), 
                  "works" : NumberInt(240), 
                  "advanced" : NumberInt(4), 
                  "needTime" : NumberInt(235), 
                  "needYield" : NumberInt(0), 
                  "saveState" : NumberInt(1), 
                  "restoreState" : NumberInt(1), 
                  "isEOF" : NumberInt(1), 
                  "invalidates" : NumberInt(0), 
                  "transformBy" : {
                      "_id" : NumberInt(1)
                  }, 
                  "inputStage" : {
                      "stage" : "FETCH", 
                      "filter" : {
                          "geo" : {
                              "$geoIntersects" : {
                                  "$geometry" : {
                                      "type" : "Point", 
                                      "coordinates" : [
                                          10.5891, 
                                          49.77997
                                      ]
                                  }
                              }
                          }
                      }, 
                      "nReturned" : NumberInt(4), 
                      "executionTimeMillisEstimate" : NumberInt(0), 
                      "works" : NumberInt(240), 
                      "advanced" : NumberInt(4), 
                      "needTime" : NumberInt(235), 
                      "needYield" : NumberInt(0), 
                      "saveState" : NumberInt(1), 
                      "restoreState" : NumberInt(1), 
                      "isEOF" : NumberInt(1), 
                      "invalidates" : NumberInt(0), 
                      "docsExamined" : NumberInt(233), 
                      "alreadyHasObj" : NumberInt(0), 
                      "inputStage" : {
                          "stage" : "IXSCAN", 
                          "nReturned" : NumberInt(233), 
                          "executionTimeMillisEstimate" : NumberInt(0), 
                          "works" : NumberInt(240), 
                          "advanced" : NumberInt(233), 
                          "needTime" : NumberInt(6), 
                          "needYield" : NumberInt(0), 
                          "saveState" : NumberInt(1), 
                          "restoreState" : NumberInt(1), 
                          "isEOF" : NumberInt(1), 
                          "invalidates" : NumberInt(0), 
                          "keyPattern" : {
                              "geo" : "2dsphere"
                          }, 
                          "indexName" : "geo_2dsphere", 
                          "isMultiKey" : true, 
                          "isUnique" : false, 
                          "isSparse" : false, 
                          "isPartial" : false, 
                          "indexVersion" : NumberInt(1), 
                          "direction" : "forward", 
                          "indexBounds" : {
                              "geo" : [
                                  "[5116089176692883456, 5116089176692883456]", 
                                  "[5161758491664187392, 5161758491664187392]", 
                                  "[5161806870175809536, 5161806870175809536]", 
                                  "[5161807601393991680, 5161807601393991680]", 
                                  "[5161807601943445504, 5161807601943445504]", 
                                  "[5161807601946329088, 5161807601946329088]", 
                                  "[5161807601946525696, 5161807601946525696]", 
                                  "[5161807601946525697, 5161807601946558463]", 
                                  "[5161807601946591232, 5161807601946591232]", 
                                  "[5161807601947639808, 5161807601947639808]", 
                                  "[5161807601997971456, 5161807601997971456]", 
                                  "[5161807602199298048, 5161807602199298048]", 
                                  "[5161807604615217152, 5161807604615217152]", 
                                  "[5161807608910184448, 5161807608910184448]", 
                                  "[5161807626090053632, 5161807626090053632]", 
                                  "[5161807694809530368, 5161807694809530368]", 
                                  "[5161807969687437312, 5161807969687437312]", 
                                  "[5161811268222320640, 5161811268222320640]", 
                                  "[5161969597896720384, 5161969597896720384]", 
                                  "[5162251072873431040, 5162251072873431040]", 
                                  "[5165628772593958912, 5165628772593958912]", 
                                  "[5170132372221329408, 5170132372221329408]"
                              ]
                          }, 
                          "keysExamined" : NumberInt(239), 
                          "dupsTested" : NumberInt(233), 
                          "dupsDropped" : NumberInt(0), 
                          "seenInvalidated" : NumberInt(0)
                      }
                  }
              }, 
              "allPlansExecution" : [
       
              ]
          }
      }
      

      Explain with the 10000ths large polygon:

      { 
          "queryPlanner" : {
              "plannerVersion" : NumberInt(1), 
              "namespace" : "test.PolygonDescription", 
              "indexFilterSet" : false, 
              "parsedQuery" : {
                  "geo" : {
                      "$geoIntersects" : {
                          "$geometry" : {
                              "type" : "Point", 
                              "coordinates" : [
                                  10.5891, 
                                  49.77997
                              ]
                          }
                      }
                  }
              }, 
              "winningPlan" : {
                  "stage" : "PROJECTION", 
                  "transformBy" : {
                      "_id" : NumberInt(1)
                  }, 
                  "inputStage" : {
                      "stage" : "FETCH", 
                      "filter" : {
                          "geo" : {
                              "$geoIntersects" : {
                                  "$geometry" : {
                                      "type" : "Point", 
                                      "coordinates" : [
                                          10.5891, 
                                          49.77997
                                      ]
                                  }
                              }
                          }
                      }, 
                      "inputStage" : {
                          "stage" : "IXSCAN", 
                          "keyPattern" : {
                              "geo" : "2dsphere"
                          }, 
                          "indexName" : "geo_2dsphere", 
                          "isMultiKey" : true, 
                          "isUnique" : false, 
                          "isSparse" : false, 
                          "isPartial" : false, 
                          "indexVersion" : NumberInt(1), 
                          "direction" : "forward", 
                          "indexBounds" : {
                              "geo" : [
                                  "[5116089176692883456, 5116089176692883456]", 
                                  "[5161758491664187392, 5161758491664187392]", 
                                  "[5161806870175809536, 5161806870175809536]", 
                                  "[5161807601393991680, 5161807601393991680]", 
                                  "[5161807601943445504, 5161807601943445504]", 
                                  "[5161807601946329088, 5161807601946329088]", 
                                  "[5161807601946525696, 5161807601946525696]", 
                                  "[5161807601946525697, 5161807601946558463]", 
                                  "[5161807601946591232, 5161807601946591232]", 
                                  "[5161807601947639808, 5161807601947639808]", 
                                  "[5161807601997971456, 5161807601997971456]", 
                                  "[5161807602199298048, 5161807602199298048]", 
                                  "[5161807604615217152, 5161807604615217152]", 
                                  "[5161807608910184448, 5161807608910184448]", 
                                  "[5161807626090053632, 5161807626090053632]", 
                                  "[5161807694809530368, 5161807694809530368]", 
                                  "[5161807969687437312, 5161807969687437312]", 
                                  "[5161811268222320640, 5161811268222320640]", 
                                  "[5161969597896720384, 5161969597896720384]", 
                                  "[5162251072873431040, 5162251072873431040]", 
                                  "[5165628772593958912, 5165628772593958912]", 
                                  "[5170132372221329408, 5170132372221329408]"
                              ]
                          }
                      }
                  }
              }, 
              "rejectedPlans" : [
       
              ]
          }, 
          "executionStats" : {
              "executionSuccess" : true, 
              "nReturned" : NumberInt(5), 
              "executionTimeMillis" : NumberInt(87), 
              "totalKeysExamined" : NumberInt(241), 
              "totalDocsExamined" : NumberInt(234), 
              "executionStages" : {
                  "stage" : "PROJECTION", 
                  "nReturned" : NumberInt(5), 
                  "executionTimeMillisEstimate" : NumberInt(80), 
                  "works" : NumberInt(241), 
                  "advanced" : NumberInt(5), 
                  "needTime" : NumberInt(235), 
                  "needYield" : NumberInt(0), 
                  "saveState" : NumberInt(2), 
                  "restoreState" : NumberInt(2), 
                  "isEOF" : NumberInt(1), 
                  "invalidates" : NumberInt(0), 
                  "transformBy" : {
                      "_id" : NumberInt(1)
                  }, 
                  "inputStage" : {
                      "stage" : "FETCH", 
                      "filter" : {
                          "geo" : {
                              "$geoIntersects" : {
                                  "$geometry" : {
                                      "type" : "Point", 
                                      "coordinates" : [
                                          10.5891, 
                                          49.77997
                                      ]
                                  }
                              }
                          }
                      }, 
                      "nReturned" : NumberInt(5), 
                      "executionTimeMillisEstimate" : NumberInt(80), 
                      "works" : NumberInt(241), 
                      "advanced" : NumberInt(5), 
                      "needTime" : NumberInt(235), 
                      "needYield" : NumberInt(0), 
                      "saveState" : NumberInt(2), 
                      "restoreState" : NumberInt(2), 
                      "isEOF" : NumberInt(1), 
                      "invalidates" : NumberInt(0), 
                      "docsExamined" : NumberInt(234), 
                      "alreadyHasObj" : NumberInt(0), 
                      "inputStage" : {
                          "stage" : "IXSCAN", 
                          "nReturned" : NumberInt(234), 
                          "executionTimeMillisEstimate" : NumberInt(0), 
                          "works" : NumberInt(241), 
                          "advanced" : NumberInt(234), 
                          "needTime" : NumberInt(6), 
                          "needYield" : NumberInt(0), 
                          "saveState" : NumberInt(2), 
                          "restoreState" : NumberInt(2), 
                          "isEOF" : NumberInt(1), 
                          "invalidates" : NumberInt(0), 
                          "keyPattern" : {
                              "geo" : "2dsphere"
                          }, 
                          "indexName" : "geo_2dsphere", 
                          "isMultiKey" : true, 
                          "isUnique" : false, 
                          "isSparse" : false, 
                          "isPartial" : false, 
                          "indexVersion" : NumberInt(1), 
                          "direction" : "forward", 
                          "indexBounds" : {
                              "geo" : [
                                  "[5116089176692883456, 5116089176692883456]", 
                                  "[5161758491664187392, 5161758491664187392]", 
                                  "[5161806870175809536, 5161806870175809536]", 
                                  "[5161807601393991680, 5161807601393991680]", 
                                  "[5161807601943445504, 5161807601943445504]", 
                                  "[5161807601946329088, 5161807601946329088]", 
                                  "[5161807601946525696, 5161807601946525696]", 
                                  "[5161807601946525697, 5161807601946558463]", 
                                  "[5161807601946591232, 5161807601946591232]", 
                                  "[5161807601947639808, 5161807601947639808]", 
                                  "[5161807601997971456, 5161807601997971456]", 
                                  "[5161807602199298048, 5161807602199298048]", 
                                  "[5161807604615217152, 5161807604615217152]", 
                                  "[5161807608910184448, 5161807608910184448]", 
                                  "[5161807626090053632, 5161807626090053632]", 
                                  "[5161807694809530368, 5161807694809530368]", 
                                  "[5161807969687437312, 5161807969687437312]", 
                                  "[5161811268222320640, 5161811268222320640]", 
                                  "[5161969597896720384, 5161969597896720384]", 
                                  "[5162251072873431040, 5162251072873431040]", 
                                  "[5165628772593958912, 5165628772593958912]", 
                                  "[5170132372221329408, 5170132372221329408]"
                              ]
                          }, 
                          "keysExamined" : NumberInt(241), 
                          "dupsTested" : NumberInt(234), 
                          "dupsDropped" : NumberInt(0), 
                          "seenInvalidated" : NumberInt(0)
                      }
                  }
              }, 
              "allPlansExecution" : [
       
              ]
          }
      }
      

      Attachments

        1. polygonabstracted.png
          polygonabstracted.png
          68 kB
        2. polygondescription.zip
          1.23 MB

        Issue Links

          Activity

            People

              backlog-query-execution Backlog - Query Execution
              camak Casoa Makaso
              Votes:
              6 Vote for this issue
              Watchers:
              23 Start watching this issue

              Dates

                Created:
                Updated: