impala-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Taras Bobrovytsky (Code Review)" <ger...@cloudera.org>
Subject [Impala-ASF-CR] IMPALA-4787: Optimize APPX MEDIAN() memory usage
Date Mon, 27 Feb 2017 21:34:10 GMT
Taras Bobrovytsky has uploaded a new patch set (#10).

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:
Added some EE APPX_MEDIAN() tests on larger datasets that excercise the
resize code path.

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/aggregation.test
M testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test
3 files changed, 201 insertions(+), 60 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/25/6025/10
-- 
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: 10
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Taras Bobrovytsky <tbobrovytsky@cloudera.com>
Gerrit-Reviewer: Alex Behm <alex.behm@cloudera.com>
Gerrit-Reviewer: Jim Apple <jbapple-impala@apache.org>
Gerrit-Reviewer: Marcel Kornacker <marcel@cloudera.com>
Gerrit-Reviewer: Matthew Jacobs <mj@cloudera.com>
Gerrit-Reviewer: Mostafa Mokhtar <mmokhtar@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tbobrovytsky@cloudera.com>

Mime
View raw message