Enum expr::MirRelationExpr

pub enum MirRelationExpr {
    Constant {
        rows: Result<Vec<(Row, Diff)>, EvalError>,
        typ: RelationType,
    },
    Get {
        id: Id,
        typ: RelationType,
    },
    Let {
        id: LocalId,
        value: Box<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>>,
    },
    DeclareKeys {
        input: Box<MirRelationExpr>,
        keys: Vec<Vec<usize>>,
    },
}

An abstract syntax tree which defines a collection.

The AST is meant 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.

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.

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

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

DeclareKeys

Fields

input: Box<MirRelationExpr>

The source collection

keys: Vec<Vec<usize>>

The set of columns in the source collection that form a key.

Declares that keys are primary keys for input. Should be used very sparingly, and only if there’s no plausible way to derive the key information from the underlying expression. The result of declaring a key that isn’t actually a key for the underlying expression is undefined.

There is no operator rendered for this IR node; thus, its runtime memory footprint is zero.

Implementations

impl MirRelationExpr

pub fn typ(&self) -> RelationType

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.

pub fn typ_with_input_types(&self, input_types: &[RelationType]) -> RelationType

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_visit1 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.

pub fn arity(&self) -> usize

The number of columns in the relation.

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

pub fn num_inputs(&self) -> usize

The number of child relations this relation has.

pub fn constant(rows: Vec<Vec<Datum<'_>>>, typ: RelationType) -> Self

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

pub fn constant_diff(
    rows: Vec<(Vec<Datum<'_>>, Diff)>,
    typ: RelationType
) -> Self

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

pub fn global_get(id: GlobalId, typ: RelationType) -> Self

Constructs the expression for getting a global collection

pub fn project(self, outputs: Vec<usize>) -> Self

Retains only the columns specified by output.

pub fn map(self, scalars: Vec<MirScalarExpr>) -> Self

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

pub fn flat_map(self, func: TableFunc, exprs: Vec<MirScalarExpr>) -> Self

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

pub fn filter<I>(self, predicates: I) -> Self where
    I: IntoIterator<Item = MirScalarExpr>, 

Retain only the rows satisifying each of several predicates.

pub fn product(self, right: Self) -> Self

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

pub fn join(
    inputs: Vec<MirRelationExpr>,
    variables: Vec<Vec<(usize, usize)>>
) -> Self

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 repr::{Datum, ColumnType, RelationType, ScalarType};
use 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]);

pub fn join_scalars(
    inputs: Vec<MirRelationExpr>,
    equivalences: Vec<Vec<MirScalarExpr>>
) -> Self

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

pub fn reduce(
    self,
    group_key: Vec<usize>,
    aggregates: Vec<AggregateExpr>,
    expected_group_size: Option<usize>
) -> Self

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.

pub fn top_k(
    self,
    group_key: Vec<usize>,
    order_key: Vec<ColumnOrder>,
    limit: Option<usize>,
    offset: usize
) -> Self

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.

pub fn negate(self) -> Self

Negates the occurrences of each row.

pub fn distinct(self) -> Self

Removes all but the first occurrence of each row.

pub fn distinct_by(self, group_key: Vec<usize>) -> Self

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

pub fn threshold(self) -> Self

Discards rows with a negative frequency.

pub fn union_many(inputs: Vec<Self>, typ: RelationType) -> Self

Unions together any number inputs.

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

pub fn union(self, other: Self) -> Self

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

pub fn arrange_by(self, keys: &[Vec<MirScalarExpr>]) -> Self

Arranges the collection by the specified columns

pub fn is_empty(&self) -> bool

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.

pub fn global_uses(&self) -> Vec<GlobalId>

Returns the distinct global identifiers on which this expression depends.

See MirRelationExpr::global_uses_into to reuse an existing vector.

pub fn global_uses_into(&self, out: &mut Vec<GlobalId>)

Appends global identifiers on which this expression depends to out.

Unlike MirRelationExpr::global_uses, this method does not deduplicate the global identifiers.

pub fn pretty_humanized(&self, id_humanizer: &impl ExprHumanizer) -> String

Pretty-print this MirRelationExpr to a string.

This method allows an additional ExprHumanizer which can annotate identifiers with human-meaningful names for the identifiers.

pub fn pretty(&self) -> String

Pretty-print this MirRelationExpr to a string.

pub fn json(&self) -> String

Print this MirRelationExpr to a JSON-formatted string.

pub fn pretty_typed(&self) -> String

Pretty-print this MirRelationExpr to a string with type information.

pub fn take_safely(&mut self) -> MirRelationExpr

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

pub fn take_dangerous(&mut self) -> MirRelationExpr

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.

pub fn replace_using<F>(&mut self, logic: F) where
    F: FnOnce(MirRelationExpr) -> MirRelationExpr, 

Replaces self with some logic applied to self.

pub fn let_in<Body>(self, id_gen: &mut IdGen, body: Body) -> MirRelationExpr where
    Body: FnOnce(&mut IdGen, MirRelationExpr) -> MirRelationExpr, 

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

