Zoltán Borók-Nagy created IMPALA-15520:
------------------------------------------
Summary: Cap join-column NDVs by the rows that survive earlier
FK/PK joins (TPC-DS q72 underestimated 40x)
Key: IMPALA-15520
URL: https://issues.apache.org/jira/browse/IMPALA-15520
Project: IMPALA
Issue Type: Improvement
Components: Frontend
Reporter: Zoltán Borók-Nagy
In TPC-DS q72 (SF100, master 1f34ea915e) the planner underestimates join 14 by
40x:
{noformat}
14:HASH JOIN [INNER JOIN, BROADCAST] d1.d_week_seq = d2.d_week_seq est.
13.86M rows, actual 558.45M
{noformat}
The N:M estimate is |L| x |R| / max(NDV) = 395.52M x 373 / 10,642, where 10,642
is the base-table NDV of date_dim.d_week_seq (JoinNode.java:585-593;
computeGenericJoinCardinality() at :517-534 scales NDVs only by the input's row
count). But d2 was joined earlier through the FK/PK join inv_date_sk =
d2.d_date_sk, and inventory has only 261 distinct inv_date_sk values. So at
most 261 date_dim rows, and at most 261 d_week_seq values, survive into join
14. With the NDV capped at 261 the estimate is 565M, within 1.2% of the actual
count.
*Consequence:* the inventory side is put on the build side of partitioned join
15. The planner estimates 576.63 MB for that join, but its hash table has
111.7M rows per instance and 24.5 GB per host. It is fed by a 59 GB shuffle and
built single-threaded after the last row arrives. q72 takes 94-99 s at default
options and is the slowest query in the workload by far.
*Proposal:*
* Track, per plan node, an upper bound on the number of distinct rows of each
tuple.
* For an inner or left outer FK/PK join L.fk = R.pk with R on the PK side, only
R rows that match an FK value survive. So R has at most NDV(L.fk) distinct rows
(the product of the NDVs for a multi-column key).
* In later N:M join estimates, use min(column NDV, bound) for R's columns.
Optionally do the same in aggregation group estimates.
* This only lowers NDVs, so it can only raise join estimates.
A prototype took q72 from 99 s to 19 s at MT_DOP=0, which is -26% for the
104-query workload (-2.7% without q72 and q78).
*Caveat:* the higher estimates propagate. In q72, join 15's estimate rises and
the per-host memory estimate goes from 7.09 GB to 197 GB, so admission would
reserve the whole cluster. It must ship together with the selectivity of
non-equi join conjuncts (IMPALA-8262), which brings the estimate back to 11.6
GB.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
