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

Should use wildcard index for descending sort with limit

    XMLWordPrintableJSON

Details

    • Icon: Improvement Improvement
    • Resolution: Won't Fix
    • Icon: Major - P3 Major - P3
    • None
    • None
    • Query Planning
    • None
    • Query Optimization

    Description

      Currently we don't use wildcard indexes for any sorts unless the query would restrict to documents that have the field we are sorting on. This is because they are sparse indexes and don't have entries for documents that are missing the field. However this is too restrictive for descending sorts with limits (eg find().sort({score:-1}).limit(1)) because null and missing values would be at the end rather than the beginning of the sorted output. This means that we can scan the index to return the top K results. If we hit the end of a path-prefixed [MaxKey, null) scan before collecting K results, then we will know that we need to fall back to a table scan to sort all documents with a nullish value for the sort field. But that is unlikely to happen in practice with a top K sort*, and if it does, we will have only wasted a relatively small amount of work in the index.

      * Notable exceptions include on an empty collection where everything is ~free and when the user typos a field name in the sort, in which case the index scan will be ~free.

      Attachments

        Activity

          People

            backlog-query-optimization Backlog - Query Optimization
            mathias@mongodb.com Mathias Stearn
            Votes:
            0 Vote for this issue
            Watchers:
            9 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: