1use super::*;
4use crate::ast::System;
5use std::cell::RefCell;
6use std::cmp::Ordering;
7use std::collections::HashMap;
8use std::rc::{Rc, Weak};
9
10pub const MULTI_CONSTRAINT_CHUNK_SIZE: usize = 256;
12
13pub 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 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#[derive(Clone)]
39struct ChildNode {
40 node: Node,
41 is_removed_overlay: bool,
42}
43
44pub 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 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 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 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 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 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 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 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 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 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
533pub 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}