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!