pub enum MirRelationExpr {
Show 15 variants Constant { rows: Result<Vec<(Row, Diff)>, EvalError>, typ: RelationType, }, Get { id: Id, typ: RelationType, }, Let { id: LocalId, value: Box<MirRelationExpr>, body: Box<MirRelationExpr>, }, LetRec { ids: Vec<LocalId>, values: Vec<MirRelationExpr>, body: Box<MirRelationExpr>, }, Project { input: Box<MirRelationExpr>, outputs: Vec<usize>, }, Map { input: Box<MirRelationExpr>, scalars: Vec<MirScalarExpr>, }, FlatMap { input: Box<MirRelationExpr>, func: TableFunc, exprs: Vec<MirScalarExpr>, }, Filter { input: Box<MirRelationExpr>, predicates: Vec<MirScalarExpr>, }, Join { inputs: Vec<MirRelationExpr>, equivalences: Vec<Vec<MirScalarExpr>>, implementation: JoinImplementation, }, Reduce { input: Box<MirRelationExpr>, group_key: Vec<MirScalarExpr>, aggregates: Vec<AggregateExpr>, monotonic: bool, expected_group_size: Option<usize>, }, TopK { input: Box<MirRelationExpr>, group_key: Vec<usize>, order_key: Vec<ColumnOrder>, limit: Option<usize>, offset: usize, monotonic: bool, }, Negate { input: Box<MirRelationExpr>, }, Threshold { input: Box<MirRelationExpr>, }, Union { base: Box<MirRelationExpr>, inputs: Vec<MirRelationExpr>, }, ArrangeBy { input: Box<MirRelationExpr>, keys: Vec<Vec<MirScalarExpr>>, },
}
Expand description

An abstract syntax tree which defines a collection.

The AST is meant to reflect the capabilities of the differential_dataflow::Collection type, written generically enough to avoid run-time compilation work.

Variants§

§

Constant

Fields

§rows: Result<Vec<(Row, Diff)>, EvalError>

Rows of the constant collection and their multiplicities.

§typ: RelationType

Schema of the collection.

A constant relation containing specified rows.

The runtime memory footprint of this operator is zero.

When you would like to pattern match on this, consider using MirRelationExpr::as_const instead, which looks behind ArrangeBys. You might want this matching behavior because constant folding doesn’t remove ArrangeBys.

§

Get

Fields

§id: Id

The identifier for the collection to load.

§typ: RelationType

Schema of the collection.

Get an existing dataflow.

The runtime memory footprint of this operator is zero.

§

Let

Fields

§id: LocalId

The identifier to be used in Get variants to retrieve value.

§value: Box<MirRelationExpr>

The collection to be bound to id.

§body: Box<MirRelationExpr>

The result of the Let, evaluated with id bound to value.

Introduce a temporary dataflow.

The runtime memory footprint of this operator is zero.

§

LetRec

Fields

§ids: Vec<LocalId>

The identifiers to be used in Get variants to retrieve each value.

§values: Vec<MirRelationExpr>

The collections to be bound to each id.

§body: Box<MirRelationExpr>

The result of the Let, evaluated with id bound to value.

Introduce mutually recursive bindings.

Each LocalId is immediately bound to an initially empty collection with the type of its corresponding MirRelationExpr. Repeatedly, each binding is evaluated using the current contents of each other binding, and is refreshed to contain the new evaluation. This process continues through all bindings, and repeats as long as changes continue to occur.

The resulting value of the expression is body evaluated once in the context of the final iterates.

A zero-binding instance can be replaced by body. A single-binding instance is equivalent to MirRelationExpr::Let.

The runtime memory footprint of this operator is zero.

§

Project

Fields

§input: Box<MirRelationExpr>

The source collection.

§outputs: Vec<usize>

Indices of columns to retain.

Project out some columns from a dataflow

The runtime memory footprint of this operator is zero.

§

Map

