[SERVER-19072] More compact 2dsphere geo index format Created: 22/Jun/15  Updated: 05/Feb/16  Resolved: 20/Jul/15

Status: Closed
Project: Core Server
Component/s: Geo
Affects Version/s: None
Fix Version/s: 3.1.6

Type: Improvement Priority: Major - P3
Reporter: Siyuan Zhou Assignee: Kevin Albertson
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
depends on SERVER-19097 New geo index version for geo perform... Closed
Related
related to SERVER-18921 Index 2DSphere points at finest level Closed
Backwards Compatibility: Fully Compatible
Participants:

 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.



 Comments   
Comment by Githook User [ 17/Jul/15 ]

Author:

{u'username': u'kevinAlbs', u'name': u'Kevin Albertson', u'email': u'kevin.albertson@10gen.com'}

Message: SERVER-19072 Make S2 index keys numeric
Branch: master
https://github.com/mongodb/mongo/commit/f4d695fcf382820c7ea082bd4b1beb84e15cf2c5

Generated at Thu Feb 08 03:49:44 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.