[SERVER-80735] [CQF] Lazy simplification Created: 05/Sep/23  Updated: 16/Jan/24

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

Type: Improvement Priority: Major - P3
Reporter: Svilen Mihaylov (Inactive) Assignee: Backlog - Query Optimization
Resolution: Unresolved Votes: 0
Labels: M9
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
is duplicated by SERVER-78635 [CQF] Refactor PartialSchemaReqConver... Closed
Related
is related to SERVER-80576 Microbenchmarks - investigate regress... Backlog
Assigned Teams:
Query Optimization
Participants:

 Description   

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.

Generated at Thu Feb 08 06:44:26 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.