[SERVER-26492] 2dsphere geoNear density estimator should stop once it exceeds $maxDistance Created: 05/Oct/16  Updated: 07/Dec/16  Resolved: 16/Nov/16

Status: Closed
Project: Core Server
Component/s: Geo, Querying
Affects Version/s: 3.0.12, 3.2.10
Fix Version/s: 3.2.12, 3.4.0-rc4

Type: Improvement Priority: Major - P3
Reporter: David Storch Assignee: David Storch
Resolution: Done Votes: 3
Labels: code-only
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-26518 Include density estimator in geoNear ... Backlog
Backwards Compatibility: Fully Compatible
Backport Completed:
Sprint: Query 2016-11-21
Participants:
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.



 Comments   
Comment by Githook User [ 22/Nov/16 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-26492 terminate density estimation after exceeding $maxDistance

(cherry picked from commit c361d2b09242c150bd84576816d5337352fcbf55)
Branch: v3.2
https://github.com/mongodb/mongo/commit/8f970ad08cbe4ced44264fc913ba27eac420873a

Comment by David Storch [ 16/Nov/16 ]

This is now fixed for 3.4.0-rc4 in the master branch with the following commit. (It appears that our automated hook for posting commit comments failed due to transient problems with github availability.)

https://github.com/mongodb/mongo/commit/c361d2b09242c150bd84576816d5337352fcbf55

We are currently in the process of releasing 3.2.11, which includes several important fixes, and cannot make further changes on the v3.2 branch. Therefore, this fix is now approved and targeted for 3.2.12. Approval for backport to the v3.0 branch is pending.

Comment by Githook User [ 15/Nov/16 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: Revert "SERVER-26492 terminate density estimation after exceeding $maxDistance"

This reverts commit be3535a26e9c0d09ccf3ec5de0fd26ac48a3a6ff.
Branch: v3.2
https://github.com/mongodb/mongo/commit/64b274e02c63ace15bd60cd47c754967339c586a

Comment by Githook User [ 15/Nov/16 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: Revert "SERVER-26492 terminate density estimation after exceeding $maxDistance"

This reverts commit 1323228230603455daceafb0dc52f15be5363e99.
Branch: master
https://github.com/mongodb/mongo/commit/bed166fa1fe6070669fce5e7a9934f8c05ce562a

Comment by David Storch [ 15/Nov/16 ]

I'm re-opening this ticket and reverting on both the master and 3.2 branches, since our continuous integration testing has discovered an issue with the patch. Work on a new patch is in progress.

Comment by Githook User [ 14/Nov/16 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-26492 terminate density estimation after exceeding $maxDistance

(cherry picked from commit 1323228230603455daceafb0dc52f15be5363e99)
Branch: v3.2
https://github.com/mongodb/mongo/commit/be3535a26e9c0d09ccf3ec5de0fd26ac48a3a6ff

Comment by Githook User [ 11/Nov/16 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-26492 terminate density estimation after exceeding $maxDistance
Branch: master
https://github.com/mongodb/mongo/commit/1323228230603455daceafb0dc52f15be5363e99

Comment by Daniel Pasette (Inactive) [ 01/Nov/16 ]

Hi girak, we understand the issue and are planning to work on this issue in the current sprint. Backports can only be made once we have a fix in place in master, but I've explicitly marked this issue as requested for backport.

Comment by Justin Leung [ 31/Oct/16 ]

Hi @david.storch is there a reason why this critical bug fix is not being backported to both versions 3.0 and 3.2?
As the density estimator bug went off to scan the whole set, it's going to push the mongod to run OOM possibly and crash.

Comment by David Storch [ 19/Oct/16 ]

Density estimation was added as a performance optimization during development for 3.0: see SERVER-15562. Therefore, this problem does not affect 2.6.x or earlier versions.

Generated at Thu Feb 08 04:12:19 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.