Fields

§input: Box<MirRelationExpr>

The source collection.

§scalars: Vec<MirScalarExpr>

Expressions which determine values to append to each row. An expression may refer to columns in input or expressions defined earlier in the vector

Append new columns to a dataflow

The runtime memory footprint of this operator is zero.

§

FlatMap

Fields

§input: Box<MirRelationExpr>

The source collection

§func: TableFunc

The table func to apply

§exprs: Vec<MirScalarExpr>

The argument to the table func

Like Map, but yields zero-or-more output rows per input row

The runtime memory footprint of this operator is zero.

§

Filter

Fields

§input: Box<MirRelationExpr>

The source collection.

§predicates: Vec<MirScalarExpr>

Predicates, each of which must be true.

Keep rows from a dataflow where all the predicates are true

The runtime memory footprint of this operator is zero.

§

Join

Fields

§inputs: Vec<MirRelationExpr>

A sequence of input relations.

§equivalences: Vec<Vec<MirScalarExpr>>

A sequence of equivalence classes of expressions on the cross product of inputs.

Each equivalence class is a list of scalar expressions, where for each class the intended interpretation is that all evaluated expressions should be equal.

Each scalar expression is to be evaluated over the cross-product of all records from all inputs. In many cases this may just be column selection from specific inputs, but more general cases exist (e.g. complex functions of multiple columns from multiple inputs, or just constant literals).

§implementation: JoinImplementation

Join implementation information.

Join several collections, where some columns must be equal.

For further details consult the documentation for MirRelationExpr::join.

The runtime memory footprint of this operator can be proportional to the sizes of all inputs and the size of all joins of prefixes. This may be reduced due to arrangements available at rendering time.

§

Reduce

Fields

§input: Box<MirRelationExpr>

The source collection.

§group_key: Vec<MirScalarExpr>

Column indices used to form groups.

§aggregates: Vec<AggregateExpr>

Expressions which determine values to append to each row, after the group keys.

§monotonic: bool

True iff the input is known to monotonically increase (only addition of records).

§expected_group_size: Option<usize>

User hint: expected number of values per group key. Used to optimize physical rendering.

Group a dataflow by some columns and aggregate over each group

The runtime memory footprint of this operator is at most proportional to the number of distinct records in the input and output. The actual requirements can be less: the number of distinct inputs to each aggregate, summed across each aggregate, plus the output size. For more details consult the code that builds the associated dataflow.

§

TopK

Fields

§input: Box<MirRelationExpr>

The source collection.

§group_key: Vec<usize>

Column indices used to form groups.

§order_key: Vec<ColumnOrder>

Column indices used to order rows within groups.

§limit: Option<usize>

Number of records to retain

§offset: usize

Number of records to skip

§monotonic: bool

True iff the input is known to monotonically increase (only addition of records).

Groups and orders within each group, limiting output.

The runtime memory footprint of this operator is proportional to its input and output.

§

Negate

Fields

§input: Box<MirRelationExpr>

The source collection.

Return a dataflow where the row counts are negated

The runtime memory footprint of this operator is zero.

§

Threshold

Fields

§input: Box<MirRelationExpr>

The source collection.

Keep rows from a dataflow where the row counts are positive

The runtime memory footprint of this operator is proportional to its input and output.

§

Union

Fields

§base: Box<MirRelationExpr>

A source collection.

§inputs: Vec<MirRelationExpr>

Source collections to union.

Adds the frequencies of elements in contained sets.

The runtime memory footprint of this operator is zero.

§

ArrangeBy

Fields

§input: Box<MirRelationExpr>

The source collection

§keys: Vec<Vec<MirScalarExpr>>

Columns to arrange input by, in order of decreasing primacy

Technically a no-op. Used to render an index. Will be used to optimize queries on finer grain. Each keys item represents a different index that should be produced from the keys.

The runtime memory footprint of this operator is proportional to its input.

