Hello Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/22926
to look at the new patch set (#14).
Change subject: IMPALA-14574: Lower memory estimate by analyzing
PipelineMembership
......................................................................
IMPALA-14574: Lower memory estimate by analyzing PipelineMembership
IMPALA-7231 group PlanNodes into a set of PipelinesMembership. Rows
stream within single pipeline and accumulate at the end of pipeline,
before handed to the next pipeline. This end of pipeline is typically a
PlanRootSink or blocking operator (ie., SORT, Final AGG, or build side
of HASH JOIN).
This patch attempt to lower memory estimate by analyzing the
dependencies between adjacent GETNEXT and OPEN pipelines in query plan
tree. Fragments that belongs to GETNEXT pipeline is less likely to
consume all of its memory allotment until all OPEN pipelines that
adjacent to that GETNEXT pipeline finish.
First, we specify following definitions:
Fragment's Memory Growth is the difference between minimum memory
reservation and estimated peak memory usage in bytes.
Pipeline X(GETNEXT) is adjacent to Y(OPEN) if a PlanNode has
PipelineMembership in both X(GETNEXT) and Y(OPEN).
A memory growth estimate of a pipeline X is sum of memory estimate of
all fragments that have PipelineMembership X(GETNEXT) plus memory growth
estimate of all fragment that have PipelineMembership Y(OPEN) where
X(GETNEXT) is adjacent to Y(OPEN) and both X and Y originate from
different fragment.
Given pipeline X(GETNEXT) and all of its adjacent pipeline Y(OPEN),
a maximum memory growth estimate rooted at pipeline X is the maximum
between:
1). Memory growth estimate of a pipeline X.
2). Sum of all maximum memory growth estimate rooted at OPEN pipelines
adjacent to X.
The pipeline-based memory estimation algorithm works in following steps:
1. For each fragments, split its peak memory estimate to minMemEstimate
and memGrowth. minMemEstimate will still be summed up across all
query fragments to prevent underestimation.
2. Analyze PipelineMembership bottom-up, from the leaves up to
PlanRoot. At meeting point between GETNEXT and OPEN pipeline, update
the memory growth of GETNEXT pipeline, sum of maximum memory growth
rooted at all OPEN pipelines adjacent to the GETNEXT pipeline, and
maximum memory growth of plan tree so far.
3. The memory estimate of plan is the maximum memory growth of plan tree
after the tree traversal reach PlanRoot fragment, plus total
minMemEstimate, plus fixed memory requirement per backend
(ie., memory needed to consume global runtime filter).
Special care is needed in step 2 to avoid double counting. The cases
are:
- OPEN pipeline comes from leftmost child of fragment.
After adding memory growth of OPEN pipeline into memory growth of
GETNEXT pipeline, substract the portion of current fragment's memory
since it is counted in both OPEN and GETNEXT.
- A GETNEXT pipeline originate and ends fully within a fragment.
This most likely happen when a fragment contain multiple blocking
operator in single path. In this case, the memory growth of adjacent
OPEN pipeline is ignored.
- There are multiple GETNEXT pipeline exist in single PlanNode.
This can happens UNION node is present in query plan. If fragment has
parallel GETNEXT pipeline, divide that fragment's memory growth evenly
among those GETNEXT pipelines. They will be resolved at parent
fragment later when the pipelines turn into OPEN pipelines.
Added query option MEMORY_ESTIMATE_MODE to control which estimation
algorithm to use. The choices are:
- TOTAL, the simple sum of all fragment instances memory
resource (default).
- MAX_PIPELINE, the pipeline-based estimation implemented in this patch.
Planner will override MEMORY_ESTIMATE_MODE to TOTAL if there is exist a
table with missing/corrupt stats.
Testing:
- Enable MAX_PIPELINE option in TpcdsCpuCostPlannerTest and observe the
decreased in memory estimate of query.
- Add test in resource-requirements.test to validate
MEMORY_ESTIMATE_MODE override.
- Run perf-AB-test comparing TOTAL vs MAX_PIPELINE strategy over TPC-DS
scale 10. No major regression is observed.
Change-Id: Iba4f40993d8360bfdc1eb592a626e285dfed1627
---
M be/src/service/query-options.cc
M be/src/service/query-options.h
M common/thrift/ImpalaService.thrift
M common/thrift/Query.thrift
A fe/src/main/java/org/apache/impala/planner/PipelineBasedMemEstimator.java
M fe/src/main/java/org/apache/impala/planner/PlanFragment.java
M fe/src/main/java/org/apache/impala/planner/Planner.java
M fe/src/main/java/org/apache/impala/planner/ResourceProfile.java
M fe/src/test/java/org/apache/impala/planner/TpcdsCpuCostPlannerTest.java
M
testdata/workloads/functional-planner/queries/PlannerTest/resource-requirements.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q01.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q02.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q04.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q05.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q06.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q08.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q10a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q11.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q12.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q14a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q14b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q22.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q23a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q23b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q24a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q24b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q28.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q30.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q31.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q32.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q33.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q34.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q35a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q38.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q39a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q39b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q41.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q44.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q45.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q46.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q47.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q49.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q51.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q54.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q56.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q57.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q58.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q59.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q60.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q64-mem_limit-10g.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q64-mem_limit_executors-20g.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q64.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q65.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q66.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q68.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q69.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q70.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q71.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q73.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q74.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q75.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q76.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q77.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q78.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q79.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q80.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q81.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q83.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q87.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q88.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q90.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q91.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q92.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q95.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q97-mem_limit-10g.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q97-mem_limit_executors-20g.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q97.test
M
testdata/workloads/functional-planner/queries/PlannerTest/tpcds_cpu_cost/tpcds-q98.test
78 files changed, 1,109 insertions(+), 149 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/26/22926/14
--
To view, visit http://gerrit.cloudera.org:8080/22926
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Iba4f40993d8360bfdc1eb592a626e285dfed1627
Gerrit-Change-Number: 22926
Gerrit-PatchSet: 14
Gerrit-Owner: Riza Suminto <[email protected]>
Gerrit-Reviewer: Impala Public Jenkins <[email protected]>
Gerrit-Reviewer: Riza Suminto <[email protected]>
