Crate mz_transform

Transformations for relation expressions.

This crate contains traits, types, and methods suitable for transforming MirRelationExpr types in ways that preserve semantics and improve performance. The core trait is Transform, and many implementors of this trait can be boxed and iterated over. Some common transformation patterns are wrapped as Transform implementors themselves.

The crate also contains the beginnings of whole-dataflow optimization, which uses the same analyses but spanning multiple dataflow elements.

Re-exports

• pub use dataflow::optimize_dataflow;

Modules

• analysis
  Traits and types for reusable expression analysis
• canonicalization
  Transformations that bring relation expressions to their canonical form.
• canonicalize_mfp
  Canonicalizes MFPs, e.g., performs CSE on the scalar expressions, eliminates identity MFPs.
• column_knowledge
  Transformations based on pulling information about individual columns from sources.
• compound
  Transformations that don’t fit into one of the canonicalization, fusion, movement, or ordering buckets.
• cse
  Common subexpression elimination.
• dataflow
  Whole-dataflow optimization
• demand
  Transformation based on pushing demand information about columns toward sources.
• equivalence_propagation
  Propagates expression equivalence from leaves to root, and back down again.
• fold_constants
  Replace operators on constants collections with constant collections.
• fusion
  Transformations that fuse together others of their kind.
• join_implementation
  Determines the join implementation for join operators.
• literal_constraints
  See if there are predicates of the form <expr> = literal that can be sped up using an index. More specifically, look for an MFP on top of a Get, where the MFP has an appropriate filter, and the Get has a matching index. Convert these to IndexedFilter joins, which is a semi-join with a constant collection.
• literal_lifting
  Hoist literal values from maps wherever possible.
• monotonic
  Analysis to identify monotonic collections, especially TopK inputs.
• movement
  Transformations that move relation expressions up (lifting) and down (pushdown) the tree.
• non_null_requirements
  Push non-null requirements toward sources.
• normalize_lets
  Normalize the structure of Let and LetRec operators in expressions.
• normalize_ops
  Normalize the structure of various operators.
• notice
  Notices that the optimizer wants to show to users.
• ordering
  Transformations that impose a canonical order on the inputs of multi-input relation expressions.
• predicate_pushdown
  Pushes predicates down through other operators.
• reduce_elision
  Removes Reduce when the input has as unique keys the keys of the reduce.
• reduce_reduction
  Breaks complex Reduce variants into a join of simpler variants.
• reduction_pushdown
  Tries to convert a reduce around a join to a join of reduces. Also absorbs Map operators into Reduce operators.
• redundant_join
  Remove redundant collections of distinct elements from joins.
• semijoin_idempotence
  Remove semijoins that are applied multiple times to no further effect.
• threshold_elision
  Remove Threshold operators when we are certain no records have negative multiplicity.
• typecheck
  Check that the visible type of each query has not been changed
• union_cancel
  Detects an input being unioned with its negation and cancels them out
• will_distinct
  Transform that pushes down the information that a collection will be subjected to a Distinct on specific columns.

Macros

• all
  Compute the conjunction of a variadic number of expressions.
• any
  Compute the disjunction of a variadic number of expressions.
• transforms 🔒
  Convenience macro for guarding transforms behind a feature flag.

Structs

• EmptyIndexOracle
  An IndexOracle that knows about no indexes.
• EmptyStatisticsOracle
  A StatisticsOracle that knows nothing and can give no estimates.
• Fixpoint
  A sequence of transformations iterated some number of times.
• FuseAndCollapse
  A sequence of transformations that simplify the MirRelationExpr
• Optimizer
  A naive optimizer for relation expressions.
• TransformCtx
  Arguments that get threaded through all transforms, plus a DataflowMetainfo that can be manipulated by the transforms.

Enums

• TransformError
  Errors that can occur during a transformation.

Constants

• FOLD_CONSTANTS_LIMIT 🔒

Traits

• IndexOracle
  A trait for a type that can answer questions about what indexes exist.
• StatisticsOracle
  A trait for a type that can estimate statistics about a given GlobalId
• Transform
  Types capable of transforming relation expressions.

Functions

• fold_constants_fixpoint
  Does constant folding to a fixpoint: An expression all of whose leaves are constants, of size small enough to be inlined and folded should reach a single MirRelationExpr::Constant.
• fuse_and_collapse_fixpoint
  Run the FuseAndCollapse transforms in a fixpoint.
• normalize
  Construct a normalizing transform that runs transforms that normalize the structure of the tree until a fixpoint.