Migrate AddExchanges to iterative optimizer

[kokosing]

No description provided.

[kokosing]

Design is mostly based on:

• ORCA - https://d1fto35gcfffzn.cloudfront.net/big-data/white-paper/SIGMODHAWQAdvantages.pdf
• SCOPES - http://www.chinacloud.cn/upload/2012-08/12081008403014.pdf
• Apache Calcite

We are going to add a new kind of optimizer which will have two phases:

• exhaustive - where search space (memo) is populated
• optimize - where the best plan is found from the search space
  This will be wrapped as ExhaustiveOptimizer, it will we be using the same Rule interface as IterativeOptimizer.

Below is the minimal list what have to be done to migrate AddExchanges.

Plan of attack (list of features that ExhaustiveOptimizer will support):

1. Support simple pattern matching with captures, so rule can say I need a filter on top of project and these nodes will be captured and provided to rule via Lookup
2. Make possible that Rule application can return several alternative plan nodes. For example when partitioning is considered a rule may return several different plan nodes one per each instance of partitioning (partitioned by a or a,b or a,b,c or a,c). It can be either satisfied by a returning a list or by injecting consumer.
3. Introduce traits (physical properties) and trait sets.

• simple traits algebra (ability that this trait instance is satisfied by this trait instance)
• (optional) trait enforcers
• (optional) negation traits (for example information that plan node is not yet partitioned)

4. Rule will be able to return plans with specified trait sets.
5. Introduce memo that will store several plan nodes per group (equivalence based)
6. Introduce ExhaustiveOptimizer

• Do not run rule which was run with the same captures twice (as rules are deterministic)

7. Finding the best plan algorithm within the memo with the usage of some sort of cost calculator (heuristic).
8. Migrate AddExchanges as set of Rules

The above order is just a suggestion, actual order of how things will be implemented may differ.
Optional points are not yet decided if they will be needed.
This plan is just an initial idea, it may change as we go.

CC: @martint @ilfrin @sopel39

[stale]

This issue has been automatically marked as stale because it has not had any activity in the last 2 years. If you feel that this issue is important, just comment and the stale tag will be removed; otherwise it will be closed in 7 days. This is an attempt to ensure that our open issues remain valuable and relevant so that we can keep track of what needs to be done and prioritize the right things.