[SERVER-15200] Query planner should move projection stage below sort stage when possible Created: 10/Sep/14  Updated: 06/Dec/19  Resolved: 26/Nov/19

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: None
Fix Version/s: 4.3.3

Type: Improvement Priority: Major - P3
Reporter: J Rassi Assignee: David Storch
Resolution: Done Votes: 6
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Problem/Incident
Related
related to SERVER-26442 Push $sort before $project and $addFi... Open
Backwards Compatibility: Fully Compatible
Sprint: Query 2019-11-04, Query 2019-11-18, Query 2019-12-02
Participants:
Linked BF Score: 0

 Description   

The query planner currently performs sort analysis before projection analysis; consequently, sort stages are placed below projection stages in the query tree. This is often desirable for queries in which the user does not request all results, since projections don't have to be computed for the documents that are not returned.

However, this is not desirable for collections with large documents, since the sort stage will buffer the entire document instead of the projected document. As a result, the sort stage can have an unnecessarily large memory footprint for these queries, and the queries will fail if the stage memory usage exceeds 32MB.

Reproduce with the following shell snippet. The snippet attempts to issue a sort+project query which technically only needs to buffer <1kB of results, but instead >32MB of results are buffered and an error is returned.

> var longString = ''; for (var i = 0; i < 1024*1024; i++) { longString += 'x'; } 0
0
> for (var i = 0; i < 50; i++) { db.foo.insert({a: 1, b: 1, longString: longString}) }
WriteResult({ "nInserted" : 1 })
> db.foo.ensureIndex({a: 1})
{
	"createdCollectionAutomatically" : false,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> db.foo.find({a: 1}, {longString: 0}).sort({b: 1})
error: {
	"$err" : "Runner error: Overflow sort stage buffered data usage of 33556640 bytes exceeds internal limit of 33554432 bytes",
	"code" : 17144
}

The error displays the following stats tree in the log:

2014-09-10T13:23:38.922-0400 [conn1] ERROR: Runner error, stats:
{ "type" : "PROJECTION",
  "works" : 35,
  "yields" : 0,
  "unyields" : 0,
  "invalidates" : 0,
  "advanced" : 0,
  "needTime" : 0,
  "needFetch" : 0,
  "isEOF" : 0,
  "children" : [
    { "type" : "SORT",
      "works" : 35,
      "yields" : 0,
      "unyields" : 0,
      "invalidates" : 0,
      "advanced" : 0,
      "needTime" : 33,
      "needFetch" : 0,
      "isEOF" : 0,
      "forcedFetches" : 0,
      "memUsage" : 33556640,
      "memLimit" : 33554432,
      "children" : [
        { "type" : "KEEP_MUTATIONS",
          "works" : 33,
          "yields" : 0,
          "unyields" : 0,
          "invalidates" : 0,
          "advanced" : 32,
          "needTime" : 1,
          "needFetch" : 0,
          "isEOF" : 0,
          "children" : [
            { "type" : "FETCH",
              "works" : 33,
              "yields" : 0,
              "unyields" : 0,
              "invalidates" : 0,
              "advanced" : 32,
              "needTime" : 1,
              "needFetch" : 0,
              "isEOF" : 0,
              "alreadyHasObj" : 0,
              "forcedFetches" : 0,
              "matchTested" : 0,
              "children" : [
                { "type" : "IXSCAN",
                  "works" : 33,
                  "yields" : 0,
                  "unyields" : 0,
                  "invalidates" : 0,
                  "advanced" : 32,
                  "needTime" : 1,
                  "needFetch" : 0,
                  "isEOF" : 0,
                  "keyPattern" : "{ a: 1.0 }",
                  "isMultiKey" : 0,
                  "boundsVerbose" : "field #0['a']: [1.0, 1.0]",
                  "yieldMovedCursor" : 0,
                  "dupsTested" : 0,
                  "dupsDropped" : 0,
                  "seenInvalidated" : 0,
                  "matchTested" : 0,
                  "keysExamined" : 33,
                  "children" : [] } ] } ] } ] } ] }
2014-09-10T13:23:38.923-0400 [conn1] assertion 17144 Runner error: Overflow sort stage buffered data usage of 33556640 bytes exceeds internal limit of 33554432 bytes ns:test2.foo query:{ query: { a: 1.0 }, orderby: { b: 1.0 } }



 Comments   
Comment by Githook User [ 26/Nov/19 ]

Author:

{'email': 'david.storch@mongodb.com', 'name': 'David Storch', 'username': 'dstorch'}

Message: SERVER-15200 Optimize projection to occur before sort when possible.

When the projection is statically known to reduce the size
of the data (i.e. when the projection does not add any newly
computed fields), then evaluating the projection first is
beneficial because it reduces the size of the data which
must be sorted.
Branch: master
https://github.com/mongodb/mongo/commit/058c4e3bbf94aa2ed1148dd0e8e473be6fcaa48b

Comment by eli jones [ 22/Sep/14 ]

I ran into a similar issue. I have a range query that returns 74,000 documents from an index.

If I try to sort by "_id" and .hint() it to use the same index, it blows up with the "Overflow sort stage buffered..." error.

This is due to the documents being fairly large and the _memUsage value being calculated based on total document size.

In the least, it seems like mongod should be able to sort 74k document _ids, and then return the documents in that order...

Comment by J Rassi [ 10/Sep/14 ]

One possible fix for this issue is to register a backup plan for these queries, where the backup plan is generated by switching the order of the projection analysis / sort analysis. This would favor the low-CPU plan (sort below projection) by default, and allow fallback to the low-memory plan (projection below sort) if the sort stage exceeds the memory limit.

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