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):
    • push the selection down to window [easy] @jiangyuzhao planner/cascades: Add the transformation rule PushSelDownWindow #14068
    • push the selection down to union [easy] @gauss1314 planner/cascades: add transformation rule PushSelDownUnionAll #14033
    • push the selection down to join
      • inner join planner/cascades: add transformation PushSelDownJoin & Implementation for HashJoin #13470
      • outer join [medium] planner/cascades: support outer join implementation and push down selection for outer join #13996
      • semi join [medium] Semi join is generated via apply. So we cannot implement this until we support decorrelate.
    • push the selection down to index scan. planner/cascades: add transformation rule PushSelDownIndexScan #13945
  • Push operators down to tikv gather(the attch2Task method of TopN and Limit):
    • push the top-n down to gather [easy] @gauss1314 planner/cascades: add transformation rule PushTopNDownTiKVSingleGather  #14242
    • push the limit down to gather [easy] @gauss1314 planner/cascades: add transformation rule PushLimitDownTiKVSingleGather #14796
  • Projection elimination(current rule_eliminate_projection.go):
    • merge the adjacent projection [easy] @pingyu planner/cascades: add transformation rule MergeAdjacentProjection #13840
    • eliminate the projection whose output columns are the same with its child. [easy] @t0350 planner/cascades: add transformation rule ProjectionElimination #13895
  • Limit pushdown(current rule_topn_push_down.go):
    • push the limit down to projection [easy] @doggeral planner/cascades: add transformation rule PushLimitDownProjcetion #14254
    • push the limit down to union. [easy] @doggeral planner/cascades: add transformation rule PushLimitDownUnionAll. #14264
    • push the limit down to outer join.[easy] @SeaRise planner/cascades: add transformation rule PushLimitDownOuterJoin #14434
  • Top-N pushdown(current rule_topn_push_down.go):
    • push the top-n down to projection [easy] @hsqlu planner/cascades: add transformation rule PushTopNDownProjection #13855
    • push the top-n down to union. [easy] @Reminiscent planner/cascades: add transformation rule PushTopNDownUnionAll #14078
    • push the top-n down to outer join. [easy] @hsqlu planner/cascades: add transformation rule PushTopNDownOuterJoin #14249
  • MergeAdjacentPlans:
    • merge the adjacent selection. [easy] @hellojujian planner/cascades: add transformation rule MergeAdjacentSelection #14165
    • merge the adjacent limit. [easy] @SeaRise planner/cascades: add transformation rule MergeAdjacentLimit #14306
    • merge the adjacent topN. [easy] @Reminiscent planner/cascades: add transformation rule MergeAdjacentTopN #14345
    • merge the adjacent Window. [easy] @An-DJ planner: add MergeAdjacentWindow rule for cascades #24556
  • 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):
    • implement XformMaxMinToTop1 [medium] @Reminiscent planner/cascades: add transformation rule EliminateSingleMaxMin #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 planner/cascades: add transformation rule EliminateOuterJoinBelowAggregation #14465
• Implement the logical expression to physical expression
  • Stream aggregation [medium] @SeaRise planner/cascades[WIP]: add ImplementationRule for StreamAgg #14857
  • Merge join [medium] @Reminiscent planner/cascades: add ImplementationRule for MergeJoin #14450
  • Hash join [medium] planner/cascades: add transformation PushSelDownJoin & Implementation for HashJoin #13470 planner/cascades: support outer join implementation and push down selection for outer join #13996
  • Index join [hard] planner/cascades: add implementationRule for IndexLookUpJoin #14831
  • TiKV's double read case (current IndexLookUpReader) planner/cascades: add implementation rule for TiKVDoubleGather #13909
  • Multi index merge case (current IndexMergeReader) [hard]
  • Window [easy] @edytagarbarz planner/cascades: Add ImplementationRule for Window #14085
  • UnionAll planner/cascades: add ImplementationRule for UnionAll #13848
  • Apply planner/cascades: support implementation rule Apply and MaxOneRow. #13873
  • MaxOneRow planner/cascades: support implementation rule Apply and MaxOneRow. #13873
• Other things that current planner have
  • The PreparePossibleProperty planner/cascades: implement PreparePossibleProperties in cascades planner #13910
  • Skyline pruning method for making the TP queries more robust. [hard]
  • Build unique Key info planner/cascades: integrate BuildKeyInfo into cascades planner #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]
  • AppliedRuleSet for GroupExpr to avoid re-apply a rule. [medium] planner/cascades: add appliedRuleSet in GroupExpr to avoid re-apply rules #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:

tidb/planner/core/rule_predicate_push_down.go

Line 564 in d438c86

func (p *LogicalWindow) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan) {

.

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 #13106 and #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:

tidb/planner/core/rule_predicate_push_down.go

Line 564 in d438c86

func (p *LogicalWindow) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan) {

.
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.

[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....

[jackwener]

The task merge the adjacent Window. [easy] is completed by An-DJ.

[jackwener]

Hi, I'm willing to take the Group merging for deduplication. [medium] up.

However, some of the backgrounds are rather scarce. Can you provide some background?