Implementations§

Reports the schema of the relation.

This method determines the type through recursive traversal of the relation expression, drawing from the types of base collections. As such, this is not an especially cheap method, and should be used judiciously.

The relation type is computed incrementally with a recursive post-order traversal, that accumulates the input types for the relations yet to be visited in type_stack.

Reports the schema of the relation given the schema of the input relations.

input_types is required to contain the schemas for the input relations of the current relation in the same order as they are visited by try_visit_children method, even though not all may be used for computing the schema of the current relation. For example, Let expects two input types, one for the value relation and one for the body, in that order, but only the one for the body is used to determine the type of the Let relation.

It is meant to be used during post-order traversals to compute relation schemas incrementally.

Reports the column types of the relation given the column types of the input relations.

input_types is required to contain the column types for the input relations of the current relation in the same order as they are visited by try_visit_children method, even though not all may be used for computing the schema of the current relation. For example, Let expects two input types, one for the value relation and one for the body, in that order, but only the one for the body is used to determine the type of the Let relation.

It is meant to be used during post-order traversals to compute column types incrementally.

Reports the unique keys of the relation given the arities and the unique keys of the input relations.

input_arities and input_keys are required to contain the corresponding info for the input relations of the current relation in the same order as they are visited by try_visit_children method, even though not all may be used for computing the schema of the current relation. For example, Let expects two input types, one for the value relation and one for the body, in that order, but only the one for the body is used to determine the type of the Let relation.

It is meant to be used during post-order traversals to compute unique keys incrementally.

The number of columns in the relation.

This number is determined from the type, which is determined recursively at non-trivial cost.

The arity is computed incrementally with a recursive post-order traversal, that accumulates the arities for the relations yet to be visited in arity_stack.

Reports the arity of the relation given the schema of the input relations.

input_arities is required to contain the arities for the input relations of the current relation in the same order as they are visited by try_visit_children method, even though not all may be used for computing the schema of the current relation. For example, Let expects two input types, one for the value relation and one for the body, in that order, but only the one for the body is used to determine the type of the Let relation.

It is meant to be used during post-order traversals to compute arities incrementally.

The number of child relations this relation has.

Constructs a constant collection from specific rows and schema, where each row will have a multiplicity of one.

Constructs a constant collection from specific rows and schema, where each row can have an arbitrary multiplicity.

If self is a constant, return the value and the type, otherwise None. Looks behind ArrangeBys.

If self is a constant, mutably return the value and the type, otherwise None. Looks behind ArrangeBys.

If self is a constant error, return the error, otherwise None. Looks behind ArrangeBys.

Checks if self is the single element collection with no columns.

Constructs the expression for getting a global collection

Retains only the columns specified by output.

Append to each row the results of applying elements of scalar.

Append to each row a single scalar.

Like map, but yields zero-or-more output rows per input row

Retain only the rows satisfying each of several predicates.

Form the Cartesian outer-product of rows in both inputs.

Performs a relational equijoin among the input collections.

The sequence inputs each describe different input collections, and the sequence variables describes equality constraints that some of their columns must satisfy. Each element in variable describes a set of pairs (input_index, column_index) where every value described by that set must be equal.

For example, the pair (input, column) indexes into inputs[input][column], extracting the inputth input collection and for each row examining its columnth column.

Example
use mz_repr::{Datum, ColumnType, RelationType, ScalarType};
use mz_expr::MirRelationExpr;

// A common schema for each input.
let schema = RelationType::new(vec![
    ScalarType::Int32.nullable(false),
    ScalarType::Int32.nullable(false),
]);

// the specific data are not important here.
let data = vec![Datum::Int32(0), Datum::Int32(1)];

// Three collections that could have been different.
let input0 = MirRelationExpr::constant(vec![data.clone()], schema.clone());
let input1 = MirRelationExpr::constant(vec![data.clone()], schema.clone());
let input2 = MirRelationExpr::constant(vec![data.clone()], schema.clone());

// Join the three relations looking for triangles, like so.
//
//     Output(A,B,C) := Input0(A,B), Input1(B,C), Input2(A,C)
let joined = MirRelationExpr::join(
    vec![input0, input1, input2],
    vec![
        vec![(0,0), (2,0)], // fields A of inputs 0 and 2.
        vec![(0,1), (1,0)], // fields B of inputs 0 and 1.
        vec![(1,1), (2,1)], // fields C of inputs 1 and 2.
    ],
);

// Technically the above produces `Output(A,B,B,C,A,C)` because the columns are concatenated.
// A projection resolves this and produces the correct output.
let result = joined.project(vec![0, 1, 3]);

Constructs a join operator from inputs and required-equal scalar expressions.

Perform a key-wise reduction / aggregation.

The group_key argument indicates columns in the input collection that should be grouped, and aggregates lists aggregation functions each of which produces one output column in addition to the keys.

Perform a key-wise reduction order by and limit.

The group_key argument indicates columns in the input collection that should be grouped, the order_key argument indicates columns that should be further used to order records within groups, and the limit argument constrains the total number of records that should be produced in each group.

Negates the occurrences of each row.

Removes all but the first occurrence of each row.

Removes all but the first occurrence of each key. Columns not included in the group_key are discarded.

Discards rows with a negative frequency.

Unions together any number inputs.

If inputs is empty, then an empty relation of type typ is constructed.

Produces one collection where each row is present with the sum of its frequencies in each input.

Arranges the collection by the specified columns

Indicates if this is a constant empty collection.

A false value does not mean the collection is known to be non-empty, only that we cannot currently determine that it is statically empty.

If the expression is a negated project, return the input and the projection.

Pretty-print this MirRelationExpr to a string.

Pretty-print this MirRelationExpr to a string using a custom ExplainConfig and an optionally provided ExprHumanizer.

Take ownership of self, leaving an empty MirRelationExpr::Constant with the correct type.

Take ownership of self, leaving an empty MirRelationExpr::Constant with an incorrect type.

This should only be used if self is about to be dropped or otherwise overwritten.

Replaces self with some logic applied to self.

Store self in a Let and pass the corresponding Get to body

Like MirRelationExpr::let_in, but with a fallible return type.

Return every row in self that does not have a matching row in the first columns of keys_and_values, using default to fill in the remaining columns (If default is a row of nulls, this is the ‘outer’ part of LEFT OUTER JOIN)

Return:

  • every row in keys_and_values
  • every row in self that does not have a matching row in the first columns of keys_and_values, using default to fill in the remaining columns (This is LEFT OUTER JOIN if:
  1. default is a row of null
  2. matching rows in keys_and_values and self have the same multiplicity.)

True iff the expression contains a NullaryFunc::MzLogicalTimestamp.

Fallible visitor for the MirScalarExprs directly owned by this relation expression.

The f visitor should not recursively descend into owned MirRelationExprs.

Fallible mutable visitor for the MirScalarExprs in the MirRelationExpr subtree rooted at self.

Note that this does not recurse into MirRelationExpr subtrees within MirScalarExpr nodes.

Infallible mutable visitor for the MirScalarExprs in the MirRelationExpr subtree rooted at at self.

Note that this does not recurse into MirRelationExpr subtrees within MirScalarExpr nodes.

Fallible visitor for the MirScalarExprs directly owned by this relation expression.

The f visitor should not recursively descend into owned MirRelationExprs.

Fallible immutable visitor for the MirScalarExprs in the MirRelationExpr subtree rooted at self.

Note that this does not recurse into MirRelationExpr subtrees within MirScalarExpr nodes.

Infallible immutable visitor for the MirScalarExprs in the MirRelationExpr subtree rooted at at self.

Note that this does not recurse into MirRelationExpr subtrees within MirScalarExpr nodes.

Clears the contents of self even if it’s so deep that simply dropping it would cause a stack overflow in drop_in_place.

Leaves self in an unusable state, so this should only be used if self is about to be dropped or otherwise overwritten.

Computes the size (total number of nodes) and maximum depth of a MirRelationExpr for debug printing purposes. Might grow the stack to a size proportional to the maximum depth.

True when expr contains a LetRec AST node.

Given the ids and values of a LetRec, it computes the subset of ids that are used across iterations. These are those ids that have a reference before they are defined, when reading all the bindings in order.

For example:

WITH MUTUALLY RECURSIVE
    x(...) AS f(z),
    y(...) AS g(x),
    z(...) AS h(y)
...;

Here, only z is returned, because x and y are referenced only within the same iteration.

Note that if a binding references itself, that is also returned.

Replaces LetRec nodes with a stack of Let nodes.

In each Let binding, uses of Get in value that are not at strictly greater identifiers are rewritten to be the constant collection. This makes the computation perform exactly “one” iteration.

This was used only temporarily while developing LetRec.

Iterates through references to child expressions.

Iterates through mutable references to child expressions.

Iterative pre-order visitor.

Iterative pre-order visitor.

Return a vector of references to the subtrees of this expression in post-visit order (the last element is &self).

Trait Implementations§

Returns a copy of the value. Read more
Performs copy-assignment from source. Read more
Appends global identifiers on which this plan depends to out.
Returns the global identifiers on which this plan depends. Read more
Formats the value using the given formatter. Read more
Deserialize this value from the given Serde deserializer. Read more

EXPLAIN ... AS TEXT support for MirRelationExpr.

The format adheres to the following conventions:

  1. In general, every line corresponds to an MirRelationExpr node in the plan.
  2. Non-recursive parameters of each sub-plan are written as $key=$val pairs on the same line.
  3. A single non-recursive parameter can be written just as $val.
  4. Exceptions in (1) can be made when virtual syntax is requested (done by default, can be turned off with WITH(raw_syntax)).
  5. Exceptions in (2) can be made when join implementations are rendered explicitly WITH(join_impls).
The type of the immutable context in which the explanation will be rendered.
The explanation type produced by a successful Explain::explain_text call.
The explanation type produced by a successful Explain::explain_json call.
The explanation type produced by a successful Explain::explain_json call.
Construct a Result::Ok of the Explain::Text format from the config and the context. Read more
Construct a Result::Ok of the Explain::Json format from the config and the context. Read more
Explain an instance of Self within the given Explain::Context. Read more
Construct a Result::Ok of the Explain::Dot format from the config and the context. Read more
Feeds this value into the given Hasher. Read more
Feeds a slice of this type into the given Hasher. Read more
Adds names and types of the fields of the struct or enum to rti. Read more
This method returns an Ordering between self and other. Read more
Compares and returns the maximum of two values. Read more
Compares and returns the minimum of two values. Read more
Restrict a value to a certain interval. Read more
This method tests for self and other values to be equal, and is used by ==.
This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
This method returns an ordering between self and other values if one exists. Read more
This method tests less than (for self and other) and is used by the < operator. Read more
This method tests less than or equal to (for self and other) and is used by the <= operator. Read more
This method tests greater than (for self and other) and is used by the > operator. Read more
This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more
Serialize this value into the given Serde serializer. Read more
Apply an infallible immutable function f to each direct child.
Apply an infallible mutable function f to each direct child.
Apply a fallible immutable function f to each direct child. Read more
Apply a fallible mutable function f to each direct child. Read more

Auto Trait Implementations§

Blanket Implementations§

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more
Compare self to key and return true if they are equal.

Returns the argument unchanged.

