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

Should use wildcard index for descending sort with limit

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

      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.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            mathias@mongodb.com Mathias Stearn
            Votes:
            0 Vote for this issue
            Watchers:
            9 Start watching this issue

              Created:
              Updated:
              Resolved: