You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@hive.apache.org by "Ning Zhang (JIRA)" <ji...@apache.org> on 2009/12/29 02:10:29 UTC
[jira] Created: (HIVE-1018) pushing down group-by before joins
pushing down group-by before joins
----------------------------------
Key: HIVE-1018
URL: https://issues.apache.org/jira/browse/HIVE-1018
Project: Hadoop Hive
Issue Type: Improvement
Reporter: Ning Zhang
Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
Examples:
-- Q1
select A.key, B.key
from A join B on (A.key=B.key)
group by A.key, B.key;
--Q2
select distinct A.key, B.key
from A join B on (A.key=B.key);
--Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
selec A.key, sum(A.value), count(1), min(value), max(value)
from A left semi join B on (A.key=B.key)
group by A.key;
-- Q4. grouping keys is a superset of join keys
select distinct A.key, A.value
from A join B on (A.key=B.key)
In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HIVE-1018) pushing down group-by before joins
Posted by "Namit Jain (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HIVE-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12901637#action_12901637 ]
Namit Jain commented on HIVE-1018:
----------------------------------
I think a immediate use case is to convert the following job:
select /*+ MAPJOIN(T2) */ count(1) from T1 join T2 on T1.x=T2.y;
into a single MR job, if T2 is small.
> pushing down group-by before joins
> ----------------------------------
>
> Key: HIVE-1018
> URL: https://issues.apache.org/jira/browse/HIVE-1018
> Project: Hadoop Hive
> Issue Type: Improvement
> Reporter: Ning Zhang
>
> Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
> A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
> Examples:
> -- Q1
> select A.key, B.key
> from A join B on (A.key=B.key)
> group by A.key, B.key;
> --Q2
> select distinct A.key, B.key
> from A join B on (A.key=B.key);
> --Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
> selec A.key, sum(A.value), count(1), min(value), max(value)
> from A left semi join B on (A.key=B.key)
> group by A.key;
> -- Q4. grouping keys is a superset of join keys
> select distinct A.key, A.value
> from A join B on (A.key=B.key)
> In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
> Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HIVE-1018) pushing down group-by before joins
Posted by "Ning Zhang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HIVE-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12795098#action_12795098 ]
Ning Zhang commented on HIVE-1018:
----------------------------------
Thanks for the link Yongqiang. The paper mostly discusses the optimization of extending join tree with group by and deciding how to order the join-groupby tree. Since we don't have stats and costing framework available, and we handle multiway joins rather than binary joins, join ordering is not the major issue. The only optimization part is whether do groupby first or join first. As the first step, we can implement a hint to pushdown grouping operator first.
> pushing down group-by before joins
> ----------------------------------
>
> Key: HIVE-1018
> URL: https://issues.apache.org/jira/browse/HIVE-1018
> Project: Hadoop Hive
> Issue Type: Improvement
> Reporter: Ning Zhang
>
> Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
> A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
> Examples:
> -- Q1
> select A.key, B.key
> from A join B on (A.key=B.key)
> group by A.key, B.key;
> --Q2
> select distinct A.key, B.key
> from A join B on (A.key=B.key);
> --Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
> selec A.key, sum(A.value), count(1), min(value), max(value)
> from A left semi join B on (A.key=B.key)
> group by A.key;
> -- Q4. grouping keys is a superset of join keys
> select distinct A.key, A.value
> from A join B on (A.key=B.key)
> In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
> Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HIVE-1018) pushing down group-by before joins
Posted by "He Yongqiang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HIVE-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12794993#action_12794993 ]
He Yongqiang commented on HIVE-1018:
------------------------------------
there is one paper "Including Group-By in Query Optimization" defining some rules of when "groupby pushing down" can be applied.
> pushing down group-by before joins
> ----------------------------------
>
> Key: HIVE-1018
> URL: https://issues.apache.org/jira/browse/HIVE-1018
> Project: Hadoop Hive
> Issue Type: Improvement
> Reporter: Ning Zhang
>
> Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
> A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
> Examples:
> -- Q1
> select A.key, B.key
> from A join B on (A.key=B.key)
> group by A.key, B.key;
> --Q2
> select distinct A.key, B.key
> from A join B on (A.key=B.key);
> --Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
> selec A.key, sum(A.value), count(1), min(value), max(value)
> from A left semi join B on (A.key=B.key)
> group by A.key;
> -- Q4. grouping keys is a superset of join keys
> select distinct A.key, A.value
> from A join B on (A.key=B.key)
> In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
> Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HIVE-1018) pushing down group-by before joins
Posted by "Joydeep Sen Sarma (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HIVE-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12881597#action_12881597 ]
Joydeep Sen Sarma commented on HIVE-1018:
-----------------------------------------
interesting idea. in most of the queries i have written (over the course of last few months - this has involved a *lot* of joins and group-bys) - either the aggregate expressions or the group by clause would have a combination of columns from all tables being joined. these would be fairly hard to optimize based on the ideas outlined here.
in most of the join+group-by cases i see - people are joining fact with dimension and then using the at least some non-join columns of the dimension for grouping (typically along with some columns from fact). the join/grouping columns being equal/superset seems interesting - but i am not sure about practical applicability.
even in the cases mentioned - some alternate trivial but effective optimizations are available:
1. join key=grouping key - grouping operator should realize that data is already sorted/clustered by grouping key (because it was joined on the same key). in this case we don't need partial aggregates - but can generate full aggregates off the output of the join. no hash maps required.
2. join key = subset of grouping keys - in this case (for sort merge join) - we can sort on the grouping keys (doesn't hurt much) for doing the join and then apply strategy #1.
> pushing down group-by before joins
> ----------------------------------
>
> Key: HIVE-1018
> URL: https://issues.apache.org/jira/browse/HIVE-1018
> Project: Hadoop Hive
> Issue Type: Improvement
> Reporter: Ning Zhang
>
> Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
> A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
> Examples:
> -- Q1
> select A.key, B.key
> from A join B on (A.key=B.key)
> group by A.key, B.key;
> --Q2
> select distinct A.key, B.key
> from A join B on (A.key=B.key);
> --Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
> selec A.key, sum(A.value), count(1), min(value), max(value)
> from A left semi join B on (A.key=B.key)
> group by A.key;
> -- Q4. grouping keys is a superset of join keys
> select distinct A.key, A.value
> from A join B on (A.key=B.key)
> In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
> Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HIVE-1018) pushing down group-by before joins
Posted by "Ning Zhang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HIVE-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12881758#action_12881758 ]
Ning Zhang commented on HIVE-1018:
----------------------------------
Good points Joy. It will be interesting to see what are the typical use cases you have combining join and GroupBy. Previous what in my mind here is to optimize away the very bad case of skewness in the join (many rows with the same join key). Since GroupBy eliminates the skewness, these rewrite rules push down GroupBy before JOIN for these special cases. What you have mentioned are definitely what we should optimize for these cases. The are helpful for the general cases (non-skewed join) as well.
> pushing down group-by before joins
> ----------------------------------
>
> Key: HIVE-1018
> URL: https://issues.apache.org/jira/browse/HIVE-1018
> Project: Hadoop Hive
> Issue Type: Improvement
> Reporter: Ning Zhang
>
> Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
> A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
> Examples:
> -- Q1
> select A.key, B.key
> from A join B on (A.key=B.key)
> group by A.key, B.key;
> --Q2
> select distinct A.key, B.key
> from A join B on (A.key=B.key);
> --Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
> selec A.key, sum(A.value), count(1), min(value), max(value)
> from A left semi join B on (A.key=B.key)
> group by A.key;
> -- Q4. grouping keys is a superset of join keys
> select distinct A.key, A.value
> from A join B on (A.key=B.key)
> In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
> Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HIVE-1018) pushing down group-by before joins
Posted by "He Yongqiang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HIVE-1018?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12794995#action_12794995 ]
He Yongqiang commented on HIVE-1018:
------------------------------------
For some situations( for example, join keys equal to group by keys), it maybe better if we can add a groupby op under join in reducer side. That way, we only need to scan the table one time.
> pushing down group-by before joins
> ----------------------------------
>
> Key: HIVE-1018
> URL: https://issues.apache.org/jira/browse/HIVE-1018
> Project: Hadoop Hive
> Issue Type: Improvement
> Reporter: Ning Zhang
>
> Queries with both Group-by and Joins are very common and they are expensive operations. By default Hive evalutes Joins first then group-by. Sometimes it is possible to rewrite queries to apply group-by (or map-side partial group by) first before join. This will remove a lot of duplicated keys in joins and alleviate skewness in join keys for this case. This rewrite should be cost-based. Before we have the stats and the CB framework, we can give users hints to do the rewrite.
> A particular case is where the join keys are the same as the grouping keys. Or the group keys is a superset of the join keys (so that grouping won't affect the result of joins).
> Examples:
> -- Q1
> select A.key, B.key
> from A join B on (A.key=B.key)
> group by A.key, B.key;
> --Q2
> select distinct A.key, B.key
> from A join B on (A.key=B.key);
> --Q3, aggregation function is sum, count, min, max, (avg and median cannot be handled).
> selec A.key, sum(A.value), count(1), min(value), max(value)
> from A left semi join B on (A.key=B.key)
> group by A.key;
> -- Q4. grouping keys is a superset of join keys
> select distinct A.key, A.value
> from A join B on (A.key=B.key)
> In the case of join keys are not a subset of grouping keys, we can introduce a map-side partial grouping operator with the keys of the UNION of the join and grouping keys, to remove unnecessary duplications. This should be cost-based though.
> Any thoughts and suggestions?
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.