Taras Bobrovytsky has uploaded a new patch set (#5).
Change subject: IMPALA-4787: Optimize APPX_MEDIAN() memory usage
......................................................................
IMPALA-4787: Optimize APPX_MEDIAN() memory usage
Before this change, ReservoirSample functions (such as APPX_MEDIAN())
allocated memory for 20,000 elements up front per grouping key. This
caused inefficient memory usage for aggregations with many grouping
keys.
This patch fixes this by initially allocating memory for 16 elements.
Once the buffer becomes full, we reallocate a new buffer with double
capacity and copy the original buffer into the new one. We continue
doubling the buffer size until the buffer has room for 20,000 elements
as before.
Testing:
Ran BE and some relevant EE tests locally.
No new tests were added, the existing tests should provide enough
coverage.
Performance benchmark:
I ran a performance benchmark locally on release build. The following
query results in 3,000 grouping keys and about 30,000 values per key:
SELECT MAX(a) from (
SELECT c1, appx_median(c2) as a FROM benchmark GROUP BY c1) t
Before: 11.57s
Operator #Hosts Avg Time Max Time #Rows Est. #Rows Peak Mem Est.
Peak Mem Detail
-------------------------------------------------------------------------------------------------------------------------
06:AGGREGATE 1 96.086us 96.086us 1 1 28.00 KB
-1.00 B FINALIZE
05:EXCHANGE 1 26.629us 26.629us 3 1 0
-1.00 B UNPARTITIONED
02:AGGREGATE 3 68.187us 87.887us 3 1 44.00 KB
10.00 MB
04:AGGREGATE 3 2s851ms 5s362ms 3.00K -1 1.95 GB
128.00 MB FINALIZE
03:EXCHANGE 3 119.540ms 220.191ms 9.00K -1 0
0 HASH(c1)
01:AGGREGATE 3 5s876ms 6s254ms 9.00K -1 2.93 GB
128.00 MB STREAMING
00:SCAN HDFS 3 127.834ms 146.842ms 98.30M -1 19.80 MB
32.00 MB tpcds_10_parquet.benchmark
After: 13.58s
Operator #Hosts Avg Time Max Time #Rows Est. #Rows Peak Mem Est.
Peak Mem Detail
-----------------------------------------------------------------------------------------------------------------------
06:AGGREGATE 1 101.101us 101.101us 1 1 28.00 KB
-1.00 B FINALIZE
05:EXCHANGE 1 32.296us 32.296us 3 1 0
-1.00 B UNPARTITIONED
02:AGGREGATE 3 83.284us 120.137us 3 1 44.00 KB
10.00 MB
04:AGGREGATE 3 3s190ms 6s555ms 3.00K -1 1.96 GB
128.00 MB FINALIZE
03:EXCHANGE 3 247.897ms 497.280ms 9.00K -1 0
0 HASH(c1)
01:AGGREGATE 3 7s370ms 8s460ms 9.00K -1 4.71 GB
128.00 MB STREAMING
00:SCAN HDFS 3 111.721ms 122.306ms 98.30M -1 19.94 MB
32.00 MB tpcds_10_parquet.benchmark
Memory benchmark:
The following query was used to verify that this patch reduces memory
usage:
SELECT APPX_MEDIAN(ss_sold_date_sk)
FROM tpcds.store_sales
GROUP BY ss_customer_sk;
Peak Mem in Agg nodes is reduced from 4.94 GB to 19.82 MB.
Summary before:
Operator #Hosts Avg Time Max Time #Rows Est. #Rows Peak Mem
Est. Peak Mem Detail
----------------------------------------------------------------------------------------------------------------
04:EXCHANGE 1 5.856ms 5.856ms 14.82K 15.21K 0
-1.00 B UNPARTITIONED
03:AGGREGATE 3 3s721ms 3s789ms 14.82K 15.21K 4.94 GB
10.00 MB FINALIZE
02:EXCHANGE 3 139.276ms 157.753ms 15.60K 15.21K 0
0 HASH(ss_customer_sk)
01:AGGREGATE 3 2s851ms 3s026ms 15.60K 15.21K 5.29 GB
10.00 MB STREAMING
00:SCAN HDFS 3 24.245ms 35.727ms 183.59K 183.59K 4.60 MB
384.00 MB tpcds.store_sales
Summary after:
Operator #Hosts Avg Time Max Time #Rows Est. #Rows Peak Mem
Est. Peak Mem Detail
----------------------------------------------------------------------------------------------------------------
04:EXCHANGE 1 288.125us 288.125us 14.82K 15.21K 0
-1.00 B UNPARTITIONED
03:AGGREGATE 3 9.358ms 10.982ms 14.82K 15.21K 19.82 MB
10.00 MB FINALIZE
02:EXCHANGE 3 129.832us 154.953us 15.62K 15.21K 0
0 HASH(ss_customer_sk)
01:AGGREGATE 3 11.086ms 13.102ms 15.62K 15.21K 9.49 MB
10.00 MB STREAMING
00:SCAN HDFS 3 40.154ms 50.220ms 183.59K 183.59K 2.94 MB
384.00 MB tpcds.store_sales
Change-Id: I99adaad574d4fb0a3cf38c6cbad8b2a23df12968
---
M be/src/exprs/aggregate-functions-ir.cc
M testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test
2 files changed, 147 insertions(+), 34 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/25/6025/5
--
To view, visit http://gerrit.cloudera.org:8080/6025
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I99adaad574d4fb0a3cf38c6cbad8b2a23df12968
Gerrit-PatchSet: 5
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Taras Bobrovytsky <[email protected]>
Gerrit-Reviewer: Alex Behm <[email protected]>
Gerrit-Reviewer: Marcel Kornacker <[email protected]>
Gerrit-Reviewer: Matthew Jacobs <[email protected]>
Gerrit-Reviewer: Mostafa Mokhtar <[email protected]>
Gerrit-Reviewer: Taras Bobrovytsky <[email protected]>
