Skip to main content

query/dist_plan/
analyzer.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use 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
71/// Placeholder for other physical partition columns that are not in logical table
72const 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/// Rewrites a logical plan into a distributed plan: the part above a merge scan runs on the
112/// frontend, and every `MergeScan` carries the sub-plan that runs in a region.
113#[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        // Preserve the historical pre-MergeScan default unless explicitly set.
129        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        // When the query is running under a scheduled Flow context, carry the
146        // logical "now" so that `SimplifyExpressions` does not constant-fold
147        // `now()` into wall-clock literals on the remote sub-plans.
148        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        // Run a filter-focused optimizer subset before MergeScan wraps remote
166        // inputs. MergeScan intentionally hides its remote_input from later
167        // optimizer passes; this pass only normalizes/decorrelates enough for
168        // DataFusion's PushDownFilter to put side-local predicates into scans.
169        // Keep this narrow: rules like PushDownLimit, OptimizeProjections, and
170        // DISTINCT rewrites can change global distributed-planning boundaries.
171        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                    // if push down failed, use fallback plan rewriter
198                    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
210/// Builds the small optimizer pre-pass that runs before `MergeScan` wrapping.
211///
212/// This is intentionally not DataFusion's full optimizer. After
213/// `PlanRewriter` wraps remote table scans in `MergeScan`,
214/// `MergeScanLogicalPlan::inputs()` hides `remote_input`, so ordinary optimizer
215/// rules can no longer see into the remote side. The main rule we need here is
216/// `PushDownFilter`: it moves side-local join/filter predicates into
217/// `TableScan.filters`, where region pruning and scan-level pruning can use
218/// them.
219///
220/// The rules before `PushDownFilter` are only the minimum cleanup/rewrite steps
221/// needed to make that filter pushdown safe around subqueries and set
222/// comparisons. For example, `RewriteSetComparison` handles ANY/ALL before they
223/// can become scan filters, and the decorrelation/subquery rules expose
224/// supported predicates as joins/filters instead of leaving raw subquery
225/// expressions under a scan.
226///
227/// Keep this list narrow. Do not add broad plan-shaping rules such as
228/// `PushDownLimit`, projection optimization, DISTINCT rewrites, or join-type
229/// rewrites here: those can change the local/remote distributed boundary or
230/// degrade unrelated planning diagnostics. Such rules belong either before this
231/// analyzer or after distributed planning, not in this pre-MergeScan,
232/// filter-focused pass.
233fn 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    // A Values plan derives its schema from its expressions. Rewriting only the expressions would
251    // leave that schema inconsistent, which affects DML planning.
252    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    /// Try push down as many nodes as possible
268    fn try_push_down(&self, plan: LogicalPlan) -> DfResult<LogicalPlan> {
269        // Use the subquery-aware transform so expression subqueries (including
270        // nested scalar subqueries left in place by DataFusion 55's
271        // `enable_physical_uncorrelated_scalar_subquery`) are visited at every
272        // depth and their table scans get wrapped in `MergeScan`.
273        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    /// Use fallback plan rewriter to rewrite the plan and only push down table scan nodes
282    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        // Workaround for https://github.com/GreptimeTeam/greptimedb/issues/5469 and https://github.com/GreptimeTeam/greptimedb/issues/5799
290        // FIXME(yingwen): Remove the `Limit` plan once we update DataFusion.
291        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        // Some plans that are special treated (should not call `with_new_exprs` on them)
302        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        // Workaround. DF doesn't support the first plan in subquery to be an Extension
338        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/// Assigns query-local RDF producer ids to visible `MergeScan` nodes after plan rewriting.
378#[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/// Status of the rewriter to mark if the current pass is expanded
410#[derive(Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
411enum RewriterStatus {
412    #[default]
413    Unexpanded,
414    Expanded,
415}
416
417#[derive(Debug, Default)]
418struct PlanRewriter {
419    /// Whether the whole plan encodes, allowing per-node checks to be skipped.
420    whole_plan_encodable: bool,
421    /// Current level in the tree
422    level: usize,
423    /// Simulated stack for the `rewrite` recursion
424    stack: Vec<(LogicalPlan, usize)>,
425    /// Stages to be expanded, will be added as parent node of merge scan one by one
426    stage: Vec<LogicalPlan>,
427    status: RewriterStatus,
428    /// Partition columns of the table in current pass
429    partition_cols: Option<AliasMapping>,
430    /// use stack count as scope to determine column requirements is needed or not
431    /// i.e for a logical plan like:
432    /// ```ignore
433    /// 1: Projection: t.number
434    /// 2: Sort: t.pk1+t.pk2
435    /// 3. Projection: t.number, t.pk1, t.pk2
436    /// ```
437    /// `Sort` will make a column requirement for `t.pk1+t.pk2` at level 2.
438    /// Which making `Projection` at level 1 need to add a ref to `t.pk1` as well.
439    /// So that the expanded plan will be
440    /// ```ignore
441    /// Projection: t.number
442    ///   MergeSort: t.pk1+t.pk2
443    ///     MergeScan: remote_input=
444    /// Projection: t.number, "t.pk1+t.pk2" <--- the original `Projection` at level 1 get added with `t.pk1+t.pk2`
445    ///  Sort: t.pk1+t.pk2
446    ///    Projection: t.number, t.pk1, t.pk2
447    /// ```
448    /// Making `MergeSort` can have `t.pk1+t.pk2` as input.
449    /// Meanwhile `Projection` at level 3 doesn't need to add any new column because 3 > 2
450    /// and col requirements at level 2 is not applicable for level 3.
451    ///
452    /// see more details in test `expand_proj_step_aggr` and `expand_proj_sort_proj`
453    ///
454    /// TODO(discord9): a simpler solution to track column requirements for merge scan
455    column_requirements: Vec<(HashSet<Column>, usize)>,
456    /// Whether to expand on next call
457    /// This is used to handle the case where a plan is transformed, but need to be expanded from it's
458    /// parent node. For example a Aggregate plan is split into two parts in frontend and datanode, and need
459    /// to be expanded from the parent node of the Aggregate plan.
460    expand_on_next_call: bool,
461    /// Expanding on next partial/conditional/transformed commutative plan
462    /// This is used to handle the case where a plan is transformed, but still
463    /// need to push down as many node as possible before next partial/conditional/transformed commutative
464    /// plan. I.e.
465    /// ```ignore
466    /// Limit:
467    ///     Sort:
468    /// ```
469    /// where `Limit` is partial commutative, and `Sort` is conditional commutative.
470    /// In this case, we need to expand the `Limit` plan,
471    /// so that we can push down the `Sort` plan as much as possible.
472    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    /// `plan` must be the root of the tree that is about to be rewritten, otherwise
532    /// [`PlanRewriter::should_expand`] may skip a check it has to perform.
533    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        // level starts from 1, it's safe to minus by 1
545        self.stack
546            .iter()
547            .rev()
548            .find(|(_, level)| *level == self.level - 1)
549            .map(|(node, _)| node)
550    }
551
552    /// Return true if should stop and expand. The input plan is the parent node of current node
553    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        // Substrait encoding recurses from the root to the leaves, so a root that encodes
564        // proves that every node below it encodes as well. `plan` here always comes from
565        // `self.stack`, which holds untouched sub-trees of that root, so one check on the
566        // root covers the whole descent. Each check builds a fresh `SessionState`, which
567        // is the dominant cost on deep PromQL plans.
568        // When the root does not encode, the plan holds at least one node that has to stay
569        // on the frontend and only the per-node check locates it.
570        //
571        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                    // a small difference is that for partial commutative, we still need to
591                    // push down it(so `Limit` can be pushed down)
592
593                    // notice how limit needed to be expanded as well to make sure query is correct
594                    // i.e. `Limit fetch=10` need to be pushed down to the leaf node
595                    self.expand_on_next_part_cond_trans_commutative = false;
596                    self.expand_on_next_call = true;
597                }
598                Commutativity::ConditionalCommutative(_)
599                | Commutativity::TransformedCommutative { .. } => {
600                    // again a new node that can be push down, we should just
601                    // do push down now and avoid further expansion
602                    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                // PATCH: we should reconsider SORT's commutativity instead of doing this trick.
615                // explain: for a fully commutative SeriesDivide, its child Sort plan only serves it. I.e., that
616                //   Sort plan is also fully commutative, instead of conditional commutative. So we can remove
617                //   the generated MergeSort from stage safely.
618                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                    // revert last `ConditionalCommutative` result for Sort plan in this case.
624                    // also need to remove any column requirements made by the Sort Plan
625                    // as it may refer to columns later no longer exist(rightfully) like by aggregate or projection
626                    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                    // notice this plan is parent of current node, so `self.level - 1` when updating column requirements
634                    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                    // notice this plan is parent of current node, so `self.level - 1` when updating column requirements
644                    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                        // update the column requirements from the last stage
670                        // notice current plan's parent plan is where we need to apply the column requirements
671                        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    /// Update the column requirements for the current plan, plan_level is the level of the plan
691    /// in the stack, which is used to determine if the column requirements are applicable
692    /// for other plans in the stack.
693    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            // this method won't fail
701            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            // update partition alias
726            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                    // there are other physical partition columns that are not in logical table and part cols are empty
777                    // so we need to add a placeholder for it to prevent certain optimization
778                    // this is used to make sure the final partition columns(that optimizer see) are not empty
779                    // notice if originally partition_cols is not empty, then there is no need to add this place holder,
780                    // as subset of phy part cols can still be used for certain optimization, and it works as if
781                    // those columns are always null
782                    // This helps with distinguishing between non-partitioned table and partitioned table with all phy part cols not in logical table
783                    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                                        // for placeholder, just return a empty alias
791                                        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                                            // the `projection` field of `TableScan` doesn't contain the partition columns,
798                                            // this is similar to not having a alias, hence return empty alias set
799                                            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    /// pop one stack item and reduce the level by 1
817    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        // store schema before expand, new child plan might have a different schema, so not using it
824        let schema = on_node.schema().clone();
825        if let Some(new_child_plan) = self.new_child_plan.take() {
826            // if there is a new child plan, use it as the new root
827            on_node = new_child_plan;
828        }
829        // Requirements are carried into the region with the plan that will satisfy them; they are
830        // never dropped. When nothing requires a column of this subtree the enforced rewrite is a
831        // no-op, so the shape of the subtree - how many inputs a node has included - only matters
832        // once a requirement actually has to travel through it.
833        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        // add merge scan as the new root
853        let mut node = MergeScanLogicalPlan::new(on_node.clone(), false).into_logical_plan();
854
855        // expand stages
856        for new_stage in self.stage.drain(..) {
857            // tracking alias for merge sort's sort exprs
858            let new_stage = if let LogicalPlan::Extension(ext) = &new_stage
859                && let Some(merge_sort) = ext.node.as_any().downcast_ref::<MergeSortLogicalPlan>()
860            {
861                // TODO(discord9): change `on_node` to `node` once alias tracking is supported for merge scan
862                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        // Extra columns introduced for distributed operations may need to be removed. A complete
872        // frame that already has the required schema must not go through column projection: its
873        // declaration is schema metadata. Ordinary SQL keeps its existing identity projection.
874        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        // recover the schema, this make sure after expand the schema is the same as old node
890        // because after expand the raw top node might have extra columns i.e. sorting columns for `Sort` node
891        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/// Implementation of the [`TreeNodeRewriter`] trait which is responsible for rewriting
902/// logical plans to enforce various requirement for distributed query.
903///
904/// Requirements enforced by this rewriter:
905/// - Enforce column requirements for `LogicalPlan::Projection` nodes. Makes sure the
906///   required columns are available in the sub plan.
907///
908/// The rewrite is requirement-driven. A requirement names columns of the plan that made it, so
909/// enforcing it means following the lineage from that plan down to the node that has to publish the
910/// column. Nothing else is rewritten: a subtree no requirement reaches is left exactly as it is,
911/// however many inputs its nodes have. Lineage is recorded per visited node rather than per depth,
912/// because two nodes at one depth are two branches and one branch must never stand in for another's
913/// origin. A requirement that would have to travel through a branch point has an ambiguous lineage,
914/// and this rewriter refuses then instead of picking a branch.
915#[derive(Debug)]
916struct EnforceDistRequirementRewriter {
917    /// only enforce column requirements after the expanding node in question,
918    /// meaning only for node with `cur_level` <= `level` will consider adding those column requirements
919    /// TODO(discord9): a simpler solution to track column requirements for merge scan
920    column_requirements: Vec<(HashSet<Column>, usize)>,
921    /// only apply column requirements >= `cur_level`
922    /// this is used to avoid applying column requirements that are not needed
923    /// for the current node, i.e. the node is not in the scope of the column requirements
924    /// i.e, for this plan:
925    /// ```ignore
926    /// Aggregate: min(t.number)
927    ///   Projection: t.number
928    /// ```
929    /// when on `Projection` node, we don't need to apply the column requirements of `Aggregate` node
930    /// because the `Projection` node is not in the scope of the `Aggregate` node
931    cur_level: usize,
932    /// Every node visited so far, in visit order, so a requirement can find the plan that made it
933    /// and the plans below it without one depth standing in for another branch.
934    visited: Vec<VisitedNode>,
935    /// Indices into [`Self::visited`] of the nodes from the rewritten node down to the node being
936    /// visited, top down.
937    path: Vec<usize>,
938}
939
940/// One node [`EnforceDistRequirementRewriter`] has visited.
941#[derive(Debug)]
942struct VisitedNode {
943    /// Depth of the node, in the same coordinates as the levels of `column_requirements`.
944    depth: usize,
945    /// The node one level up on the path this node was visited on, `None` for the rewritten root.
946    parent: Option<usize>,
947    /// The node as it now stands, including whatever enforcement already happened below it.
948    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    /// Whether a requirement reaches this rewrite at all.
966    ///
967    /// A requirement made above the rewritten node is not in this rewrite's scope, and a node
968    /// nothing requires a column of is left as it is, whatever its shape.
969    fn has_applicable_requirements(&self) -> bool {
970        self.column_requirements
971            .iter()
972            .any(|(_, level)| *level >= self.cur_level)
973    }
974
975    /// The plan that made the requirement registered at `level`, when it is reachable from `node`.
976    ///
977    /// Reachable means on the path from the rewritten node down to `node`, `node` included, or
978    /// inside `node`'s own subtree. A plan on a sibling branch is not reachable, and a requirement
979    /// it made says nothing about `node`. Two reachable plans at `level` below `node` are two
980    /// branches the column could come from, which is exactly the ambiguity this refuses to resolve.
981    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    /// Whether the node at `node` was visited inside the subtree of the node at `ancestor`.
1007    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    /// Return a mapping from (original column, level) to aliased columns in current node of all
1019    /// applicable column requirements
1020    /// i.e. only column requirements with level >= `cur_level` will be considered
1021    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        // track alias for columns and use aliased columns instead
1033        // aliased col reqs at current level
1034        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                // query for alias in current plan
1041                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                        // if no aliased column found in current node, there should be alias in child node as promised by enforce col reqs
1051                        // because it should insert required columns in child node
1052                        // so we can find the alias in child node
1053                        // if not found, it's an internal error
1054                        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    /// Add the columns `node` requires to the projection `node`, if it has to publish any.
1080    ///
1081    /// Only a projection is repaired here: it is the one node whose output can grow without
1082    /// changing what it computes, which is what lets the node above it keep a column it asked for.
1083    fn enforce_column_requirements(
1084        &mut self,
1085        node_id: usize,
1086        node: LogicalPlan,
1087    ) -> DfResult<Transformed<LogicalPlan>> {
1088        // make sure all projection applicable scope has the required columns
1089        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                    // remove all columns that are already in the projection exprs
1105                    !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                // use the first alias in alias set as the column to add
1115                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            // update plan for later use
1131            self.visited[node_id].plan = new_node.clone();
1132
1133            // still need to continue for next projection if applicable
1134            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        // The children may have been rewritten below this node.
1163        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    /// descend
1175    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        // decendening will clear the stage
1179        self.stage.clear();
1180        self.set_unexpanded();
1181        self.partition_cols = None;
1182        Ok(Transformed::no(node))
1183    }
1184
1185    /// ascend
1186    ///
1187    /// Besure to call `pop_stack` before returning
1188    fn f_up(&mut self, node: Self::Node) -> DfResult<Transformed<Self::Node>> {
1189        // only expand once on each ascending
1190        if self.is_expanded() {
1191            self.pop_stack();
1192            return Ok(Transformed::no(node));
1193        }
1194
1195        // only expand when the leaf is table scan
1196        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            // TODO(ruihang): does this work for nodes with multiple children?;
1223            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}