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

Should use wildcard index for descending sort with limit

    XMLWordPrintable

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Won't Fix
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Query Planning
    • Labels:
      None

      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

            Assignee:
            backlog-query-optimization Backlog - Query Optimization
            Reporter:
            redbeard0531 Mathias Stearn
            Participants:
            Votes:
            0 Vote for this issue
            Watchers:
            9 Start watching this issue

              Dates

              Created:
              Updated:
              Resolved: