Struct DependencyMap 

pub struct DependencyMap {
    map: IndexMap<PhysicalSortExpr, DependencyNode>,
}

Maps an expression –> DependencyNode

Debugging / deplaying DependencyMap

This structure implements Display to assist debugging. For example:

DependencyMap: {
  a@0 ASC --> (target: a@0 ASC, dependencies: [[]])
  b@1 ASC --> (target: b@1 ASC, dependencies: [[a@0 ASC, c@2 ASC]])
  c@2 ASC --> (target: c@2 ASC, dependencies: [[b@1 ASC, a@0 ASC]])
  d@3 ASC --> (target: d@3 ASC, dependencies: [[c@2 ASC, b@1 ASC]])
}

Note on IndexMap Rationale

Using IndexMap (which preserves insert order) to ensure consistent results across different executions for the same query. We could have used HashSet and HashMap instead without any loss of functionality.

As an example, if existing orderings are

1. [a ASC, b ASC]
2. [c ASC]

Then both the following output orderings are valid

1. [a ASC, b ASC, c ASC]
2. [c ASC, a ASC, b ASC]

These are both valid as they are concatenated versions of the alternative orderings. Had we used HashSet/HashMap, we couldn’t guarantee to generate the same result among the possible two results in the example above.

Fields

map: IndexMap<PhysicalSortExpr, DependencyNode>

Implementations

impl DependencyMap

pub fn insert( &mut self, sort_expr: PhysicalSortExpr, target_sort_expr: Option<PhysicalSortExpr>, dependency: Option<PhysicalSortExpr>, )

Insert a new dependency of sort_expr (i.e. dependency) into the map along with its target sort expression.

Methods from Deref<Target = IndexMap<PhysicalSortExpr, DependencyNode>>

pub fn capacity(&self) -> usize

Return the number of elements the map can hold without reallocating.

This number is a lower bound; the map might be able to hold more, but is guaranteed to be able to hold at least this many.

Computes in O(1) time.

pub fn hasher(&self) -> &S

Return a reference to the map’s BuildHasher.

pub fn len(&self) -> usize

Return the number of key-value pairs in the map.

Computes in O(1) time.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Computes in O(1) time.

pub fn iter(&self) -> Iter<'_, K, V>

Return an iterator over the key-value pairs of the map, in their order

pub fn keys(&self) -> Keys<'_, K, V>

Return an iterator over the keys of the map, in their order

pub fn values(&self) -> Values<'_, K, V>

Return an iterator over the values of the map, in their order

pub fn contains_key<Q>(&self, key: &Q) -> bool

where Q: Hash + Equivalent<K> + ?Sized,

Return true if an equivalent to key exists in the map.

Computes in O(1) time (average).

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where Q: Hash + Equivalent<K> + ?Sized,

Return a reference to the stored value for key, if it is present, else None.

Computes in O(1) time (average).

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>

where Q: Hash + Equivalent<K> + ?Sized,

Return references to the stored key-value pair for the lookup key, if it is present, else None.

Computes in O(1) time (average).

pub fn get_full<Q>(&self, key: &Q) -> Option<(usize, &K, &V)>

where Q: Hash + Equivalent<K> + ?Sized,

Return the index with references to the stored key-value pair for the lookup key, if it is present, else None.

Computes in O(1) time (average).

pub fn get_index_of<Q>(&self, key: &Q) -> Option<usize>

where Q: Hash + Equivalent<K> + ?Sized,

Return the item index for key, if it is present, else None.

Computes in O(1) time (average).

pub fn binary_search_keys(&self, x: &K) -> Result<usize, usize>

where K: Ord,

Search over a sorted map for a key.

Returns the position where that key is present, or the position where it can be inserted to maintain the sort. See slice::binary_search for more details.

Computes in O(log(n)) time, which is notably less scalable than looking the key up using [get_index_of][IndexMap::get_index_of], but this can also position missing keys.

pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>

where F: FnMut(&'a K, &'a V) -> Ordering,

Search over a sorted map with a comparator function.

Returns the position where that value is present, or the position where it can be inserted to maintain the sort. See slice::binary_search_by for more details.

Computes in O(log(n)) time.

pub fn binary_search_by_key<'a, B, F>( &'a self, b: &B, f: F, ) -> Result<usize, usize>

where F: FnMut(&'a K, &'a V) -> B, B: Ord,

Search over a sorted map with an extraction function.

Returns the position where that value is present, or the position where it can be inserted to maintain the sort. See slice::binary_search_by_key for more details.

Computes in O(log(n)) time.

pub fn is_sorted(&self) -> bool

where K: PartialOrd,

Checks if the keys of this map are sorted.

pub fn is_sorted_by<'a, F>(&'a self, cmp: F) -> bool

where F: FnMut(&'a K, &'a V, &'a K, &'a V) -> bool,

Checks if this map is sorted using the given comparator function.

pub fn is_sorted_by_key<'a, F, T>(&'a self, sort_key: F) -> bool

where F: FnMut(&'a K, &'a V) -> T, T: PartialOrd,

Checks if this map is sorted using the given sort-key function.

pub fn partition_point<P>(&self, pred: P) -> usize

where P: FnMut(&K, &V) -> bool,

Returns the index of the partition point of a sorted map according to the given predicate (the index of the first element of the second partition).

See slice::partition_point for more details.

Computes in O(log(n)) time.

pub fn as_slice(&self) -> &Slice<K, V>

Returns a slice of all the key-value pairs in the map.

Computes in O(1) time.

pub fn get_index(&self, index: usize) -> Option<(&K, &V)>

Get a key-value pair by index

Valid indices are 0 <= index < self.len().

Computes in O(1) time.

pub fn get_range<R>(&self, range: R) -> Option<&Slice<K, V>>

where R: RangeBounds<usize>,

Returns a slice of key-value pairs in the given range of indices.

Valid indices are 0 <= index < self.len().

Computes in O(1) time.

pub fn first(&self) -> Option<(&K, &V)>

Get the first key-value pair

Computes in O(1) time.

pub fn last(&self) -> Option<(&K, &V)>

Get the last key-value pair

Computes in O(1) time.

Trait Implementations

impl Debug for DependencyMap

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

Formats the value using the given formatter.

impl Default for DependencyMap

fn default() -> DependencyMap

Returns the “default value” for a type.

impl Deref for DependencyMap

type Target = IndexMap<PhysicalSortExpr, DependencyNode>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl Display for DependencyMap

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

Formats the value using the given formatter.