Skip to main content

zero_client/ivm/
flipped_join.rs

1//! `FlippedJoin` (`packages/zql/src/ivm/flipped-join.ts`).
2
3use super::*;
4use crate::ast::System;
5use std::cell::RefCell;
6use std::cmp::Ordering;
7use std::collections::HashMap;
8use std::rc::{Rc, Weak};
9
10/// The most entries in one batched parent fetch (`flipped-join.ts`).
11pub const MULTI_CONSTRAINT_CHUNK_SIZE: usize = 256;
12
13/// What [`FlippedJoin::new`] joins, and how.
14pub struct FlippedJoinArgs {
15    pub parent: Rc<dyn Input>,
16    pub child: Rc<dyn Input>,
17    pub parent_key: Vec<String>,
18    pub child_key: Vec<String>,
19    pub relationship_name: String,
20    pub hidden: bool,
21    pub system: System,
22    pub parent_partition_key: Option<Vec<String>>,
23    pub bound_provider: Option<Rc<dyn TakeBoundProvider>>,
24    /// An index kept elsewhere (by a `JoinIndexTap`); the join keeps its
25    /// own when `None`.
26    pub parent_index: Option<Rc<JoinIndex>>,
27}
28
29#[derive(Default)]
30struct Inprogress {
31    change: Option<Change>,
32    position: Option<Row>,
33    parent_fetch_bounds: Option<Vec<ParentFetchBound>>,
34}
35
36/// A child node, and whether it is the in-progress removed child spliced
37/// back in (JS compares it by identity).
38#[derive(Clone)]
39struct ChildNode {
40    node: Node,
41    is_removed_overlay: bool,
42}
43
44/// An inner join that fetches children first, then their parents. Outputs
45/// parents, in parent order, that have at least one related child.
46pub struct FlippedJoin {
47    me: Weak<FlippedJoin>,
48    parent: Rc<dyn Input>,
49    child: Rc<dyn Input>,
50    parent_key: Vec<String>,
51    child_key: Vec<String>,
52    relationship_name: String,
53    schema: Rc<SourceSchema>,
54    bound_provider: Option<Rc<dyn TakeBoundProvider>>,
55    /// The parents this join has output.
56    parent_index: Rc<JoinIndex>,
57    indexes_parents: bool,
58    output: RefCell<Weak<dyn Output>>,
59    parent_output: Rc<ClosureOutput>,
60    child_output: Rc<ClosureOutput>,
61    inprogress: RefCell<Inprogress>,
62}
63
64impl FlippedJoin {
65    pub fn new(args: FlippedJoinArgs) -> Rc<Self> {
66        let FlippedJoinArgs {
67            parent,
68            child,
69            parent_key,
70            child_key,
71            relationship_name,
72            hidden,
73            system,
74            parent_partition_key,
75            bound_provider,
76            parent_index,
77        } = args;
78        assert!(
79            !is_same(parent.as_ref(), child.as_ref()),
80            "Parent and child must be different operators"
81        );
82        assert!(
83            parent_key.len() == child_key.len(),
84            "The parentKey and childKey keys must have same length"
85        );
86        let parent_schema = parent.get_schema();
87        let (parent_index, indexes_parents) = match parent_index {
88            Some(index) => (index, false),
89            None => (
90                JoinIndex::new(
91                    parent_key.clone(),
92                    parent_schema.primary_key.clone(),
93                    parent_partition_key,
94                ),
95                true,
96            ),
97        };
98        let mut child_schema = (*child.get_schema()).clone();
99        child_schema.is_hidden = hidden;
100        child_schema.system = system;
101        let schema = Rc::new(parent_schema.adding(&relationship_name, Rc::new(child_schema)));
102        let op = Rc::new_cyclic(|me: &Weak<FlippedJoin>| {
103            let (push_parent, reconcile_parent) = (me.clone(), me.clone());
104            let (push_child, reconcile_child) = (me.clone(), me.clone());
105            FlippedJoin {
106                me: me.clone(),
107                parent: parent.clone(),
108                child: child.clone(),
109                parent_key,
110                child_key,
111                relationship_name,
112                schema,
113                bound_provider,
114                parent_index,
115                indexes_parents,
116                output: RefCell::new(no_output()),
117                parent_output: ClosureOutput::new(
118                    move |c| {
119                        if let Some(j) = push_parent.upgrade() {
120                            j.push_parent(c)
121                        }
122                    },
123                    move || {
124                        if let Some(j) = reconcile_parent.upgrade() {
125                            j.reconcile_output()
126                        }
127                    },
128                ),
129                child_output: ClosureOutput::new(
130                    move |c| {
131                        if let Some(j) = push_child.upgrade() {
132                            j.push_child(c)
133                        }
134                    },
135                    move || {
136                        if let Some(j) = reconcile_child.upgrade() {
137                            j.reconcile_output()
138                        }
139                    },
140                ),
141                inprogress: RefCell::default(),
142            }
143        });
144        parent.set_output(Rc::downgrade(&op.parent_output) as Weak<dyn Output>);
145        child.set_output(Rc::downgrade(&op.child_output) as Weak<dyn Output>);
146        op
147    }
148
149    fn reconcile_output(&self) {
150        let out = self.output.borrow().upgrade();
151        if let Some(out) = out {
152            out.reconcile(self);
153        }
154    }
155
156    fn emit(&self, change: Change) {
157        let out = self.output.borrow().upgrade();
158        if let Some(out) = out {
159            out.push(change, self);
160        }
161    }
162
163    fn fetch_now(self: &Rc<Self>, req: &FetchRequest) -> NodeStream {
164        // Constraints on the parent's join key become child constraints.
165        let mut child_constraint = Constraint::default();
166        if let Some(constraint) = &req.constraint {
167            for (k, v) in &constraint.entries {
168                if let Some(i) = self.parent_key.iter().position(|p| p == k) {
169                    child_constraint.set(&self.child_key[i], v.clone());
170                }
171            }
172        }
173        let child_req = FetchRequest {
174            constraint: (!child_constraint.is_empty()).then_some(child_constraint),
175            ..FetchRequest::default()
176        };
177        let mut child_nodes: Vec<ChildNode> = self
178            .child
179            .fetch(&child_req)
180            .map(|node| ChildNode {
181                node,
182                is_removed_overlay: false,
183            })
184            .collect();
185
186        // Undo an in-progress remove here; it is re-applied below to the
187        // parents the push has reached.
188        let removed = match &self.inprogress.borrow().change {
189            Some(Change::Remove(n)) => Some(n.clone()),
190            _ => None,
191        };
192        if let Some(removed) = removed {
193            let compare = self.child.get_schema().compare_rows.clone();
194            let pos = binary_search(child_nodes.len(), |i| {
195                compare(&removed.row, &child_nodes[i].node.row)
196            });
197            child_nodes.insert(
198                pos,
199                ChildNode {
200                    node: removed,
201                    is_removed_overlay: true,
202                },
203            );
204        }
205        self.fetch_batched(req, child_nodes)
206    }
207
208    fn fetch_batched(
209        self: &Rc<Self>,
210        req: &FetchRequest,
211        child_nodes: Vec<ChildNode>,
212    ) -> NodeStream {
213        let mut computed_multi: Vec<Constraint> = Vec::new();
214        let mut child_indexes_by_key: HashMap<String, Vec<usize>> = HashMap::new();
215        for (i, child) in child_nodes.iter().enumerate() {
216            let Some(from_child) =
217                build_join_constraint(&child.node.row, &self.child_key, &self.parent_key)
218            else {
219                continue;
220            };
221            if let Some(c) = &req.constraint
222                && !from_child.is_compatible(c)
223            {
224                continue;
225            }
226            let key = canonical_key_of_constraint(&from_child, &self.parent_key);
227            match child_indexes_by_key.get_mut(&key) {
228                Some(idxs) => idxs.push(i),
229                None => {
230                    child_indexes_by_key.insert(key, vec![i]);
231                    computed_multi.push(from_child);
232                }
233            }
234        }
235        if computed_multi.is_empty() {
236            return empty();
237        }
238
239        let incoming = req.multi_constraints.clone().unwrap_or_default();
240        let with_multi = |chunk: &[Constraint]| {
241            let mut multi = incoming.clone();
242            multi.push(chunk.to_vec());
243            self.parent.fetch(&FetchRequest {
244                multi_constraints: Some(multi),
245                ..req.clone()
246            })
247        };
248        let parent_stream = if computed_multi.len() <= MULTI_CONSTRAINT_CHUNK_SIZE {
249            with_multi(&computed_multi)
250        } else {
251            let compare_rows = self.schema.compare_rows.clone();
252            let reverse = req.reverse;
253            merge_sorted_streams(
254                computed_multi
255                    .chunks(MULTI_CONSTRAINT_CHUNK_SIZE)
256                    .map(with_multi)
257                    .collect(),
258                Rc::new(move |a: &Node, b: &Node| {
259                    if reverse {
260                        compare_rows(&b.row, &a.row)
261                    } else {
262                        compare_rows(&a.row, &b.row)
263                    }
264                }),
265            )
266        };
267
268        let me = self.clone();
269        Box::new(parent_stream.filter_map(move |node| {
270            // A parent that matches none of the computed constraints comes
271            // from an operator that passes multiConstraints through
272            // unfiltered.
273            let idxs = child_indexes_by_key.get(&canonical_key(&node.row, &me.parent_key))?;
274            let related: Vec<&ChildNode> = idxs.iter().map(|&i| &child_nodes[i]).collect();
275            me.parent_with_overlay(node, &related)
276        }))
277    }
278
279    fn parent_with_overlay(&self, min_parent: Node, related: &[&ChildNode]) -> Option<Node> {
280        let mut overlaid: Vec<Node> = related.iter().map(|c| c.node.clone()).collect();
281        let inprogress = {
282            let p = self.inprogress.borrow();
283            p.position
284                .clone()
285                .map(|position| (p.change.clone(), position, p.parent_fetch_bounds.clone()))
286        };
287        if let Some((Some(change), position, bounds)) = inprogress {
288            // The parent has yet to get the in-progress child change if it
289            // comes after the current position and a parent fetch of the
290            // push yields it.
291            let compare_rows = self.parent.get_schema().compare_rows.clone();
292            let in_push_queue = compare_rows(&min_parent.row, &position) == Ordering::Greater
293                && bounds
294                    .as_ref()
295                    .is_none_or(|b| is_in_parent_fetch(b, &min_parent.row, &compare_rows));
296            if is_join_match(
297                &change.node().row,
298                &self.child_key,
299                &min_parent.row,
300                &self.parent_key,
301            ) {
302                if change.change_type() == ChangeType::Remove {
303                    if !in_push_queue {
304                        // The removed child was spliced into the children
305                        // above.
306                        overlaid = related
307                            .iter()
308                            .filter(|c| !c.is_removed_overlay)
309                            .map(|c| c.node.clone())
310                            .collect();
311                    }
312                } else if in_push_queue {
313                    overlaid =
314                        generate_with_overlay(from_vec(overlaid), change, self.child.get_schema())
315                            .collect();
316                }
317            }
318        }
319        if overlaid.is_empty() {
320            return None;
321        }
322        self.index_parent_row(&min_parent.row);
323        let children = Rc::new(overlaid);
324        Some(min_parent.with(
325            &self.relationship_name,
326            Rc::new(move || from_vec(children.as_ref().clone())),
327        ))
328    }
329
330    fn push_child(&self, change: Change) {
331        match &change {
332            Change::Add(_) | Change::Remove(_) => self.push_child_change(change, false),
333            Change::Edit { node, old_node } => {
334                assert!(
335                    row_equals_for_compound_key(&old_node.row, &node.row, &self.child_key),
336                    "Child edit must not change relationship."
337                );
338                self.push_child_change(change, true)
339            }
340            Change::Child(..) => self.push_child_change(change, true),
341        }
342    }
343
344    fn push_child_change(&self, change: Change, exists: bool) {
345        {
346            let mut p = self.inprogress.borrow_mut();
347            p.change = Some(change.clone());
348            p.position = None;
349        }
350        self.push_child_change_inner(change, exists);
351        *self.inprogress.borrow_mut() = Inprogress::default();
352    }
353
354    /// The `child_key`-to-`parent_key` fetch of a parent's children.
355    fn child_stream(&self, parent_row: &Row) -> RelationshipStream {
356        let me = self.me.clone();
357        let row = parent_row.clone();
358        Rc::new(move || -> NodeStream {
359            let Some(me) = me.upgrade() else {
360                return empty();
361            };
362            match build_join_constraint(&row, &me.parent_key, &me.child_key) {
363                Some(c) => me.child.fetch(&FetchRequest {
364                    constraint: Some(c),
365                    ..FetchRequest::default()
366                }),
367                None => empty(),
368            }
369        })
370    }
371
372    fn push_child_change_inner(&self, change: Change, exists: bool) {
373        let child_row = change.node().row.clone();
374        let Some(constraint) = build_join_constraint(&child_row, &self.child_key, &self.parent_key)
375        else {
376            return;
377        };
378        let change_type = change.change_type();
379        let adds = matches!(change_type, ChangeType::Add | ChangeType::Child);
380        let partitions = self.parent_index.lookup(&child_row, &self.child_key);
381        // Without a resident parent, a remove or edit cannot affect the view.
382        let fetch_constraints: Vec<Constraint> = match partitions {
383            _ if adds => vec![constraint],
384            None => return,
385            Some(partitions) => partitions
386                .into_iter()
387                .map(|p| match p {
388                    Some(p) => constraint.merging(&p),
389                    None => constraint.clone(),
390                })
391                .collect(),
392        };
393        if let Some(provider) = &self.bound_provider {
394            self.inprogress.borrow_mut().parent_fetch_bounds = Some(read_parent_fetch_bounds(
395                provider.as_ref(),
396                &fetch_constraints,
397            ));
398        }
399        let fetch = |c: Constraint| {
400            self.parent.fetch(&FetchRequest {
401                constraint: Some(c),
402                ..FetchRequest::default()
403            })
404        };
405        let parent_nodes: NodeStream = if fetch_constraints.len() == 1 {
406            fetch(fetch_constraints.into_iter().next().unwrap())
407        } else {
408            let compare = self.schema.compare_rows.clone();
409            merge_sorted_streams(
410                fetch_constraints.into_iter().map(fetch).collect(),
411                Rc::new(move |a: &Node, b: &Node| compare(&a.row, &b.row)),
412            )
413        };
414        let child_compare = self.child.get_schema().compare_rows.clone();
415        for parent_node in parent_nodes {
416            {
417                let mut p = self.inprogress.borrow_mut();
418                p.change = Some(change.clone());
419                p.position = Some(parent_node.row.clone());
420            }
421            let child_stream = self.child_stream(&parent_node.row);
422            let parent_exists = exists
423                || child_stream().any(|n| child_compare(&n.row, &child_row) != Ordering::Equal);
424            if parent_exists {
425                self.emit(Change::child(
426                    parent_node.with(&self.relationship_name, child_stream),
427                    self.relationship_name.clone(),
428                    change.clone(),
429                ));
430            } else {
431                let changed = change.node().clone();
432                let new_node = parent_node.clone().with(
433                    &self.relationship_name,
434                    Rc::new(move || from_vec(vec![changed.clone()])),
435                );
436                if change_type == ChangeType::Add {
437                    self.index_parent_row(&parent_node.row);
438                    self.emit(Change::Add(new_node));
439                } else {
440                    self.unindex_parent_row(&parent_node.row);
441                    self.emit(Change::Remove(new_node));
442                }
443            }
444        }
445    }
446
447    fn index_parent_row(&self, row: &Row) {
448        if self.indexes_parents {
449            self.parent_index.add(row);
450        }
451    }
452
453    fn unindex_parent_row(&self, row: &Row) {
454        if self.indexes_parents {
455            self.parent_index.remove(row);
456        }
457    }
458
459    fn push_parent(&self, change: Change) {
460        let flip = |node: Node| {
461            let stream = self.child_stream(&node.row);
462            node.with(&self.relationship_name, stream)
463        };
464        // An inner join: no related child, no push.
465        let Some(c) = build_join_constraint(&change.node().row, &self.parent_key, &self.child_key)
466        else {
467            return;
468        };
469        let has_child = self
470            .child
471            .fetch(&FetchRequest {
472                constraint: Some(c),
473                ..FetchRequest::default()
474            })
475            .next()
476            .is_some();
477        if !has_child {
478            return;
479        }
480        match change {
481            Change::Add(node) => {
482                self.index_parent_row(&node.row);
483                self.emit(Change::Add(flip(node)));
484            }
485            Change::Remove(node) => {
486                self.unindex_parent_row(&node.row);
487                self.emit(Change::Remove(flip(node)));
488            }
489            Change::Child(node, child) => self.emit(Change::Child(flip(node), child)),
490            Change::Edit { node, old_node } => {
491                assert!(
492                    row_equals_for_compound_key(&old_node.row, &node.row, &self.parent_key),
493                    "Parent edit must not change relationship."
494                );
495                self.unindex_parent_row(&old_node.row);
496                self.index_parent_row(&node.row);
497                self.emit(Change::Edit {
498                    node: flip(node),
499                    old_node: flip(old_node),
500                });
501            }
502        }
503    }
504}
505
506impl InputBase for FlippedJoin {
507    fn get_schema(&self) -> Rc<SourceSchema> {
508        self.schema.clone()
509    }
510    fn destroy(&self) {
511        self.child.destroy();
512        self.parent.destroy();
513    }
514}
515
516impl Input for FlippedJoin {
517    fn set_output(&self, output: Weak<dyn Output>) {
518        *self.output.borrow_mut() = output;
519    }
520
521    fn fetch(&self, req: &FetchRequest) -> NodeStream {
522        let me = self.me.clone();
523        let req = req.clone();
524        lazy(move || -> NodeStream {
525            match me.upgrade() {
526                Some(me) => me.fetch_now(&req),
527                None => empty(),
528            }
529        })
530    }
531}
532
533/// `binarySearch(high, compare)` (`shared/src/binary-search.ts`): the index
534/// where `compare` is equal, or the first index past the elements it is
535/// greater for.
536pub fn binary_search(high: usize, compare: impl Fn(usize) -> Ordering) -> usize {
537    let (mut low, mut high) = (0, high);
538    while low < high {
539        let mid = low + ((high - low) >> 1);
540        match compare(mid) {
541            Ordering::Equal => return mid,
542            Ordering::Greater => low = mid + 1,
543            Ordering::Less => high = mid,
544        }
545    }
546    low
547}