-
Type: Improvement
-
Resolution: Unresolved
-
Priority: Major - P3
-
None
-
Affects Version/s: None
-
Component/s: None
-
Query Optimization
Currently the optimizer uses an aggressive simplification strategy for its interval and PSR expressions. Consider the following workflow:
- A filter or eval expression is translated into a PSR.
- On every non-trivial path element (composem or -a) the two trees are merged and simplified.
- After the translation is complete, the paths are simplified and the intervals are intersected. This happens in both the substitution and exploration phase.
- If there are multiple filters and/or multiple evaluation nodes, those are separately translated and their expressions merged and simplified sequentially.
- Candidate indexes are computed every time we create a sargable node.
Pros and cons:
- Easier to debug and justify correctness.
- All expressions are always kept as DNF.
- Easier not to defer decisions regarding overly complex predicates.
- Cons: can lead to quadratic simplification algorithms when we repeatedly use "merge-and-simplify" pattern.
Proposal: lazy simplification.
- Introduce a new "simplification" rewrite, with a high numeric priority, to be executed after all the other simplification rewrites in the substitution phase.
* Do not simplify expressions as they are translated from filter/eval nodes (just combine with a conjunction/disjunction node). Thus the expressions may no longer be in DNF/CNF.
- Do not compute candidate indexes until the final rewrite.
- The final rewrite will do the following: convert expressions to DNF, simplify, and compute candidate indexes.
- is duplicated by
-
SERVER-78635 [CQF] Refactor PartialSchemaReqConverter to avoid quadratic behavior
- Closed
- is related to
-
SERVER-80576 Microbenchmarks - investigate regression in $in queries
- Backlog