[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: File linux-desktop-278-vs-264.svg     File linux-desktop-278-vs-277.svg    
Issue Links:
Related
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. SERVER-15576 improves its performance by 20%.


Original Title
Geo $near with 2d index query performance issue with 2.7.8-pre-

Original Description

When comparing performance of 2.7.8-pre vs 2.7.7, following query is 30-40% slower.

find({loc: {$near: [x, y]}}).limit(100)

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: SERVER-15562 Search neighbors for density estimation with 2d index
Branch: master
https://github.com/mongodb/mongo/commit/f5090f81588b684fc3cd27200ae6a822f16c37ae

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: SERVER-15562 Estimate density before near search
Branch: master
https://github.com/mongodb/mongo/commit/385f03dc7205ef60bbb9cb8b475afd9c802bc67d

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