DataFusion Optimizer framework discussion

[mingmwang]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
A clear and concise description of what the problem is. Ex. I'm always frustrated when [...]

Current DataFusion's optimizer rules are complex and not easy to implement. I think one of the reason is each optimization rule has to deal with the plan tree traversing, pattern matching and rewriting. It is more a visitor model (like the old Presto optimizer rules).
And if we add new logical plan nodes, especially non-leaf plan nodes, it is very possible that all the rules need to be modified to add the related visit logic.

An alternative approach is we can have the Optimizer itself drive the plan tree traversing and apply the rules down/up the tree, it will make the rule logic much clear and can focus on pattern matching and rewriting.

I see there is a new experimental optimizer framework which leverages the egg lib.
#440
I'm not familiar with egg and not sure how mature the egg lib is.

Please share your thoughts.

Describe the solution you'd like
A clear and concise description of what you want to happen.

Describe alternatives you've considered
A clear and concise description of any alternative solutions or features you've considered.

Additional context
Add any other context or screenshots about the feature request here.

[mingmwang]

@alamb @andygrove Please share your thoughts and insights.

[alamb]

Thank you for bringing this up @mingmwang. My view is that the current optimizer framework could definitely use improving 👍

t is more a visitor model (like the old Presto optimizer rules).

I think I would say the current optimizer rules "aspire" to be a visitor model; Right now the interface for an optimizer looks like this:

pub trait OptimizerRule {
    /// Rewrite `plan` to an optimized form
    fn optimize(
        &self,
        plan: &LogicalPlan,
        execution_props: &ExecutionProps,
    ) -> Result<LogicalPlan>;

    /// A human readable name for this optimizer rule
    fn name(&self) -> &str;
}

which as you say requires each optimizer rule to handle the recursion itself and intermixes the traversal from whatever rewrites are happening. There are helpers in https://github.com/apache/arrow-datafusion/blob/master/datafusion/src/optimizer/utils.rs such as optimize_children and from_plan but I would say they are not particularly ergonomic

