Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-80735

[CQF] Lazy simplification

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 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.

            Assignee:
            backlog-query-optimization [DO NOT USE] Backlog - Query Optimization
            Reporter:
            svilen.mihaylov@mongodb.com Svilen Mihaylov (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            8 Start watching this issue

              Created:
              Updated: