1use 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#[derive(Clone)]
21pub struct ExistsJoin {
22 pub op: CorrelatedSubqueryOperator,
23 pub parent_index: Rc<JoinIndex>,
24}
25
26pub 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#[derive(Default)]
42struct Inprogress {
43 change: Option<Change>,
44 position: Option<Row>,
46 reached_parents: Option<HashSet<String>>,
49 parent_fetch_bounds: Option<Vec<ParentFetchBound>>,
50}
51
52pub 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 indexes_parents: bool,
66 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 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 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
395pub trait TakeBoundProvider {
397 fn get_bound(&self, constraint: Option<&Constraint>) -> Option<Row>;
398}
399
400#[derive(Clone, Debug)]
402pub struct ParentFetchBound {
403 pub constraint: Constraint,
404 pub bound: Option<Row>,
405}
406
407pub 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
421pub 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
432pub 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
534pub 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}