Skip to content

Apache DataFusion SQL Query Engine

7.9 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements

//! Walk and rewrite logical plans, including subqueries embedded in expressions.
//! Run with `cargo run --example query_planning -- plan_walk`.

use std::collections::BTreeSet;
use std::sync::Arc;

use arrow::datatypes::{DataType, Field, Schema};
use datafusion::common::Result;
use datafusion::common::tree_node::{
    Transformed, TreeNode, TreeNodeRecursion, TreeNodeRewriter,
};
use datafusion::logical_expr::logical_plan::builder::table_scan_with_filters;
use datafusion::logical_expr::{Expr, LogicalPlan, col, in_subquery, lit, table_scan};

pub fn plan_walk() -> Result<()> {
    let schema = Schema::new(vec![
        Field::new("name", DataType::Utf8, false),
        Field::new("salary", DataType::Int32, false),
    ]);

    // table_scan returns a LogicalPlanBuilder. Build a tree of operators:
    // Projection(name, salary)
    //   Filter(salary > 1000)
    //     TableScan(employee)
    // Only a schema is needed to inspect these plans; no data is read.
    let plan = table_scan(Some("employee"), &schema, None)?
        .filter(col("salary").gt(lit(1000)))?
        .project(vec![col("name"), col("salary")])?
        .build()?;
    println!("Original plan:\n{}", plan.display_indent());

    // apply borrows the plan and visits each node before visiting its inputs.
    // Continue visits the inputs, Jump skips them, and Stop ends the walk.
    let mut tables = BTreeSet::new();
    plan.apply(|node| {
        if let LogicalPlan::TableScan(scan) = node {
            tables.insert(scan.table_name.to_string());
        }
        Ok(TreeNodeRecursion::Continue)
    })?;
    assert_eq!(tables, BTreeSet::from(["employee".to_string()]));
    println!("Referenced tables: {tables:?}");

    // rewrite consumes the plan. Clone it here to keep the original for comparison.
    // This illustrative rewrite changes query semantics by removing filters;
    // it is not an optimizer rule that preserves query results.
    let mut rewriter = RemoveFilters::default();
    let rewritten = plan.clone().rewrite(&mut rewriter)?;
    assert!(rewritten.transformed);
    assert_eq!(rewriter.removed, 1);
    assert_eq!(rewritten.data.schema(), plan.schema());
    assert_eq!(
        rewritten.data.display_indent().to_string(),
        "Projection: employee.name, employee.salary\n  TableScan: employee"
    );
    println!("Without Filter nodes:\n{}", rewritten.data.display_indent());

    // Consecutive Filters are removed bottom-up: f_up sees the outer Filter
    // after its inner Filter has already been replaced with the TableScan.
    let plan = table_scan(Some("employee"), &schema, None)?
        .filter(col("salary").gt(lit(1000)))?
        .filter(col("salary").lt(lit(2000)))?
        .build()?;
    assert_eq!(
        plan.display_indent().to_string(),
        "Filter: employee.salary < Int32(2000)\n  Filter: employee.salary > Int32(1000)\n    TableScan: employee"
    );
    let mut rewriter = RemoveFilters::default();
    let rewritten = plan.rewrite(&mut rewriter)?;
    assert!(rewritten.transformed);
    assert_eq!(rewriter.removed, 2);
    assert_eq!(
        rewritten.data.display_indent().to_string(),
        "TableScan: employee"
    );

    // A subquery in an expression is not an ordinary plan input, so apply
    // and rewrite do not traverse it. Use their *_with_subqueries variants.
    // Include a scan filter to illustrate predicates that have been pushed down
    // into a table source. Here it is set explicitly rather than by an optimizer.
    let scan_predicate = col("eligible.salary").gt(lit(1000));
    let subquery_predicate = col("eligible.salary").lt(lit(2000));
    let subquery = table_scan_with_filters(
        Some("eligible"),
        &schema,
        None,
        vec![scan_predicate.clone()],
    )?
    .filter(subquery_predicate.clone())?
    .project(vec![col("salary")])?
    .build()?;
    let plan = table_scan(Some("employee"), &schema, None)?
        .filter(col("salary").gt(lit(0)))?
        .project(vec![
            col("name"),
            in_subquery(col("salary"), Arc::new(subquery)).alias("is_eligible"),
        ])?
        .build()?;

    tables.clear();
    plan.apply(|node| {
        if let LogicalPlan::TableScan(scan) = node {
            tables.insert(scan.table_name.to_string());
        }
        Ok(TreeNodeRecursion::Continue)
    })?;
    assert_eq!(tables, BTreeSet::from(["employee".to_string()]));

    let summary = summarize(&plan)?;
    assert_eq!(
        summary.tables,
        BTreeSet::from(["eligible".to_string(), "employee".to_string()])
    );
    // The outer Filter, the subquery's Filter, and the scan's pushed-down filter.
    assert_eq!(summary.filters.len(), 3);
    assert!(summary.filters.contains(&scan_predicate));
    println!("Tables including subqueries: {:?}", summary.tables);
    for predicate in &summary.filters {
        println!("Filter predicate: {predicate}");
    }

    // Ordinary rewrite removes only the outer Filter. The subquery's Filter
    // and pushed-down scan predicate remain because it does not visit subqueries.
    let mut rewriter = RemoveFilters::default();
    let rewritten = plan.clone().rewrite(&mut rewriter)?;
    assert!(rewritten.transformed);
    assert_eq!(rewriter.removed, 1);
    let summary = summarize(&rewritten.data)?;
    assert_eq!(summary.filters.len(), 2);
    assert!(summary.filters.contains(&subquery_predicate));
    assert!(summary.filters.contains(&scan_predicate));

    let mut rewriter = RemoveFilters::default();
    let rewritten = plan.rewrite_with_subqueries(&mut rewriter)?;
    assert!(rewritten.transformed);
    assert_eq!(rewriter.removed, 2);
    // Both Filter nodes were removed, but the subquery in the Projection and
    // its pushed-down scan filter remain. Rewriting Filter nodes does not
    // modify TableScan.filters.
    let summary = summarize(&rewritten.data)?;
    assert_eq!(
        summary.tables,
        BTreeSet::from(["eligible".to_string(), "employee".to_string()])
    );
    assert_eq!(summary.filters, vec![scan_predicate]);

    Ok(())
}

#[derive(Debug, Default)]
struct PlanSummary {
    tables: BTreeSet<String>,
    filters: Vec<Expr>,
}

fn summarize(plan: &LogicalPlan) -> Result<PlanSummary> {
    let mut summary = PlanSummary::default();
    plan.apply_with_subqueries(|node| {
        match node {
            LogicalPlan::TableScan(scan) => {
                summary.tables.insert(scan.table_name.to_string());
                summary.filters.extend(scan.filters.iter().cloned());
            }
            LogicalPlan::Filter(filter) => {
                summary.filters.push(filter.predicate.clone());
            }
            _ => {}
        }
        Ok(TreeNodeRecursion::Continue)
    })?;
    // Filter pushdown support determines whether predicates appear in Filter
    // nodes, TableScan.filters, or both. This list may therefore have duplicates.
    // Other predicates, such as join conditions, are not collected here.
    Ok(summary)
}

// A rewriter can keep state across nodes, such as the number of removed filters.
#[derive(Default)]
struct RemoveFilters {
    removed: usize,
}

impl TreeNodeRewriter for RemoveFilters {
    type Node = LogicalPlan;

    // f_up runs after the inputs (and, with rewrite_with_subqueries, embedded
    // subqueries) have been rewritten. Returning the rewritten input also works
    // when several Filter nodes are nested.
    // For a stateless bottom-up rewrite, transform_up accepts a closure instead.
    fn f_up(&mut self, node: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
        match node {
            LogicalPlan::Filter(filter) => {
                self.removed += 1;
                Ok(Transformed::yes(filter.input.as_ref().clone()))
            }
            _ => Ok(Transformed::no(node)),
        }
    }
}