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

More compact 2dsphere geo index format

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.1.6
    • Component/s: Geo
    • Labels:
      None
    • Backwards Compatibility:
      Fully Compatible

      Description

      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.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              kevin.albertson Kevin Albertson
              Reporter:
              siyuan.zhou Siyuan Zhou
              Participants:
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: