Tidb: Call For Participation: add rules for cascades optimizer

[winoros]

In https://github.com/pingcap/tidb/blob/master/docs/design/2018-08-29-new-planner.md, we proposed a new planner based on cascades.
We create this issue to track the dev progress of the new planner.

If you're interested in this project, feel free to join the discussion by entering the slack channel #sig-planner in the tidbcommunity slack workspace. Or just pick some TODO issues listed in this tracking issue using the following working flow:

1. Find one issue which you're interested in.
2. If it's a simple work you can just reply in this issue to let the community know that issue is picked by you. Or you can create a separate issue to describe the rough implementation and discussing with the community.
3. File new pull requests.

You can find the basic workflow for adding a transformation rule here.

The issues below with [easy] tag are highly recommended for new contributors.

Issues

• Porting the existing rules in the old planner:
  
  
  
  • Predicate pushdown(current rule_predicate_push_down.go):
    
    
    
    
    
    • [x] push the selection down to window [easy] @jiangyuzhao #14068
    
    
    
    • [x] push the selection down to union [easy] @gauss1314 #14033
    
    
    
    • [ ] push the selection down to join
      
      
      
      
      
      
      
      • [x] inner join #13470
      
      
      
      
      • [x] outer join [medium] #13996
      
      
      
      
      • [ ] semi join [medium] Semi join is generated via apply. So we cannot implement this until we support decorrelate.
      
      
      
      
    
    
    
    • [x] push the selection down to index scan. #13945
    
    
    
  
  
  • Push operators down to tikv gather(the attch2Task method of TopN and Limit):
    
    
    
    
    
    • [x] push the top-n down to gather [easy] @gauss1314 #14242
    
    
    
    • [x] push the limit down to gather [easy] @gauss1314 #14796
    
    
    
  
  
  • Projection elimination(current rule_eliminate_projection.go):
    
    
    
    
    
    • [x] merge the adjacent projection [easy] @pingyu #13840
    
    
    
    • [x] eliminate the projection whose output columns are the same with its child. [easy] @t0350 #13895
    
    
    
  
  
  • Limit pushdown(current rule_topn_push_down.go):
    
    
    
    
    
    • [x] push the limit down to projection [easy] @doggeral #14254
    
    
    
    • [x] push the limit down to union. [easy] @doggeral #14264
    
    
    
    • [x] push the limit down to outer join.[easy] @SeaRise #14434
    
    
    
  
  
  • Top-N pushdown(current rule_topn_push_down.go):
    
    
    
    
    
    • [x] push the top-n down to projection [easy] @hsqlu #13855
    
    
    
    • [x] push the top-n down to union. [easy] @Reminiscent #14078
    
    
    
    • [x] push the top-n down to outer join. [easy] @hsqlu #14249
    
    
    
  
  
  • MergeAdjacentPlans:
    
    
    
    
    
    • [x] merge the adjacent selection. [easy] @hellojujian #14165
    
    
    
    • [x] merge the adjacent limit. [easy] @SeaRise #14306
    
    
    
    • [x] merge the adjacent topN. [easy] @Reminiscent #14345
    
    
    
    • [ ] merge the adjacent Window. [easy]
    
    
    
  
  
  • Decorrelate the correlated subquery (current rule_decorrelate.go):
    
    
    
    
    
    • [ ] create a draft designing which is compatible with cascades.
    
    
    
  
  
  • Global max/min elimination(current rule_max_min_eliminate.go):
    
    
    
    
    
    • [x] implement XformMaxMinToTop1 [medium] @Reminiscent #14274
    
    
    
  
  
  • Aggregation elimination(current rule_aggregation_elimination.go):
    
    
    
    
    
    • [ ] implement XfromAggToProj [medium]
    
    
    
  
  
  • Aggregation pushdown(current rule_aggregation_push_down.go):
    
    
    
    
    
    • [ ] a draft design for a better functionality than current planner first. [hard]
    
    
    
  
  
  • Join reorder:
    
    
    
    
    
    • [ ] create a draft designing which is compatible with cascades. [super hard]
    
    
    
  
  
  • Some rewriting method applied in plan building phase:
    
    
    
    
    
    • [ ] Rewrite in subquery to inner join with aggregation [hard]
    
    
    
  
  
  • Outer join elimination(current rule_join_elimination.go) @SeaRise #14465
  
  
