[SERVER-15562] Estimate density before $near search Created: 08/Oct/14 Updated: 19/Nov/14 Resolved: 30/Oct/14 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Geo |
| Affects Version/s: | 2.7.8 |
| Fix Version/s: | 2.8.0-rc0 |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | Rui Zhang (Inactive) | Assignee: | Siyuan Zhou |
| Resolution: | Done | Votes: | 0 |
| Labels: | 28qa | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Attachments: |
|
||||
| Issue Links: |
|
||||
| Backwards Compatibility: | Fully Compatible | ||||
| Operating System: | ALL | ||||
| Participants: | |||||
| Description |
|
Find the nearest point using $near with 2d index is slow in 2.7.8-pre- because we start from a small circle to search the documents, however that circle is proportional to the finest index level to guarantee we don't return too many on the first try. If the data is sparse, it takes several rounds to find the first document by expending the searching area exponentially. We can make it better by looking for the nearest document in its ancestor cell before the first search. Usually, this will give us a good estimate of the density. In S2, we look for such nearest document in the neighbors of closest vertex to this cell at coarser level. Find the nearest 100 points using $near with 2d index is slow because of the slowness in hashing function. Original Title Original Description When comparing performance of 2.7.8-pre vs 2.7.7, following query is 30-40% slower.
index is 2d geo index. please see attached svg for details. |
| Comments |
| Comment by Githook User [ 30/Oct/14 ] |
|
Author: {u'username': u'visualzhou', u'name': u'Siyuan Zhou', u'email': u'siyuan.zhou@mongodb.com'}Message: |
| Comment by Githook User [ 28/Oct/14 ] |
|
Author: {u'username': u'visualzhou', u'name': u'Siyuan Zhou', u'email': u'siyuan.zhou@mongodb.com'}Message: |