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

2dsphere geoNear density estimator should stop once it exceeds $maxDistance

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: 3.0.12, 3.2.10
    • Fix Version/s: 3.2.12, 3.4.0-rc4
    • Component/s: Geo, Querying
    • Labels:
    • Backwards Compatibility:
      Fully Compatible
    • Backport Completed:
    • Sprint:
      Query 2016-11-21
    • Case:
    • Linked BF Score:
      0

      Description

      The GeoNear2DSphereStage::DensityEstimator implements a process to calculate the radius for the geoNear search annuli. See "Background on density estimator" below for some further information on this. The density estimator, however, is willing to search areas which entirely contain the $maxDistance. Rather than continuing to search larger and larger areas beyond the max radius, density estimation should stop as soon as its search area exceeds the max. This should prevent the system from wasting work doing unnecessary density estimation.

      Background on density estimator

      First I'd like to explain the density estimator in more detail. 2dsphere geo hashes represent cells on the Earth's surface at varying granularities, on a spectrum from fine to coarse. The density estimator begins by choosing an initial granularity level, which should be relatively fine. At this initial level, it finds the cell which contains the starting point. It then finds the vertex of this cell which is closest to the geoNear starting point and the three neighboring cells at the same granularity level which share the vertex. Then, we construct an index scan which determines whether there is any matching data inside the four cells.

      If we find at least one matching document, the granularity is used to compute the radius increment which we will use to determine the size of the geoNear search annuli. On the other hand, if no matching documents are found, then we step up to the next coarsest level of granularity. This process continues iteratively until we either find a document, or we reach the coarsest possible granularity.

        Attachments

          Issue Links

            Activity

              People

              • Votes:
                3 Vote for this issue
                Watchers:
                15 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: