You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2022/10/10 23:00:05 UTC
[GitHub] [arrow-datafusion] andygrove opened a new pull request, #3788: MINOR: Optimizer example and docs
andygrove opened a new pull request, #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
N/A
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
I want to make it easier for new contributors to be able to write and review optimization rules.
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
- Example
- Docs
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
No
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] ursabot commented on pull request #3788: MINOR: Optimizer example and docs, deprecate `Expr::name`
Posted by GitBox <gi...@apache.org>.
ursabot commented on PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788#issuecomment-1276682153
Benchmark runs are scheduled for baseline = a226587de5a17f93c175727bca37844ef0bd934a and contender = 4cb8ac094ee88dc0023b4cde1b39840a0a362ee0. 4cb8ac094ee88dc0023b4cde1b39840a0a362ee0 is a master commit associated with this PR. Results will be available as each benchmark for each run completes.
Conbench compare runs links:
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ec2-t3-xlarge-us-east-2] [ec2-t3-xlarge-us-east-2](https://conbench.ursa.dev/compare/runs/2236f2f25c434caba799d992521c4f5c...ac7d331c259944b7bf9726806ff5691b/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on test-mac-arm] [test-mac-arm](https://conbench.ursa.dev/compare/runs/2bc00d47ed304f738f9b9cf772c5a323...dac8ec8fc9144f578a1dda2c0e262017/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-i9-9960x] [ursa-i9-9960x](https://conbench.ursa.dev/compare/runs/22fa2fbf86904af4a3b05efb7f742d13...ba1c95baf8574d84806fd2581ea54183/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-thinkcentre-m75q] [ursa-thinkcentre-m75q](https://conbench.ursa.dev/compare/runs/6edc7d0dd95443dd8426e6f4cad4efd3...e90001ff18ff49e7b75e5e6cab289b03/)
Buildkite builds:
Supported benchmarks:
ec2-t3-xlarge-us-east-2: Supported benchmark langs: Python, R. Runs only benchmarks with cloud = True
test-mac-arm: Supported benchmark langs: C++, Python, R
ursa-i9-9960x: Supported benchmark langs: Python, R, JavaScript
ursa-thinkcentre-m75q: Supported benchmark langs: C++, Java
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #3788: MINOR: Optimizer example and docs, deprecate `Expr::name`
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788#discussion_r993566835
##########
datafusion/optimizer/README.md:
##########
@@ -17,10 +17,317 @@
under the License.
-->
-# DataFusion Query Optimizer Rules
+# DataFusion Query Optimizer
-[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory format.
+[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory
+format.
-This crate is a submodule of DataFusion that provides query optimizer rules.
+DataFusion has modular design, allowing individual crates to be re-used in other projects.
+
+This crate is a submodule of DataFusion that provides a query optimizer for logical plans.
Review Comment:
```suggestion
This crate is a submodule of DataFusion that provides a query optimizer for logical plans, and
contains an extensive set of OptimizerRules that may rewrite the plan and/or its expressions so
they execute more quickly while still computing the same result.
```
##########
datafusion/optimizer/README.md:
##########
@@ -17,10 +17,317 @@
under the License.
-->
-# DataFusion Query Optimizer Rules
+# DataFusion Query Optimizer
-[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory format.
+[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory
+format.
-This crate is a submodule of DataFusion that provides query optimizer rules.
+DataFusion has modular design, allowing individual crates to be re-used in other projects.
+
+This crate is a submodule of DataFusion that provides a query optimizer for logical plans.
+
+## Running the Optimizer
+
+The following code demonstrates the basic flow of creating the optimizer with a default set of optimization rules
+and applying it to a logical plan to produce an optimized logical plan.
+
+```rust
+
+// We need a logical plan as the starting point. There are many ways to build a logical plan:
+//
+// The `datafusion-expr` crate provides a LogicalPlanBuilder
+// The `datafusion-sql` crate provides a SQL query planner that can create a LogicalPlan from SQL
+// The `datafusion` crate provides a DataFrame API that can create a LogicalPlan
+let logical_plan = ...
+
+let mut config = OptimizerConfig::default();
+let optimizer = Optimizer::new(&config);
+let optimized_plan = optimizer.optimize(&logical_plan, &mut config, observe)?;
+
+fn observe(plan: &LogicalPlan, rule: &dyn OptimizerRule) {
+ println!(
+ "After applying rule '{}':\n{}",
+ rule.name(),
+ plan.display_indent()
+ )
+}
+```
+
+## Providing Custom Rules
+
+The optimizer can be created with a custom set of rules.
+
+```rust
+let optimizer = Optimizer::with_rules(vec![
+ Arc::new(MyRule {})
+]);
+```
+
+## Writing Optimization Rules
+
+Please refer to the [examples](examples) to learn more about the general approach to writing optimizer rules and
+then move onto studying the existing rules.
+
+All rules must implement the `OptimizerRule` trait.
+
+```rust
+/// `OptimizerRule` transforms one ['LogicalPlan'] into another which
+/// computes the same results, but in a potentially more efficient
+/// way. If there are no suitable transformations for the input plan,
+/// the optimizer can simply return it as is.
+pub trait OptimizerRule {
+ /// Rewrite `plan` to an optimized form
+ fn optimize(
+ &self,
+ plan: &LogicalPlan,
+ optimizer_config: &mut OptimizerConfig,
+ ) -> Result<LogicalPlan>;
+
+ /// A human readable name for this optimizer rule
+ fn name(&self) -> &str;
+}
+```
+
+### General Guidelines
+
+Rules typical walk the logical plan and walk the expression trees inside operators and selectively mutate
+individual operators or expressions.
+
+Sometimes there is an initial pass that visits the plan and builds state that is used in a second pass that performs
+the actual optimization. This approach is used in projection push down and filter push down.
+
+### Expression Naming
+
+Every expression in DataFusion has a name, which is used as the column name. For example, in this example the output
+contains a single column with the name `"COUNT(aggregate_test_100.c9)"`:
+
+```text
+❯ select count(c9) from aggregate_test_100;
++------------------------------+
+| COUNT(aggregate_test_100.c9) |
++------------------------------+
+| 100 |
++------------------------------+
+```
+
+These names are used to refer to the columns in both subqueries as well as internally from one stage of the LogicalPlan
+to another. For example:
+
+```text
+❯ select "COUNT(aggregate_test_100.c9)" + 1 from (select count(c9) from aggregate_test_100) as sq;
++--------------------------------------------+
+| sq.COUNT(aggregate_test_100.c9) + Int64(1) |
++--------------------------------------------+
+| 101 |
++--------------------------------------------+
+```
+
+### Implication
+
+DataFusion contains an extensive set of OptimizerRules that may rewrite the plan and/or its expressions so they execute
+more quickly.
+
+Because DataFusion identifies columns using a string name, it means it is critical that the names of expressions are
+not changed by the optimizer when it rewrites expressions. This is typically accomplished by renaming a rewritten
+expression by adding an alias.
+
+Here is a simple example of such a rewrite. The expression `1 + 2` can be internally simplified to 3 but must still be
+displayed the same as `1 + 2`:
+
+```text
+❯ select 1 + 2;
++---------------------+
+| Int64(1) + Int64(2) |
++---------------------+
+| 3 |
++---------------------+
+```
+
+Looking at the `EXPLAIN` output we can see that the optimizer has effectively rewritten `1 + 2` into effectively
+`3 as "1 + 2"`:
+
+```text
+❯ explain select 1 + 2;
++---------------+-------------------------------------------------+
+| plan_type | plan |
++---------------+-------------------------------------------------+
+| logical_plan | Projection: Int64(3) AS Int64(1) + Int64(2) |
+| | EmptyRelation |
+| physical_plan | ProjectionExec: expr=[3 as Int64(1) + Int64(2)] |
+| | EmptyExec: produce_one_row=true |
+| | |
++---------------+-------------------------------------------------+
+```
+
+If the expression name is not preserved, bugs such as [#3704](https://github.com/apache/arrow-datafusion/issues/3704)
+and [#3555](https://github.com/apache/arrow-datafusion/issues/3555) occur where the expected columns can not be found.
+
+### Building Expression Names
+
+There are currently two ways to create a name for an expression in the logical plan.
+
+```rust
+impl Expr {
+ /// Returns the name of this expression as it should appear in a schema. This name
+ /// will not include any CAST expressions.
+ pub fn display_name(&self) -> Result<String> {
+ create_name(self)
+ }
+
+ /// Returns a full and complete string representation of this expression.
+ pub fn canonical_name(&self) -> String {
+ format!("{}", self)
+ }
+}
+```
+
+When comparing expressions to determine if they are equivalent, `canonical_name` should be used, and when creating a
+name to be used in a schema, `display_name` should be used.
+
+### Utilities
+
+There are a number of utility methods provided that take care of some common tasks.
+
+### ExprVisitor
+
+The `ExprVisitor` and `ExprVisitable` traits provide a mechanism for applying a visitor pattern to an expression tree.
+
+Here is an example that demonstrates this.
+
+```rust
+fn extract_subquery_filters(expression: &Expr, extracted: &mut Vec<Expr>) -> Result<()> {
+ struct InSubqueryVisitor<'a> {
+ accum: &'a mut Vec<Expr>,
+ }
+
+ impl ExpressionVisitor for InSubqueryVisitor<'_> {
+ fn pre_visit(self, expr: &Expr) -> Result<Recursion<Self>> {
+ if let Expr::InSubquery { .. } = expr {
+ self.accum.push(expr.to_owned());
+ }
+ Ok(Recursion::Continue(self))
+ }
+ }
+
+ expression.accept(InSubqueryVisitor { accum: extracted })?;
+ Ok(())
+}
+```
+
+### Rewriting Expressions
+
+The `MyExprRewriter` trait can be implemented to provide a way to rewrite expressions. This rule can then be applied
+to an expression by calling `Expr::rewrite` (from the `ExprRewritable` trait).
+
+The `rewrite` method will perform a depth first walk of the expression and its children to rewrite an expression,
+consuming `self` producing a new expression.
+
+```rust
+let mut expr_rewriter = MyExprRewriter {};
+let expr = expr.rewrite(&mut expr_rewriter)?;
+```
+
+Here is an example implementation which will rewrite `expr BETWEEN a AND b` as `expr >= a AND expr <= b`. Note that the
+implementation does not need to perform any recursion since this is handled by the `rewrite` method.
+
+```rust
+struct MyExprRewriter {}
+
+impl ExprRewriter for MyExprRewriter {
+ fn mutate(&mut self, expr: Expr) -> Result<Expr> {
+ match expr {
+ Expr::Between {
+ negated,
+ expr,
+ low,
+ high,
+ } => {
+ let expr: Expr = expr.as_ref().clone();
+ let low: Expr = low.as_ref().clone();
+ let high: Expr = high.as_ref().clone();
+ if negated {
+ Ok(expr.clone().lt(low).or(expr.clone().gt(high)))
+ } else {
+ Ok(expr.clone().gt_eq(low).and(expr.clone().lt_eq(high)))
+ }
+ }
+ _ => Ok(expr.clone()),
+ }
+ }
+}
+```
+
+### optimize_children
+
+It is quite typical for a rule to be applied recursively to all operators within a query plan. Rather than duplicate
+that logic in each rule, an `optimize_children` method is provided. This recursively invokes the `optimize` method on
+the plan's children and then returns a node of the same type.
Review Comment:
```suggestion
Typically a rule is applied recursively to all operators within a query plan. Rather than duplicate
that logic in each rule, an `optimize_children` method is provided. This recursively invokes the `optimize` method on
the plan's children and then returns a node of the same type.
```
##########
datafusion/optimizer/README.md:
##########
@@ -17,10 +17,317 @@
under the License.
-->
-# DataFusion Query Optimizer Rules
+# DataFusion Query Optimizer
-[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory format.
+[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory
+format.
-This crate is a submodule of DataFusion that provides query optimizer rules.
+DataFusion has modular design, allowing individual crates to be re-used in other projects.
+
+This crate is a submodule of DataFusion that provides a query optimizer for logical plans.
+
+## Running the Optimizer
+
+The following code demonstrates the basic flow of creating the optimizer with a default set of optimization rules
+and applying it to a logical plan to produce an optimized logical plan.
+
+```rust
+
+// We need a logical plan as the starting point. There are many ways to build a logical plan:
+//
+// The `datafusion-expr` crate provides a LogicalPlanBuilder
+// The `datafusion-sql` crate provides a SQL query planner that can create a LogicalPlan from SQL
+// The `datafusion` crate provides a DataFrame API that can create a LogicalPlan
+let logical_plan = ...
+
+let mut config = OptimizerConfig::default();
+let optimizer = Optimizer::new(&config);
+let optimized_plan = optimizer.optimize(&logical_plan, &mut config, observe)?;
+
+fn observe(plan: &LogicalPlan, rule: &dyn OptimizerRule) {
+ println!(
+ "After applying rule '{}':\n{}",
+ rule.name(),
+ plan.display_indent()
+ )
+}
+```
+
+## Providing Custom Rules
+
+The optimizer can be created with a custom set of rules.
+
+```rust
+let optimizer = Optimizer::with_rules(vec![
+ Arc::new(MyRule {})
+]);
+```
+
+## Writing Optimization Rules
+
+Please refer to the [examples](examples) to learn more about the general approach to writing optimizer rules and
+then move onto studying the existing rules.
+
+All rules must implement the `OptimizerRule` trait.
+
+```rust
+/// `OptimizerRule` transforms one ['LogicalPlan'] into another which
+/// computes the same results, but in a potentially more efficient
+/// way. If there are no suitable transformations for the input plan,
+/// the optimizer can simply return it as is.
+pub trait OptimizerRule {
+ /// Rewrite `plan` to an optimized form
+ fn optimize(
+ &self,
+ plan: &LogicalPlan,
+ optimizer_config: &mut OptimizerConfig,
+ ) -> Result<LogicalPlan>;
+
+ /// A human readable name for this optimizer rule
+ fn name(&self) -> &str;
+}
+```
+
+### General Guidelines
+
+Rules typical walk the logical plan and walk the expression trees inside operators and selectively mutate
+individual operators or expressions.
+
+Sometimes there is an initial pass that visits the plan and builds state that is used in a second pass that performs
+the actual optimization. This approach is used in projection push down and filter push down.
+
+### Expression Naming
+
+Every expression in DataFusion has a name, which is used as the column name. For example, in this example the output
+contains a single column with the name `"COUNT(aggregate_test_100.c9)"`:
+
+```text
+❯ select count(c9) from aggregate_test_100;
++------------------------------+
+| COUNT(aggregate_test_100.c9) |
++------------------------------+
+| 100 |
++------------------------------+
+```
+
+These names are used to refer to the columns in both subqueries as well as internally from one stage of the LogicalPlan
+to another. For example:
+
+```text
+❯ select "COUNT(aggregate_test_100.c9)" + 1 from (select count(c9) from aggregate_test_100) as sq;
++--------------------------------------------+
+| sq.COUNT(aggregate_test_100.c9) + Int64(1) |
++--------------------------------------------+
+| 101 |
++--------------------------------------------+
+```
+
+### Implication
+
+DataFusion contains an extensive set of OptimizerRules that may rewrite the plan and/or its expressions so they execute
+more quickly.
Review Comment:
```suggestion
```
Suggest moving this up
##########
datafusion/optimizer/examples/rewrite_expr.rs:
##########
@@ -0,0 +1,163 @@
+// Licensed to the Apache Software Foundation (ASF) under one
Review Comment:
I personally recommend putting this example into `datafusion/examples` rather than `datafusion/optimizer/examples` so that it is easier to find
##########
datafusion/optimizer/README.md:
##########
@@ -17,10 +17,317 @@
under the License.
-->
-# DataFusion Query Optimizer Rules
+# DataFusion Query Optimizer
-[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory format.
+[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory
+format.
-This crate is a submodule of DataFusion that provides query optimizer rules.
+DataFusion has modular design, allowing individual crates to be re-used in other projects.
+
+This crate is a submodule of DataFusion that provides a query optimizer for logical plans.
+
+## Running the Optimizer
+
+The following code demonstrates the basic flow of creating the optimizer with a default set of optimization rules
+and applying it to a logical plan to produce an optimized logical plan.
+
+```rust
+
+// We need a logical plan as the starting point. There are many ways to build a logical plan:
+//
+// The `datafusion-expr` crate provides a LogicalPlanBuilder
+// The `datafusion-sql` crate provides a SQL query planner that can create a LogicalPlan from SQL
+// The `datafusion` crate provides a DataFrame API that can create a LogicalPlan
+let logical_plan = ...
+
+let mut config = OptimizerConfig::default();
+let optimizer = Optimizer::new(&config);
+let optimized_plan = optimizer.optimize(&logical_plan, &mut config, observe)?;
+
+fn observe(plan: &LogicalPlan, rule: &dyn OptimizerRule) {
+ println!(
+ "After applying rule '{}':\n{}",
+ rule.name(),
+ plan.display_indent()
+ )
+}
+```
+
+## Providing Custom Rules
+
+The optimizer can be created with a custom set of rules.
+
+```rust
+let optimizer = Optimizer::with_rules(vec![
+ Arc::new(MyRule {})
+]);
+```
+
+## Writing Optimization Rules
+
+Please refer to the [examples](examples) to learn more about the general approach to writing optimizer rules and
+then move onto studying the existing rules.
+
+All rules must implement the `OptimizerRule` trait.
+
+```rust
+/// `OptimizerRule` transforms one ['LogicalPlan'] into another which
+/// computes the same results, but in a potentially more efficient
+/// way. If there are no suitable transformations for the input plan,
+/// the optimizer can simply return it as is.
+pub trait OptimizerRule {
+ /// Rewrite `plan` to an optimized form
+ fn optimize(
+ &self,
+ plan: &LogicalPlan,
+ optimizer_config: &mut OptimizerConfig,
+ ) -> Result<LogicalPlan>;
+
+ /// A human readable name for this optimizer rule
+ fn name(&self) -> &str;
+}
+```
+
+### General Guidelines
+
+Rules typical walk the logical plan and walk the expression trees inside operators and selectively mutate
+individual operators or expressions.
+
+Sometimes there is an initial pass that visits the plan and builds state that is used in a second pass that performs
+the actual optimization. This approach is used in projection push down and filter push down.
+
+### Expression Naming
+
+Every expression in DataFusion has a name, which is used as the column name. For example, in this example the output
+contains a single column with the name `"COUNT(aggregate_test_100.c9)"`:
+
+```text
+❯ select count(c9) from aggregate_test_100;
++------------------------------+
+| COUNT(aggregate_test_100.c9) |
++------------------------------+
+| 100 |
++------------------------------+
+```
+
+These names are used to refer to the columns in both subqueries as well as internally from one stage of the LogicalPlan
+to another. For example:
+
+```text
+❯ select "COUNT(aggregate_test_100.c9)" + 1 from (select count(c9) from aggregate_test_100) as sq;
++--------------------------------------------+
+| sq.COUNT(aggregate_test_100.c9) + Int64(1) |
++--------------------------------------------+
+| 101 |
++--------------------------------------------+
+```
+
+### Implication
+
+DataFusion contains an extensive set of OptimizerRules that may rewrite the plan and/or its expressions so they execute
+more quickly.
+
+Because DataFusion identifies columns using a string name, it means it is critical that the names of expressions are
+not changed by the optimizer when it rewrites expressions. This is typically accomplished by renaming a rewritten
+expression by adding an alias.
+
+Here is a simple example of such a rewrite. The expression `1 + 2` can be internally simplified to 3 but must still be
+displayed the same as `1 + 2`:
+
+```text
+❯ select 1 + 2;
++---------------------+
+| Int64(1) + Int64(2) |
++---------------------+
+| 3 |
++---------------------+
+```
+
+Looking at the `EXPLAIN` output we can see that the optimizer has effectively rewritten `1 + 2` into effectively
+`3 as "1 + 2"`:
+
+```text
+❯ explain select 1 + 2;
++---------------+-------------------------------------------------+
+| plan_type | plan |
++---------------+-------------------------------------------------+
+| logical_plan | Projection: Int64(3) AS Int64(1) + Int64(2) |
+| | EmptyRelation |
+| physical_plan | ProjectionExec: expr=[3 as Int64(1) + Int64(2)] |
+| | EmptyExec: produce_one_row=true |
+| | |
++---------------+-------------------------------------------------+
+```
+
+If the expression name is not preserved, bugs such as [#3704](https://github.com/apache/arrow-datafusion/issues/3704)
+and [#3555](https://github.com/apache/arrow-datafusion/issues/3555) occur where the expected columns can not be found.
+
+### Building Expression Names
+
+There are currently two ways to create a name for an expression in the logical plan.
+
+```rust
+impl Expr {
+ /// Returns the name of this expression as it should appear in a schema. This name
+ /// will not include any CAST expressions.
+ pub fn display_name(&self) -> Result<String> {
+ create_name(self)
+ }
+
+ /// Returns a full and complete string representation of this expression.
+ pub fn canonical_name(&self) -> String {
+ format!("{}", self)
+ }
+}
+```
+
+When comparing expressions to determine if they are equivalent, `canonical_name` should be used, and when creating a
+name to be used in a schema, `display_name` should be used.
+
+### Utilities
+
+There are a number of utility methods provided that take care of some common tasks.
+
+### ExprVisitor
+
+The `ExprVisitor` and `ExprVisitable` traits provide a mechanism for applying a visitor pattern to an expression tree.
+
+Here is an example that demonstrates this.
+
+```rust
+fn extract_subquery_filters(expression: &Expr, extracted: &mut Vec<Expr>) -> Result<()> {
+ struct InSubqueryVisitor<'a> {
+ accum: &'a mut Vec<Expr>,
+ }
+
+ impl ExpressionVisitor for InSubqueryVisitor<'_> {
+ fn pre_visit(self, expr: &Expr) -> Result<Recursion<Self>> {
+ if let Expr::InSubquery { .. } = expr {
+ self.accum.push(expr.to_owned());
+ }
+ Ok(Recursion::Continue(self))
+ }
+ }
+
+ expression.accept(InSubqueryVisitor { accum: extracted })?;
+ Ok(())
+}
+```
+
+### Rewriting Expressions
+
+The `MyExprRewriter` trait can be implemented to provide a way to rewrite expressions. This rule can then be applied
+to an expression by calling `Expr::rewrite` (from the `ExprRewritable` trait).
+
+The `rewrite` method will perform a depth first walk of the expression and its children to rewrite an expression,
+consuming `self` producing a new expression.
+
+```rust
+let mut expr_rewriter = MyExprRewriter {};
+let expr = expr.rewrite(&mut expr_rewriter)?;
+```
+
+Here is an example implementation which will rewrite `expr BETWEEN a AND b` as `expr >= a AND expr <= b`. Note that the
+implementation does not need to perform any recursion since this is handled by the `rewrite` method.
+
+```rust
+struct MyExprRewriter {}
+
+impl ExprRewriter for MyExprRewriter {
+ fn mutate(&mut self, expr: Expr) -> Result<Expr> {
+ match expr {
+ Expr::Between {
+ negated,
+ expr,
+ low,
+ high,
+ } => {
+ let expr: Expr = expr.as_ref().clone();
+ let low: Expr = low.as_ref().clone();
+ let high: Expr = high.as_ref().clone();
+ if negated {
+ Ok(expr.clone().lt(low).or(expr.clone().gt(high)))
+ } else {
+ Ok(expr.clone().gt_eq(low).and(expr.clone().lt_eq(high)))
+ }
+ }
+ _ => Ok(expr.clone()),
+ }
+ }
+}
+```
+
+### optimize_children
+
+It is quite typical for a rule to be applied recursively to all operators within a query plan. Rather than duplicate
+that logic in each rule, an `optimize_children` method is provided. This recursively invokes the `optimize` method on
+the plan's children and then returns a node of the same type.
+
+```rust
+fn optimize(
+ &self,
+ plan: &LogicalPlan,
+ _config: &mut OptimizerConfig,
+) -> Result<LogicalPlan> {
+ // recurse down and optimize children first
+ let plan = utils::optimize_children(self, plan, _config)?;
+
+ ...
+}
+```
+
+### Writing Tests
+
+There should be unit tests in the same file as the new rule that test the effect of the rule being applied to a plan
+in isolation (without any other rule being applied).
+
+There should also be a test in `integration-tests.rs` that tests the rule as part of the overall optimization process.
+
+### Debugging
+
+The `EXPLAIN VERBOSE` command can be used to show the effect of each optimization rule on a query.
Review Comment:
```suggestion
The `EXPLAIN VERBOSE` command can be used to show the effect of each optimization rule on a query.
In the following example, the `type_coercion` and `simplify_expressions` passes have simplified the plan so that it returns the constant `"3.2"` rather than doing a computation at execution time.
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] andygrove merged pull request #3788: MINOR: Optimizer example and docs, deprecate `Expr::name`
Posted by GitBox <gi...@apache.org>.
andygrove merged PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] andygrove commented on a diff in pull request #3788: MINOR: Optimizer example and docs, deprecate `Expr::name`
Posted by GitBox <gi...@apache.org>.
andygrove commented on code in PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788#discussion_r993795542
##########
datafusion/optimizer/examples/rewrite_expr.rs:
##########
@@ -0,0 +1,163 @@
+// Licensed to the Apache Software Foundation (ASF) under one
Review Comment:
Done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #3788: MINOR: Optimizer example and docs, deprecate `Expr::name`
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788#issuecomment-1276686816
🎉
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] andygrove commented on a diff in pull request #3788: MINOR: Optimizer example and docs
Posted by GitBox <gi...@apache.org>.
andygrove commented on code in PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788#discussion_r993425976
##########
datafusion/optimizer/README.md:
##########
@@ -17,10 +17,181 @@
under the License.
-->
-# DataFusion Query Optimizer Rules
+# DataFusion Query Optimizer
-[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory format.
+[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory
+format.
-This crate is a submodule of DataFusion that provides query optimizer rules.
+DataFusion has modular design, allowing individual crates to be re-used in other projects.
+
+This crate is a submodule of DataFusion that provides a query optimizer for logical plans.
+
+## Running the Optimizer
+
+The following code demonstrates the basic flow of creating the optimizer with a default set of optimization rules
+and applying it to a logical plan to produce an optimized logical plan.
+
+```rust
+
+// We need a logical plan as the starting point. There are many ways to build a logical plan:
+//
+// The `datafusion-expr` crate provides a LogicalPlanBuilder
+// The `datafusion-sql` crate provides a SQL query planner that can create a LogicalPlan from SQL
+// The `datafusion` crate provides a DataFrame API that can create a LogicalPlan
+let logical_plan = ...
+
+let mut config = OptimizerConfig::default();
+let optimizer = Optimizer::new(&config);
+let optimized_plan = optimizer.optimize(&logical_plan, &mut config, observe)?;
+
+fn observe(plan: &LogicalPlan, rule: &dyn OptimizerRule) {
+ println!(
+ "After applying rule '{}':\n{}",
+ rule.name(),
+ plan.display_indent()
+ )
+}
+```
+
+## Providing Custom Rules
+
+The optimizer can be created with a custom set of rules.
+
+```rust
+let optimizer = Optimizer::with_rules(vec![
+ Arc::new(MyRule {})
+]);
+```
+
+## Writing Optimization Rules
+
+Please refer to the [examples](examples) to learn more about the general approach to writing optimizer rules and
+then move onto studying the existing rules.
+
+All rules must implement the `OptimizerRule` trait.
+
+```rust
+/// `OptimizerRule` transforms one ['LogicalPlan'] into another which
+/// computes the same results, but in a potentially more efficient
+/// way.
Review Comment:
That's a very good point. I will add this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] isidentical commented on a diff in pull request #3788: MINOR: Optimizer example and docs
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #3788:
URL: https://github.com/apache/arrow-datafusion/pull/3788#discussion_r992861091
##########
datafusion/optimizer/README.md:
##########
@@ -17,10 +17,181 @@
under the License.
-->
-# DataFusion Query Optimizer Rules
+# DataFusion Query Optimizer
-[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory format.
+[DataFusion](df) is an extensible query execution framework, written in Rust, that uses Apache Arrow as its in-memory
+format.
-This crate is a submodule of DataFusion that provides query optimizer rules.
+DataFusion has modular design, allowing individual crates to be re-used in other projects.
+
+This crate is a submodule of DataFusion that provides a query optimizer for logical plans.
+
+## Running the Optimizer
+
+The following code demonstrates the basic flow of creating the optimizer with a default set of optimization rules
+and applying it to a logical plan to produce an optimized logical plan.
+
+```rust
+
+// We need a logical plan as the starting point. There are many ways to build a logical plan:
+//
+// The `datafusion-expr` crate provides a LogicalPlanBuilder
+// The `datafusion-sql` crate provides a SQL query planner that can create a LogicalPlan from SQL
+// The `datafusion` crate provides a DataFrame API that can create a LogicalPlan
+let logical_plan = ...
+
+let mut config = OptimizerConfig::default();
+let optimizer = Optimizer::new(&config);
+let optimized_plan = optimizer.optimize(&logical_plan, &mut config, observe)?;
+
+fn observe(plan: &LogicalPlan, rule: &dyn OptimizerRule) {
+ println!(
+ "After applying rule '{}':\n{}",
+ rule.name(),
+ plan.display_indent()
+ )
+}
+```
+
+## Providing Custom Rules
+
+The optimizer can be created with a custom set of rules.
+
+```rust
+let optimizer = Optimizer::with_rules(vec![
+ Arc::new(MyRule {})
+]);
+```
+
+## Writing Optimization Rules
+
+Please refer to the [examples](examples) to learn more about the general approach to writing optimizer rules and
+then move onto studying the existing rules.
+
+All rules must implement the `OptimizerRule` trait.
+
+```rust
+/// `OptimizerRule` transforms one ['LogicalPlan'] into another which
+/// computes the same results, but in a potentially more efficient
+/// way.
Review Comment:
Does it make sense to emphasize that in the event of there are no transformations to apply (for the given input), the optimizer could (and should) return the input as is (e.g. instead of failing with an exception)?
```
/// `OptimizerRule` can transform one ['LogicalPlan'] into another which
/// computes the same results, but in a potentially more efficient way. If
/// there are no suitable transformations for the input plan, the optimizer can
/// simply return it as is.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org