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