Module com.darkcollective.relix.optimizer
Package com.darkcollective.relix.optimizer.internal

Class QueryOptimizer

java.lang.Object
com.darkcollective.relix.optimizer.internal.QueryOptimizer
public final class QueryOptimizer extends Object
Entry point for the Relix query optimizer.

The optimizer takes a SemanticModel produced by semantic analysis and rewrites each query's RelNode tree to a semantically equivalent but more efficient form. Every transformation is logged in an OptimizationContext and returned as an OptimizationResult so the audit trail can be rendered by the console's optimization report.

Optimization phases

The rules, their order, and which groups are iterated are declared by OptimizationPipeline, which this class builds once per query and runs. The six phases run once each, in order, and the rules within a phase are swept repeatedly until they stop making progress (capped at OptimizationPipeline.DEFAULT_MAX_ITERATIONS sweeps):

  1. simplify — expression then predicate simplification.
  2. pushdown — selection splitting, the nest/unnest laws, selection pushdown, partition/group pruning, and the join rules.
  3. cleanup — selection merging, the projection rules, and the redundant-γ/δ/τ eliminations.
  4. sip — folding a constraint into CLOSURE/TRACE/ FIX/a generator.
  5. limit — limit pushdown and the top-N fusion.
  6. prune — column pruning, once.

The split into phases is load-bearing, not cosmetic: SEL-003/ PROJ-003 and SEL-001/SEL-002 are mutual inverses, so iterating all the rules together would never terminate. See OptimizationPipeline for the placement rule a new pass has to satisfy.

Three rewrites run outside the pipeline, in optimize(SemanticModel)'s per-query preamble, because each needs the model's SymbolTable and every rule in the pipeline is a pure syntactic rewrite: ViewInliner (INLINE-001) expands view references, RenameEliminationPass (RENAME-001..RENAME-004) removes the alias wrappers inlining leaves behind and tidies the column renames, and LateralDecorrelationPass (LATERAL-001) turns an uncorrelated LATERAL into a × — which needs the table to resolve the function and classify its body as deterministic. All three run before schemas are re-inferred for the expanded tree.

Rule by rule, in the order they run:

  1. Expression simplification — bottom-up constant folding, arithmetic identity elimination, constant accumulation, and idempotent function call elimination (EXPR-001..008).
  2. Predicate simplification — constant-branch folding and double-NOT elimination (PRED-001..002).
  3. Selection splitting — conjunctive predicates decomposed into stacked selections (SEL-001) to expose independent pushdown opportunities (SelectionSplitPass).
  4. Nest/unnest round-trip laws — collapse a μ over a COLLECT to a projection and push σ/π below μ (NEST-001..003) (NestUnnestPass).
  5. Selection pushdown (SEL-003..009) (SelectionPushdownPass). The projection rules, including the inverse PROJ-003, are in the cleanup phase below.
  6. Partition pruning into WINDOW/TopK — push a partition-key equality below the operator so only the matching partition is computed (WINDOW-001, TOPK-001) (SelectionIntoWindowPass).
  7. Group pruning into OPTIMIZE — push a PER grouping-key equality below the operator so the solver runs for only the matching group (OPTIMIZE-001) (SelectionIntoOptimizePass).
  8. Cross-product to theta-join conversion (JOIN-001).
  9. Selection into join inputs (JOIN-002, SEL-005).
  10. Selection and projection merging — cleanup pass (SEL-002, PROJ-001..002).
  11. Redundant-grouping elimination — collapse a γ stacked redundantly on another γ (AGG-001) (RedundantGroupingPass).
  12. Redundant-DISTINCT elimination — remove a δ whose input is already duplicate-free (DIST-001) (DistinctEliminationPass).
  13. Redundant-SORT elimination — remove a τ whose input already delivers a satisfying order (SORT-001) (SortEliminationPass).
  14. Selection-into-CLOSURE pushdown — fold a constant endpoint equality above a CLOSURE into a source/target bound, collapsing all-pairs reachability to single-source/single-pair (CLOSURE-001) (SelectionIntoClosurePass).
  15. Selection-into-TRACE pushdown — fold a constant endpoint equality above a TRACE into a source/target bound, collapsing all-pairs optimal-path search to single-source/single-pair (TRACE-001) (SelectionIntoTracePass).
  16. Magic-sets into FIX — push a selection over frozen columns into a FIX least-fixpoint so the recursion is seeded and restricted by the bound rather than computed in full (FIX-001) — the general case of which CLOSURE/TRACE pushdown are fixed-shape instances (SelectionIntoFixpointPass).
  17. Bound pushdown into a monotone generator — fold an upper bound above an unbounded ascending generator into a production stop, so the scan terminates (GEN-001) (SelectionIntoGeneratorPass).
  18. Limit pushdown (LIM-001..004).
  19. Column pruning — a top-down "required columns" walk that narrows every base relation to the columns the query actually reads (PROJ-004) (ColumnPruningPass). Runs last so it cannot hide the shapes the pattern-matching phases above match on.

