[SERVER-45689] DISTINCT_SCAN candidate plans should be generated and evaluated with the multi-planner Created: 21/Jan/20  Updated: 04/Jan/23

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

Type: Improvement Priority: Major - P3
Reporter: David Storch Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 1
Labels: qopt-team
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-22460 Logic for applying distinct scan and ... Backlog
is related to SERVER-14227 add index hint support for distinct c... Closed
Assigned Teams:
Query Optimization
Sprint: QO 2022-09-19
Participants:
Case:

 Description   

The DISTINCT_SCAN stage implements an optimized specialization of an index scan which is appropriate for a subset of distinct or aggregate operations. It involves skipping duplicate keys via an index seek.

The planning logic for DISTINCT_SCAN is implemented outside of the planner. It involves first invoking QueryPlanner::plan(), and then seeing if any of the resulting plans can be correctly converted to a DISTINCT_SCAN. However, as soon as we are able to construct our first DISTINCT_SCAN plan, we pass it off to the execution engine without considering other candidates. See https://github.com/mongodb/mongo/blob/48cd578fa9c3ef317666ca475f9ee14c1fe0bc4f/src/mongo/db/query/get_executor.cpp#L1535-L1556. It is possible that there are multiple DISTINCT_SCAN plans, and that one will outperform another. The efficiency of the DISTINCT_SCAN relates to position of the field we're "distincting" in the index key pattern, as well as the number of unique values in the collection for the preceding key pattern fields. By simply selecting the first DISTINCT_SCAN, we might select a plan that is substantially suboptimal.

Instead, we should generate a set of DISTINCT_SCAN candidate plans. These candidates could then be scored and ranked according to our usual multi-planning algorithm.

A few additional concerns that come to mind:

  • Is there any reason to generate IXSCAN candidates alongside the DISTINCT_SCAN candidates, or is it safe to assume that DISTINCT_SCAN should always be preferred?
  • How hard would it be to move the DISTINCT_SCAN logic into QueryPlanner::plan()? It's always bothered me that we have such heavy query planning logic living outside of the planning module.


 Comments   
Comment by Brenda Rodriguez [ 31/Oct/22 ]

We are sending this back to the backlog and director triage for assignment

Comment by Joel Redman (Inactive) [ 22/Oct/21 ]

Initial thoughts:

  • Is there any reason to generate IXSCAN candidates alongside the DISTINCT_SCAN candidates, or is it safe to assume that DISTINCT_SCAN should always be preferred?
    • A DISTINCT_SCAN is a long series of seeks as I understand it, so it seems that in the case where the index is unique, or almost unique, you'd end up doing a lot of unnecessary starting over at the top of the BTree, so at least in some cases, a IXSCAN could be more performant. I'd have to do some perf testing to prove that though, or to find the number of concurrent records to show the difference.
  • I'd definitely prefer to push the DISTINCT_SCAN logic into the planner, just for consistency. That also makes them available for other situations that can take advantage of the distinct scan, in principle.
Comment by Charlie Swanson [ 08/Sep/21 ]

Flipping this back to triage based off christopher.harris's comment which should help steve.la and bernard.gorman make a more informed scheduling decision.

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