[SERVER-42090] Make ordering of OR branches stable in query data access planning Created: 05/Jul/19  Updated: 29/Oct/23  Resolved: 04/Sep/19

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

Type: Improvement Priority: Major - P3
Reporter: David Storch Assignee: David Storch
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
Backwards Compatibility: Fully Compatible
Sprint: Query 2019-08-12, Query 2019-08-26, Query 2019-09-09
Participants:
Case:

 Description   

The ordering of the branches in an OR stage should not affect the performance of the plan, since all branches must be executed in full in order for the plan to complete. However, the order of the children can matter for plan selection, e.g. for users who are affected by SERVER-20616. The ordering chosen by the access planner is not only arbitrary right now, but it is not stable. That is, multiple executions of the same query could theoretically choose a different OR ordering. The improvement tracked by this ticket is to ensure that the planner always chooses a particular, if arbitrary, ordering.

The ordering chosen right now is a function of the sort by TagComparison done in preparation for access planning. The problem is that two very different MatchExpression nodes can easily sort equally under this comparison. In particular, $and MatchExpression nodes can sort equally. To fix this, we can refine the comparator function to consider two nodes' children if they would otherwise be considered equal.



 Comments   
Comment by Githook User [ 04/Sep/19 ]

Author:

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

Message: SERVER-42090 Ensure query planner produces a stable ordering of OR branches.
Branch: master
https://github.com/mongodb/mongo/commit/bac2b16a61498a65cbd61da0e15235363e7e77b9

Generated at Thu Feb 08 04:59:34 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.