1use std::collections::{BTreeMap, BTreeSet, HashSet};
16use std::sync::Arc;
17
18use common_function::function::FunctionContext;
19use common_telemetry::debug;
20use datafusion::config::{ConfigExtension, ExtensionOptions};
21use datafusion::datasource::DefaultTableSource;
22use datafusion::error::Result as DfResult;
23use datafusion_common::config::ConfigOptions;
24use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeRewriter};
25use datafusion_common::{Column, DFSchema, ScalarValue};
26use datafusion_expr::expr::{Exists, InSubquery};
27use datafusion_expr::utils::expr_to_columns;
28use datafusion_expr::{Expr, LogicalPlan, LogicalPlanBuilder, Subquery, col as col_fn};
29use datafusion_optimizer::analyzer::AnalyzerRule;
30use datafusion_optimizer::decorrelate_lateral_join::DecorrelateLateralJoin;
31use datafusion_optimizer::decorrelate_predicate_subquery::DecorrelatePredicateSubquery;
32use datafusion_optimizer::eliminate_filter::EliminateFilter;
33use datafusion_optimizer::extract_equijoin_predicate::ExtractEquijoinPredicate;
34use datafusion_optimizer::filter_null_join_keys::FilterNullJoinKeys;
35use datafusion_optimizer::optimizer::Optimizer;
36use datafusion_optimizer::propagate_empty_relation::PropagateEmptyRelation;
37use datafusion_optimizer::push_down_filter::PushDownFilter;
38use datafusion_optimizer::rewrite_set_comparison::RewriteSetComparison;
39use datafusion_optimizer::scalar_subquery_to_join::ScalarSubqueryToJoin;
40use datafusion_optimizer::simplify_expressions::SimplifyExpressions;
41use promql::extension_plan::{FusedSeries, SeriesDivide};
42use substrait::{DFLogicalSubstraitConvertor, SubstraitPlan};
43use table::metadata::TableType;
44use table::table::adapter::DfTableProviderAdapter;
45
46use crate::dist_plan::RemoteDynFilterProducerId;
47use crate::dist_plan::analyzer::utils::{
48 PatchOptimizerContext, PlanTreeExpressionSimplifier, aliased_columns_for,
49 rewrite_merge_sort_exprs,
50};
51use crate::dist_plan::commutativity::{
52 Categorizer, Commutativity, partial_commutative_transformer,
53};
54use crate::dist_plan::merge_scan::MergeScanLogicalPlan;
55use crate::dist_plan::merge_sort::MergeSortLogicalPlan;
56use crate::metrics::PUSH_DOWN_FALLBACK_ERRORS_TOTAL;
57use crate::optimizer::expr_depth;
58use crate::optimizer::infer_aggregate_input_bounds::InferAggregateInputBoundsRule;
59use crate::options::ScheduledTimeExtension;
60use crate::plan::ExtractExpr;
61use crate::query_engine::DefaultSerializer;
62
63#[cfg(test)]
64mod test;
65
66mod fallback;
67pub(crate) mod utils;
68
69pub(crate) use utils::AliasMapping;
70
71const OTHER_PHY_PART_COL_PLACEHOLDER: &str = "__OTHER_PHYSICAL_PART_COLS_PLACEHOLDER__";
73
74#[derive(Debug, Clone)]
75pub struct DistPlannerOptions {
76 pub allow_query_fallback: bool,
77}
78
79impl ConfigExtension for DistPlannerOptions {
80 const PREFIX: &'static str = "dist_planner";
81}
82
83impl ExtensionOptions for DistPlannerOptions {
84 fn as_any(&self) -> &dyn std::any::Any {
85 self
86 }
87
88 fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
89 self
90 }
91
92 fn cloned(&self) -> Box<dyn ExtensionOptions> {
93 Box::new(self.clone())
94 }
95
96 fn set(&mut self, key: &str, value: &str) -> DfResult<()> {
97 Err(datafusion_common::DataFusionError::NotImplemented(format!(
98 "DistPlannerOptions does not support set key: {key} with value: {value}"
99 )))
100 }
101
102 fn entries(&self) -> Vec<datafusion::config::ConfigEntry> {
103 vec![datafusion::config::ConfigEntry {
104 key: "allow_query_fallback".to_string(),
105 value: Some(self.allow_query_fallback.to_string()),
106 description: "Allow query fallback to fallback plan rewriter",
107 }]
108 }
109}
110
111#[derive(Debug, Default)]
114pub struct DistPlannerAnalyzer {}
115
116impl AnalyzerRule for DistPlannerAnalyzer {
117 fn name(&self) -> &str {
118 "DistPlannerAnalyzer"
119 }
120
121 fn analyze(
122 &self,
123 plan: LogicalPlan,
124 config: &ConfigOptions,
125 ) -> datafusion_common::Result<LogicalPlan> {
126 expr_depth::validate_plan(&plan)?;
127 let mut config = config.clone();
128 let explicit = config
130 .extensions
131 .get::<FunctionContext>()
132 .is_some_and(|context| {
133 context
134 .query_ctx
135 .extension("datafusion.optimizer.filter_null_join_keys")
136 .is_some()
137 });
138 if !explicit {
139 config.optimizer.filter_null_join_keys = true;
140 }
141 let config = Arc::new(config);
142 let opt = config.extensions.get::<DistPlannerOptions>();
143 let allow_fallback = opt.map(|o| o.allow_query_fallback).unwrap_or(false);
144
145 let scheduled_time = config
149 .extensions
150 .get::<ScheduledTimeExtension>()
151 .and_then(|ext| ext.scheduled_time);
152
153 let optimizer_context = PatchOptimizerContext {
154 inner: datafusion_optimizer::OptimizerContext::new(),
155 config: config.clone(),
156 scheduled_time,
157 };
158
159 let plan = plan
160 .rewrite_with_subqueries(&mut PlanTreeExpressionSimplifier::new(optimizer_context))?
161 .data;
162 expr_depth::validate_plan(&plan)?;
163 let fallback_plan = plan.clone();
164
165 let optimizer_context = PatchOptimizerContext {
172 inner: datafusion_optimizer::OptimizerContext::new(),
173 config: config.clone(),
174 scheduled_time,
175 };
176 let plan = match pre_merge_scan_optimizer().optimize(plan, &optimizer_context, |_, _| {}) {
177 Ok(plan) => plan,
178 Err(err) => {
179 if allow_fallback {
180 common_telemetry::warn!(err; "Failed to pre-optimize plan, using fallback plan rewriter for plan: {fallback_plan}");
181 PUSH_DOWN_FALLBACK_ERRORS_TOTAL.inc();
182 return self.use_fallback(fallback_plan);
183 } else {
184 return Err(err);
185 }
186 }
187 };
188 let plan = plan
189 .transform_down_with_subqueries(&unwrap_dictionary_literals)?
190 .data;
191
192 let result = match self.try_push_down(plan.clone()) {
193 Ok(plan) => plan,
194 Err(err) => {
195 if allow_fallback {
196 common_telemetry::warn!(err; "Failed to push down plan, using fallback plan rewriter for plan: {plan}");
197 PUSH_DOWN_FALLBACK_ERRORS_TOTAL.inc();
199 self.use_fallback(fallback_plan)?
200 } else {
201 return Err(err);
202 }
203 }
204 };
205
206 Ok(result)
207 }
208}
209
210fn pre_merge_scan_optimizer() -> Optimizer {
234 Optimizer::with_rules(vec![
235 Arc::new(RewriteSetComparison::new()),
236 Arc::new(DecorrelatePredicateSubquery::new()),
237 Arc::new(ScalarSubqueryToJoin::new()),
238 Arc::new(DecorrelateLateralJoin::new()),
239 Arc::new(ExtractEquijoinPredicate::new()),
240 Arc::new(EliminateFilter::new()),
241 Arc::new(PropagateEmptyRelation::new()),
242 Arc::new(FilterNullJoinKeys::default()),
243 Arc::new(InferAggregateInputBoundsRule),
244 Arc::new(PushDownFilter::new()),
245 Arc::new(SimplifyExpressions::new()),
246 ])
247}
248
249fn unwrap_dictionary_literals(plan: LogicalPlan) -> DfResult<Transformed<LogicalPlan>> {
250 if matches!(&plan, LogicalPlan::Values(_)) {
253 return Ok(Transformed::no(plan));
254 }
255
256 plan.map_expressions(|expr| {
257 expr.transform_up(|expr| match expr {
258 Expr::Literal(ScalarValue::Dictionary(_, value), metadata) => {
259 Ok(Transformed::yes(Expr::Literal(*value, metadata)))
260 }
261 _ => Ok(Transformed::no(expr)),
262 })
263 })
264}
265
266impl DistPlannerAnalyzer {
267 fn try_push_down(&self, plan: LogicalPlan) -> DfResult<LogicalPlan> {
269 let plan =
274 plan.transform_with_subqueries(&|plan| Self::inspect_plan_with_subquery(plan))?;
275 let plan = rewrite_hybrid_binary_operands(plan.data)?;
276 let mut rewriter = PlanRewriter::new(&plan);
277 let result = plan.rewrite(&mut rewriter)?.data;
278 Self::assign_merge_scan_remote_dyn_filter_producer_ids(result)
279 }
280
281 fn use_fallback(&self, plan: LogicalPlan) -> DfResult<LogicalPlan> {
283 let mut rewriter = fallback::FallbackPlanRewriter;
284 let result = plan.rewrite(&mut rewriter)?.data;
285 Self::assign_merge_scan_remote_dyn_filter_producer_ids(result)
286 }
287
288 fn inspect_plan_with_subquery(plan: LogicalPlan) -> DfResult<Transformed<LogicalPlan>> {
289 if let LogicalPlan::Limit(_) | LogicalPlan::Distinct(_) = &plan {
292 return Ok(Transformed::no(plan));
293 }
294
295 let exprs = plan
296 .expressions_consider_join()
297 .into_iter()
298 .map(|e| e.transform(Self::transform_subquery).map(|x| x.data))
299 .collect::<DfResult<Vec<_>>>()?;
300
301 if !matches!(plan, LogicalPlan::Unnest(_)) {
303 let inputs = plan.inputs().into_iter().cloned().collect::<Vec<_>>();
304 Ok(Transformed::yes(plan.with_new_exprs(exprs, inputs)?))
305 } else {
306 Ok(Transformed::no(plan))
307 }
308 }
309
310 fn transform_subquery(expr: Expr) -> DfResult<Transformed<Expr>> {
311 match expr {
312 Expr::Exists(exists) => Ok(Transformed::yes(Expr::Exists(Exists {
313 subquery: Self::handle_subquery(exists.subquery)?,
314 negated: exists.negated,
315 }))),
316 Expr::InSubquery(in_subquery) => Ok(Transformed::yes(Expr::InSubquery(InSubquery {
317 expr: in_subquery.expr,
318 subquery: Self::handle_subquery(in_subquery.subquery)?,
319 negated: in_subquery.negated,
320 }))),
321 Expr::ScalarSubquery(scalar_subquery) => Ok(Transformed::yes(Expr::ScalarSubquery(
322 Self::handle_subquery(scalar_subquery)?,
323 ))),
324
325 _ => Ok(Transformed::no(expr)),
326 }
327 }
328
329 fn handle_subquery(subquery: Subquery) -> DfResult<Subquery> {
330 let mut rewriter = PlanRewriter::new(&subquery.subquery);
331 let mut rewrote_subquery = subquery
332 .subquery
333 .as_ref()
334 .clone()
335 .rewrite(&mut rewriter)?
336 .data;
337 if matches!(rewrote_subquery, LogicalPlan::Extension(_)) {
339 let output_schema = rewrote_subquery.schema().clone();
340 let project_exprs = output_schema
341 .fields()
342 .iter()
343 .map(|f| col_fn(f.name()))
344 .collect::<Vec<_>>();
345 rewrote_subquery = LogicalPlanBuilder::from(rewrote_subquery)
346 .project(project_exprs)?
347 .build()?;
348 }
349
350 Ok(Subquery {
351 subquery: Arc::new(rewrote_subquery),
352 outer_ref_columns: subquery.outer_ref_columns,
353 spans: Default::default(),
354 })
355 }
356
357 fn assign_merge_scan_remote_dyn_filter_producer_ids(
358 plan: LogicalPlan,
359 ) -> DfResult<LogicalPlan> {
360 let mut assigner = MergeScanRemoteDynFilterProducerIdAssigner::default();
361 Ok(plan.rewrite_with_subqueries(&mut assigner)?.data)
362 }
363}
364
365#[derive(Debug, Default)]
366struct RemoteDynFilterProducerIdAllocator {
367 next_remote_dyn_filter_producer_id: u64,
368}
369
370impl RemoteDynFilterProducerIdAllocator {
371 fn allocate(&mut self) -> RemoteDynFilterProducerId {
372 self.next_remote_dyn_filter_producer_id += 1;
373 RemoteDynFilterProducerId::new(self.next_remote_dyn_filter_producer_id)
374 }
375}
376
377#[derive(Debug, Default)]
379struct MergeScanRemoteDynFilterProducerIdAssigner {
380 remote_dyn_filter_producer_id_allocator: RemoteDynFilterProducerIdAllocator,
381}
382
383impl TreeNodeRewriter for MergeScanRemoteDynFilterProducerIdAssigner {
384 type Node = LogicalPlan;
385
386 fn f_up(&mut self, node: Self::Node) -> DfResult<Transformed<Self::Node>> {
387 let LogicalPlan::Extension(extension) = &node else {
388 return Ok(Transformed::no(node));
389 };
390 let Some(merge_scan) = extension
391 .node
392 .as_any()
393 .downcast_ref::<MergeScanLogicalPlan>()
394 else {
395 return Ok(Transformed::no(node));
396 };
397
398 Ok(Transformed::yes(
399 merge_scan
400 .clone()
401 .with_remote_dyn_filter_producer_id(
402 self.remote_dyn_filter_producer_id_allocator.allocate(),
403 )
404 .into_logical_plan(),
405 ))
406 }
407}
408
409#[derive(Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
411enum RewriterStatus {
412 #[default]
413 Unexpanded,
414 Expanded,
415}
416
417#[derive(Debug, Default)]
418struct PlanRewriter {
419 whole_plan_encodable: bool,
421 level: usize,
423 stack: Vec<(LogicalPlan, usize)>,
425 stage: Vec<LogicalPlan>,
427 status: RewriterStatus,
428 partition_cols: Option<AliasMapping>,
430 column_requirements: Vec<(HashSet<Column>, usize)>,
456 expand_on_next_call: bool,
461 expand_on_next_part_cond_trans_commutative: bool,
473 new_child_plan: Option<LogicalPlan>,
474}
475
476fn native_operand_wrapper_child(plan: &LogicalPlan) -> Option<&LogicalPlan> {
477 match plan {
478 LogicalPlan::SubqueryAlias(alias) => Some(alias.input.as_ref()),
479 LogicalPlan::Projection(projection) => Some(projection.input.as_ref()),
480 LogicalPlan::Filter(filter) => Some(filter.input.as_ref()),
481 LogicalPlan::Window(window) => Some(window.input.as_ref()),
482 _ => None,
483 }
484}
485
486fn native_operand_fused(plan: &LogicalPlan) -> Option<&LogicalPlan> {
487 let mut node = plan;
488 while let Some(child) = native_operand_wrapper_child(node) {
489 node = child;
490 }
491 (is_fused_series_plan(node) && matches!(node.inputs().as_slice(), [LogicalPlan::TableScan(_)]))
492 .then_some(node)
493}
494
495fn is_native_operand_subtree(plan: &LogicalPlan) -> bool {
496 native_operand_fused(plan).is_some()
497}
498
499fn rewrite_hybrid_binary_operands(plan: LogicalPlan) -> DfResult<LogicalPlan> {
500 plan.transform_up(|plan| {
501 let LogicalPlan::Join(join) = &plan else {
502 return Ok(Transformed::no(plan));
503 };
504 if !is_native_operand_subtree(&join.left) || !is_native_operand_subtree(&join.right) {
505 return Ok(Transformed::no(plan));
506 }
507 fn rewrite_side(side: &LogicalPlan) -> DfResult<LogicalPlan> {
508 if let Some(child) = native_operand_wrapper_child(side) {
509 let rewritten_child = rewrite_side(child)?;
510 return side
511 .clone()
512 .with_new_exprs(side.expressions(), vec![rewritten_child]);
513 }
514 let mut rw = PlanRewriter::new(side);
515 Ok(side.clone().rewrite(&mut rw)?.data)
516 }
517 let left = rewrite_side(&join.left)?;
518 let right = rewrite_side(&join.right)?;
519 let mut rebuilt = LogicalPlan::Join(join.clone());
520 rebuilt = rebuilt.with_new_exprs(rebuilt.expressions(), vec![left, right])?;
521 Ok(Transformed::yes(rebuilt))
522 })
523 .map(|transformed| transformed.data)
524}
525
526fn is_fused_series_plan(plan: &LogicalPlan) -> bool {
527 matches!(plan, LogicalPlan::Extension(extension) if extension.node.as_any().is::<FusedSeries>())
528}
529
530impl PlanRewriter {
531 fn new(plan: &LogicalPlan) -> Self {
534 let whole_plan_encodable = DFLogicalSubstraitConvertor
535 .encode(plan, DefaultSerializer)
536 .is_ok();
537 Self {
538 whole_plan_encodable,
539 ..Default::default()
540 }
541 }
542
543 fn get_parent(&self) -> Option<&LogicalPlan> {
544 self.stack
546 .iter()
547 .rev()
548 .find(|(_, level)| *level == self.level - 1)
549 .map(|(node, _)| node)
550 }
551
552 fn should_expand(&mut self, plan: &LogicalPlan) -> DfResult<bool> {
554 debug!(
555 "Check should_expand at level: {} with Stack:\n{}, ",
556 self.level,
557 self.stack
558 .iter()
559 .map(|(p, l)| format!("{l}:{}{}", " ".repeat(l - 1), p.display()))
560 .collect::<Vec<String>>()
561 .join("\n"),
562 );
563 if !self.whole_plan_encodable
572 && let Err(e) = DFLogicalSubstraitConvertor.encode(plan, DefaultSerializer)
573 {
574 debug!(
575 "PlanRewriter: plan cannot be converted to substrait with error={e:?}, expanding now: {plan}"
576 );
577 return Ok(true);
578 }
579
580 if self.expand_on_next_call {
581 self.expand_on_next_call = false;
582 debug!("PlanRewriter: expand_on_next_call is true, expanding now");
583 return Ok(true);
584 }
585
586 if self.expand_on_next_part_cond_trans_commutative {
587 let comm = Categorizer::check_plan(plan, self.partition_cols.clone())?;
588 match comm {
589 Commutativity::PartialCommutative => {
590 self.expand_on_next_part_cond_trans_commutative = false;
596 self.expand_on_next_call = true;
597 }
598 Commutativity::ConditionalCommutative(_)
599 | Commutativity::TransformedCommutative { .. } => {
600 self.expand_on_next_part_cond_trans_commutative = false;
603 debug!(
604 "PlanRewriter: meet a new conditional/transformed commutative plan, expanding now: {plan}"
605 );
606 return Ok(true);
607 }
608 _ => (),
609 }
610 }
611
612 match Categorizer::check_plan(plan, self.partition_cols.clone())? {
613 Commutativity::Commutative => {
614 if let LogicalPlan::Extension(ext_a) = plan
619 && ext_a.node.name() == SeriesDivide::name()
620 && let Some(LogicalPlan::Extension(ext_b)) = self.stage.last()
621 && ext_b.node.name() == MergeSortLogicalPlan::name()
622 {
623 self.stage.pop();
627 self.expand_on_next_part_cond_trans_commutative = false;
628 self.column_requirements.clear();
629 }
630 }
631 Commutativity::PartialCommutative => {
632 if let Some(plan) = partial_commutative_transformer(plan) {
633 self.update_column_requirements(&plan, self.level - 1);
635 self.expand_on_next_part_cond_trans_commutative = true;
636 self.stage.push(plan)
637 }
638 }
639 Commutativity::ConditionalCommutative(transformer) => {
640 if let Some(transformer) = transformer
641 && let Some(plan) = transformer(plan)
642 {
643 self.update_column_requirements(&plan, self.level - 1);
645 self.expand_on_next_part_cond_trans_commutative = true;
646 self.stage.push(plan)
647 }
648 }
649 Commutativity::TransformedCommutative { transformer } => {
650 if let Some(transformer) = transformer {
651 let transformer_actions = transformer(plan)?;
652 debug!(
653 "PlanRewriter: transformed plan: {}\n from {plan}",
654 transformer_actions
655 .extra_parent_plans
656 .iter()
657 .enumerate()
658 .map(|(i, p)| format!(
659 "Extra {i}-th parent plan from parent to child = {}",
660 p.display()
661 ))
662 .collect::<Vec<_>>()
663 .join("\n")
664 );
665 if let Some(new_child_plan) = &transformer_actions.new_child_plan {
666 debug!("PlanRewriter: new child plan: {}", new_child_plan);
667 }
668 if let Some(last_stage) = transformer_actions.extra_parent_plans.last() {
669 self.update_column_requirements(last_stage, self.level - 1);
672 }
673 self.stage
674 .extend(transformer_actions.extra_parent_plans.into_iter().rev());
675 self.expand_on_next_call = true;
676 self.new_child_plan = transformer_actions.new_child_plan;
677 }
678 }
679 Commutativity::NonCommutative
680 | Commutativity::Unimplemented
681 | Commutativity::Unsupported => {
682 debug!("PlanRewriter: meet a non-commutative plan, expanding now: {plan}");
683 return Ok(true);
684 }
685 }
686
687 Ok(false)
688 }
689
690 fn update_column_requirements(&mut self, plan: &LogicalPlan, plan_level: usize) {
694 debug!(
695 "PlanRewriter: update column requirements for plan: {plan}\n with old column_requirements: {:?}",
696 self.column_requirements
697 );
698 let mut container = HashSet::new();
699 for expr in plan.expressions() {
700 let _ = expr_to_columns(&expr, &mut container);
702 }
703
704 self.column_requirements.push((container, plan_level));
705 debug!(
706 "PlanRewriter: updated column requirements: {:?}",
707 self.column_requirements
708 );
709 }
710
711 fn is_expanded(&self) -> bool {
712 self.status == RewriterStatus::Expanded
713 }
714
715 fn set_expanded(&mut self) {
716 self.status = RewriterStatus::Expanded;
717 }
718
719 fn set_unexpanded(&mut self) {
720 self.status = RewriterStatus::Unexpanded;
721 }
722
723 fn maybe_set_partitions(&mut self, plan: &LogicalPlan) -> DfResult<()> {
724 if let Some(part_cols) = &mut self.partition_cols {
725 let child = plan.inputs().first().cloned().ok_or_else(|| {
727 datafusion_common::DataFusionError::Internal(format!(
728 "PlanRewriter: maybe_set_partitions: plan has no child: {plan}"
729 ))
730 })?;
731
732 for alias_set in part_cols.values_mut() {
733 let aliased_cols = aliased_columns_for(
734 &alias_set.clone().into_iter().collect(),
735 plan,
736 Some(child),
737 )?;
738 *alias_set = aliased_cols.into_values().flatten().collect();
739 }
740
741 debug!(
742 "PlanRewriter: maybe_set_partitions: updated partition columns: {:?} at plan: {}",
743 part_cols,
744 plan.display()
745 );
746
747 return Ok(());
748 }
749
750 if let LogicalPlan::TableScan(table_scan) = plan
751 && let Some(source) = table_scan.source.downcast_ref::<DefaultTableSource>()
752 && let Some(provider) = source
753 .table_provider
754 .downcast_ref::<DfTableProviderAdapter>()
755 {
756 let table = provider.table();
757 if table.table_type() == TableType::Base {
758 let info = table.table_info();
759 let partition_key_indices = info.meta.partition_key_indices.clone();
760 let schema = info.meta.schema.clone();
761 let mut partition_cols = partition_key_indices
762 .iter()
763 .map(|index| schema.column_name_by_index(*index).to_string())
764 .collect::<Vec<String>>();
765 debug!(
766 "PlanRewriter: loaded table partition metadata, table: {}, table_id: {}, partition_key_indices: {:?}, partition_columns: {:?}",
767 info.name, info.ident.table_id, info.meta.partition_key_indices, partition_cols,
768 );
769
770 let partition_rules = table.partition_rules();
771 let exist_phy_part_cols_not_in_logical_table = partition_rules
772 .map(|r| !r.extra_phy_cols_not_in_logical_table.is_empty())
773 .unwrap_or(false);
774
775 if exist_phy_part_cols_not_in_logical_table && partition_cols.is_empty() {
776 partition_cols.push(OTHER_PHY_PART_COL_PLACEHOLDER.to_string());
784 }
785 self.partition_cols = Some(
786 partition_cols
787 .into_iter()
788 .map(|c| {
789 if c == OTHER_PHY_PART_COL_PLACEHOLDER {
790 return Ok((c.clone(), BTreeSet::new()));
792 }
793 let index =
794 if let Some(c) = plan.schema().index_of_column_by_name(None, &c){
795 c
796 } else {
797 return Ok((c.clone(), BTreeSet::new()))
800 };
801 let column = plan.schema().columns().get(index).cloned().ok_or_else(|| {
802 datafusion_common::DataFusionError::Internal(format!(
803 "PlanRewriter: maybe_set_partitions: column index {index} out of bounds in schema of plan: {plan}"
804 ))
805 })?;
806 Ok((c.clone(), BTreeSet::from([column])))
807 })
808 .collect::<DfResult<AliasMapping>>()?,
809 );
810 }
811 }
812
813 Ok(())
814 }
815
816 fn pop_stack(&mut self) {
818 self.level -= 1;
819 self.stack.pop();
820 }
821
822 fn expand(&mut self, mut on_node: LogicalPlan) -> DfResult<LogicalPlan> {
823 let schema = on_node.schema().clone();
825 if let Some(new_child_plan) = self.new_child_plan.take() {
826 on_node = new_child_plan;
828 }
829 let mut rewriter = EnforceDistRequirementRewriter::new(
834 std::mem::take(&mut self.column_requirements),
835 self.level,
836 );
837 if rewriter.has_applicable_requirements() {
838 debug!(
839 "PlanRewriter: enforce column requirements for node: {on_node} with rewriter: {rewriter:?}"
840 );
841 on_node = on_node.rewrite(&mut rewriter)?.data;
842 debug!(
843 "PlanRewriter: after enforced column requirements with rewriter: {rewriter:?} for node:\n{on_node}"
844 );
845 }
846
847 debug!(
848 "PlanRewriter: expand on node: {on_node} with partition col alias mapping: {:?}",
849 self.partition_cols
850 );
851
852 let mut node = MergeScanLogicalPlan::new(on_node.clone(), false).into_logical_plan();
854
855 for new_stage in self.stage.drain(..) {
857 let new_stage = if let LogicalPlan::Extension(ext) = &new_stage
859 && let Some(merge_sort) = ext.node.as_any().downcast_ref::<MergeSortLogicalPlan>()
860 {
861 rewrite_merge_sort_exprs(merge_sort, &on_node)?
863 } else {
864 new_stage
865 };
866 node = new_stage
867 .with_new_exprs(new_stage.expressions_consider_join(), vec![node.clone()])?;
868 }
869 self.set_expanded();
870
871 let has_frame_metadata = |schema: &DFSchema| {
875 schema
876 .metadata()
877 .keys()
878 .any(|key| key.starts_with("greptime.series."))
879 };
880 if node.schema() == &schema && has_frame_metadata(schema.as_ref()) {
881 return Ok(node);
882 }
883 if has_frame_metadata(schema.as_ref()) || has_frame_metadata(node.schema().as_ref()) {
884 return Err(datafusion_common::DataFusionError::Plan(
885 "distributed schema recovery cannot project a series frame".into(),
886 ));
887 }
888
889 let node = LogicalPlanBuilder::from(node)
892 .project(schema.iter().map(|(qualifier, field)| {
893 Expr::Column(Column::new(qualifier.cloned(), field.name()))
894 }))?
895 .build()?;
896
897 Ok(node)
898 }
899}
900
901#[derive(Debug)]
916struct EnforceDistRequirementRewriter {
917 column_requirements: Vec<(HashSet<Column>, usize)>,
921 cur_level: usize,
932 visited: Vec<VisitedNode>,
935 path: Vec<usize>,
938}
939
940#[derive(Debug)]
942struct VisitedNode {
943 depth: usize,
945 parent: Option<usize>,
947 plan: LogicalPlan,
949}
950
951impl EnforceDistRequirementRewriter {
952 fn new(column_requirements: Vec<(HashSet<Column>, usize)>, cur_level: usize) -> Self {
953 debug!(
954 "Create EnforceDistRequirementRewriter with column_requirements: {:?} at cur_level: {}",
955 column_requirements, cur_level
956 );
957 Self {
958 column_requirements,
959 cur_level,
960 visited: Vec::new(),
961 path: Vec::new(),
962 }
963 }
964
965 fn has_applicable_requirements(&self) -> bool {
970 self.column_requirements
971 .iter()
972 .any(|(_, level)| *level >= self.cur_level)
973 }
974
975 fn original_plan_at(&self, node: usize, level: usize) -> DfResult<Option<&LogicalPlan>> {
982 let mut ancestor = Some(node);
983 while let Some(candidate) = ancestor {
984 if self.visited[candidate].depth == level {
985 return Ok(Some(&self.visited[candidate].plan));
986 }
987 ancestor = self.visited[candidate].parent;
988 }
989
990 let mut found = None;
991 for (id, visited) in self.visited.iter().enumerate() {
992 if visited.depth != level || !self.is_descendant_of(id, node) {
993 continue;
994 }
995 if found.is_some() {
996 return Err(datafusion_common::DataFusionError::Internal(format!(
997 "EnforceDistRequirementRewriter: column requirement at level {level} has more than one candidate plan below, so which branch it refers to is ambiguous: {}",
998 self.visited[node].plan,
999 )));
1000 }
1001 found = Some(id);
1002 }
1003 Ok(found.map(|id| &self.visited[id].plan))
1004 }
1005
1006 fn is_descendant_of(&self, node: usize, ancestor: usize) -> bool {
1008 let mut current = node;
1009 while let Some(parent) = self.visited[current].parent {
1010 if parent == ancestor {
1011 return true;
1012 }
1013 current = parent;
1014 }
1015 false
1016 }
1017
1018 fn get_current_applicable_column_requirements(
1022 &self,
1023 node_id: usize,
1024 node: &LogicalPlan,
1025 ) -> DfResult<BTreeMap<(Column, usize), BTreeSet<Column>>> {
1026 let col_req_per_level = self
1027 .column_requirements
1028 .iter()
1029 .filter(|(_, level)| *level >= self.cur_level)
1030 .collect::<Vec<_>>();
1031
1032 let mut result_alias_mapping = BTreeMap::new();
1035 let Some(child) = node.inputs().first().cloned() else {
1036 return Ok(Default::default());
1037 };
1038 for (col_req, level) in col_req_per_level {
1039 if let Some(original) = self.original_plan_at(node_id, *level)? {
1040 let aliased_cols =
1042 aliased_columns_for(&col_req.iter().cloned().collect(), node, Some(original))?;
1043 for original_col in col_req {
1044 let aliased_cols = aliased_cols.get(original_col).cloned();
1045 if let Some(cols) = aliased_cols
1046 && !cols.is_empty()
1047 {
1048 result_alias_mapping.insert((original_col.clone(), *level), cols);
1049 } else {
1050 let aliases_in_child = aliased_columns_for(
1055 &[original_col.clone()].into(),
1056 child,
1057 Some(original),
1058 )?;
1059 let Some(aliases) = aliases_in_child
1060 .get(original_col)
1061 .cloned()
1062 .filter(|a| !a.is_empty())
1063 else {
1064 return Err(datafusion_common::DataFusionError::Internal(format!(
1065 "EnforceDistRequirementRewriter: no alias found for required column {original_col} at level {level} in current node's child plan: \n{child} from original plan: \n{original}",
1066 )));
1067 };
1068
1069 result_alias_mapping.insert((original_col.clone(), *level), aliases);
1070 }
1071 }
1072 }
1073 }
1074 Ok(result_alias_mapping)
1075 }
1076}
1077
1078impl EnforceDistRequirementRewriter {
1079 fn enforce_column_requirements(
1084 &mut self,
1085 node_id: usize,
1086 node: LogicalPlan,
1087 ) -> DfResult<Transformed<LogicalPlan>> {
1088 if let LogicalPlan::Projection(ref projection) = node {
1090 let mut applicable_column_requirements =
1091 self.get_current_applicable_column_requirements(node_id, &node)?;
1092
1093 debug!(
1094 "EnforceDistRequirementRewriter: applicable column requirements at level {} = {:?} for node {}",
1095 self.cur_level,
1096 applicable_column_requirements,
1097 node.display()
1098 );
1099
1100 for expr in &projection.expr {
1101 let (qualifier, name) = expr.qualified_name();
1102 let column = Column::new(qualifier, name);
1103 applicable_column_requirements.retain(|_col_level, alias_set| {
1104 !alias_set.contains(&column)
1106 });
1107 }
1108 if applicable_column_requirements.is_empty() {
1109 return Ok(Transformed::no(node));
1110 }
1111
1112 let mut new_exprs = projection.expr.clone();
1113 for (col, alias_set) in &applicable_column_requirements {
1114 new_exprs.push(Expr::Column(alias_set.first().cloned().ok_or_else(
1116 || {
1117 datafusion_common::DataFusionError::Internal(
1118 format!("EnforceDistRequirementRewriter: alias set is empty, for column {col:?} in node {node}"),
1119 )
1120 },
1121 )?));
1122 }
1123 let new_node =
1124 node.with_new_exprs(new_exprs, node.inputs().into_iter().cloned().collect())?;
1125 debug!(
1126 "EnforceDistRequirementRewriter: added missing columns {:?} to projection node from old node: \n{node}\n Making new node: \n{new_node}",
1127 applicable_column_requirements
1128 );
1129
1130 self.visited[node_id].plan = new_node.clone();
1132
1133 return Ok(Transformed::yes(new_node));
1135 }
1136 Ok(Transformed::no(node))
1137 }
1138}
1139
1140impl TreeNodeRewriter for EnforceDistRequirementRewriter {
1141 type Node = LogicalPlan;
1142
1143 fn f_down(&mut self, node: Self::Node) -> DfResult<Transformed<Self::Node>> {
1144 let id = self.visited.len();
1145 self.visited.push(VisitedNode {
1146 depth: self.cur_level,
1147 parent: self.path.last().copied(),
1148 plan: node.clone(),
1149 });
1150 self.path.push(id);
1151 self.cur_level += 1;
1152 Ok(Transformed::no(node))
1153 }
1154
1155 fn f_up(&mut self, node: Self::Node) -> DfResult<Transformed<Self::Node>> {
1156 self.cur_level -= 1;
1157 let node_id = *self.path.last().ok_or_else(|| {
1158 datafusion_common::DataFusionError::Internal(
1159 "EnforceDistRequirementRewriter: f_up without a matching f_down".to_string(),
1160 )
1161 })?;
1162 self.visited[node_id].plan = node.clone();
1164
1165 let transformed = self.enforce_column_requirements(node_id, node)?;
1166 self.path.pop();
1167 Ok(transformed)
1168 }
1169}
1170
1171impl TreeNodeRewriter for PlanRewriter {
1172 type Node = LogicalPlan;
1173
1174 fn f_down<'a>(&mut self, node: Self::Node) -> DfResult<Transformed<Self::Node>> {
1176 self.level += 1;
1177 self.stack.push((node.clone(), self.level));
1178 self.stage.clear();
1180 self.set_unexpanded();
1181 self.partition_cols = None;
1182 Ok(Transformed::no(node))
1183 }
1184
1185 fn f_up(&mut self, node: Self::Node) -> DfResult<Transformed<Self::Node>> {
1189 if self.is_expanded() {
1191 self.pop_stack();
1192 return Ok(Transformed::no(node));
1193 }
1194
1195 if node.inputs().is_empty() && !matches!(node, LogicalPlan::TableScan(_)) {
1197 self.set_expanded();
1198 self.pop_stack();
1199 return Ok(Transformed::no(node));
1200 }
1201
1202 self.maybe_set_partitions(&node)?;
1203
1204 let Some(parent) = self.get_parent() else {
1205 debug!("Plan Rewriter: expand now for no parent found for node: {node}");
1206 let node = self.expand(node);
1207 debug!(
1208 "PlanRewriter: expanded plan: {}",
1209 match &node {
1210 Ok(n) => n.to_string(),
1211 Err(e) => format!("Error expanding plan: {e}"),
1212 }
1213 );
1214 let node = node?;
1215 self.pop_stack();
1216 return Ok(Transformed::yes(node));
1217 };
1218
1219 let parent = parent.clone();
1220
1221 if self.should_expand(&parent)? {
1222 debug!(
1224 "PlanRewriter: should expand child:\n {node}\n Of Parent: {}",
1225 parent.display()
1226 );
1227 let node = self.expand(node);
1228 debug!(
1229 "PlanRewriter: expanded plan: {}",
1230 match &node {
1231 Ok(n) => n.to_string(),
1232 Err(e) => format!("Error expanding plan: {e}"),
1233 }
1234 );
1235 let node = node?;
1236 self.pop_stack();
1237 return Ok(Transformed::yes(node));
1238 }
1239
1240 self.pop_stack();
1241 Ok(Transformed::no(node))
1242 }
1243}