Zoltán Borók-Nagy created IMPALA-15522:
------------------------------------------
Summary: Random choice of broadcast runtime filter producers makes
codegen nondeterministic and defeats the codegen cache
Key: IMPALA-15522
URL: https://issues.apache.org/jira/browse/IMPALA-15522
Project: IMPALA
Issue Type: Improvement
Components: Backend
Reporter: Zoltán Borók-Nagy
For a broadcast join with only non-local filter targets, the coordinator picks
MAX_BROADCAST_FILTER_PRODUCERS (3) random instances to produce each filter
(coordinator.cc:479, random_shuffle() then resize()).
On each backend, PhjBuilderConfig drops the filters this backend does not
produce before codegen (partitioned-hash-join-builder.cc:120), and the
codegen'd build loop emits one insert per kept filter. So the generated IR of
the build differs between producer and non-producer backends. Which backends
are producers changes on every run.
The codegen cache key is the module bitcode, so these fragments miss the cache
on warm runs.
*Evidence* (TPC-DS SF100, 5 executors, master 1f34ea915e):
* 57 of 1887 fragments had host- and run-dependent IR, and they accounted for
every warm cache miss: 144 of 144 in the second iteration and 71 of 71 in the
third.
* Example: for q1 F02, hosts {1,3,5} got the larger IR in one run and hosts
{2,4,5} in the next.
* Each miss means a full LLVM optimization and compile. About 40% of that
compile time shows up in wall time overall, and 60-100% for sub-second queries.
*Proposed fix:* codegen inserts for all filters of the join on every backend,
and skip the filters this backend does not produce at runtime.
* Keep a FilterContext with filter == nullptr for them, and don't allocate or
publish them.
* The codegen'd insert already returns early when the local filter is null.
* The IR then depends only on the plan.
The alternative, choosing producers deterministically (for example a stable
backend order rotated by filter id), still leaves producer and non-producer IR
different. It also breaks whenever the set of backends changes.
A prototype of the proposed fix took warm codegen-cache misses over the
workload from 128 to 0. The geomean of per-query times was 0.87 (-2.9% total);
most of the gain is on sub-second queries.
Side note: std::random_shuffle is deprecated in C++14 and removed in C++17.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
