Hello Qifan Chen, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/18141
to look at the new patch set (#10).
Change subject: WIP IMPALA-10898: Add runtime IN-list filters for ORC tables
......................................................................
WIP IMPALA-10898: Add runtime IN-list filters for ORC tables
ORC files have optional bloom filter indexes for each column. Since
ORC-1.7.0, the C++ reader supports pushing down predicates to skip
unreleated RowGroups. The pushed down predicates will be evaludated on
file indexes (i.e. statistics and bloom filter indexes). Note that only
EQUALS and IN-list predicates can leverage bloom filter indexes.
Currently Impala has two kinds of runtime filters: bloom filter and
min-max filter. Unfortunately they can't be converted into EQUALS or
IN-list predicates. So they can't leverage the file level bloom filter
indexes.
This patch adds runtime IN-list filters for this purpose. Currently they
are generated only for small build side (e.g. #rows <= 1024) of a
broadcast join. They will only be applied on ORC tables and be pushed
down to the ORC reader(i.e. ORC lib). To avoid exploding the IN-list,
if #rows of the build side exceeds the threshold (1024), we set the
filter to ALWAYS_TRUE. The threshold can be configured by a new query
option, RUNTIME_IN_LIST_FILTER_ENTRY_LIMIT.
Example query that will benefit from this patch:
use tpch_orc_def;
select count(*) from lineitem_bf join (
select * from partsupp, part
where ps_partkey = p_partkey and p_size = 15
and p_type like '%BRASS' and ps_availqty < 10) v
on l_partkey = ps_partkey and l_suppkey = ps_suppkey;
The inline-view populates a runtime IN-list filter with 4 items. Note that
we need to re-generate the lineitem table with bloom filter indexes enabled
(e.g. setting orc.bloom.filter.columns to
"l_orderkey,l_partkey,l_suppkey,l_linenumber,l_quantity" in
tblproperties before inserting the data), so the runtime IN-list filter
can have a better filter rate.
Evaluating runtime IN-list filters is much slower than evaluating
runtime bloom filters due to the current simple implementation (i.e.
std::unorder_set). So we disable it at row level.
For visibility, this patch addes two counters in the HdfsScanNode:
- NumPushedDownPredicates
- NumPushedDownRuntimeFilters
They reflect the predicates and runtime filters that are pushed down to
the ORC reader.
Ran perf tests on a 3 instances cluster on my desktop using TPC-DS with
scale factor 20. It shows significant improvements in some queries:
+-----------+-------------+--------------------+--------+-------------+------------+------------+----------------+-------+----------------+---------+--------+
| Workload | Query | File Format | Avg(s) | Base Avg(s) |
Delta(Avg) | StdDev(%) | Base StdDev(%) | Iters | Median Diff(%) | MW Zval |
Tval |
+-----------+-------------+--------------------+--------+-------------+------------+------------+----------------+-------+----------------+---------+--------+
| TPCDS(20) | TPCDS-Q67A | orc / snap / block | 35.07 | 44.01 | I
-20.32% | 0.38% | 1.38% | 10 | I -25.69% | -3.58 |
-45.33 |
| TPCDS(20) | TPCDS-Q37 | orc / snap / block | 1.08 | 1.45 | I
-25.23% | 7.14% | 3.09% | 10 | I -34.09% | -3.58 |
-12.94 |
| TPCDS(20) | TPCDS-Q70A | orc / snap / block | 6.30 | 8.60 | I
-26.81% | 5.24% | 4.21% | 10 | I -36.67% | -3.58 |
-14.88 |
| TPCDS(20) | TPCDS-Q16 | orc / snap / block | 1.33 | 1.85 | I
-28.28% | 4.98% | 5.92% | 10 | I -39.38% | -3.58 |
-12.93 |
| TPCDS(20) | TPCDS-Q18A | orc / snap / block | 5.70 | 8.06 | I
-29.25% | 3.00% | 4.12% | 10 | I -40.30% | -3.58 |
-19.95 |
| TPCDS(20) | TPCDS-Q22A | orc / snap / block | 2.01 | 2.97 | I
-32.21% | 6.12% | 5.94% | 10 | I -47.68% | -3.58 |
-14.05 |
| TPCDS(20) | TPCDS-Q77A | orc / snap / block | 8.49 | 12.44 | I
-31.75% | 6.44% | 3.96% | 10 | I -49.71% | -3.58 |
-16.97 |
| TPCDS(20) | TPCDS-Q75 | orc / snap / block | 7.76 | 12.27 | I
-36.76% | 5.01% | 3.87% | 10 | I -59.56% | -3.58 |
-23.26 |
| TPCDS(20) | TPCDS-Q21 | orc / snap / block | 0.71 | 1.27 | I
-44.26% | 4.56% | 4.24% | 10 | I -77.31% | -3.58 |
-28.31 |
| TPCDS(20) | TPCDS-Q80A | orc / snap / block | 9.24 | 20.42 | I
-54.77% | 4.03% | 3.82% | 10 | I -123.12% | -3.58 |
-40.90 |
| TPCDS(20) | TPCDS-Q39-1 | orc / snap / block | 1.07 | 2.26 | I
-52.74% | * 23.83% * | 2.60% | 10 | I -149.68% | -3.58 |
-14.43 |
| TPCDS(20) | TPCDS-Q39-2 | orc / snap / block | 1.00 | 2.33 | I
-56.95% | * 19.53% * | 2.07% | 10 | I -151.89% | -3.58 |
-20.81 |
+-----------+-------------+--------------------+--------+-------------+------------+------------+----------------+-------+----------------+---------+--------+
"Base Avg" is the avg of the original time. "Avg" is the current time.
However, we also see some regressions due to the suboptimal
implementation. The follow-up JIRAs will focus on improvements:
- IMPALA-xxxxx: Codegen InListFilter::Insert() and InListFilter::Find()
- IMPALA-xxxxx: Use exact data types in IN-list filters instead of
casting data to a set of int64_t or a set of string.
- IMPALA-xxxxx: Consider IN-list filters in partitioned joins.
Currently, runtime IN-list filters are disabled by default. This patch
extends the query option, ENABLED_RUNTIME_FILTER_TYPES, to support a
comma separated list of filter types. It defaults to be "BLOOM,MIN_MAX".
Add "IN_LIST" in it to enable runtime IN-list filters.
Tests:
- TODO: Test IN-list filter with NULLs
- TODO: Test IN-list filter on complex exprs targets
- TODO: Test IN-list filter on all types including DATE
Change-Id: I25080628233799aa0b6be18d5a832f1385414501
---
M be/src/codegen/gen_ir_descriptions.py
M be/src/codegen/impala-ir.cc
M be/src/exec/filter-context.cc
M be/src/exec/filter-context.h
M be/src/exec/hdfs-orc-scanner.cc
M be/src/exec/hdfs-orc-scanner.h
M be/src/exec/hdfs-scanner-ir.cc
M be/src/exec/join-builder.cc
M be/src/exec/nested-loop-join-builder.h
M be/src/exec/orc-metadata-utils.cc
M be/src/exec/partitioned-hash-join-builder.cc
M be/src/exec/partitioned-hash-join-builder.h
M be/src/exec/scan-node.cc
M be/src/runtime/coordinator-filter-state.h
M be/src/runtime/coordinator.cc
M be/src/runtime/runtime-filter-bank.cc
M be/src/runtime/runtime-filter-bank.h
M be/src/runtime/runtime-filter-ir.cc
M be/src/runtime/runtime-filter-test.cc
M be/src/runtime/runtime-filter.cc
M be/src/runtime/runtime-filter.h
M be/src/runtime/runtime-filter.inline.h
M be/src/service/child-query.cc
M be/src/service/data-stream-service.cc
M be/src/service/query-options-test.cc
M be/src/service/query-options.cc
M be/src/service/query-options.h
M be/src/util/CMakeLists.txt
M be/src/util/debug-util.cc
M be/src/util/debug-util.h
A be/src/util/in-list-filter-ir.cc
A be/src/util/in-list-filter.cc
A be/src/util/in-list-filter.h
M common/protobuf/data_stream_service.proto
M common/thrift/ImpalaService.thrift
M common/thrift/PlanNodes.thrift
M common/thrift/Query.thrift
M fe/src/main/java/org/apache/impala/planner/RuntimeFilterGenerator.java
M fe/src/test/java/org/apache/impala/planner/PlannerTest.java
M tests/query_test/test_runtime_filters.py
40 files changed, 1,017 insertions(+), 208 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/41/18141/10
--
To view, visit http://gerrit.cloudera.org:8080/18141
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I25080628233799aa0b6be18d5a832f1385414501
Gerrit-Change-Number: 18141
Gerrit-PatchSet: 10
Gerrit-Owner: Quanlong Huang <[email protected]>
Gerrit-Reviewer: Impala Public Jenkins <[email protected]>
Gerrit-Reviewer: Qifan Chen <[email protected]>
Gerrit-Reviewer: Quanlong Huang <[email protected]>
