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.
(
&self,
mut local_keys: I,
equivalences: &[Vec<MirScalarExpr>],
)
| 98 | /// Currently, we only figure out a small subset of the keys that |
| 99 | /// can remain unique. |
| 100 | pub fn global_keys<'a, I>( |
| 101 | &self, |
| 102 | mut local_keys: I, |
| 103 | equivalences: &[Vec<MirScalarExpr>], |
| 104 | ) -> Vec<Vec<usize>> |
| 105 | where |
| 106 | I: Iterator<Item = &'a Vec<Vec<usize>>>, |
| 107 | { |
| 108 | // A relation's uniqueness constraint holds if there is a |
| 109 | // sequence of the other relations such that each one has |
| 110 | // a uniqueness constraint whose columns are used in join |
| 111 | // constraints with relations prior in the sequence. |
| 112 | // |
| 113 | // Currently, we only: |
| 114 | // 1. test for whether the uniqueness constraints for the first input will hold |
| 115 | // 2. try one sequence, namely the inputs in order |
| 116 | // 3. check that the column themselves are used in the join constraints |
| 117 | // Technically uniqueness constraint would still hold if a 1-to-1 |
| 118 | // expression on a unique key is used in the join constraint. |
| 119 | |
| 120 | // for inputs `1..self.total_inputs()`, store a set of columns from that |
| 121 | // input that exist in join constraints that have expressions belonging to |
| 122 | // earlier inputs. |
| 123 | let mut column_with_prior_bound_by_input = vec![BTreeSet::new(); self.total_inputs() - 1]; |
| 124 | for equivalence in equivalences { |
| 125 | // do a scan to find the first input represented in the constraint |
| 126 | let min_bound_input = equivalence |
| 127 | .iter() |
| 128 | .flat_map(|expr| self.lookup_inputs(expr).max()) |
| 129 | .min(); |
| 130 | if let Some(min_bound_input) = min_bound_input { |
| 131 | for expr in equivalence { |
| 132 | // then store all columns in the constraint that don't come |
| 133 | // from the first input |
| 134 | if let MirScalarExpr::Column(c, _name) = expr { |
| 135 | let (col, input) = self.map_column_to_local(*c); |
| 136 | if input > min_bound_input { |
| 137 | column_with_prior_bound_by_input[input - 1].insert(col); |
| 138 | } |
| 139 | } |
| 140 | } |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | if self.total_inputs() > 0 { |
| 145 | let first_input_keys = local_keys.next().unwrap().clone(); |
| 146 | // for inputs `1..self.total_inputs()`, checks the keys belong to each |
| 147 | // input against the storage of columns that exist in join constraints |
| 148 | // that have expressions belonging to earlier inputs. |
| 149 | let remains_unique = local_keys.enumerate().all(|(index, keys)| { |
| 150 | keys.iter().any(|ks| { |
| 151 | ks.iter() |
| 152 | .all(|k| column_with_prior_bound_by_input[index].contains(k)) |
| 153 | }) |
| 154 | }); |
| 155 | |
| 156 | if remains_unique { |
| 157 | return first_input_keys; |
no test coverage detected