Zoltán Borók-Nagy created IMPALA-15689:
------------------------------------------
Summary: MAX_NUM_RUNTIME_FILTERS keeps bloom filters by join
selectivity, so FK/PK estimates of 1.0 drop the most useful ones (TPC-DS q64
store_returns joins)
Key: IMPALA-15689
URL: https://issues.apache.org/jira/browse/IMPALA-15689
Project: IMPALA
Issue Type: Improvement
Components: Frontend
Reporter: Zoltán Borók-Nagy
Beyond MAX_NUM_RUNTIME_FILTERS bloom filters (default 10), the planner keeps
the lowest-selectivity ones and silently drops the rest
({{RuntimeFilterGenerator.java:943-969}}, master c580d36e61). Selectivity is
the source join's output/probe cardinality ratio
({{RuntimeFilterGenerator.java:1529-1535}}), not its effect on the target scan.
*TPC-DS q64 with CTE_THRESHOLD=1:* the store_returns joins are {{sr_item_sk =
i_item_sk, sr_ticket_number = ss_ticket_number}}. The FK/PK path ignores the
second conjunct ({{JoinNode.java:410-412}}), divides the build cardinality by
item's row count and caps the result at the probe cardinality
({{JoinNode.java:470,479}}). The build exceeds item's row count, so the
estimate is "no reduction". In master's expected plan
({{tpcds_cte/tpcds-q64.test}}), joins 37 and 73 have 3.11M build rows (item:
360K rows) and keep 863.99M of 863.99M probe rows. They keep their uncapped
min_max filters but lose their bloom filters (RF032/RF033, RF066/RF067); the
plan has exactly 10.
*Measured* (TPC-DS SF10000, 12 executors, MT_DOP=8, PLANNER=CALCITE,
CTE_THRESHOLD=1, best of 3, with pending planner changes): q64 takes 31.8 s.
Both store_returns scans return all 2.88B rows, shuffled into joins that output
431K and 433K rows: a 5.5 s phase that filters would cut to ~1.5 s (estimate).
MAX_NUM_RUNTIME_FILTERS=20 left q64 unchanged in an earlier run (38.7 vs 39.4
s), but in master's plan the store_returns filters rank 28th-38th of 40 bloom
filters.
Without CTEs (master, legacy planner, 103.9 s), these joins use store_sales'
key and their filters cut store_returns to 84.33M and 81.22M rows. The cap
binds there too: in both planners, two of the 10 slots go to
catalog_sales/catalog_returns filters that reject 0 rows.
*Proposal:*
* Rank filters by expected rows removed at their targets, e.g. target
cardinality x (1 - build-key NDV / target NDV).
* In the FK/PK estimate, use the build-side NDV of the PK column when the build
exceeds the PK table's rows.
* List dropped filters in EXPLAIN.
* Then revisit the default of 10.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
