Brandon Zhang and Kevin Albertson
Geospatial Performance Improvements in MongoDB 3.2
MongoDB supports geospatial data and specialized indexes that make building applications with geospatial features easy and scalable. One of the most popular features, the $geoNear operator, returns documents in order, from nearest to farthest with respect to a given point. To avoid sorting the entire collection in one go, the $geoNear algorithm iteratively expands its search in distance intervals (the red annulus shown below), aiming to have a few hundred documents per interval. Searching all documents in an interval is accomplished by finding an index cell covering (the set of grey index cells shown below). This covering ensures that all of the documents in the interval can be found using an index scan. The documents in the covering but not in the interval are filtered out afterwards. After all of the documents in an interval are found, they are sorted and returned.