Struct mz_transform::literal_constraints::LiteralConstraints

pub struct LiteralConstraints;

Convert literal constraints into IndexedFilter joins.

Implementations

impl LiteralConstraints

fn action( &self, relation: &mut MirRelationExpr, transform_ctx: &mut TransformCtx<'_>, ) -> Result<(), TransformError>

fn detect_literal_constraints( mfp: &MapFilterProject, get_id: GlobalId, transform_ctx: &mut TransformCtx<'_>, ) -> Option<(GlobalId, Vec<MirScalarExpr>, Vec<Row>)>

Detects literal constraints in an MFP on top of a Get of id, and a matching index that can be used to speed up the Filter of the MFP.

For example, if there is an index on (f1, f2), and the Filter is (f1 = 3 AND f2 = 5) OR (f1 = 7 AND f2 = 9), it returns Some([f1, f2], [[3,5], [7,9]]).

We can use an index if each argument of the OR includes a literal constraint on each of the key fields of the index. Extra predicates inside the OR arguments are ok.

Returns (idx_id, idx_key, values to lookup in the index).

fn remove_literal_constraints( mfp: &mut MapFilterProject, key: &Vec<MirScalarExpr>, ) -> bool

Removes the expressions that LiteralConstraints::detect_literal_constraints found, if possible. Returns whether it removed anything. For example, if the key of the detected literal constraint is just f1, and we have the expression (f1 = 3 AND f2 = 5) OR (f1 = 7 AND f2 = 5), then this modifies it to f2 = 5. However, if OR branches differ in their non-key parts, then we cannot remove the literal constraint. For example, (f1 = 3 AND f2 = 5) OR (f1 = 7 AND f2 = 555), then we cannot remove the f1 parts, because then the filter wouldn’t know whether to check f2 = 5 or f2 = 555.

fn remove_impossible_or_args( mfp: &mut MapFilterProject, ) -> Result<bool, RecursionLimitError>

1. Removes such OR args in which there are contradicting literal constraints.
2. Also, if an OR arg doesn’t have any contradiction, this fn just deduplicates the AND arg list of that OR arg. (Might additionally sort all AND arg lists.)

Returns whether it performed any removal or deduplication.

Example for 1: <arg1> OR (a = 5 AND a = 5 AND a = 8) OR <arg3> –> <arg1> OR <arg3>

Example for 2: <arg1> OR (a = 5 AND a = 5 AND b = 8) OR <arg3> –> <arg1> OR (a = 5 AND b = 8) OR <arg3>

fn get_or_args(mfp: &MapFilterProject) -> Vec<MirScalarExpr>

Returns the arguments of the predicate’s top-level OR as a Vec. If there is no top-level OR, then interpret the predicate as a 1-arg OR, i.e., return a 1-element Vec.

Assumes that LiteralConstraints::list_of_predicates_to_and_of_predicates has already run.

fn inline_literal_constraints(mfp: &mut MapFilterProject)

Makes the job of LiteralConstraints::detect_literal_constraints easier by undoing some CSE to reconstruct literal constraints.

fn list_of_predicates_to_and_of_predicates(mfp: &mut MapFilterProject)

MFPs have a Vec of predicates [p1, p2, ...], which logically represents p1 AND p2 AND .... This function performs this conversion. Note that it might create a variadic AND with 0 or 1 args, so the resulting predicate Vec always has exactly 1 element.

fn canonicalize_predicates( mfp: &mut MapFilterProject, relation: &MirRelationExpr, )

Call mz_expr::canonicalize::canonicalize_predicates on each of the predicates in the MFP.

fn distribute_and_over_or( mfp: &mut MapFilterProject, ) -> Result<(), RecursionLimitError>

Distribute AND over OR + do flatten_and_or until fixed point. This effectively converts to disjunctive normal form (DNF) (i.e., an OR of ANDs), because MirScalarExpr::reduce did Demorgans and double-negation-elimination. So after MirScalarExpr::reduce, we get here a tree of AND/OR nodes. A distribution step lifts an OR up the tree by 1 level, and a MirScalarExpr::flatten_associative merges two ORs that are at adjacent levels, so eventually we’ll end up with just one OR that is at the top of the tree, with ANDs below it. For example: (a || b) && (c || d) -> ((a || b) && c) || ((a || b) && d) -> (a && c) || (b && c) || (a && d) || (b && d) (This is a variadic OR with 4 arguments.)

Example: User wrote WHERE (a,b) IN ((1,2), (1,4), (8,5)), from which MirScalarExpr::undistribute_and_or made this before us: (#0 = 1 AND (#1 = 2 OR #1 = 4)) OR (#0 = 8 AND #1 = 5) And now we distribute the first AND over the first OR in 2 steps: First to ((#0 = 1 AND #1 = 2) OR (#0 = 1 AND #1 = 4)) OR (#0 = 8 AND #1 = 5) then MirScalarExpr::flatten_associative: (#0 = 1 AND #1 = 2) OR (#0 = 1 AND #1 = 4) OR (#0 = 8 AND #1 = 5)

Note that MirScalarExpr::undistribute_and_or is not exactly an inverse to this because

1. it can undistribute both AND over OR and OR over AND.
2. it cannot always undo the distribution, because an expression might have multiple overlapping undistribution opportunities, see comment there.

fn unary_and(mfp: &mut MapFilterProject)

For each of the arguments of the top-level OR (if no top-level OR, then interpret the whole expression as a 1-arg OR, see LiteralConstraints::get_or_args), check if it’s an AND, and if not, then wrap it in a 1-arg AND.

fn predicates_size(mfp: &MapFilterProject) -> usize

Trait Implementations

impl Debug for LiteralConstraints

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Transform for LiteralConstraints

fn name(&self) -> &'static str

A short string naming the transform, as it will be reported in metrics.

fn actually_perform_transform( &self, relation: &mut MirRelationExpr, ctx: &mut TransformCtx<'_>, ) -> Result<(), TransformError>

Transform a relation into a functionally equivalent relation.

fn transform( &self, relation: &mut MirRelationExpr, args: &mut TransformCtx<'_>, ) -> Result<(), TransformError>

Transforms a relation into a functionally equivalent relation.

fn debug(&self) -> String

A string describing the transform.