S2 sometimes returns empty coverings

XMLWordPrintableJSON

    • Type: Bug
    • Resolution: Done
    • Priority: Major - P3
    • None
    • Affects Version/s: 3.0.4
    • Component/s: Geo
    • Query
    • ALL
    • Hide

      To see the effects of this, you can run the following:

      db.phantom.insert({loc: {type: "Point", coordinates: [106.6331,10.7395]}})
db.phantom.createIndex({loc: "2dsphere"}, {coarsestIndexedLevel: 26, finestIndexedLevel: 30})
// returns nothing
db.phantom.find({loc: {$near: {$geometry: {type:"Point", coordinates:[106.6331,10.7395]}, $maxDistance:.05}}})
// but with *smaller* maxDistance, we get our point back
db.phantom.find({loc: {$near: {$geometry: {type:"Point", coordinates:[106.6331,10.7395]}, $maxDistance:.001}}})

      Additionally, attached is a patch including a unit test to reproduce this bug with just the S2 functions. Compile it with:
      scons -j4 build/opt/mongo/db/geo/s2_covering_test
      Run with:
      build/opt/mongo/db/geo/s2_covering_test

      Show
      To see the effects of this, you can run the following: db.phantom.insert({loc: {type: "Point" , coordinates: [106.6331,10.7395]}}) db.phantom.createIndex({loc: "2dsphere" }, {coarsestIndexedLevel: 26, finestIndexedLevel: 30}) // returns nothing db.phantom.find({loc: {$near: {$geometry: {type: "Point" , coordinates:[106.6331,10.7395]}, $maxDistance:.05}}}) // but with *smaller* maxDistance, we get our point back db.phantom.find({loc: {$near: {$geometry: {type: "Point" , coordinates:[106.6331,10.7395]}, $maxDistance:.001}}}) Additionally, attached is a patch including a unit test to reproduce this bug with just the S2 functions. Compile it with: scons -j4 build/opt/mongo/db/geo/s2_covering_test Run with: build/opt/mongo/db/geo/s2_covering_test
    • None
    • None
    • None
    • None
    • None
    • None
    • None

      Some very specific $near queries with small (but not negligible) $maxDistance values will unexpectedly return empty results. So far this can only be reproduced in the shell by manually setting the coarsestIndexedLevel and finestIndexedLevel.

      Ultimately, this is caused by S2 returning empty coverings for S2Cap regions. The root of this problem seems to be caused by floating point error in the S2Cap::Contains method.

      For a full S2Cap (entire sphere) S2Cap::Contains will return false on some points along/near the negative axis. The expected behavior is to return true for any point or geometry, since it is the full sphere.

        1. s2_covering_unit_test.patch
          5 kB

            Assignee:
            Backlog - Query Team (Inactive)
            Reporter:
            Kevin Albertson
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: