Call For Participation: add rules for cascades optimizer

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 #14068
    • push the selection down to union [easy] @gauss1314 #14033
    • push the selection down to join
      • inner join #13470
      • outer join [medium] #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. #13945
  • Push operators down to tikv gather(the attch2Task method of TopN and Limit):
    • push the top-n down to gather [easy] @gauss1314 #14242
    • push the limit down to gather [easy] @gauss1314 #14796
  • Projection elimination(current rule_eliminate_projection.go):
    • merge the adjacent projection [easy] @pingyu #13840
    • eliminate the projection whose output columns are the same with its child. [easy] @t0350 #13895
  • Limit pushdown(current rule_topn_push_down.go):
    • push the limit down to projection [easy] @doggeral #14254
    • push the limit down to union. [easy] @doggeral #14264
    • push the limit down to outer join.[easy] @SeaRise #14434
  • Top-N pushdown(current rule_topn_push_down.go):
    • push the top-n down to projection [easy] @hsqlu #13855
    • push the top-n down to union. [easy] @Reminiscent #14078
    • push the top-n down to outer join. [easy] @hsqlu #14249
  • MergeAdjacentPlans:
    • merge the adjacent selection. [easy] @hellojujian #14165
    • merge the adjacent limit. [easy] @SeaRise #14306
    • merge the adjacent topN. [easy] @Reminiscent #14345
    • merge the adjacent Window. [easy] @An-DJ #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 #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
  • Merge join [medium] @Reminiscent #14450
  • Hash join [medium] #13470 #13996
  • Index join [hard] #14831
  • TiKV's double read case (current IndexLookUpReader) #13909
  • Multi index merge case (current IndexMergeReader) [hard]
  • Window [easy] @edytagarbarz #14085
  • UnionAll #13848
  • Apply #13873
  • MaxOneRow #13873
• Other things that current planner have
  • The PreparePossibleProperty #13910
  • Skyline pruning method for making the TP queries more robust. [hard]
  • 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]
  • 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.