[enhancement] rules don't need to recursion inside themselves

[jackwener]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Now, all rules in optimizer must handle subplan by recursing optimize themselves.

I'd like to let optimizer to handle subplan, rule just focus on the optimize logic.

I have add optimizer struct for this PR in #2616 .

Describe the solution you'd like
Handle the subplan in optimizer by recursing optimization.

Describe alternatives you've considered

Additional context

[alamb]

I think it would be awesome to create some sort of LogicalPlanRewriter that is in the style of ExprRewriter or ExprVisitor and captures the traversal pattern across a plan

[jackwener]

Currently, datafusion optimize the plan many times. Because the all rules will traverse the whole plan tree one time.
Times is O(n). (n is number of rules).

I think it's not good choice. But now explain verbose print the changes after apply one rule. This ability depends on apply rule one by one.

I think the better and usual practice is traverse plan instead of traverse rules.

Now:
rules.foreach(
     plan.apply(rule)
)

After
for(childPlanNode: Plan) {
     childPlanNode.appy(rules).
}

In this way, we just need traverse the plan tree just one time. But it will affect the print change ability

[jackwener]

@alamb @Dandandan @andygrove @houqp

How do you think about this trade-off

[alamb]

How do you think about this trade-off

I think it may be quite challenging to implement all the rewrite rules in parallel like this, though it would be interesting to try.

In terms of efficiency, I think it would be worth profiling to see if the optimizer it taking significant time and if so if there are any tall poles that can be addressed (having each pass make a clone() of the input plan would be one thing I suspect could be improved)

[alamb]

🎉