Converts to this type from a reference to the input type.
Attaches the provided Context to this type, returning a WithContext wrapper. Read more
Attaches the current Context to this type, returning a WithContext wrapper. Read more
The type of the output value.
A well-distributed integer derived from the data.
Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
Instruments this type with the current Span, returning an Instrumented wrapper. Read more

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Wrap the input message T in a tonic::Request
Upcasts this ProgressEventTimestamp to Any. Read more
Returns the name of the concrete type of this object. Read more
Should always be Self
The resulting type after obtaining ownership.
Creates owned data from borrowed data, usually by cloning. Read more
Uses borrowed data to replace owned data, usually by cloning. Read more
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.
source§

fn visit_post<F>(&self, f: &mut F) -> Result<(), RecursionLimitError>where
    F: FnMut(&T),

Post-order immutable infallible visitor for self.
source§

fn visit_post_nolimit<F>(&self, f: &mut F)where
    F: FnMut(&T),

👎Deprecated: Use visit_post instead.
Post-order immutable infallible visitor for self. Does not enforce a recursion limit.
source§

fn visit_mut_post<F>(&mut self, f: &mut F) -> Result<(), RecursionLimitError>where
    F: FnMut(&mut T),

Post-order mutable infallible visitor for self.
source§

fn visit_mut_post_nolimit<F>(&mut self, f: &mut F)where
    F: FnMut(&mut T),

👎Deprecated: Use visit_mut_post instead.
Post-order mutable infallible visitor for self. Does not enforce a recursion limit.
source§

fn try_visit_post<F, E>(&self, f: &mut F) -> Result<(), E>where
    F: FnMut(&T) -> Result<(), E>,
    E: From<RecursionLimitError>,

Post-order immutable fallible visitor for self.
source§

fn try_visit_mut_post<F, E>(&mut self, f: &mut F) -> Result<(), E>where
    F: FnMut(&mut T) -> Result<(), E>,
    E: From<RecursionLimitError>,

Post-order mutable fallible visitor for self.
Pre-order immutable infallible visitor for self.
Pre-order immutable infallible visitor for self, which also accumulates context information along the path from the root to the current node’s parent. acc_fun is a similar closure as in fold. The accumulated context is passed to the visitor, along with the current node. Read more
👎Deprecated: Use visit_pre instead.
Pre-order immutable infallible visitor for self. Does not enforce a recursion limit.
Pre-order mutable infallible visitor for self.
👎Deprecated: Use visit_mut_pre instead.
Pre-order mutable infallible visitor for self. Does not enforce a recursion limit.
Pre-order immutable fallible visitor for self.
Pre-order mutable fallible visitor for self.
source§

fn visit_pre_post<F1, F2>(
    &self,
    pre: &mut F1,
    post: &mut F2
) -> Result<(), RecursionLimitError>where
    F1: FnMut(&T) -> Option<Vec<&T, Global>>,
    F2: FnMut(&T),

source§

fn visit_pre_post_nolimit<F1, F2>(&self, pre: &mut F1, post: &mut F2)where
    F1: FnMut(&T) -> Option<Vec<&T, Global>>,
    F2: FnMut(&T),

👎Deprecated: Use visit instead.
A generalization of Visit::visit_pre and Visit::visit_post. Does not enforce a recursion limit. Read more
source§

fn visit_mut_pre_post<F1, F2>(
    &mut self,
    pre: &mut F1,
    post: &mut F2
) -> Result<(), RecursionLimitError>where
    F1: FnMut(&mut T) -> Option<Vec<&mut T, Global>>,
    F2: FnMut(&mut T),

👎Deprecated: Use visit_mut instead.
source§

fn visit_mut_pre_post_nolimit<F1, F2>(&mut self, pre: &mut F1, post: &mut F2)where
    F1: FnMut(&mut T) -> Option<Vec<&mut T, Global>>,
    F2: FnMut(&mut T),

👎Deprecated: Use visit_mut_pre_post instead.
A generalization of Visit::visit_mut_pre and Visit::visit_mut_post. Does not enforce a recursion limit. Read more
Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more