Struct dataflow_types::plan::Permutation

pub struct Permutation { /* fields omitted */ }

A permutation is applied to a Row split into a key and a value part, and presents it as if it is the row containing as its columns the columns referenced by permutation. The key_arity describes how many columns are in the key, which is important when joining relations and forming joint permutations.

Arrangements conceptually store data split in key-value pairs, where all data is grouped by the key. It is desirable to remove redundancy between the key and value by not repeating columns in the value that are already present in the key. This struct provides an abstraction to encode this deduplication of columns in the key.

A Permutation consists of two parts: An expression to thin the columns in the value and a permutation defined on the key appended with the value to reconstruct the original value.

Example of an identity permutation

For identity mappings, the thinning leaves the value as-is and the permutation restores the original order of elements

• Input: key expressions of length n: [key_0, ..., key_n]; arity of the row
• Thinning: [0, ..., arity]
• Permutation: [n, ..., n + arity]

Example of a non-identity permutation

We remove all columns from a row that are present in the key.

• Input: key expressions of length n: [key_0, ..., key_n]; arity of the row
• Thinning: [i \in 0, ..., arity | key_i != column reference]
• Permutation: for each column i in the input:
  • if i is in the key: offset of Column(i) in key
  • offset in thinned row

Joining permutations

For joined relations with thinned values, we need to construct a joined permutation to undo the thinning. Let’s assume a join produces rows of the form [key, value_1, value_2] where the inputs where of the form [key, value_1] and [key, value_2] and the join groups on the key.

Conceptually, the joined permutation is the permutation of the left relation appended with the permutation of the right permutation. The right permutation needs to be offset by the length of the thinned values of the left relation, while keeping key references unchanged.

• Input 1: Key Column(0), value Column(1), permutation [0, 1]
• Input 2: Key Column(0), value Column(1), Column(2), permutation [0, 1, 2]
• Joined relation:
  0. Key Column(0),
  1. Value Column(1) of input 1,
  2. Key Column(0),
  3. Column(1) of input 2,
  4. Column(2) of input 2.
• Result: Key Column(0), permutation [0, 1, 0, 2, 3]

Implementations

impl Permutation

pub fn construct_from_columns(
    key_cols: &[usize],
    arity: usize
) -> (Self, Vec<usize>)

Construct a permutation and thinning expression from a key description and the relation’s arity.

This constructs a permutation that removes redundant columns from the value if they are part of the key.

pub fn identity(key_arity: usize, arity: usize) -> Self

Construct an identity Permutation that expects all data in the value.

pub fn join(&self, other: &Self) -> Self

Compute the join of two permutations.

This assumes two relations [key, value_1] and [key, value_2] are joined into [key, value_1, value_2] and constructs a permutation accordingly.

pub fn permute_in_place<T: Copy>(&self, data: &mut Vec<T>)

Permute a [key, value] row to reconstruct a non-permuted variant.

The function truncates the data to the length of the permutation, which should match the expectation of any subsequent map/filter/project or operator.

Example

let mut datum_vec = DatumVec::new();
let mut borrow = datum_vec.borrow_with_many(&[&key, &val]);
permutation.permute_in_place(&mut borrow);

pub fn arity(&self) -> usize

The arity of the permutation

pub fn permute_mfp(&self, mfp: &mut MapFilterProject)

Prepares the MFP mfp to act on permuted input, according to this permutation

pub fn permute_mfp_plan(&self, mfp: &mut MfpPlan)

Prepares the MfpPlan mfp to act on permuted input, according to this permutation

pub fn permute_safe_mfp_plan(&self, mfp: &mut SafeMfpPlan)

Prepares the SafeMfpPlan mfp to act on permuted input, according to this permutation

Trait Implementations

impl Clone for Permutation

fn clone(&self) -> Permutation

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Permutation

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for Permutation

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

Deserialize this value from the given Serde deserializer.

impl Serialize for Permutation

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

Serialize this value into the given Serde serializer.