• Implement the logical expression to physical expression
  
  
  
  • [ ] Stream aggregation [medium] @SeaRise #14857
  
  
  • [x] Merge join [medium] @Reminiscent #14450
  
  
  • [x] Hash join [medium] #13470 #13996
  
  
  • [ ] Index join [hard] #14831
  
  
  • [ ] TiKV's double read case (current IndexLookUpReader) #13909
  
  
  • [ ] Multi index merge case (current IndexMergeReader) [hard]
  
  
  • [x] Window [easy] @edytagarbarz #14085
  
  
  • [x] UnionAll #13848
  
  
  • [x] Apply #13873
  
  
  • [x] MaxOneRow #13873
  
  
• Other things that current planner have
  
  
  
  • [x] The PreparePossibleProperty #13910
  
  
  • [ ] Skyline pruning method for making the TP queries more robust. [hard]
  
  
  • [x] Build unique Key info #13799
  
  
  • [ ] Hint support [hard]
  
  
  • [ ] Prepare cache support [hard]
  
  
  • [ ] Support of Partitioned table. [hard]
  
  
• Other powerful things:
  
  
  
  • [ ] A powerful functional dependency check to implement a better only_full_group_by checking than TiDB current does and for further optimizations. [hard]
  
  
  • [ ] PlanHash or the fingerprint of expression to do the expression deduplication. [hard]
  
  
  • [ ] Group merging for deduplication. [medium]
  
  
  • [x] AppliedRuleSet for GroupExpr to avoid re-apply a rule. [medium] #14073
  
  
  • [ ] Optimizer trace to show the inner progress of the planner. Make people understand the planner more easily and help dev debug.
  
  
  • New rules to make the planner more powerful.
  
  
  • New properties the planner holding to enlarge the searching space.
  
  

[francis0407]

I highly recommend new contributors try rules like 'Limit PushDown' and 'TopN PushDown' above. They are truly easy to implement and can help you get familiar with the cascades framework.

[tangwz]

let me fix Limit PushDown.

[hsqlu]

I'd like to take TopN PushDown.

[francis0407]

That's great. You'd better implement only one transformation rule in one PR. cc @tangwz @hsqlu

[jiangyuzhao]

@francis0407 Do you have some other recommendations for new contributors? Thank you very much!

[francis0407]

You can try this transformation rule: PushSelDownWindow which pushes the Selection down to the child of Window. The current implementation is here: https://github.com/pingcap/tidb/blob/d438c860a660f00c755094e1d6c9e61c18715edf/planner/core/rule_predicate_push_down.go#L564.

The logic of this rule is simple, I think. You only need to implement this rule and add tests in cascades/testdata/transformation_rules_test_in.json/TestPredicatePushDown.

If you encounter any difficulties, you can ask us in slack. @jiangyuzhao

[jiangyuzhao]

@francis0407 OK. Thank you very much. I will try to implement PushSelDownWindow. I'm a new contributor, and I'm not familiar with slack. Do you mean I can send comment below the issue?

[francis0407]

@jiangyuzhao Slack is a powerful software for online communication. You may need to sign up at first. Then check this link: https://pingcap.com/tidbslack/. We can discuss issues about cascades optimizer in the channel sig-planner.

[jiangyuzhao]

@francis0407 Thanks for your explanation~

[gauss1314]

Let me fix PushSelDownUnion from push the selection down to union of Predicate pushdown.

[pingyu]

Let me fix merge the adjacent projection of Projection elimination

[francis0407]

Hi guys,
If you are not sure how to implement a rule or how to add unit test for the rule, I think https://github.com/pingcap/tidb/pull/13106 and https://github.com/pingcap/tidb/pull/13288 could be good examples.
Note that GetPattern() is not used to define the Pattern anymore, you have to define a function like NewRuleXXXXX to create the rule you have implemented and define the pattern of the rule inside this function.

[francis0407]

Workflow for Adding a Transformation Rule

Here is the basic workflow for adding a Transformation rule in cascades optimizer. Add Optimization Rules for Cascades Optimizer(in Chinese only) may provide more information.

Implement a Transformation Rule

1. Define a struct for the rule, like PushSelDownAggregation.
2. Implement two methods OnMatch() and OnTransform().
3. Add a function NewRuleXXX to create such a rule, and register it's Pattern inside.

Add unit test for a Transformatino Rule

1. Add the rule into transformation_rules.go/defaultTransformationMap. The position where it supposed to be depends on the top Operand of its Pattern. For example, if its Pattern is Selection->Projection, it should be in the group of memo.OperandSelection: { ... }.
2. Add unit test case in transformation_rules_test.go, TestPredicatePushDown is a good example.
3. Add the rule into the test optimizer's transformation map.
4. Add test SQL in file testdata/transformation_rules_suite_in.json. Make sure those SQLs will trigger the rule you just implemented.
5. Run go test with arguments --record, it will generate test results into file testdata/transformation_rules_suite_out.json.
6. Check if the result shows the rule works.

[edytagarbarz]

Let me fix Stream aggregation

[francis0407]

Hi, @edytagarbarz
Stream aggregation might not be ready to be implemented now. It requires a bottom-up method to prune physical properties called PreparePossibleProperty(currently in file planner/core/property_cols_prune.go), which I'm still working on.
Could you please try other tasks? I think the implementationRule for LogicalWindow is quite easy to do.
When I finish the PreparePossibleProperty, I will let you know and invite you to fix the Stream agg.

[edytagarbarz]

@francis0407 definitely!
I'll do implementationRule for LogicalWindow then, thanks!

[jiangyuzhao]

You can try this transformation rule: PushSelDownWindow which pushes the Selection down to the child of Window. The current implementation is here:

https://github.com/pingcap/tidb/blob/d438c860a660f00c755094e1d6c9e61c18715edf/planner/core/rule_predicate_push_down.go#L564

.
The logic of this rule is simple, I think. You only need to implement this rule and add tests in cascades/testdata/transformation_rules_test_in.json/TestPredicatePushDown.

If you encounter any difficulties, you can ask us in slack. @jiangyuzhao

@francis0407 I'm sorry for being busy this week. I will finish the task soon!

[francis0407]

@jiangyuzhao Don't worry, enjoy the world of open source.

[francis0407]

If you are looking for PR examples, check the cascades project.

[t0350]

I'd like to fix eliminate the projection whose output columns are the same with its child from projection elimination.

[gauss1314]

Let me fix push the top-n down to gather of push operators down to tikv gather.

[Reminiscent]

Let me fix：

• [x] push the top-n down to union #14214
• [x] implement XformMaxMinToTop1 #14274
• [x] merge the adjacent topN #14345
• [x] Merge join #14450

[hellojujian]

let me fix

• [x] merge the adjacent selection.

[doggeral]

let me fix push the limit down to projection

[winoros]

@doggeral If you need some help, you can contact us via slack channel #sig-planner in the tidbcommunity

[edytagarbarz]

Let me fix Aggregation elimination implement XfromAggToProj

[gauss1314]

Let me fix Aggregation elimination implement XfromAggToProj

Hi @edytagarbarz , can I do this if you haven't started yet?

[SeaRise]

@gauss1314
I am so sorry...I've started to implement XfromAggToProj....