This class is stateless and safe to reuse across multiple optimization runs.

  • Constructor Details

    • QueryOptimizer

      public QueryOptimizer()
      Constructs a QueryOptimizer with the default full rule set.

  • Method Details

    • optimize

      public RelNode optimize(RelNode node, String queryName, SchemaAnnotations schemas, OptimizationContext ctx)
      Optimizes a single RelNode tree, recording all transformations in the supplied context.

      Every rule the optimizer ships is a pure syntactic rewrite, so this needs neither a symbol table nor a cost model. Cost-driven join decisions are the planner's, where they can be made without permuting the logical schema.

      The rules that ask what a function may do — whether a call folds, or an aggregate ignores multiplicity — read the FunctionCatalog off ctx. optimize(SemanticModel) puts the model's own catalogue there; a caller entering here directly supplies one when it wants those rules to fire, and gets a slower plan rather than a wrong one when it does not.

      Parameters:
      node - the root of the query tree to optimize; must not be null
      queryName - display name used in transformation records; must not be blank
      schemas - schema annotations from semantic analysis; must not be null
      ctx - context that accumulates transformation records; must not be null
      Returns:
      the optimized tree; the original node when no rules fired

    • optimize

      public List<OptimizationResult> optimize(SemanticModel model)
      Optimizes all root queries in the given SemanticModel.

      Each root query statement is optimized in the order it appears in SemanticModel.rootQueries(). For a NamedQueryTarget the symbol is looked up in the model's symbol table:

      For an ExpressionQueryTarget (an inline query { … } statement) the expression is optimized directly and assigned the generated name "query[n]" where n is the 1-based ordinal of inline queries encountered so far.

      Schema annotations carried in SemanticModel.nodeSchemas() are forwarded to each optimization pass so that schema-dependent rules (e.g. PROJ-001) can operate correctly.

      Parameters:
      model - the semantic model to optimize; must not be null
      Returns:
      unmodifiable list of per-query results, in root-query order; never null; empty when the model has no root queries

    • optimize

      public List<OptimizationResult> optimize(SemanticModel model, QueryEventListener listener)
      Optimizes all root queries in model, emitting a QueryEvent to listener for every rule that fires (in addition to recording it in the returned results).
      Parameters:
      model - the semantic model to optimize; must not be null
      listener - notified on each rule firing; must not be null (use QueryEventListener.NONE for no observation)
      Returns:
      unmodifiable list of per-query results, in root-query order

    • optimize

      public List<OptimizationResult> optimize(SemanticModel model, QueryEventListener listener, DistinctnessSource distinctness)
      As optimize(SemanticModel, QueryEventListener), plus a per-leaf DistinctnessSource so DIST-001 removes δ over an inherently-distinct leaf (e.g. a duplicate-free generator). The CLI supplies a generator-backed source; DistinctnessSource.NONE disables the leaf rule.
      Parameters:
      model - the semantic model to optimize; must not be null
      listener - notified on each rule firing; must not be null
      distinctness - the per-leaf duplicate-free lookup; must not be null
      Returns:
      unmodifiable list of per-query results, in root-query order

    • optimize

      public List<OptimizationResult> optimize(SemanticModel model, QueryEventListener listener, DistinctnessSource distinctness, MonotoneGeneratorSource monotoneGenerators)
      As optimize(SemanticModel, QueryEventListener, DistinctnessSource), plus a per-leaf MonotoneGeneratorSource so GEN-001 folds an upper-bound σ over a monotone unbounded generator into a production stop. The runtime supplies a generator-backed source; MonotoneGeneratorSource.NONE disables the rule.
      Parameters:
      model - the semantic model to optimize; must not be null
      listener - notified on each rule firing; must not be null
      distinctness - the per-leaf duplicate-free lookup; must not be null
      monotoneGenerators - the per-leaf ascending-generator lookup; must not be null
      Returns:
      unmodifiable list of per-query results, in root-query order