1use std::cmp::Ordering;
10use std::collections::btree_map::Entry;
11use std::collections::BTreeMap;
12use std::collections::Bound::Included;
13use std::mem;
14use std::ops::Bound::Excluded;
15
16use either::{Left, Right};
17use itertools::Itertools;
18use miette::Result;
19
20use crate::data::aggr::Aggregation;
21use crate::data::tuple::Tuple;
22use crate::data::value::DataValue;
23
24#[derive(Default, Debug)]
27pub struct RegularTempStore {
28 inner: BTreeMap<Tuple, bool>,
29}
30
31const EMPTY_TUPLE_REF: &Tuple = &vec![];
32
33impl RegularTempStore {
34 pub(crate) fn wrap(self) -> TempStore {
35 TempStore::Normal(self)
36 }
37 pub fn exists(&self, key: &Tuple) -> bool {
39 self.inner.contains_key(key)
40 }
41
42 fn range_iter<'a>(
43 &'a self,
44 lower: &Tuple,
45 upper: &Tuple,
46 upper_inclusive: bool,
47 ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
48 let lower_bound = Included(lower.to_vec());
49 let upper_bound = if upper_inclusive {
50 Included(upper.to_vec())
51 } else {
52 Excluded(upper.to_vec())
53 };
54 self.inner
55 .range((lower_bound, upper_bound))
56 .map(|(t, skip)| TupleInIter(t, EMPTY_TUPLE_REF, *skip))
57 }
58 pub fn put(&mut self, tuple: Tuple) {
60 self.inner.insert(tuple, false);
61 }
62 pub(crate) fn put_with_skip(&mut self, tuple: Tuple) {
63 self.inner.insert(tuple, true);
64 }
65 pub(crate) fn merge_in(&mut self, prev: &mut Self, mut new: Self) -> bool {
68 prev.inner.clear();
69 if new.inner.is_empty() {
70 return false;
71 }
72 if self.inner.is_empty() {
73 mem::swap(&mut new, self);
74 return true;
75 }
76 for (k, v) in new.inner {
77 match self.inner.entry(k) {
78 Entry::Vacant(ent) => {
79 prev.inner.insert(ent.key().clone(), v);
80 ent.insert(v);
81 }
82 Entry::Occupied(mut ent) => {
83 ent.insert(v);
84 }
85 }
86 }
87 false
88 }
89}
90
91#[derive(Debug)]
92pub(crate) struct MeetAggrStore {
93 inner: BTreeMap<Tuple, Tuple>,
94 aggregations: Vec<(Aggregation, Vec<DataValue>)>,
95 grouping_len: usize,
96}
97
98impl MeetAggrStore {
99 pub(crate) fn wrap(self) -> TempStore {
100 TempStore::MeetAggr(self)
101 }
102 pub(crate) fn exists(&self, key: &Tuple) -> bool {
103 let truncated = &key[0..self.grouping_len];
104 self.inner.contains_key(truncated)
105 }
106 pub(crate) fn is_empty(&self) -> bool {
107 self.inner.is_empty()
108 }
109 pub(crate) fn new(aggrs: Vec<Option<(Aggregation, Vec<DataValue>)>>) -> Result<Self> {
110 let total_key_len = aggrs.len();
111 let mut aggregations = aggrs.into_iter().flatten().collect_vec();
112 for (aggr, args) in aggregations.iter_mut() {
113 aggr.meet_init(args)?;
114 }
115 let grouping_len = total_key_len - aggregations.len();
116 Ok(Self {
117 inner: Default::default(),
118 aggregations,
119 grouping_len,
120 })
121 }
122 pub(crate) fn meet_put(&mut self, tuple: Tuple) -> Result<bool> {
125 let (key_part, val_part) = tuple.split_at(self.grouping_len);
126 match self.inner.get_mut(key_part) {
127 Some(prev_aggr) => {
128 let mut changed = false;
129 for (i, (aggr_op, _)) in self.aggregations.iter().enumerate() {
130 let op = aggr_op.meet_op.as_ref().unwrap();
131 changed |= op.update(&mut prev_aggr[i], &val_part[i])?;
132 }
133 Ok(changed)
134 }
135 None => {
136 self.inner.insert(key_part.to_vec(), val_part.to_vec());
137 Ok(true)
138 }
139 }
140 }
141 fn range_iter<'a>(
142 &'a self,
143 lower: &Tuple,
144 upper: &Tuple,
145 upper_inclusive: bool,
146 ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
147 let lower_key = if lower.len() > self.grouping_len {
148 lower[0..self.grouping_len].to_vec()
149 } else {
150 lower.to_vec()
151 };
152 let upper_key = if upper.len() > self.grouping_len {
153 upper[0..self.grouping_len].to_vec()
154 } else {
155 upper.to_vec()
156 };
157 let lower = lower.to_vec();
158 let upper = upper.to_vec();
159 self.inner
160 .range(lower_key..=upper_key)
161 .filter_map(move |(k, v)| {
162 let ret = TupleInIter(k, v, false);
163 if ret.partial_cmp(&lower as &[DataValue]) == Some(Ordering::Less) {
164 None
165 } else {
166 match ret.partial_cmp(&upper as &[DataValue]).unwrap() {
167 Ordering::Less => Some(ret),
168 Ordering::Equal => {
169 if upper_inclusive {
170 Some(ret)
171 } else {
172 None
173 }
174 }
175 Ordering::Greater => None,
176 }
177 }
178 })
179 }
180 pub(crate) fn merge_in(&mut self, prev: &mut Self, mut new: Self) -> Result<bool> {
183 prev.inner.clear();
184 if new.inner.is_empty() {
185 return Ok(false);
186 }
187 if self.inner.is_empty() {
188 mem::swap(self, &mut new);
189 return Ok(true);
190 }
191 for (k, v) in new.inner {
192 match self.inner.entry(k) {
193 Entry::Vacant(ent) => {
194 prev.inner.insert(ent.key().clone(), v.clone());
195 ent.insert(v);
196 }
197 Entry::Occupied(mut ent) => {
198 let mut changed = false;
199 {
200 let target = ent.get_mut();
201 for (i, (aggr_op, _)) in self.aggregations.iter().enumerate() {
202 let op = aggr_op.meet_op.as_ref().unwrap();
203 changed |= op.update(&mut target[i], &v[i])?;
204 }
205 }
206 if changed {
207 prev.inner.insert(ent.key().clone(), ent.get().clone());
208 }
209 }
210 }
211 }
212 Ok(false)
213 }
214}
215
216#[derive(Debug)]
217pub(crate) enum TempStore {
218 Normal(RegularTempStore),
219 MeetAggr(MeetAggrStore),
220}
221
222impl TempStore {
223 fn exists(&self, key: &Tuple) -> bool {
224 match self {
225 TempStore::Normal(n) => n.exists(key),
226 TempStore::MeetAggr(m) => m.exists(key),
227 }
228 }
229 fn range_iter<'a>(
230 &'a self,
231 lower: &Tuple,
232 upper: &Tuple,
233 upper_inclusive: bool,
234 ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
235 match self {
236 TempStore::Normal(n) => Left(n.range_iter(lower, upper, upper_inclusive)),
237 TempStore::MeetAggr(m) => Right(m.range_iter(lower, upper, upper_inclusive)),
238 }
239 }
240 fn is_empty(&self) -> bool {
241 match self {
242 TempStore::Normal(n) => n.inner.is_empty(),
243 TempStore::MeetAggr(m) => m.inner.is_empty(),
244 }
245 }
246}
247
248#[derive(Debug)]
249pub(crate) struct EpochStore {
250 total: TempStore,
251 delta: TempStore,
252 use_total_for_delta: bool,
253 pub(crate) arity: usize,
254}
255
256impl EpochStore {
257 pub(crate) fn exists(&self, key: &Tuple) -> bool {
258 self.total.exists(key)
259 }
260 pub(crate) fn new_normal(arity: usize) -> Self {
261 Self {
262 total: TempStore::Normal(RegularTempStore::default()),
263 delta: TempStore::Normal(RegularTempStore::default()),
264 use_total_for_delta: true,
265 arity,
266 }
267 }
268 pub(crate) fn new_meet(aggrs: &[Option<(Aggregation, Vec<DataValue>)>]) -> Result<Self> {
269 Ok(Self {
270 total: TempStore::MeetAggr(MeetAggrStore::new(aggrs.to_vec())?),
271 delta: TempStore::MeetAggr(MeetAggrStore::new(aggrs.to_vec())?),
272 use_total_for_delta: true,
273 arity: aggrs.len(),
274 })
275 }
276 pub(crate) fn merge_in(&mut self, new: TempStore) -> Result<()> {
277 match (&mut self.total, &mut self.delta, new) {
278 (TempStore::Normal(total), TempStore::Normal(prev), TempStore::Normal(new)) => {
279 self.use_total_for_delta = total.merge_in(prev, new);
280 }
281 (TempStore::MeetAggr(total), TempStore::MeetAggr(prev), TempStore::MeetAggr(new)) => {
282 self.use_total_for_delta = total.merge_in(prev, new)?;
283 }
284 _ => unreachable!(),
285 }
286 Ok(())
287 }
288 pub(crate) fn has_delta(&self) -> bool {
289 if self.use_total_for_delta {
290 !self.total.is_empty()
291 } else {
292 !self.delta.is_empty()
293 }
294 }
295 pub(crate) fn range_iter<'a>(
296 &'a self,
297 lower: &Tuple,
298 upper: &Tuple,
299 upper_inclusive: bool,
300 ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
301 self.total.range_iter(lower, upper, upper_inclusive)
302 }
303 pub(crate) fn delta_range_iter<'a>(
304 &'a self,
305 lower: &Tuple,
306 upper: &Tuple,
307 upper_inclusive: bool,
308 ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
309 if self.use_total_for_delta {
310 self.total.range_iter(lower, upper, upper_inclusive)
311 } else {
312 self.delta.range_iter(lower, upper, upper_inclusive)
313 }
314 }
315 pub(crate) fn prefix_iter<'a>(&'a self, prefix: &Tuple) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
316 let mut upper = prefix.to_vec();
317 upper.push(DataValue::Bot);
318 self.range_iter(prefix, &upper, true)
319 }
320 pub(crate) fn delta_prefix_iter<'a>(
321 &'a self,
322 prefix: &Tuple,
323 ) -> impl Iterator<Item = TupleInIter<'a>> + use<'a> {
324 let mut upper = prefix.to_vec();
325 upper.push(DataValue::Bot);
326 self.delta_range_iter(prefix, &upper, true)
327 }
328 pub(crate) fn all_iter(&self) -> impl Iterator<Item = TupleInIter<'_>> {
329 self.prefix_iter(&vec![])
330 }
331 pub(crate) fn delta_all_iter(&self) -> impl Iterator<Item = TupleInIter<'_>> {
332 self.delta_prefix_iter(&vec![])
333 }
334 pub(crate) fn early_returned_iter(&self) -> impl Iterator<Item = TupleInIter<'_>> {
335 self.all_iter().filter(|t| !t.should_skip())
336 }
337}
338
339#[derive(Copy, Clone)]
340pub(crate) struct TupleInIter<'a>(&'a Tuple, &'a Tuple, bool);
341
342impl<'a> TupleInIter<'a> {
343 pub(crate) fn get(self, idx: usize) -> &'a DataValue {
344 self.0
345 .get(idx)
346 .unwrap_or_else(|| self.1.get(idx - self.0.len()).unwrap())
347 }
348 fn should_skip(&self) -> bool {
349 self.2
350 }
351 pub(crate) fn into_tuple(self) -> Tuple {
352 self.into_iter().cloned().collect_vec()
353 }
354}
355
356impl<'a> IntoIterator for TupleInIter<'a> {
357 type Item = &'a DataValue;
358 type IntoIter = TupleInIterIterator<'a>;
359
360 fn into_iter(self) -> Self::IntoIter {
361 TupleInIterIterator {
362 inner: self,
363 idx: 0,
364 }
365 }
366}
367
368pub(crate) struct TupleInIterIterator<'a> {
369 inner: TupleInIter<'a>,
370 idx: usize,
371}
372
373impl PartialEq for TupleInIter<'_> {
374 fn eq(&self, other: &Self) -> bool {
375 self.into_iter().eq(other.into_iter())
376 }
377}
378
379impl Eq for TupleInIter<'_> {}
380
381impl Ord for TupleInIter<'_> {
382 fn cmp(&self, other: &Self) -> Ordering {
383 self.into_iter().cmp(other.into_iter())
384 }
385}
386
387impl PartialOrd for TupleInIter<'_> {
388 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
389 Some(self.cmp(other))
390 }
391}
392
393impl PartialEq<[DataValue]> for TupleInIter<'_> {
394 fn eq(&self, other: &'_ [DataValue]) -> bool {
395 self.into_iter().eq(other.iter())
396 }
397}
398
399impl PartialOrd<[DataValue]> for TupleInIter<'_> {
400 fn partial_cmp(&self, other: &'_ [DataValue]) -> Option<Ordering> {
401 self.into_iter().partial_cmp(other.iter())
402 }
403}
404
405impl<'a> Iterator for TupleInIterIterator<'a> {
406 type Item = &'a DataValue;
407
408 fn next(&mut self) -> Option<Self::Item> {
409 let ret = match self.inner.0.get(self.idx) {
410 Some(d) => d,
411 None => match self.inner.1.get(self.idx - self.inner.0.len()) {
412 None => return None,
413 Some(d) => d,
414 },
415 };
416 self.idx += 1;
417 Some(ret)
418 }
419}