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

Estimate density before $near search

    XMLWordPrintableJSON

Details

    • Icon: Bug Bug
    • Resolution: Done
    • Icon: Major - P3 Major - P3
    • 2.8.0-rc0
    • 2.7.8
    • Geo
    • Fully Compatible
    • ALL

    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.

      Attachments

        1. linux-desktop-278-vs-264.svg
          146 kB
        2. linux-desktop-278-vs-277.svg
          145 kB

        Activity

          People

            siyuan.zhou@mongodb.com Siyuan Zhou
            rui.zhang Rui Zhang (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: