You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "Kurt Deschler (Jira)" <ji...@apache.org> on 2026/10/08 20:22:00 UTC
[jira] [Commented] (IMPALA-15520) Cap join-column NDVs by the rows that survive earlier FK/PK joins (TPC-DS q72 underestimated 40x)
[ https://issues.apache.org/jira/browse/IMPALA-15520?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18125233#comment-18125233 ]
Kurt Deschler commented on IMPALA-15520:
----------------------------------------
It may be good to add a join expansion factor multiplier similar to [AGG_MEM_CORRELATION_FACTOR|[http://example.com|https://gerrit.cloudera.org/#/c/20104/]]
> 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
> Priority: Major
> Labels: performance
>
> 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)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org