So what I had hoped to do at some point was to make an actual visitor / mutator pattern for rewriting LogicalPlan. We have done this for Expr rewriting expr_rewriter.rs and I think it works very well to separate out the structure traversal from the actual changes (see, for example, the code for simplifying expressions here: simplify_expressions.rs

cc @Dandandan and @realno who may also have idea on this

[alamb]

I was imagining an actual mutator like this:

trait LogicalPlanRewriter {
   pub fn rewrite(plan: LogicalPlan) -> Result<LogicalPlan>
}

that would handle the traversal into children so that each optimizer would look something like

impl LogicalPlanRewriter for MyOptimizerPass {
  fn rewrite(plan: LogicalPlan) -> Result<LogicalPlan> {
    match plan {
      // special handling for the types of plans the optimizer cares about
      LogicalPlan::Filter(..) => {...}
      ...
      // default is no rewrite
      _ => Ok(plan)
   }
}

I vaguely remember trying to write something like this up once, but as I recall I got stuck on the fact that LogicalPlans can have shared inputs (there are Arcs ?) but I can't remember exactly and it was a while ago.

A slight variant on the above that looks more like a typical vistitor would be something that handled each type of LogicalPlan and defaults to itself and could save the switch statement:

trait LogicalPlanRewriter {
   // rewrite a LogicalPlan filter node; Default implementation returns the same plan
   pub fn rewrite_filter(filter: Filter) -> Result<LogicalPlan> {
    Ok(LogicalPlan::Filter(filter)
   } 

   // rewrite a LogicalPlan table_scan node; Default implementation returns the same plan
   pub fn rewrite_filter(table_scan: TableScan) -> Result<LogicalPlan> {
    Ok(LogicalPlan::TableScan(table_scan)
   } 

   ...
}

What do you think?

[alamb]

If I were going to do this, I would probably sketch out a PlanRewriter and then try to port one or two of the existing optimizers to use it (without changing the Optimizer trait at first) as a proof of concept. Then as follow on PRs I would port over the remaining optimizers

[jackwener]

which as you say requires each optimizer rule to handle the recursion itself and intermixes the traversal from whatever rewrites are happening. There are helpers in https://github.com/apache/arrow-datafusion/blob/master/datafusion/src/optimizer/utils.rs such as optimize_children and from_plan but I would say they are not particularly ergonomic

So what I had hoped to do at some point was to make an actual visitor / mutator pattern for rewriting LogicalPlan. We have done this for Expr rewriting expr_rewriter.rs and I think it works very well to separate out the structure traversal from the actual changes (see, for example, the code for simplifying expressions here: simplify_expressions.rs

I also found these problems when I enhance the optimizer.

It's a significant proposal, I'm focus this part currently.

I'm planning to add the volcano/cascades optimizer framework for datafusion. After I get more familiar with datafusion, I will add more detail and RFC for this part.

[jackwener]

But, It's a big change, we can do it in the long term.

Currently, I'm planning enhance the optimizer gradually,

[Dandandan]

I believe ithat we really should continue experimenting with egg as a optimization framework. This doesn't mean we should move everything to the egg framework, but we can have one or multiple egg-based passes.

Some nice things that make egg (besides written in Rust) a nice candidate for DataFusion:

• Optimized algorithm hard to match with manual written optimization passes
• Easier and less verbose to add simple rules
• Plugin framework to add slightly more complex optimizations
• Does not depend on rule order and combined with being able to apply multiple rules in one pass and until convergence, can optimize further than currently is possible (or what would be possible using a optimization strategy like Apache Spark)
• Cost-based optimization easy to add (this is a native feature)

[realno]

I definitely agree the optimizer framework needs some attention. Specifically, each rule needs to handle tree traversal which is quite tedious and also less efficient due to the repeated full tree traversal. Also it is error prone, if not careful it may introduce dependency on the order of the rules in code.

I am leaning towards deciding which framework to go with asap for the following reasons: 1. we have limited rules for now so it is small effort to change it now. 2. simplifying rule implementation can encourage more people contributing in this area. 3. this may also help benchmarking and optimization work.

I saw a few options were brought up, we can make a list for ones worth investigating.

[xudong963]

I believe ithat we really should continue experimenting with egg as a optimization framework. This doesn't mean we should move everything to the egg framework, but we can have one or multiple egg-based passes.

I agree, egg is potential.
Seems egg will generate DAGs than tree? @Dandandan

[xudong963]

I'm planning to add the volcano/cascades optimizer framework for datafusion. After I get more familiar with datafusion, I will add more detail and RFC for this part.

Cascades is an optimization framework that uses a cost-based approach to explore possible executable
of the search space. So I have some my thoughts:

1. It requires a solid and as accurate as possible cost-based optimization.
2. It is likely to lead to misguidance, which produces local convergence of the search and fails to produce an optimal solution.
3. It will have a relatively large impact on the current codebase. (Of course, if it can be verified that there is a clear benefit in most scenarios, I support its introduction)
4. I prefer to continue experimenting with egg, @pjmore has done many works Add experimental Tokomak optimizer #1485, fyi Future of experimental optimizer datafusion-tokomak #440

[jackwener]

I,m sorry that I don,t know more about agg, I also try it to do something for datafusion

[jackwener]

@Dandandan hi, about agg, there is some design doc or some discussion about it？ I want to know more about it in order to contirbute for enhancing our optimizer

[jackwener]

I'm planning to add the volcano/cascades optimizer framework for datafusion. After I get more familiar with datafusion, I will add more detail and RFC for this part.

Cascades is an optimization framework that uses a cost-based approach to explore possible executable of the search space. So I have some my thoughts:

1. It requires a solid and as accurate as possible cost-based optimization.
2. It is likely to lead to misguidance, which produces local convergence of the search and fails to produce an optimal solution.
3. It will have a relatively large impact on the current codebase. (Of course, if it can be verified that there is a clear benefit in most scenarios, I support its introduction)
4. I prefer to continue experimenting with egg, @pjmore has done many works Add experimental Tokomak optimizer #1485

I just mean that add a like top to down optimizer instead speacify optimizer

[xudong963]

I'm planning to add the volcano/cascades optimizer framework for datafusion. After I get more familiar with datafusion, I will add more detail and RFC for this part.

Cascades is an optimization framework that uses a cost-based approach to explore possible executable of the search space. So I have some my thoughts:

1. It requires a solid and as accurate as possible cost-based optimization.
2. It is likely to lead to misguidance, which produces local convergence of the search and fails to produce an optimal solution.
3. It will have a relatively large impact on the current codebase. (Of course, if it can be verified that there is a clear benefit in most scenarios, I support its introduction)
4. I prefer to continue experimenting with egg, @pjmore has done many works Add experimental Tokomak optimizer #1485

I just mean that add a like top to down optimizer instead speacify optimizer

I know -- volcano/cascades optimizer framework both are top-down optimizers, my thoughts covered both.