[
https://issues.apache.org/jira/browse/HIVE-26184?focusedWorklogId=765818&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-765818
]
ASF GitHub Bot logged work on HIVE-26184:
-----------------------------------------
Author: ASF GitHub Bot
Created on: 04/May/22 04:18
Start Date: 04/May/22 04:18
Worklog Time Spent: 10m
Work Description: 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;
}
```
Issue Time Tracking
-------------------
Worklog Id: (was: 765818)
Time Spent: 1h (was: 50m)
> COLLECT_SET with GROUP BY is very slow when some keys are highly skewed
> -----------------------------------------------------------------------
>
> Key: HIVE-26184
> URL: https://issues.apache.org/jira/browse/HIVE-26184
> Project: Hive
> Issue Type: Bug
> Components: Hive
> Affects Versions: 2.3.8, 3.1.3
> Reporter: okumin
> Assignee: okumin
> Priority: Major
> Labels: pull-request-available
> Time Spent: 1h
> Remaining Estimate: 0h
>
> I observed some reducers spend 98% of CPU time in invoking
> `java.util.HashMap#clear`.
> Looking the detail, I found COLLECT_SET reuses a LinkedHashSet and its
> `clear` can be quite heavy when a relation has a small number of highly
> skewed keys.
>
> To reproduce the issue, first, we will create rows with a skewed key.
> {code:java}
> INSERT INTO test_collect_set
> SELECT '00000000-0000-0000-0000-000000000000' AS key, CAST(UUID() AS VARCHAR)
> AS value
> FROM table_with_many_rows
> LIMIT 100000;{code}
> Then, we will create many non-skewed rows.
> {code:java}
> INSERT INTO test_collect_set
> SELECT UUID() AS key, UUID() AS value
> FROM table_with_many_rows
> LIMIT 5000000;{code}
> We can observe the issue when we aggregate values by `key`.
> {code:java}
> SELECT key, COLLECT_SET(value) FROM group_by_skew GROUP BY key{code}
--
This message was sent by Atlassian Jira
(v8.20.7#820007)
