[SERVER-63641] Improve SBE multi-planning by choosing which plan to work next based on a priority metric Created: 14/Feb/22  Updated: 29/Oct/23  Resolved: 28/Feb/23

Status: Closed
Project: Core Server
Component/s: Query Execution, Query Planning
Affects Version/s: None
Fix Version/s: 7.0.0-rc0

Type: Improvement Priority: Minor - P4
Reporter: David Storch Assignee: Ivan Fefer
Resolution: Fixed Votes: 0
Labels: pm2697-m2
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-78077 the log of getProductivityFormula fun... Closed
related to SERVER-63642 Add serverStatus metrics to measure m... Closed
is related to SERVER-62150 SBE Multiplanning can be slow when su... Open
is related to SERVER-62981 Make SBE multi-planner's trial period... Closed
is related to SERVER-63642 Add serverStatus metrics to measure m... Closed
Backwards Compatibility: Fully Compatible
Sprint: QE 2023-02-06, QE 2023-02-20, QE 2023-03-06
Participants:
Story Points: 10

 Description   

This improvement aims to improve performance for queries affected by SERVER-62150. I recommend reviewing related ticket SERVER-62150 for context.

Today, the SBE multi-planner works in the following way. Let's assume there are n candidate plans, and they have some arbitrary order. The algorithm, in pseudocode, looks like this:

maxReads <- internalQueryPlanEvaluationWorksSbe // Defaults to 10,000.
for (plan in plans) {
     numReadsDoneByPlan <- runTrialPeriod(plan, maxReads);
     maxReads <- min(maxReads, numReadsDoneByPlan);
}

The reads budget for the trial period is initialized to 10,000, the default value for the internalQueryPlanEvaluationWorksSbe query knob. Next, we run the trial period for each plan in turn (without any interleaving or round-robin execution). The trial period for a given plan ends if either 1) the plan reaches EOF, 2) the plan produces its first batch of results, or 3) the reads budget is expended. In cases (1) and (2), the number of reads required to reach either EOF or the first batch of results is returned as numReadsDoneByPlan in the pseudocode above. This becomes the new reads budget, which means that no plan's trial period is allowed to last longer than that of the previous plan.

The problem with this approach is that the overall work done during the trial period is very much dependent on the order in which the candidates are trialed. Let's say there is a bad plan which requires all 10,000 reads during the trial period and a good plan which reaches EOF in 10 reads. If the bad plan runs first, then the total reads during the trial period will be 10,000 + 10 = 10,010. If the good plan runs first, it immediately reduces the reads budget to 10, and the trial period costs just 10 + 10 = 20 reads in total.

This ticket proposes an alternative algorithm which aims to reduce the average cost of SBE multi-planning. Here is the updated pseudocode:

maxReads = internalQueryPlanEvaluationWorksSbe // Defaults to 10,000.
PriorityQueue q
q <- all candidates, initialized with the same default priority
while (q is not empty) {
    planToRun <- q.Pop()
    done, numReadsDoneByPlan, newPriority <- planToRun.GetNext()
    if (not done) {
        q.Push(planToRun, newPriority)
    } else {
        maxReads = min(maxReads, numReadsDoneByPlan)
    }
}

 
Here, the idea is to interleave execution of the candidate plans (which brings the SBE multi-planner a bit closer to the round-robin strategy employed by the classic multi-planner). We call getNext() just once on whichever plan is currently prioritized. The calculation of the priority is not spelled out in the pseudocode, but I imagine that the highest priority plan is the one which currently has the highest "productivity ratio": namely, the highest ratio of documents returned so far to storage reads. As in the current SBE multi-planning algorithm, when a plan's trial period completes, the reads budget is reduced for all plans which remain in the priority queue.

Credit to mihai.andrei for proposing this idea!



 Comments   
Comment by Githook User [ 28/Feb/23 ]

Author:

{'name': 'Ivan Fefer', 'email': 'ivan.fefer@mongodb.com', 'username': 'Fefer-Ivan'}

Message: SERVER-63641 Use priority queue to sort plans during multiplanning
Branch: master
https://github.com/mongodb/mongo/commit/d8c5a79107bed46f3a9accefc1da43fd45fa0270

Comment by Mihai Andrei [ 07/Feb/23 ]

Per offline discussion, assigning this to myself.

Comment by Ana Meza [ 13/Apr/22 ]

Assigning to steve.la@mongodb.com  based on this slack chat and changing the priority to P4

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