1mod pushdown;
8
9pub use pushdown::*;
10
11use crate::ast::{
12 Aggregate as AggregateSpec, AggregateFunction, Ast, Condition, CorrelatedSubquery,
13 CorrelatedSubqueryOperator, Direction, OrderPart, System,
14};
15use crate::ivm::*;
16use crate::json::number;
17use crate::keys::{AGGREGATE_TABLE_PREFIX, aggregate_columns as cols};
18use crate::map::OrderedMap;
19use crate::schema::Column;
20use crate::strings;
21use std::collections::HashSet;
22use std::rc::{Rc, Weak};
23
24pub trait BuilderDelegate {
26 fn get_source(&self, table_name: &str) -> Option<Rc<dyn Source>>;
27 fn apply_filters_anyway(&self) -> bool {
29 false
30 }
31 fn enable_not_exists(&self) -> bool {
34 false
35 }
36 fn disable_correlated_predicate_pushdown(&self) -> bool {
39 false
40 }
41 fn map_ast(&self, ast: &Ast) -> Ast {
42 ast.clone()
43 }
44 fn aggregates_from_source(&self) -> bool {
48 false
49 }
50 fn get_aggregate_source(
54 &self,
55 name: &str,
56 _columns: OrderedMap<Column>,
57 _primary_key: Vec<String>,
58 _optimistic: Option<OptimisticAggregate>,
59 ) -> Option<Rc<dyn Source>> {
60 self.get_source(name)
61 }
62 fn aggregate_key_columns(&self, _table: &str, columns: &[String]) -> Vec<String> {
65 columns.to_vec()
66 }
67}
68
69#[derive(Clone)]
73pub struct OptimisticAggregate {
74 pub aggregate_table: String,
76 pub table: String,
78 pub child_field: Vec<String>,
80 pub key_field: Vec<String>,
82 pub aggregate: AggregateSpec,
83 pub predicate: Option<RowPredicate>,
86 pub grouped: bool,
89}
90
91pub const EXISTS_LIMIT: f64 = 3.0;
94pub const PERMISSIONS_EXISTS_LIMIT: f64 = 1.0;
95
96type Result<T> = std::result::Result<T, PipelineError>;
97
98fn err<T>(message: impl Into<String>) -> Result<T> {
99 Err(PipelineError::new(message))
100}
101
102pub fn build_pipeline(
104 ast: &Ast,
105 delegate: &dyn BuilderDelegate,
106 query_id: &str,
107) -> Result<Rc<dyn Input>> {
108 let mut ast = delegate.map_ast(ast);
109 if ast.group_by.is_some() && ast.aggregate.as_ref().is_some_and(|a| a.distinct.is_some()) {
110 return err("a count of distinct values per group is not supported yet");
111 }
112 if (ast.aggregate.is_some() || ast.group_by.is_some()) && delegate.aggregates_from_source() {
115 return Builder { delegate, query_id }.build(&ast, "", None, false);
116 }
117 if ast.group_by.is_some() || ast.aggregate.as_ref().is_some_and(|a| a.distinct.is_some()) {
118 ast.order_by = Some(group_ordering(&ast));
121 }
122 ast = complete_ordering(&ast, &|table| match delegate.get_source(table) {
123 Some(s) => Ok(s.table_schema().primary_key.clone()),
124 None => err(format!("Source not found: {table}")),
125 })?;
126 if !delegate.disable_correlated_predicate_pushdown() {
127 let columns_of = |table: &str| -> OrderedMap<Column> {
128 delegate
129 .get_source(table)
130 .map(|s| s.table_schema().columns.clone())
131 .unwrap_or_default()
132 };
133 ast = push_down_correlated_predicates(&ast, &columns_of);
134 }
135 Builder { delegate, query_id }.build(&ast, "", None, false)
136}
137
138fn assert_no_not_exists(condition: &Condition) -> Result<()> {
140 match condition {
141 Condition::Simple { .. } => Ok(()),
142 Condition::CorrelatedSubquery {
143 op: CorrelatedSubqueryOperator::NotExists,
144 ..
145 } => err(
146 "not(exists()) is not supported on the client - see https://bugs.rocicorp.dev/issue/3438",
147 ),
148 Condition::CorrelatedSubquery { .. } => Ok(()),
149 Condition::And(cs) | Condition::Or(cs) => cs.iter().try_for_each(assert_no_not_exists),
150 }
151}
152
153struct CsqCondition {
154 related: CorrelatedSubquery,
155 op: CorrelatedSubqueryOperator,
156 flip: Option<bool>,
157}
158
159struct Builder<'a> {
160 delegate: &'a dyn BuilderDelegate,
161 query_id: &'a str,
162}
163
164impl Builder<'_> {
165 fn build(
166 &self,
167 ast_in: &Ast,
168 name: &str,
169 partition_key: Option<&[String]>,
170 is_non_flipped_exists_child: bool,
171 ) -> Result<Rc<dyn Input>> {
172 if ast_in.group_by.is_some() && !name.is_empty() {
173 return err("groupBy is only supported at the top level");
174 }
175 if ast_in.aggregate.is_some()
176 && ast_in.group_by.is_none()
177 && self.delegate.aggregates_from_source()
178 {
179 let table = top_level_aggregate_table_name(self.query_id);
181 let Some(source) = self.delegate.get_source(&table) else {
182 return err(format!("Aggregate source not found: {table}"));
183 };
184 let conn = source.connect(
185 Some(vec![OrderPart {
186 field: cols::KEY.to_owned(),
187 direction: Direction::Asc,
188 }]),
189 None,
190 None,
191 )?;
192 return Ok(conn);
193 }
194 if ast_in.group_by.is_some() && self.delegate.aggregates_from_source() {
195 return self.group_from_source(ast_in);
196 }
197 let Some(source) = self.delegate.get_source(&ast_in.table) else {
198 return err(format!("Source not found: {}", ast_in.table));
199 };
200 let ast = uniquify_correlated_subquery_condition_aliases(ast_in);
201 if !self.delegate.enable_not_exists()
202 && let Some(w) = &ast.where_
203 {
204 assert_no_not_exists(w)?;
205 }
206
207 let csq_conditions = gather_correlated_subquery_conditions(ast.where_.as_ref());
208 let mut split_edit_keys: HashSet<String> =
209 partition_key.unwrap_or_default().iter().cloned().collect();
210 for csq in &csq_conditions {
211 split_edit_keys.extend(csq.related.correlation.parent_field.iter().cloned());
212 }
213 for csq in ast.related.iter().flatten() {
214 split_edit_keys.extend(csq.correlation.parent_field.iter().cloned());
215 }
216 if is_non_flipped_exists_child {
217 if ast.start.is_some() {
219 return err("EXISTS subqueries must not have start");
220 }
221 if ast.related.is_some() {
222 return err("EXISTS subqueries must not have related");
223 }
224 }
225
226 let use_cap = is_non_flipped_exists_child
230 && !ast
231 .where_
232 .as_ref()
233 .is_some_and(condition_includes_flipped_subquery_at_any_level);
234
235 let sort = if use_cap {
236 None
237 } else {
238 Some(ast.order_by.clone().expect("ordering is complete"))
239 };
240 let conn = source.connect(sort, ast.where_.as_ref(), Some(&split_edit_keys))?;
241 let fully_applied_filters = conn.fully_applied_filters();
242 let mut end: Rc<dyn Input> = conn;
243
244 if let Some(start) = &ast.start {
245 end = Skip::new(end, start);
246 }
247
248 let mut take_gate: Option<Rc<TakeGate>> = None;
249 if ast.limit.is_some() && !use_cap {
250 let gate = TakeGate::new(end);
251 end = gate.clone();
252 take_gate = Some(gate);
253 }
254 let bound_provider = take_gate.clone().map(|g| g as Rc<dyn TakeBoundProvider>);
255
256 let mut exists_parent_indexes: Vec<Rc<JoinIndex>> = Vec::new();
259 for csq in csq_conditions.iter().filter(|c| c.flip != Some(true)) {
260 let parent_index = JoinIndex::new(
261 csq.related.correlation.parent_field.clone(),
262 end.get_schema().primary_key.clone(),
263 None,
264 );
265 exists_parent_indexes.push(parent_index.clone());
266 let mut related = csq.related.clone();
267 related.subquery.limit = Some(if related.system == Some(System::Permissions) {
268 PERMISSIONS_EXISTS_LIMIT
269 } else {
270 EXISTS_LIMIT
271 });
272 end = self.apply_correlated_subquery(
273 &related,
274 end,
275 name,
276 true,
277 None,
278 bound_provider.clone(),
279 Some(ExistsJoin {
280 op: csq.op,
281 parent_index,
282 }),
283 )?;
284 }
285
286 if let Some(w) = &ast.where_
287 && (!fully_applied_filters || self.delegate.apply_filters_anyway())
288 {
289 end = self.apply_where(
290 end,
291 w,
292 name,
293 partition_key,
294 bound_provider.clone(),
295 &mut exists_parent_indexes,
296 true,
297 )?;
298 }
299
300 if let Some(limit_value) = ast.limit {
301 if !(limit_value >= 0.0 && limit_value.fract() == 0.0) {
302 return err(format!("Invalid limit {}", number::format(limit_value)));
303 }
304 let limit = limit_value as usize;
305 if use_cap {
306 end = Cap::new(end, limit, partition_key.map(<[String]>::to_vec));
307 } else {
308 let take = Take::new(end, limit, partition_key.map(<[String]>::to_vec))?;
309 if let Some(gate) = &take_gate {
310 gate.set_bound_provider(Rc::downgrade(&take) as Weak<dyn TakeBoundProvider>);
311 take.set_take_gate(gate);
312 }
313 end = take;
314 }
315 }
316
317 if !exists_parent_indexes.is_empty() {
318 end = JoinIndexTap::new(end, exists_parent_indexes);
319 }
320
321 if ast.group_by.is_some() {
322 if ast.start.is_some() || ast.limit.is_some() || ast.related.is_some() {
325 return err("groupBy does not support start, limit or related");
326 }
327 return Ok(GroupBy::new(
328 end,
329 &group_ordering(&ast),
330 group_table_name(self.query_id),
331 reducer_of(&ast),
332 )?);
333 }
334
335 if let Some(aggregate) = &ast.aggregate {
336 let count = AggregateSpec::new(AggregateFunction::Count);
341 if aggregate.distinct.is_some() {
342 if ast.start.is_some() || ast.limit.is_some() {
345 return err("a count of distinct values does not support start or limit");
346 }
347 end = GroupBy::new(
348 end,
349 &group_ordering(&ast),
350 group_table_name(self.query_id),
351 count.clone(),
352 )?;
353 }
354 let reduced = if aggregate.distinct.is_none() {
355 aggregate.clone()
356 } else {
357 count
358 };
359 return Ok(Aggregate::new(
360 end,
361 Vec::new(),
362 reduced,
363 Some(top_level_aggregate_table_name(self.query_id)),
364 )?);
365 }
366
367 if let Some(related) = &ast.related {
368 let mut by_alias: Vec<(&str, &CorrelatedSubquery)> = Vec::new();
371 for csq in related {
372 let alias = csq.subquery.alias.as_deref().unwrap_or("");
373 match by_alias.iter_mut().find(|(a, _)| *a == alias) {
374 Some(entry) => entry.1 = csq,
375 None => by_alias.push((alias, csq)),
376 }
377 }
378 for (_, csq) in by_alias {
379 end = self.apply_correlated_subquery(
380 csq,
381 end,
382 name,
383 false,
384 partition_key,
385 None,
386 None,
387 )?;
388 }
389 }
390 Ok(end)
391 }
392
393 #[allow(clippy::too_many_arguments)]
394 fn apply_where(
395 &self,
396 input: Rc<dyn Input>,
397 condition: &Condition,
398 name: &str,
399 parent_partition_key: Option<&[String]>,
400 bound_provider: Option<Rc<dyn TakeBoundProvider>>,
401 exists_parent_indexes: &mut Vec<Rc<JoinIndex>>,
402 track_indexes: bool,
403 ) -> Result<Rc<dyn Input>> {
404 if !condition_includes_flipped_subquery_at_any_level(condition) {
405 return build_filter_pipeline(
406 input,
407 |f| self.apply_filter(f, condition, name),
408 transform_filters(Some(condition)).0,
409 );
410 }
411 self.apply_filter_with_flips(
412 input,
413 condition,
414 name,
415 parent_partition_key,
416 bound_provider,
417 exists_parent_indexes,
418 track_indexes,
419 )
420 }
421
422 #[allow(clippy::too_many_arguments)]
423 fn apply_filter_with_flips(
424 &self,
425 input: Rc<dyn Input>,
426 condition: &Condition,
427 name: &str,
428 parent_partition_key: Option<&[String]>,
429 bound_provider: Option<Rc<dyn TakeBoundProvider>>,
430 exists_parent_indexes: &mut Vec<Rc<JoinIndex>>,
431 track_indexes: bool,
432 ) -> Result<Rc<dyn Input>> {
433 let mut end = input;
434 match condition {
435 Condition::Simple { .. } => panic!("Simple conditions cannot have flips"),
436 Condition::And(conditions) => {
437 let (with_flipped, without_flipped): (Vec<_>, Vec<_>) = conditions
438 .iter()
439 .cloned()
440 .partition(condition_includes_flipped_subquery_at_any_level);
441 if !without_flipped.is_empty() {
442 let and = Condition::And(without_flipped.clone());
443 end = build_filter_pipeline(
444 end,
445 |f| self.apply_and(f, &without_flipped, name),
446 transform_filters(Some(&and)).0,
447 )?;
448 }
449 assert!(!with_flipped.is_empty(), "Impossible to have no flips here");
450 for cond in &with_flipped {
451 end = self.apply_filter_with_flips(
452 end,
453 cond,
454 name,
455 parent_partition_key,
456 bound_provider.clone(),
457 exists_parent_indexes,
458 track_indexes,
459 )?;
460 }
461 }
462 Condition::Or(conditions) => {
463 let (with_flipped, without_flipped): (Vec<_>, Vec<_>) = conditions
464 .iter()
465 .cloned()
466 .partition(condition_includes_flipped_subquery_at_any_level);
467 assert!(!with_flipped.is_empty(), "Impossible to have no flips here");
468 let ufo = UnionFanOut::new(end);
469 let ufo_input: Rc<dyn Input> = ufo.clone();
470 let mut branches: Vec<Rc<dyn Input>> = Vec::new();
471 if !without_flipped.is_empty() {
472 let or = Condition::Or(without_flipped.clone());
473 branches.push(build_filter_pipeline(
474 ufo_input.clone(),
475 |f| self.apply_or(f, &without_flipped, name),
476 transform_filters(Some(&or)).0,
477 )?);
478 }
479 for cond in &with_flipped {
480 branches.push(self.apply_filter_with_flips(
481 ufo_input.clone(),
482 cond,
483 name,
484 parent_partition_key,
485 bound_provider.clone(),
486 exists_parent_indexes,
487 track_indexes,
488 )?);
489 }
490 end = UnionFanIn::new(&ufo, branches);
491 }
492 Condition::CorrelatedSubquery { related: sq, .. } => {
493 let alias = sq
494 .subquery
495 .alias
496 .clone()
497 .expect("Subquery must have an alias");
498 let child = Builder {
499 delegate: self.delegate,
500 query_id: "",
501 }
502 .build(
503 &sq.subquery,
504 &format!("{name}.{alias}"),
505 Some(&sq.correlation.child_field),
506 false,
507 )?;
508 let parent_index = track_indexes.then(|| {
509 let index = JoinIndex::new(
510 sq.correlation.parent_field.clone(),
511 end.get_schema().primary_key.clone(),
512 parent_partition_key.map(<[String]>::to_vec),
513 );
514 exists_parent_indexes.push(index.clone());
515 index
516 });
517 end = FlippedJoin::new(FlippedJoinArgs {
518 parent: end,
519 child,
520 parent_key: sq.correlation.parent_field.clone(),
521 child_key: sq.correlation.child_field.clone(),
522 relationship_name: alias,
523 hidden: sq.hidden.unwrap_or(false),
524 system: sq.system.unwrap_or(System::Client),
525 parent_partition_key: parent_partition_key.map(<[String]>::to_vec),
526 bound_provider,
527 parent_index,
528 });
529 }
530 }
531 Ok(end)
532 }
533
534 fn apply_filter(
535 &self,
536 input: Rc<dyn FilterInput>,
537 condition: &Condition,
538 name: &str,
539 ) -> Result<Rc<dyn FilterInput>> {
540 match condition {
541 Condition::And(cs) => self.apply_and(input, cs, name),
542 Condition::Or(cs) => self.apply_or(input, cs, name),
543 Condition::CorrelatedSubquery { related, op, .. } => {
544 Ok(apply_correlated_subquery_condition(input, related, *op))
545 }
546 Condition::Simple { .. } => Ok(Filter::new(input, create_predicate(condition)?)),
547 }
548 }
549
550 fn apply_and(
551 &self,
552 input: Rc<dyn FilterInput>,
553 conditions: &[Condition],
554 name: &str,
555 ) -> Result<Rc<dyn FilterInput>> {
556 let mut input = input;
557 for c in conditions {
558 input = self.apply_filter(input, c, name)?;
559 }
560 Ok(input)
561 }
562
563 fn apply_or(
564 &self,
565 input: Rc<dyn FilterInput>,
566 conditions: &[Condition],
567 name: &str,
568 ) -> Result<Rc<dyn FilterInput>> {
569 let (other, subquery): (Vec<_>, Vec<_>) = conditions
570 .iter()
571 .cloned()
572 .partition(is_not_and_does_not_contain_subquery);
573 if subquery.is_empty() {
575 return Ok(Filter::new(input, create_predicate(&Condition::Or(other))?));
576 }
577 let fan_out = FanOut::new(input);
578 let fan_out_input: Rc<dyn FilterInput> = fan_out.clone();
579 let mut branches: Vec<Rc<dyn FilterInput>> = Vec::new();
580 for c in &subquery {
581 branches.push(self.apply_filter(fan_out_input.clone(), c, name)?);
582 }
583 if !other.is_empty() {
584 branches.push(Filter::new(
585 fan_out_input,
586 create_predicate(&Condition::Or(other))?,
587 ));
588 }
589 let fan_in = FanIn::new(&fan_out, branches);
590 fan_out.set_fan_in(&fan_in);
591 Ok(fan_in)
592 }
593
594 #[allow(clippy::too_many_arguments)]
595 fn aggregate_from_source(
600 &self,
601 sq: &CorrelatedSubquery,
602 aggregate: &AggregateSpec,
603 child_key: &[String],
604 name: &str,
605 ) -> Result<Rc<dyn Input>> {
606 let table = aggregate_table_name(self.query_id, sq, name);
607 let Some(child_source) = self.delegate.get_source(&sq.subquery.table) else {
608 return err(format!("Source not found: {}", sq.subquery.table));
609 };
610 let mut input_columns = child_source.table_schema().columns.clone();
613 let junction = sq.subquery.related.as_ref().and_then(|r| r.first());
614 if let Some(dest) = junction {
615 let Some(dest_source) = self.delegate.get_source(&dest.subquery.table) else {
616 return err(format!("Source not found: {}", dest.subquery.table));
617 };
618 for (k, v) in dest_source.table_schema().columns.iter() {
619 input_columns.insert(k.clone(), v.clone());
620 }
621 }
622 let (client_columns, _) =
623 aggregate_source_schema(&input_columns, &sq.correlation.child_field, aggregate)?;
624 let columns = rename_columns(&client_columns, &sq.correlation.child_field, child_key);
625 let mut optimistic = None;
629 if junction.is_none()
630 && is_invertible(aggregate.fn_)
631 && sq.subquery.limit.is_none()
632 && sq.subquery.start.is_none()
633 && let Some(predicate) = per_row_predicate(sq.subquery.where_.as_ref())?
634 {
635 optimistic = Some(OptimisticAggregate {
636 aggregate_table: table.clone(),
637 table: sq.subquery.table.clone(),
638 child_field: sq.correlation.child_field.clone(),
639 key_field: child_key.to_vec(),
640 aggregate: aggregate.clone(),
641 predicate,
642 grouped: false,
643 });
644 }
645 let Some(source) =
646 self.delegate
647 .get_aggregate_source(&table, columns, child_key.to_vec(), optimistic)
648 else {
649 return err(format!("Aggregate source not found: {table}"));
650 };
651 let sort = child_key
652 .iter()
653 .map(|k| OrderPart {
654 field: k.clone(),
655 direction: Direction::Asc,
656 })
657 .collect();
658 Ok(source.connect(Some(sort), None, None)?)
659 }
660
661 fn group_from_source(&self, ast: &Ast) -> Result<Rc<dyn Input>> {
664 let Some(table_source) = self.delegate.get_source(&ast.table) else {
665 return err(format!("Source not found: {}", ast.table));
666 };
667 let reducer = reducer_of(ast);
668 let mut columns = ast.group_by.clone().unwrap_or_default();
671 if let Some(field) = &reducer.field
672 && !columns.contains(field)
673 {
674 columns.push(field.clone());
675 }
676 let names = self.delegate.aggregate_key_columns(&ast.table, &columns);
677 let input_name = |column: &str| -> String {
678 let i = columns
679 .iter()
680 .position(|c| c == column)
681 .expect("a group column");
682 names[i].clone()
683 };
684 let table_columns = &table_source.table_schema().columns;
685 let mut input_columns = OrderedMap::new();
686 for column in &columns {
687 if let Some(c) = table_columns.get(column) {
688 input_columns.insert(input_name(column), c.clone());
689 }
690 }
691 let mut server_aggregate = reducer.clone();
692 server_aggregate.field = server_aggregate.field.as_deref().map(input_name);
693 let ordering: Vec<OrderPart> = group_ordering(ast)
694 .into_iter()
695 .map(|p| OrderPart {
696 field: input_name(&p.field),
697 direction: p.direction,
698 })
699 .collect();
700 let (source_columns, primary_key, sort) =
701 group_source_schema(&input_columns, &ordering, &server_aggregate)?;
702 let table = group_table_name(self.query_id);
703 let optimistic = group_optimistic_delta(ast, &reducer, &table, &input_name)?;
704 let Some(source) = self.delegate.get_aggregate_source(
705 &table,
706 sorted_columns(&source_columns),
707 primary_key,
708 optimistic,
709 ) else {
710 return err(format!("Group source not found: {table}"));
711 };
712 Ok(source.connect(Some(sort), None, None)?)
713 }
714
715 #[allow(clippy::too_many_arguments)]
716 fn apply_correlated_subquery(
717 &self,
718 sq: &CorrelatedSubquery,
719 end: Rc<dyn Input>,
720 name: &str,
721 from_condition: bool,
722 parent_partition_key: Option<&[String]>,
723 bound_provider: Option<Rc<dyn TakeBoundProvider>>,
724 exists: Option<ExistsJoin>,
725 ) -> Result<Rc<dyn Input>> {
726 if sq.subquery.limit == Some(0.0) && from_condition {
729 return Ok(end);
730 }
731 let alias = sq
732 .subquery
733 .alias
734 .clone()
735 .expect("Subquery must have an alias");
736 if let Some(aggregate) = &sq.aggregate
737 && self.delegate.aggregates_from_source()
738 {
739 if aggregate.distinct.is_some() {
742 return err("a count of distinct values is not supported in a relationship yet");
743 }
744 let child_key = self
745 .delegate
746 .aggregate_key_columns(&sq.subquery.table, &sq.correlation.child_field);
747 for column in &child_key {
750 assert_not_synthetic_column(column)?;
751 }
752 let child = self.aggregate_from_source(sq, aggregate, &child_key, name)?;
753 return Ok(Join::new(JoinArgs {
754 parent: end,
755 child,
756 parent_key: sq.correlation.parent_field.clone(),
757 child_key,
758 relationship_name: alias,
759 hidden: sq.hidden.unwrap_or(false),
760 system: sq.system.unwrap_or(System::Client),
761 parent_partition_key: if from_condition {
762 None
763 } else {
764 parent_partition_key.map(<[String]>::to_vec)
765 },
766 bound_provider,
767 exists,
768 }));
769 }
770 let mut child = self.build(
771 &sq.subquery,
772 &child_pipeline_name(name, sq),
773 Some(&sq.correlation.child_field),
774 from_condition,
775 )?;
776 if let Some(aggregate) = &sq.aggregate {
777 if aggregate.distinct.is_some() {
781 return err("a count of distinct values is not supported in a relationship yet");
782 }
783 let mut aggregated = aggregate.clone();
784 if let Some(dest) = sq.subquery.related.as_ref().and_then(|r| r.first()) {
785 let (Some(dest_alias), Some(field)) = (&dest.subquery.alias, &aggregate.field)
790 else {
791 panic!("a junction aggregate needs a destination alias and a field");
792 };
793 child = LiftField::new(
794 child,
795 dest_alias.clone(),
796 field.clone(),
797 aggregate.path.is_some().then(|| aggregate.clone()),
798 );
799 aggregated = AggregateSpec {
800 field: Some(LIFTED_FIELD_COLUMN.to_owned()),
801 path: None,
802 ..AggregateSpec::new(aggregate.fn_)
803 };
804 }
805 child = Aggregate::new(
806 child,
807 sq.correlation.child_field.clone(),
808 aggregated,
809 Some(aggregate_table_name(self.query_id, sq, name)),
810 )?;
811 }
812 Ok(Join::new(JoinArgs {
813 parent: end,
814 child,
815 parent_key: sq.correlation.parent_field.clone(),
816 child_key: sq.correlation.child_field.clone(),
817 relationship_name: alias,
818 hidden: sq.hidden.unwrap_or(false),
819 system: sq.system.unwrap_or(System::Client),
820 parent_partition_key: if from_condition {
821 None
822 } else {
823 parent_partition_key.map(<[String]>::to_vec)
824 },
825 bound_provider,
826 exists,
827 }))
828 }
829}
830
831fn build_filter_pipeline(
832 input: Rc<dyn Input>,
833 pipeline: impl FnOnce(Rc<dyn FilterInput>) -> Result<Rc<dyn FilterInput>>,
834 condition: Option<Condition>,
835) -> Result<Rc<dyn Input>> {
836 let start = FilterStart::new(input, condition);
837 let middle = pipeline(start.clone())?;
838 Ok(FilterEnd::new(start, middle))
839}
840
841fn is_not_and_does_not_contain_subquery(condition: &Condition) -> bool {
842 match condition {
843 Condition::CorrelatedSubquery { .. } => false,
844 Condition::Simple { .. } => true,
845 Condition::And(cs) | Condition::Or(cs) => {
846 cs.iter().all(is_not_and_does_not_contain_subquery)
847 }
848 }
849}
850
851fn apply_correlated_subquery_condition(
852 input: Rc<dyn FilterInput>,
853 related: &CorrelatedSubquery,
854 op: CorrelatedSubqueryOperator,
855) -> Rc<dyn FilterInput> {
856 if related.subquery.limit == Some(0.0) {
857 let result = op != CorrelatedSubqueryOperator::Exists;
858 return Filter::new(input, Rc::new(move |_: &Row| result));
859 }
860 let alias = related
861 .subquery
862 .alias
863 .clone()
864 .expect("Subquery must have an alias");
865 Exists::new(input, alias, related.correlation.parent_field.clone(), op)
866}
867
868fn gather_correlated_subquery_conditions(condition: Option<&Condition>) -> Vec<CsqCondition> {
869 fn gather(c: &Condition, out: &mut Vec<CsqCondition>) {
870 match c {
871 Condition::CorrelatedSubquery {
872 related, op, flip, ..
873 } => out.push(CsqCondition {
874 related: related.clone(),
875 op: *op,
876 flip: *flip,
877 }),
878 Condition::And(cs) | Condition::Or(cs) => cs.iter().for_each(|x| gather(x, out)),
879 Condition::Simple { .. } => {}
880 }
881 }
882 let mut out = Vec::new();
883 if let Some(c) = condition {
884 gather(c, &mut out);
885 }
886 out
887}
888
889fn uniquify_correlated_subquery_condition_aliases(ast: &Ast) -> Ast {
892 let Some(w @ (Condition::And(_) | Condition::Or(_))) = &ast.where_ else {
893 return ast.clone();
894 };
895 fn uniquify(c: &Condition, count: &mut usize) -> Condition {
896 match c {
897 Condition::Simple { .. } => c.clone(),
898 Condition::CorrelatedSubquery {
899 related,
900 op,
901 flip,
902 scalar,
903 } => {
904 let mut related = related.clone();
905 let alias = related.subquery.alias.take().unwrap_or_default();
906 related.subquery.alias = Some(format!("{alias}_{count}"));
907 *count += 1;
908 Condition::CorrelatedSubquery {
909 related,
910 op: *op,
911 flip: *flip,
912 scalar: *scalar,
913 }
914 }
915 Condition::And(cs) => Condition::And(cs.iter().map(|x| uniquify(x, count)).collect()),
916 Condition::Or(cs) => Condition::Or(cs.iter().map(|x| uniquify(x, count)).collect()),
917 }
918 }
919 let mut result = ast.clone();
920 result.where_ = Some(uniquify(w, &mut 0));
921 result
922}
923
924fn condition_includes_flipped_subquery_at_any_level(c: &Condition) -> bool {
925 match c {
926 Condition::CorrelatedSubquery { flip, .. } => flip.unwrap_or(false),
927 Condition::And(cs) | Condition::Or(cs) => cs
928 .iter()
929 .any(condition_includes_flipped_subquery_at_any_level),
930 Condition::Simple { .. } => false,
931 }
932}
933
934type PrimaryKeyOf<'a> = dyn Fn(&str) -> Result<Vec<String>> + 'a;
935
936pub fn complete_ordering(ast: &Ast, primary_key_of: &PrimaryKeyOf) -> Result<Ast> {
939 let primary_key = primary_key_of(&ast.table)?;
940 let mut result = ast.clone();
941 if let Some(related) = &ast.related {
942 let mut out = Vec::new();
943 for r in related {
944 let mut c = r.clone();
945 c.subquery = Box::new(complete_ordering(&r.subquery, primary_key_of)?);
946 out.push(c);
947 }
948 result.related = Some(out);
949 }
950 if let Some(w) = &ast.where_ {
951 result.where_ = Some(complete_ordering_in_condition(w, primary_key_of)?);
952 }
953 result.order_by = Some(add_primary_keys(&primary_key, ast.order_by.as_deref()));
954 Ok(result)
955}
956
957fn complete_ordering_in_condition(
958 c: &Condition,
959 primary_key_of: &PrimaryKeyOf,
960) -> Result<Condition> {
961 Ok(match c {
962 Condition::Simple { .. } => c.clone(),
963 Condition::CorrelatedSubquery {
964 related,
965 op,
966 flip,
967 scalar,
968 } => {
969 let mut related = related.clone();
970 related.subquery = Box::new(complete_ordering(&related.subquery, primary_key_of)?);
971 Condition::CorrelatedSubquery {
972 related,
973 op: *op,
974 flip: *flip,
975 scalar: *scalar,
976 }
977 }
978 Condition::And(cs) => Condition::And(
979 cs.iter()
980 .map(|x| complete_ordering_in_condition(x, primary_key_of))
981 .collect::<Result<_>>()?,
982 ),
983 Condition::Or(cs) => Condition::Or(
984 cs.iter()
985 .map(|x| complete_ordering_in_condition(x, primary_key_of))
986 .collect::<Result<_>>()?,
987 ),
988 })
989}
990
991fn add_primary_keys(primary_key: &[String], order_by: Option<&[OrderPart]>) -> Vec<OrderPart> {
992 let order_by = order_by.unwrap_or_default();
993 let mut to_add: Vec<&String> = Vec::new();
994 for k in primary_key {
995 if !to_add.contains(&k) && !order_by.iter().any(|p| &p.field == k) {
996 to_add.push(k);
997 }
998 }
999 let mut result = order_by.to_vec();
1000 result.extend(to_add.into_iter().map(|k| OrderPart {
1001 field: k.clone(),
1002 direction: Direction::Asc,
1003 }));
1004 result
1005}
1006
1007fn child_pipeline_name(name: &str, sq: &CorrelatedSubquery) -> String {
1011 format!(
1012 "{name}.{}",
1013 encode_uri_component(sq.subquery.alias.as_deref().unwrap_or(""), true)
1014 )
1015}
1016
1017pub fn aggregate_table_name(query_id: &str, sq: &CorrelatedSubquery, parent_name: &str) -> String {
1021 let path = child_pipeline_name(parent_name, sq);
1022 format!("{AGGREGATE_TABLE_PREFIX}{query_id}:{}", &path[1..])
1023}
1024
1025pub fn top_level_aggregate_table_name(query_id: &str) -> String {
1027 format!("{AGGREGATE_TABLE_PREFIX}{query_id}")
1028}
1029
1030pub fn group_table_name(query_id: &str) -> String {
1033 format!("{AGGREGATE_TABLE_PREFIX}{query_id}:#group")
1034}
1035
1036fn reducer_of(ast: &Ast) -> AggregateSpec {
1039 ast.aggregate
1040 .clone()
1041 .unwrap_or_else(|| AggregateSpec::new(AggregateFunction::Count))
1042}
1043
1044pub fn group_view_input(
1048 input: Rc<dyn Input>,
1049 ast: &Ast,
1050 delegate: &dyn BuilderDelegate,
1051) -> Result<Rc<dyn Input>> {
1052 let view_names = delegate.map_ast(ast).group_by.unwrap_or_default();
1053 let names = if delegate.aggregates_from_source() {
1054 delegate.aggregate_key_columns(&ast.table, ast.group_by.as_deref().unwrap_or_default())
1055 } else {
1056 view_names.clone()
1057 };
1058 let columns = view_names
1059 .into_iter()
1060 .zip(names)
1061 .map(|(out, from)| ProjectedColumn { out, from })
1062 .collect();
1063 Ok(GroupProjection::new(
1064 input,
1065 columns,
1066 ast.aggregate.as_ref().map(|a| a.fn_.as_str().to_owned()),
1067 )?)
1068}
1069
1070fn rename_columns(
1073 columns: &OrderedMap<Column>,
1074 from: &[String],
1075 to: &[String],
1076) -> OrderedMap<Column> {
1077 let mut sorted: Vec<(&String, &Column)> = columns.iter().collect();
1078 sorted.sort_by(|a, b| strings::utf16(a.0, b.0));
1079 sorted
1080 .into_iter()
1081 .map(|(name, c)| {
1082 let name = from
1083 .iter()
1084 .position(|f| f == name)
1085 .map_or_else(|| name.clone(), |i| to[i].clone());
1086 (name, c.clone())
1087 })
1088 .collect()
1089}
1090
1091fn sorted_columns(columns: &OrderedMap<Column>) -> OrderedMap<Column> {
1093 rename_columns(columns, &[], &[])
1094}
1095
1096fn per_row_predicate(condition: Option<&Condition>) -> Result<Option<Option<RowPredicate>>> {
1099 let Some(condition) = condition else {
1100 return Ok(Some(None));
1101 };
1102 let (filters, removed) = transform_filters(Some(condition));
1103 match filters {
1104 Some(filters) if !removed => Ok(Some(Some(create_predicate(&filters)?))),
1105 _ => Ok(None),
1106 }
1107}
1108
1109fn group_optimistic_delta(
1113 ast: &Ast,
1114 reducer: &AggregateSpec,
1115 table: &str,
1116 input_name: &dyn Fn(&str) -> String,
1117) -> Result<Option<OptimisticAggregate>> {
1118 if !is_invertible(reducer.fn_) {
1119 return Ok(None);
1120 }
1121 let Some(predicate) = per_row_predicate(ast.where_.as_ref())? else {
1122 return Ok(None);
1123 };
1124 let columns: Vec<String> = group_ordering(ast).into_iter().map(|p| p.field).collect();
1126 Ok(Some(OptimisticAggregate {
1127 aggregate_table: table.to_owned(),
1128 table: ast.table.clone(),
1129 key_field: columns.iter().map(|c| input_name(c)).collect(),
1130 child_field: columns,
1131 aggregate: reducer.clone(),
1132 predicate,
1133 grouped: true,
1134 }))
1135}
1136
1137pub fn encode_uri_component(s: &str, escaping_dots: bool) -> String {
1140 const HEX: &[u8; 16] = b"0123456789ABCDEF";
1141 let mut out = String::with_capacity(s.len());
1142 for b in s.bytes() {
1143 match b {
1144 b'A'..=b'Z' | b'a'..=b'z' | b'0'..=b'9' => out.push(b as char),
1145 b'.' if !escaping_dots => out.push('.'),
1146 b'-' | b'_' | b'!' | b'~' | b'*' | b'\'' | b'(' | b')' => out.push(b as char),
1147 _ => {
1148 out.push('%');
1149 out.push(HEX[(b >> 4) as usize] as char);
1150 out.push(HEX[(b & 0xF) as usize] as char);
1151 }
1152 }
1153 }
1154 out
1155}