You are viewing a plain text version of this content. The canonical link for it is here.
Posted to gitbox@hive.apache.org by GitBox <gi...@apache.org> on 2022/04/28 08:39:27 UTC
[GitHub] [hive] okumin opened a new pull request, #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
okumin opened a new pull request, #3253:
URL: https://github.com/apache/hive/pull/3253
### What changes were proposed in this pull request?
This would reduce the time complexity of `COLLECT_SET` from `O({maximum length} * {num rows})` into `O({maximum length} + {num rows})`.
https://issues.apache.org/jira/browse/HIVE-26184
### Why are the changes needed?
I'm observing some reducers take much time due to this issue.
### Does this PR introduce _any_ user-facing change?
No
### How was this patch tested?
I have run the reproduction case in HIVE-26184 with this patch and confirmed the reduce vertex finished more than 30x faster.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] okumin commented on a diff in pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
okumin commented on code in PR #3253:
URL: https://github.com/apache/hive/pull/3253#discussion_r864445686
##########
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFMkCollectionEvaluator.java:
##########
@@ -95,11 +95,27 @@ public MkArrayAggregationBuffer() {
throw new RuntimeException("Buffer type unknown");
}
}
+
+ private void reset() {
+ if (bufferType == BufferType.LIST) {
+ container.clear();
Review Comment:
@dengzhhu653 The short answer is no.
`ArrayList#clear` takes `O({the number of elements, not capacity})`. Actually, I don't reproduce the same issue with `COLLECT_LIST` at least in our environment. This is a dummy code to illustrate the behavior of `ArrayList#clear`. Even if the length of `elementsContainer` is 1 million, it only updates the first `ArrayList#size`.
```
// elementsContainer is Object[] with its length enlarged based on the maximum ArrayList#size so far
// Note that this.size is ArrayList#size, not the length of elementsContainer
for (int i = 0; i < this.size; i++) {
elementsContainer[i] = null;
}
```
In case of HashMap, the complexity depends on its capacity. That's because `clear` doesn't know which indexes have values because of hash table's nature.
```
// table is Node[] with its length enlarged based on the maximum HashMap#size so far
// Note that table.length is not HashMap#size
for (int i = 0; i < table.length; i++) {
table[i] = null;
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] okumin commented on pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
okumin commented on PR #3253:
URL: https://github.com/apache/hive/pull/3253#issuecomment-1120663054
CI failed but I think it's not apparently caused by this PR.
```
[2022-05-08T14:33:40.267Z] [ERROR] Failures:
[2022-05-08T14:33:40.267Z] [ERROR] TestRpc.testServerPort:234 Port should match configured one:22 expected:<32951> but was:<22>
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] kgyrtkirk commented on a diff in pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
kgyrtkirk commented on code in PR #3253:
URL: https://github.com/apache/hive/pull/3253#discussion_r860749534
##########
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFMkCollectionEvaluator.java:
##########
@@ -95,11 +95,27 @@ public MkArrayAggregationBuffer() {
throw new RuntimeException("Buffer type unknown");
}
}
+
+ private void reset() {
+ if (bufferType == BufferType.LIST) {
+ container.clear();
+ } else if (bufferType == BufferType.SET) {
+ // Don't reuse a container because HashSet#clear can be very slow. The operation takes O(N)
Review Comment:
why did the entries got skewed in the firstplace? don't we miss or have incorrect implementation of some `hashCode()` method?
could you please add a testcase which reproduces the issue?
maybe you could probably write a test against the UDF itself..
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] okumin commented on a diff in pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
okumin commented on code in PR #3253:
URL: https://github.com/apache/hive/pull/3253#discussion_r860788021
##########
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFMkCollectionEvaluator.java:
##########
@@ -95,11 +95,27 @@ public MkArrayAggregationBuffer() {
throw new RuntimeException("Buffer type unknown");
}
}
+
+ private void reset() {
+ if (bufferType == BufferType.LIST) {
+ container.clear();
+ } else if (bufferType == BufferType.SET) {
+ // Don't reuse a container because HashSet#clear can be very slow. The operation takes O(N)
Review Comment:
@kgyrtkirk Thanks for your quick review!
I wanted to mean skew of GROUP BY keys here, not elements of HashSet. Let me illustrate that with the following query, mapping articles into their comments. If a certain article accidentally gets very popular, it has much more comments than the others. My `skew` means such situation.
```
SELECT article_id, COLLECT_SET(comment) FROM comments GROUP BY article_id
```
The capacity of the internal hash table of `MkArrayAggregationBuffer#container` will eventually grow as much as it can retain all comments tied to the most skewed article so far. Also, the internal hash table will never get smaller because resizing happens only when new entries are added(precisely, this point depends on the implementation of JDK).
From the nature of hash tables, the duration of `HashSet#clear` relies on the capacity of an internal hash table. It's an operation to fill all cells with NULLs.
Because of the two points, GroupByOperator suddenly slows down once it processes a skewed key. For example, assuming the first `article_id=1` has 1,000,000 comments, `GenericUDAFMkCollectionEvaluator#reset` has to fill a very big hash table with many NULLs every time even if all following articles have 0 comments.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] dengzhhu653 commented on a diff in pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
dengzhhu653 commented on code in PR #3253:
URL: https://github.com/apache/hive/pull/3253#discussion_r864405523
##########
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFMkCollectionEvaluator.java:
##########
@@ -95,11 +95,27 @@ public MkArrayAggregationBuffer() {
throw new RuntimeException("Buffer type unknown");
}
}
+
+ private void reset() {
+ if (bufferType == BufferType.LIST) {
+ container.clear();
Review Comment:
If I understand it, the `clear()` of ArrayList should have the same problem, right?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] kgyrtkirk merged pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
kgyrtkirk merged PR #3253:
URL: https://github.com/apache/hive/pull/3253
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] okumin commented on a diff in pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
okumin commented on code in PR #3253:
URL: https://github.com/apache/hive/pull/3253#discussion_r860788021
##########
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFMkCollectionEvaluator.java:
##########
@@ -95,11 +95,27 @@ public MkArrayAggregationBuffer() {
throw new RuntimeException("Buffer type unknown");
}
}
+
+ private void reset() {
+ if (bufferType == BufferType.LIST) {
+ container.clear();
+ } else if (bufferType == BufferType.SET) {
+ // Don't reuse a container because HashSet#clear can be very slow. The operation takes O(N)
Review Comment:
@kgyrtkirk Thanks for your quick review!
I wanted to mean skew of GROUP BY keys here, not elements of HashSet. Let me illustrate that with the following query, mapping articles into their comments. If a certain article accidentally gets very popular, it has much more comments than the others. My `skew` means such situation.
```
SELECT article_id, COLLECT_SET(comment) FROM comments GROUP BY article_id
```
The capacity of the internal hash table of `MkArrayAggregationBuffer#container` will eventually grow as much as it can retain all comments tied to the most skewed article so far. Also, the internal hash table will never get smaller because resizing happens only when new entries are added(precisely, this point depends on the implementation of JDK).
From the nature of hash tables, the duration of `HashSet#clear` relies on the capacity of an internal hash table. It's an operation to fill all cells with NULLs.
Because of the two points, GroupByOperator suddenly slows down once it processes a skewed key. For example, assuming the first `article_id=1` has 1,000,000 comments, `GenericUDAFMkCollectionEvaluator#reset` has to fill a very big hash table with many NULLs every time even if all following articles(`article_id=2`, `article_id=3`, ...) have 0 comments.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] dengzhhu653 commented on a diff in pull request #3253: HIVE-26184: COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
Posted by GitBox <gi...@apache.org>.
dengzhhu653 commented on code in PR #3253:
URL: https://github.com/apache/hive/pull/3253#discussion_r864458003
##########
ql/src/java/org/apache/hadoop/hive/ql/udf/generic/GenericUDAFMkCollectionEvaluator.java:
##########
@@ -95,11 +95,27 @@ public MkArrayAggregationBuffer() {
throw new RuntimeException("Buffer type unknown");
}
}
+
+ private void reset() {
+ if (bufferType == BufferType.LIST) {
+ container.clear();
Review Comment:
get it, thanks for the explanation!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org