diff options
author | wangzhenhua <wangzhenhua@huawei.com> | 2017-03-08 16:01:28 +0100 |
---|---|---|
committer | Herman van Hovell <hvanhovell@databricks.com> | 2017-03-08 16:01:28 +0100 |
commit | e44274870dee308f4e3e8ce79457d8d19693b6e5 (patch) | |
tree | 99cde8d5b623e14e9b1a8fa86ab152a4cba0e640 /sql/hive | |
parent | 9ea201cf6482c9c62c9428759d238063db62d66e (diff) | |
download | spark-e44274870dee308f4e3e8ce79457d8d19693b6e5.tar.gz spark-e44274870dee308f4e3e8ce79457d8d19693b6e5.tar.bz2 spark-e44274870dee308f4e3e8ce79457d8d19693b6e5.zip |
[SPARK-17080][SQL] join reorder
## What changes were proposed in this pull request?
Reorder the joins using a dynamic programming algorithm (Selinger paper):
First we put all items (basic joined nodes) into level 1, then we build all two-way joins at level 2 from plans at level 1 (single items), then build all 3-way joins from plans at previous levels (two-way joins and single items), then 4-way joins ... etc, until we build all n-way joins and pick the best plan among them.
When building m-way joins, we only keep the best plan (with the lowest cost) for the same set of m items. E.g., for 3-way joins, we keep only the best plan for items {A, B, C} among plans (A J B) J C, (A J C) J B and (B J C) J A. Thus, the plans maintained for each level when reordering four items A, B, C, D are as follows:
```
level 1: p({A}), p({B}), p({C}), p({D})
level 2: p({A, B}), p({A, C}), p({A, D}), p({B, C}), p({B, D}), p({C, D})
level 3: p({A, B, C}), p({A, B, D}), p({A, C, D}), p({B, C, D})
level 4: p({A, B, C, D})
```
where p({A, B, C, D}) is the final output plan.
For cost evaluation, since physical costs for operators are not available currently, we use cardinalities and sizes to compute costs.
## How was this patch tested?
add test cases
Author: wangzhenhua <wangzhenhua@huawei.com>
Author: Zhenhua Wang <wzh_zju@163.com>
Closes #17138 from wzhfy/joinReorder.
Diffstat (limited to 'sql/hive')
0 files changed, 0 insertions, 0 deletions