pub fn anti_lookup(
    self,
    id_gen: &mut IdGen,
    keys_and_values: MirRelationExpr,
    default: Vec<(Datum<'_>, ColumnType)>
) -> MirRelationExpr

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)

pub fn lookup(
    self,
    id_gen: &mut IdGen,
    keys_and_values: MirRelationExpr,
    default: Vec<(Datum<'static>, ColumnType)>
) -> MirRelationExpr

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.)

pub fn declare_keys(self, keys: Vec<Vec<usize>>) -> Self

Passes the collection through unchanged, but informs the optimizer that keys are primary keys.

pub fn try_visit_children<'a, F, E>(&'a self, f: F) -> Result<(), E> where
    F: FnMut(&'a MirRelationExpr) -> Result<(), E>,
    E: From<RecursionLimitError>, 

Applies a fallible immutable f to each child of type MirRelationExpr.

pub fn try_visit_mut_children<'a, F, E>(&'a mut self, f: F) -> Result<(), E> where
    F: FnMut(&'a mut MirRelationExpr) -> Result<(), E>,
    E: From<RecursionLimitError>, 

Applies a fallible mutable f to each child of type MirRelationExpr.

pub fn visit_children<'a, F>(&'a self, f: F) where
    F: FnMut(&'a MirRelationExpr), 

Applies an infallible immutable f to each child of type MirRelationExpr.

pub fn visit_mut_children<'a, F>(&'a mut self, f: F) where
    F: FnMut(&'a mut MirRelationExpr), 

Applies an infallible mutable f to each child of type MirRelationExpr.

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

Post-order immutable fallible MirRelationExpr visitor.

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

Post-order mutable fallible MirRelationExpr visitor.

pub fn visit_post<'a, F>(&'a self, f: &mut F) where
    F: FnMut(&'a MirRelationExpr), 

Post-order immutable infallible MirRelationExpr visitor.

pub fn visit_mut_post<F>(&mut self, f: &mut F) where
    F: FnMut(&mut MirRelationExpr), 

Post-order mutable infallible MirRelationExpr visitor.

pub fn try_visit_pre<F, E>(&self, f: &mut F) -> Result<(), E> where
    F: FnMut(&MirRelationExpr) -> Result<(), E>,
    E: From<RecursionLimitError>, 

Pre-order immutable fallible MirRelationExpr visitor.

pub fn try_visit_mut_pre<F, E>(&mut self, f: &mut F) -> Result<(), E> where
    F: FnMut(&mut MirRelationExpr) -> Result<(), E>,
    E: From<RecursionLimitError>, 

Pre-order mutable fallible MirRelationExpr visitor.

pub fn visit_pre<F>(&self, f: &mut F) where
    F: FnMut(&MirRelationExpr), 

Pre-order immutable infallible MirRelationExpr visitor.

pub fn visit_mut_pre<F>(&mut self, f: &mut F) where
    F: FnMut(&mut MirRelationExpr), 

Pre-order mutable infallible MirRelationExpr visitor.

pub fn visit_pre_post<F1, F2>(&self, pre: &mut F1, post: &mut F2) where
    F1: FnMut(&MirRelationExpr) -> Option<Vec<&MirRelationExpr>>,
    F2: FnMut(&MirRelationExpr), 

A generalization of Self::visit_pre and Self::visit_post.

The function pre runs on a MirRelationExpr before it runs on any of the child MirRelationExprs. The function post runs on child MirRelationExprs first before the parent.

Optionally, pre can return which child MirRelationExprs, if any, should be visited (default is to visit all children).

pub fn try_visit_scalars_mut1<F, E>(&mut self, f: &mut F) -> Result<(), E> where
    F: FnMut(&mut MirScalarExpr) -> Result<(), E>, 

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

The f visitor should not recursively descend into owned MirRelationExprs.

pub fn try_visit_scalars_mut<F, E>(&mut self, f: &mut F) -> Result<(), E> where
    F: FnMut(&mut MirScalarExpr) -> Result<(), E>,
    E: From<RecursionLimitError>, 

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.

pub fn visit_scalars_mut<F>(&mut self, f: &mut F) where
    F: FnMut(&mut MirScalarExpr), 

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.

Trait Implementations

impl Clone for MirRelationExpr

fn clone(&self) -> MirRelationExpr

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MirRelationExpr

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MirRelationExpr

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl Hash for MirRelationExpr

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl MzReflect for MirRelationExpr

fn add_to_reflected_type_info(rti: &mut ReflectedTypeInfo)

Adds names and types of the fields of the struct or enum to rti.

impl PartialEq<MirRelationExpr> for MirRelationExpr

fn eq(&self, other: &MirRelationExpr) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &MirRelationExpr) -> bool

This method tests for !=.

impl Serialize for MirRelationExpr

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl Eq for MirRelationExpr

impl StructuralEq for MirRelationExpr

impl StructuralPartialEq for MirRelationExpr