Struct JoinInputMapper

pub struct JoinInputMapper {
    arities: Vec<usize>,
    input_relation: Vec<usize>,
    prior_arities: Vec<usize>,
}

Any column in a join expression exists in two contexts:

1. It has a position relative to the result of the join (global)
2. It has a position relative to the specific input it came from (local) This utility focuses on taking expressions that are in terms of the local input and re-expressing them in global terms and vice versa.

Methods in this class that take an argument equivalences are only guaranteed to return a correct answer if equivalence classes are in canonical form. (See crate::relation::canonicalize::canonicalize_equivalences.)

Fields

arities: Vec<usize>

The number of columns per input. All other fields in this struct are derived using the information in this field.

input_relation: Vec<usize>

Looks up which input each column belongs to. Derived from arities. Stored as a field to avoid recomputation.

prior_arities: Vec<usize>

The sum of the arities of the previous inputs in the join. Derived from arities. Stored as a field to avoid recomputation.

Implementations

impl JoinInputMapper

pub fn new(inputs: &[MirRelationExpr]) -> Self

Creates a new JoinInputMapper and calculates the mapping of global context columns to local context columns.

pub fn new_from_input_types(types: &[RelationType]) -> Self

Creates a new JoinInputMapper and calculates the mapping of global context columns to local context columns. Using this method saves is more efficient if input types have been pre-calculated

pub fn new_from_input_arities<I>(arities: I) -> Self

where I: IntoIterator<Item = usize>,

Creates a new JoinInputMapper and calculates the mapping of global context columns to local context columns. Using this method saves is more efficient if input arities have been pre-calculated

pub fn total_columns(&self) -> usize

reports sum of the number of columns of each input

pub fn total_inputs(&self) -> usize

reports total numbers of inputs in the join

pub fn global_keys<'a, I>( &self, local_keys: I, equivalences: &[Vec<MirScalarExpr>], ) -> Vec<Vec<usize>>

where I: Iterator<Item = &'a Vec<Vec<usize>>>,

Using the keys that came from each local input, figures out which keys remain unique in the larger join Currently, we only figure out a small subset of the keys that can remain unique.

pub fn input_arity(&self, index: usize) -> usize

returns the arity for a particular input

pub fn local_columns(&self, index: usize) -> Range<usize>

All column numbers in order for a particular input in the local context

pub fn global_columns(&self, index: usize) -> Range<usize>

All column numbers in order for a particular input in the global context

pub fn map_expr_to_local(&self, expr: MirScalarExpr) -> MirScalarExpr

Takes an expression from the global context and creates a new version where column references have been remapped to the local context. Assumes that all columns in expr are from the same input.

pub fn map_expr_to_global( &self, expr: MirScalarExpr, index: usize, ) -> MirScalarExpr

Takes an expression from the local context of the indexth input and creates a new version where column references have been remapped to the global context.

pub fn map_column_to_local(&self, column: usize) -> (usize, usize)

Remap column numbers from the global to the local context. Returns a 2-tuple (<new column number>, <index of input>)

pub fn map_column_to_global(&self, column: usize, index: usize) -> usize

Remap a column number from a local context to the global context.

pub fn split_column_set_by_input<'a, I>( &self, columns: I, ) -> Vec<BTreeSet<usize>>

where I: Iterator<Item = &'a usize>,

Takes a sequence of columns in the global context and splits it into a Vec containing self.total_inputs() BTreeSets, each containing the localized columns that belong to the particular input.

pub fn lookup_inputs( &self, expr: &MirScalarExpr, ) -> impl Iterator<Item = usize> + use<>

Find the sorted, dedupped set of inputs an expression references

pub fn single_input(&self, expr: &MirScalarExpr) -> Option<usize>

Returns the index of the only input referenced in the given expression.

pub fn is_localized(&self, expr: &MirScalarExpr, index: usize) -> bool

Returns whether the given expr refers to columns of only the indexth input.

pub fn find_bound_expr( &self, expr: &MirScalarExpr, bound_inputs: &[usize], equivalences: &[Vec<MirScalarExpr>], ) -> Option<MirScalarExpr>

Takes an expression in the global context and looks in equivalences for an equivalent expression (also expressed in the global context) that belongs to one or more of the inputs in bound_inputs

Examples

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

// A two-column schema common to each of the three inputs
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)];
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());

// [input0(#0) = input2(#1)], [input0(#1) = input1(#0) = input2(#0)]
let equivalences = vec![
  vec![MirScalarExpr::column(0), MirScalarExpr::column(5)],
  vec![MirScalarExpr::column(1), MirScalarExpr::column(2), MirScalarExpr::column(4)],
];

let input_mapper = JoinInputMapper::new(&[input0, input1, input2]);
assert_eq!(
  Some(MirScalarExpr::column(4)),
  input_mapper.find_bound_expr(&MirScalarExpr::column(2), &[2], &equivalences)
);
assert_eq!(
  None,
  input_mapper.find_bound_expr(&MirScalarExpr::column(0), &[1], &equivalences)
);

pub fn try_localize_to_input_with_bound_expr( &self, expr: &mut MirScalarExpr, index: usize, equivalences: &[Vec<MirScalarExpr>], ) -> bool

Try to rewrite expr from the global context so that all the columns point to the indexth input by replacing subexpressions with their bound equivalents in the indexth input if necessary. Returns whether the rewriting was successful. If it returns true, then expr is in the context of the indexth input. If it returns false, then still some subexpressions might have been rewritten. However, expr is still in the global context.

pub fn consequence_for_input( &self, expr: &MirScalarExpr, index: usize, ) -> Option<MirScalarExpr>

Try to find a consequence c of the given expression e for the given input.

If we return Some(c), that means

1. c uses only columns from the given input;
2. if c doesn’t hold on a row of the input, then e also wouldn’t hold;
3. if c holds on a row of the input, then e might or might not hold.
4. and 2. means that if we have a join with predicate e then we can use c for pre-filtering a join input before the join. However, 3. means that e shouldn’t be deleted from the join predicates, i.e., we can’t do a “traditional” predicate pushdown.

Note that “c is a consequence of e” is the same thing as 2., see https://en.wikipedia.org/wiki/Contraposition

Example: For (t1.f2 = 3 AND t2.f2 = 4) OR (t1.f2 = 5 AND t2.f2 = 6) we find t1.f2 = 3 OR t1.f2 = 5 for t1, and t2.f2 = 4 OR t2.f2 = 6 for t2.

Further examples are in TPC-H Q07, Q19, and chbench Q07, Q19.

Parameters:

• expr: The expression e from above. try_localize_to_input_with_bound_expr should be called on expr before us!
• index: The index of the join input whose columns we will use.
• equivalences: Join equivalences that we can use for try_map_to_input_with_bound_expr. If successful, the returned expression is in the local context of the specified input.

Trait Implementations

impl Debug for JoinInputMapper

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

Formats the value using the given formatter.