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

Floating-point inaccuracy when unhashing GeoHash to box

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • 2.7.8
    • Affects Version/s: 2.7.7
    • Component/s: Geo
    • None
    • Fully Compatible
    • ALL

      Assume P is the lower left corner of a geohash. We hash and unhash the point in the following way.

      // hash
      h = hash(p) = (p - min) / scale
      // h.x and h.y should be integers with a rounding error.
      
      // unhash
      p_approx = h * scale + min
      

      Due to the floating-point accuracy, p != p_approx. As a result, it is possible that the box unhash(hash(p)) doesn't contain p. The following script gives an example.

      db.geo_precision.drop();
      
      db.geo_precision.insert({loc: [-7201198.6497758823, 0.10000000000000001]});
      var min = [ -7201198.65, 0.095 ];
      var max = [ -7201198.64977588, 0.11 ];
      // The document lives in the box defined by min and max.
      assert.eq(1, db.geo_precision.find({loc: {$within: {$box: [min, max]}}}).count());
      
      // 2d index should return the same result. But failed with 2.7.7.
      db.geo_precision.ensureIndex({loc: "2d"}, {min: -100000000.3, max: 100000000.3, bits: 32});
      assert.eq(1, db.geo_precision.find({loc: {$within: {$box: [min, max]}}}).count());
      

      In the above example, the point is outside the box of its geohash, so with a carefully constructed query, the covering of the query contains that document but doesn't intersect with the box of geohash. Thus the covering will exclude the GeoHash that contains the document and return no documents.

      To guarantee the point is alway contained by the box of its GeoHash, we should expand the box by a small error bound when unhashing geohash to box. Since the unhashed boxes are only used by the following the functions, expanding the box will keep the same contract.

      // Return true if we are confident that this region contains the box.
      R2Region::fastContains(const Box& other);
      // Return true if we are confident that this region disjoints with the box.
      R2Region::fastDisjoint(const Box& other);
      

      This regression bug is introduced by the covering of 2d shapes in 2.7.

            Assignee:
            siyuan.zhou@mongodb.com Siyuan Zhou
            Reporter:
            siyuan.zhou@mongodb.com Siyuan Zhou
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated:
              Resolved: