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

More compact 2dsphere geo index format



    • Icon: Improvement Improvement
    • Resolution: Done
    • Icon: Major - P3 Major - P3
    • 3.1.6
    • None
    • Geo
    • None
    • Fully Compatible


      Currently, 2dsphere index is based on human readable string, because the order of string satisfies the requirement of index. However, its size can be about 4 times larger than using an unsigned 64-bit integer, at the finest level. With index versioning, we could implement a compact version of 2dsphere index.

      // An S2CellId is a 64-bit unsigned integer that uniquely identifies a
      // cell in the S2 cell decomposition.  It has the following format:
      //   id = [face][face_pos]
      //   face:     a 3-bit number (range 0..5) encoding the cube face.
      //   face_pos: a 61-bit number encoding the position of the center of this
      //             cell along the Hilbert curve over this face (see the Wiki
      //             pages for details).

      Since BSON doesn't support unsigned 64-bit integer, we have to work around this constraint. There are several possible solutions.
      1. Add / subtract a bias between signed and unsigned 64-bit integer, then use BSON signed 64-bit integer for indexing.
      2. The first 3 bits of S2CellId is for face. If we can guarantee the range search of index scan never crosses the boundary of faces, the range search will never cross 0, then two's complement representation guarantees the relative order in each face. static_cast<uint64_t> would be an option in this case.
      3. Use BSON binary type to encode S2CellId, like 2d index.
      4. Increase the finest level by one and shift S2CellId by two bits to make it fit in signed integer.




            kevin.albertson@mongodb.com Kevin Albertson
            siyuan.zhou@mongodb.com Siyuan Zhou
            0 Vote for this issue
            4 Start watching this issue