Zoltán Borók-Nagy created IMPALA-15653:
------------------------------------------
Summary: Bloom runtime filters of large builds saturate at
RUNTIME_FILTER_MAX_SIZE (16 MB); size them from the actual build
Key: IMPALA-15653
URL: https://issues.apache.org/jira/browse/IMPALA-15653
Project: IMPALA
Issue Type: Improvement
Components: Backend
Reporter: Zoltán Borók-Nagy
The planner sizes bloom runtime filters from NDV estimates and caps them at
RUNTIME_FILTER_MAX_SIZE, 16 MB by default (RuntimeFilterGenerator.java:762-773
and 793-818, master 15cc045e2d). Producers allocate that size; merges require
equal sizes (bloom-filter.cc:138-145).
*Example: TPC-DS q93 at SF10000 (12 executors, MT_DOP=8, PLANNER=CALCITE, best
of 3).* RF003 (ss_ticket_number <- sr_ticket_number) saturates with 39.7M keys:
3.4 bits per key, fpp 0.46. About 1.7% of store_sales rows match, but 13.4B of
28.6B checked rows pass. q93 sends 367 GB over the network. The planner expects
2.78G build rows, because another runtime filter cuts store_returns.
*Measured effect:*
* RUNTIME_FILTER_MAX_SIZE=64MB: q93 38.9 -> 17.1 s, q50 21.6 -> 18.5 s. But 7
short queries with unchanged plans lose 7.9 s in total (a same-session A/B
confirms). E.g. q25 plans 64 MB for 26.8K actual build rows.
* 68 of 72 capped partitioned-join filters have estimated fpp above 0.1; the
planner cannot tell q93 from q25. A prototype planner rule only matched plain
64 MB (1244.3 vs 1244.7 s, 103 queries). A folding prototype was neutral;
producers still allocate 64 MB.
With a 32-bit hash (filter-context.cc:95-97), the fpp is at least ndv / 4.29
billion: 0.9% for 39.7M keys. In a microbenchmark (39.7M keys, 8 threads), 128
MB vs 64 MB passes 0.93% vs 1.22% of absent keys, at 39.7 vs 28.0 ns per probe.
*Proposal:*
* Size filters at runtime from the actual build: after the hash table
(IMPALA-11928) or by folding, both needing mixed-size merges, or per partition
(IMPALA-12455).
* Derive the target fpp from expected join selectivity.
* Use a wider hash for large builds (Kudu targets need today's format or a
client change).
* Raise the default cap only after runtime sizing works.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
