[EPIC]: reimplement all rules which contains global-state

[jackwener]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

Current some rule contains global-state

Such as limit_push_down use ancestor: &Ancestor collect the limit-state of whole tree.

• Reimplement filter_push_down #4266
• Reimplement projection_push_down #4265
• Reimplement eliminate_limit #4264
• Reimplement limit_push_down #4263
• reimplement reduce_outer_join #4270
• Reimplement the eliminate_cross_join #4176

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.

[jackwener]

let me explain why.

Due to global-state exists, we can't just optimize a subtree, we must traverse the whole tree.

In fact, I prefer to Pattern-match, we match a subtree pattern, and just optimize the pattren/subtree.

A example: Merge Limit

match plan {
     Limit =>  {
           match childPlan => {
              Limit => {  merge(limit, childlimit)  }
               _ => { don't match pattern, return None or recurse....}
           }
     }
     _ => { don't match pattern, return None or recurse....}
}

we just match limit-limit, and handle it.

BUT, global-state force we must handle various situations， and we must traverse the tree all.

What's more, global-stats is easy to cause bugs. Such as projection exist alias, the global-stats exist bug.

[jackwener]

After finish this job,
I will need to finish #4208 .
After finish them, All preparations will be done.
I will do #3972 ! It will make our optimizer simple and easy-use.

[jackwener]

cc @andygrove @alamb @mingmwang @liukun4515

[alamb]

👍 the idea of pattern matching on the way back up during rewrite rules makes lots of sense to me 👍

[mingmwang]

I think it depends on what the global-state is. If the global states are predicates or something related to Column/Exprs, then we should remove such kind of global states.. But for some optimization rules, it might be better to keep a global state so that it is easily to figure out a best plan.

[mingmwang]

I think today in DataFusion's logical optimizer rules, most of the complexity comes from dealing with predicates. That's why I want to introduce the QueryConstraints into the logical plan structs.

#4222

[jackwener]

I think it depends on what the global-state is. If the global states are predicates or something related to Column/Exprs, then we should remove such kind of global states.. But for some optimization rules, it might be better to keep a global state so that it is easily to figure out a best plan.

Agree it, global-state of all rules that I change is related Column/Exprs or limit number.

I think today in DataFusion's logical optimizer rules, most of the complexity comes from dealing with predicates.

Agree, especially for rule about projection/filter/agg.