Skip to main content

zero_client/ivm/
join.rs

1//! `Join`, the `TakeGate` that caps its parent fetches, and the
2//! `JoinIndexTap` that keeps EXISTS joins' parent indexes
3//! (`packages/zql/src/ivm/join.ts`, `take-gate.ts`, and
4//! `join-index-tap.ts`).
5
6use super::*;
7use crate::ast::{CorrelatedSubqueryOperator, System};
8use std::cell::{Cell, RefCell};
9use std::cmp::Ordering;
10use std::collections::HashSet;
11use std::rc::{Rc, Weak};
12
13fn upgrade<T: ?Sized>(w: &RefCell<Weak<T>>) -> Option<Rc<T>> {
14    w.borrow().upgrade()
15}
16
17/// Set when a join feeds an EXISTS or NOT EXISTS condition (`ExistsJoin` in
18/// `join.ts`). Its parent index is kept by a [`JoinIndexTap`] at the end of
19/// the pipeline.
20#[derive(Clone)]
21pub struct ExistsJoin {
22    pub op: CorrelatedSubqueryOperator,
23    pub parent_index: Rc<JoinIndex>,
24}
25
26/// What [`Join::new`] joins, and how.
27pub struct JoinArgs {
28    pub parent: Rc<dyn Input>,
29    pub child: Rc<dyn Input>,
30    pub parent_key: Vec<String>,
31    pub child_key: Vec<String>,
32    pub relationship_name: String,
33    pub hidden: bool,
34    pub system: System,
35    pub parent_partition_key: Option<Vec<String>>,
36    pub bound_provider: Option<Rc<dyn TakeBoundProvider>>,
37    pub exists: Option<ExistsJoin>,
38}
39
40/// The child change a join is pushing to its parents.
41#[derive(Default)]
42struct Inprogress {
43    change: Option<Change>,
44    /// The last parent row the change reached.
45    position: Option<Row>,
46    /// Primary keys of the parents the change reached, kept when the parent
47    /// input is unordered.
48    reached_parents: Option<HashSet<String>>,
49    parent_fetch_bounds: Option<Vec<ParentFetchBound>>,
50}
51
52/// Joins a parent and a child input into hierarchical output: each parent
53/// node gets a relationship streaming its children (`join.ts`).
54pub struct Join {
55    me: Weak<Join>,
56    parent: Rc<dyn Input>,
57    child: Rc<dyn Input>,
58    parent_key: Vec<String>,
59    child_key: Vec<String>,
60    relationship_name: String,
61    schema: Rc<SourceSchema>,
62    parent_index: Rc<JoinIndex>,
63    /// Whether this join maintains `parent_index` itself; not for EXISTS
64    /// joins.
65    indexes_parents: bool,
66    /// The child change type still pushed when no indexed parent has its
67    /// key.
68    qualifying_child_change: Option<ChangeType>,
69    bound_provider: Option<Rc<dyn TakeBoundProvider>>,
70    output: RefCell<Weak<dyn Output>>,
71    parent_output: Rc<ClosureOutput>,
72    child_output: Rc<ClosureOutput>,
73    inprogress: RefCell<Inprogress>,
74}
75
76impl Join {
77    pub fn new(args: JoinArgs) -> Rc<Self> {
78        let JoinArgs {
79            parent,
80            child,
81            parent_key,
82            child_key,
83            relationship_name,
84            hidden,
85            system,
86            parent_partition_key,
87            bound_provider,
88            exists,
89        } = args;
90        assert!(
91            !is_same(parent.as_ref(), child.as_ref()),
92            "Parent and child must be different operators"
93        );
94        assert!(
95            parent_key.len() == child_key.len(),
96            "The parentKey and childKey keys must have same length"
97        );
98        assert!(
99            exists.is_none() || parent_partition_key.is_none(),
100            "EXISTS joins are not partitioned"
101        );
102        let parent_schema = parent.get_schema();
103        let (parent_index, indexes_parents, qualifying_child_change) = match &exists {
104            Some(exists) => (
105                exists.parent_index.clone(),
106                false,
107                Some(match exists.op {
108                    CorrelatedSubqueryOperator::Exists => ChangeType::Add,
109                    CorrelatedSubqueryOperator::NotExists => ChangeType::Remove,
110                }),
111            ),
112            None => (
113                JoinIndex::new(
114                    parent_key.clone(),
115                    parent_schema.primary_key.clone(),
116                    parent_partition_key,
117                ),
118                true,
119                None,
120            ),
121        };
122        let mut child_schema = (*child.get_schema()).clone();
123        child_schema.is_hidden = hidden;
124        child_schema.system = system;
125        let schema = Rc::new(parent_schema.adding(&relationship_name, Rc::new(child_schema)));
126
127        let op = Rc::new_cyclic(|me: &Weak<Join>| {
128            let (push_parent, reconcile_parent) = (me.clone(), me.clone());
129            let (push_child, reconcile_child) = (me.clone(), me.clone());
130            Join {
131                me: me.clone(),
132                parent: parent.clone(),
133                child: child.clone(),
134                parent_key,
135                child_key,
136                relationship_name,
137                schema,
138                parent_index,
139                indexes_parents,
140                qualifying_child_change,
141                bound_provider,
142                output: RefCell::new(no_output()),
143                parent_output: ClosureOutput::new(
144                    move |c| {
145                        if let Some(j) = push_parent.upgrade() {
146                            j.push_parent(c)
147                        }
148                    },
149                    move || {
150                        if let Some(j) = reconcile_parent.upgrade() {
151                            j.reconcile_output()
152                        }
153                    },
154                ),
155                child_output: ClosureOutput::new(
156                    move |c| {
157                        if let Some(j) = push_child.upgrade() {
158                            j.push_child(c)
159                        }
160                    },
161                    move || {
162                        if let Some(j) = reconcile_child.upgrade() {
163                            j.reconcile_output()
164                        }
165                    },
166                ),
167                inprogress: RefCell::default(),
168            }
169        });
170        parent.set_output(Rc::downgrade(&op.parent_output) as Weak<dyn Output>);
171        child.set_output(Rc::downgrade(&op.child_output) as Weak<dyn Output>);
172        op
173    }
174
175    fn reconcile_output(&self) {
176        if let Some(out) = upgrade(&self.output) {
177            out.reconcile(self);
178        }
179    }
180
181    fn emit(&self, change: Change) {
182        if let Some(out) = upgrade(&self.output) {
183            out.push(change, self);
184        }
185    }
186
187    fn push_parent(&self, change: Change) {
188        match change {
189            Change::Add(node) => {
190                self.index_parent_row(&node.row);
191                self.emit(Change::Add(self.process_parent_node(&node)));
192            }
193            Change::Remove(node) => {
194                self.unindex_parent_row(&node.row);
195                self.emit(Change::Remove(self.process_parent_node(&node)));
196            }
197            Change::Child(node, child) => {
198                self.emit(Change::Child(self.process_parent_node(&node), child));
199            }
200            Change::Edit { node, old_node } => {
201                assert!(
202                    row_equals_for_compound_key(&old_node.row, &node.row, &self.parent_key),
203                    "Parent edit must not change relationship."
204                );
205                self.unindex_parent_row(&old_node.row);
206                self.index_parent_row(&node.row);
207                self.emit(Change::Edit {
208                    node: self.process_parent_node(&node),
209                    old_node: self.process_parent_node(&old_node),
210                });
211            }
212        }
213    }
214
215    fn push_child(&self, change: Change) {
216        if let Change::Edit { node, old_node } = &change {
217            assert!(
218                row_equals_for_compound_key(&old_node.row, &node.row, &self.child_key),
219                "Child edit must not change relationship."
220            );
221        }
222        let row = change.node().row.clone();
223        {
224            let mut p = self.inprogress.borrow_mut();
225            p.change = Some(change.clone());
226            p.position = None;
227            p.reached_parents = self.parent.get_schema().sort.is_none().then(HashSet::new);
228        }
229        self.push_child_change(&row, change);
230        *self.inprogress.borrow_mut() = Inprogress::default();
231    }
232
233    fn push_child_change(&self, child_row: &Row, change: Change) {
234        let Some(constraint) = build_join_constraint(child_row, &self.child_key, &self.parent_key)
235        else {
236            return;
237        };
238        let fetch_constraints: Vec<Constraint> =
239            match self.parent_index.lookup(child_row, &self.child_key) {
240                Some(partitions) => partitions
241                    .into_iter()
242                    .map(|p| match p {
243                        Some(p) => constraint.merging(&p),
244                        None => constraint.clone(),
245                    })
246                    .collect(),
247                None if Some(change.change_type()) == self.qualifying_child_change => {
248                    vec![constraint]
249                }
250                None => return,
251            };
252        if let Some(provider) = &self.bound_provider {
253            self.inprogress.borrow_mut().parent_fetch_bounds = Some(read_parent_fetch_bounds(
254                provider.as_ref(),
255                &fetch_constraints,
256            ));
257        }
258        let fetch = |c: Constraint| {
259            self.parent.fetch(&FetchRequest {
260                constraint: Some(c),
261                ..FetchRequest::default()
262            })
263        };
264        let parent_nodes: NodeStream = if fetch_constraints.len() == 1 {
265            fetch(fetch_constraints.into_iter().next().unwrap())
266        } else {
267            let compare = self.schema.compare_rows.clone();
268            merge_sorted_streams(
269                fetch_constraints.into_iter().map(fetch).collect(),
270                Rc::new(move |a: &Node, b: &Node| compare(&a.row, &b.row)),
271            )
272        };
273        for parent_node in parent_nodes {
274            {
275                let mut p = self.inprogress.borrow_mut();
276                p.position = Some(parent_node.row.clone());
277                if let Some(reached) = &mut p.reached_parents {
278                    reached.insert(canonical_key(&parent_node.row, &self.schema.primary_key));
279                }
280            }
281            self.emit(Change::child(
282                self.process_parent_node(&parent_node),
283                self.relationship_name.clone(),
284                change.clone(),
285            ));
286        }
287    }
288
289    /// Whether the in-progress child change has yet to reach `row` in the
290    /// parent stream.
291    fn is_after_inprogress_position(&self, p: &Inprogress, row: &Row) -> bool {
292        let Some(position) = &p.position else {
293            return false;
294        };
295        if let Some(reached) = &p.reached_parents {
296            return !reached.contains(&canonical_key(row, &self.schema.primary_key));
297        }
298        (self.schema.compare_rows)(row, position) == Ordering::Greater
299    }
300
301    fn index_parent_row(&self, row: &Row) {
302        if self.indexes_parents {
303            self.parent_index.add(row);
304        }
305    }
306
307    fn unindex_parent_row(&self, row: &Row) {
308        if self.indexes_parents {
309            self.parent_index.remove(row);
310        }
311    }
312
313    fn process_parent_node(&self, parent: &Node) -> Node {
314        let me = self.me.clone();
315        let row = parent.row.clone();
316        let child_stream = Rc::new(move || -> NodeStream {
317            let Some(me) = me.upgrade() else {
318                return empty();
319            };
320            let stream = match build_join_constraint(&row, &me.parent_key, &me.child_key) {
321                Some(c) => me.child.fetch(&FetchRequest {
322                    constraint: Some(c),
323                    ..FetchRequest::default()
324                }),
325                None => empty(),
326            };
327            // The parent has yet to get the in-progress child change if it
328            // comes after the current position and a parent fetch of the push
329            // yields it.
330            let overlay = {
331                let p = me.inprogress.borrow();
332                p.change.as_ref().and_then(|inprogress| {
333                    let in_push_queue = me.is_after_inprogress_position(&p, &row)
334                        && p.parent_fetch_bounds.as_ref().is_none_or(|bounds| {
335                            is_in_parent_fetch(bounds, &row, &me.schema.compare_rows)
336                        });
337                    (in_push_queue
338                        && is_join_match(
339                            &row,
340                            &me.parent_key,
341                            &inprogress.node().row,
342                            &me.child_key,
343                        ))
344                    .then(|| inprogress.clone())
345                })
346            };
347            let Some(overlay) = overlay else {
348                return stream;
349            };
350            let child_schema = me.child.get_schema();
351            if child_schema.sort.is_none() {
352                generate_with_overlay_unordered(stream, overlay, child_schema)
353            } else {
354                generate_with_overlay(stream, overlay, child_schema)
355            }
356        });
357        let mut node = parent.clone();
358        node.relationships
359            .set(&self.relationship_name, Some(child_stream));
360        node
361    }
362}
363
364impl InputBase for Join {
365    fn get_schema(&self) -> Rc<SourceSchema> {
366        self.schema.clone()
367    }
368    fn destroy(&self) {
369        self.parent.destroy();
370        self.child.destroy();
371    }
372}
373
374impl Input for Join {
375    fn set_output(&self, output: Weak<dyn Output>) {
376        *self.output.borrow_mut() = output;
377    }
378
379    fn fetch(&self, req: &FetchRequest) -> NodeStream {
380        let me = self.me.clone();
381        let req = req.clone();
382        lazy(move || -> NodeStream {
383            let Some(me) = me.upgrade() else {
384                return empty();
385            };
386            let parents = me.parent.fetch(&req);
387            Box::new(parents.map(move |node| {
388                me.index_parent_row(&node.row);
389                me.process_parent_node(&node)
390            }))
391        })
392    }
393}
394
395/// Provides `Take`'s bound to upstream operators (`take-gate.ts`).
396pub trait TakeBoundProvider {
397    fn get_bound(&self, constraint: Option<&Constraint>) -> Option<Row>;
398}
399
400/// The bound a [`TakeGate`] caps one parent fetch of a child push at.
401#[derive(Clone, Debug)]
402pub struct ParentFetchBound {
403    pub constraint: Constraint,
404    pub bound: Option<Row>,
405}
406
407/// Reads the bounds for a child push's parent fetches before they start.
408pub fn read_parent_fetch_bounds(
409    provider: &dyn TakeBoundProvider,
410    constraints: &[Constraint],
411) -> Vec<ParentFetchBound> {
412    constraints
413        .iter()
414        .map(|c| ParentFetchBound {
415            constraint: c.clone(),
416            bound: provider.get_bound(Some(c)),
417        })
418        .collect()
419}
420
421/// Whether one of the parent fetches of a push yields `row`.
422pub fn is_in_parent_fetch(bounds: &[ParentFetchBound], row: &Row, compare: &Comparator) -> bool {
423    match bounds.iter().find(|b| b.constraint.matches(row)) {
424        None => false,
425        Some(ParentFetchBound { bound: None, .. }) => true,
426        Some(ParentFetchBound {
427            bound: Some(bound), ..
428        }) => compare(row, bound) != Ordering::Greater,
429    }
430}
431
432/// Caps upstream parent fetches at a downstream `Take`'s bound.
433pub struct TakeGate {
434    me: Weak<TakeGate>,
435    input: Rc<dyn Input>,
436    comparator: Comparator,
437    bound_provider: RefCell<Option<Weak<dyn TakeBoundProvider>>>,
438    output: RefCell<Weak<dyn Output>>,
439    open_depth: Cell<usize>,
440}
441
442impl TakeGate {
443    pub fn new(input: Rc<dyn Input>) -> Rc<Self> {
444        let schema = input.get_schema();
445        assert!(schema.sort.is_some(), "TakeGate requires sorted input");
446        let op = Rc::new_cyclic(|me| TakeGate {
447            me: me.clone(),
448            input: input.clone(),
449            comparator: schema.compare_rows.clone(),
450            bound_provider: RefCell::new(None),
451            output: RefCell::new(no_output()),
452            open_depth: Cell::new(0),
453        });
454        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
455        op
456    }
457
458    pub fn open(&self) {
459        self.open_depth.set(self.open_depth.get() + 1);
460    }
461
462    pub fn close(&self) {
463        let depth = self.open_depth.get();
464        assert!(depth > 0, "TakeGate.close called without matching open");
465        self.open_depth.set(depth - 1);
466    }
467
468    pub fn set_bound_provider(&self, provider: Weak<dyn TakeBoundProvider>) {
469        *self.bound_provider.borrow_mut() = Some(provider);
470    }
471
472    fn provider_bound(&self, constraint: Option<&Constraint>) -> Option<Row> {
473        let provider = self.bound_provider.borrow().as_ref()?.upgrade()?;
474        provider.get_bound(constraint)
475    }
476}
477
478impl TakeBoundProvider for TakeGate {
479    fn get_bound(&self, constraint: Option<&Constraint>) -> Option<Row> {
480        if self.open_depth.get() > 0 {
481            return None;
482        }
483        self.provider_bound(constraint)
484    }
485}
486
487impl InputBase for TakeGate {
488    fn get_schema(&self) -> Rc<SourceSchema> {
489        self.input.get_schema()
490    }
491    fn destroy(&self) {
492        self.input.destroy()
493    }
494}
495
496impl Input for TakeGate {
497    fn set_output(&self, output: Weak<dyn Output>) {
498        *self.output.borrow_mut() = output;
499    }
500
501    fn fetch(&self, req: &FetchRequest) -> NodeStream {
502        let me = self.me.clone();
503        let req = req.clone();
504        lazy(move || -> NodeStream {
505            let Some(me) = me.upgrade() else {
506                return empty();
507            };
508            let stream = me.input.fetch(&req);
509            if me.open_depth.get() > 0 || req.reverse {
510                return stream;
511            }
512            let Some(bound) = me.provider_bound(req.constraint.as_ref()) else {
513                return stream;
514            };
515            let comparator = me.comparator.clone();
516            Box::new(stream.take_while(move |n| comparator(&n.row, &bound) != Ordering::Greater))
517        })
518    }
519}
520
521impl Output for TakeGate {
522    fn push(&self, change: Change, _pusher: &dyn InputBase) {
523        if let Some(out) = upgrade(&self.output) {
524            out.push(change, self);
525        }
526    }
527    fn reconcile(&self, _pusher: &dyn InputBase) {
528        if let Some(out) = upgrade(&self.output) {
529            out.reconcile(self);
530        }
531    }
532}
533
534/// Keeps the parent indexes of a pipeline's EXISTS joins equal to the rows
535/// the pipeline emits (`join-index-tap.ts`).
536pub struct JoinIndexTap {
537    input: Rc<dyn Input>,
538    indexes: Rc<Vec<Rc<JoinIndex>>>,
539    output: RefCell<Weak<dyn Output>>,
540}
541
542impl JoinIndexTap {
543    pub fn new(input: Rc<dyn Input>, indexes: Vec<Rc<JoinIndex>>) -> Rc<Self> {
544        let op = Rc::new(JoinIndexTap {
545            input: input.clone(),
546            indexes: Rc::new(indexes),
547            output: RefCell::new(no_output()),
548        });
549        input.set_output(Rc::downgrade(&op) as Weak<dyn Output>);
550        op
551    }
552}
553
554impl InputBase for JoinIndexTap {
555    fn get_schema(&self) -> Rc<SourceSchema> {
556        self.input.get_schema()
557    }
558    fn destroy(&self) {
559        self.input.destroy()
560    }
561}
562
563impl Input for JoinIndexTap {
564    fn set_output(&self, output: Weak<dyn Output>) {
565        *self.output.borrow_mut() = output;
566    }
567
568    fn fetch(&self, req: &FetchRequest) -> NodeStream {
569        let indexes = self.indexes.clone();
570        Box::new(self.input.fetch(req).inspect(move |node| {
571            for index in indexes.iter() {
572                index.add(&node.row);
573            }
574        }))
575    }
576}
577
578impl Output for JoinIndexTap {
579    fn push(&self, change: Change, _pusher: &dyn InputBase) {
580        match &change {
581            Change::Add(node) => self.indexes.iter().for_each(|i| i.add(&node.row)),
582            Change::Remove(node) => self.indexes.iter().for_each(|i| i.remove(&node.row)),
583            Change::Edit { node, old_node } => {
584                for index in self.indexes.iter() {
585                    index.remove(&old_node.row);
586                    index.add(&node.row);
587                }
588            }
589            Change::Child(..) => {}
590        }
591        if let Some(out) = upgrade(&self.output) {
592            out.push(change, self);
593        }
594    }
595    fn reconcile(&self, _pusher: &dyn InputBase) {
596        if let Some(out) = upgrade(&self.output) {
597            out.reconcile(self);
598        }
599    }
600}