[SERVER-57225] SBE plans may trigger stack overflow Created: 26/May/21  Updated: 29/Oct/23  Resolved: 03/Jun/21

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 5.1.0-rc0

Type: Bug Priority: Major - P3
Reporter: Ian Boros Assignee: Ian Boros
Resolution: Fixed Votes: 0
Labels: sbe-post-rc0
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
Related
is related to SERVER-57291 Investigate stack overflow in SBE plans Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v5.0
Sprint: Query Execution 2021-05-31, Query Execution 2021-06-14
Participants:
Linked BF Score: 137

 Description   

filterObj = {}; for (let i = 0; i < 225; ++i) { filterObj["foo" + i] = 123; }
db.coll.runCommand({explain: {find: "coll", filter: filterObj}}) 

This was enough to trigger it on an optimized build on my machine. An unoptimized build will likely fair worse.

The implicit ANDs in the filter are translated in a way which makes each clause of the AND a child of the previous one (instead of a sibling). This is known as the "top level AND optimization." With such a deep tree, when each stack frame is large, it is quite easy to overflow.



 Comments   
Comment by Vivian Ge (Inactive) [ 06/Oct/21 ]

Updating the fixversion since branching activities occurred yesterday. This ticket will be in rc0 when it’s been triggered. For more active release information, please keep an eye on #server-release. Thank you!

Comment by Githook User [ 01/Jun/21 ]

Author:

{'name': 'Ian Boros', 'email': 'ian.boros@mongodb.com', 'username': 'puppyofkosh'}

Message: SERVER-57225 Prevent top-level AND optimization from being used for ANDs with many children
Branch: master
https://github.com/mongodb/mongo/commit/90eb445e58124ed8b6b46a048834bffe350dad4c

Comment by Ian Boros [ 27/May/21 ]

anton.korshunov this optimization allows us to build plans that are arbitrarily deep. We can also trigger a stack overflow on many other paths (e.g. saveState()) just by bumping the number of clauses. I'll re-title the ticket to avoid confusion. If you want to discuss more let me know!

Comment by Anton Korshunov [ 27/May/21 ]

ian.boros Or rewrite the explainer without recursion?

Comment by Ian Boros [ 26/May/21 ]

If I'm reading this right, the only time we stack the AND clauses on top of each other like this is with the "top level AND optimization." If we just disable that optimization for ANDs which have more than X children (say, 50), this shouldn't be a problem anymore.

Comment by Ian Boros [ 26/May/21 ]

I believe the reason for the large stack frames is inlined calls on BSONObjBuilder in these blocks which serialize debug info.

Generated at Thu Feb 08 05:41:18 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.