rgbuilds commented on issue #25616:
URL: https://github.com/apache/datafusion/issues/25616#issuecomment-6360138664
Investigation update: I reproduced the issue exactly.
- Equality-only join:
- Estimated rows: `6,001,215`
- Actual rows: `6,001,215`
- Join with `l_quantity < p_size`:
- Estimated rows: `6,001,215`
- Actual rows: `2,932,286`
- Q-error: `2.05x`
I traced the missing statistics edge to
`HashJoinExec::statistics_from_inputs`. `HashJoinExec` owns `self.filter`, but
the call to `estimate_join_statistics` does not pass it.
I also tested the existing `FilterExec` interval analyzer with two columns
whose ranges are both `[1, 50]`.
- Predicate: `column_0 < column_1`
- Expression supported: yes
- Refined ranges:
- `column_0`: `[1, 49]`
- `column_1`: `[2, 50]`
- Selectivity returned: `0.9604`
- Estimated rows from `10,000`: `9,604`
The interval analyzer multiplies the two marginal range reductions:
`(49 / 50) × (49 / 50) = 0.9604`
For independent uniform discrete values, however, the pair probability is:
`P(column_0 < column_1) = 1,225 / 2,500 = 0.49`
Applying the current interval estimate to the reproduced join would produce
approximately `5,763,567` estimated rows, which would barely improve the
current error. Applying `0.49` would produce approximately `2,940,596` rows,
close to the actual `2,932,286`.
Therefore, directly reusing the current interval-product selectivity would
recognize the expression but would not adequately fix the reported estimation
error.
My proposed first scope is:
- Pass the optional `JoinFilter` into join statistics estimation.
- Map `JoinFilter::column_indices` into compact column statistics.
- Recognize direct numeric column-to-column comparisons such as `<`, `<=`,
`>`, and `>=`.
- Estimate their pair-survival probability using a specialized uniform-range
model.
- Apply the resulting selectivity to equality candidate pairs for inner
joins.
- Mark the resulting row estimate as inexact.
- Preserve current estimates when:
- There is no residual filter.
- The expression is unsupported.
- Required statistics are missing.
- The join is outer, semi, anti, or mark.
I propose leaving outer and semi/anti residual estimation unchanged
initially because pair selectivity is not sufficient for those joins.
- Outer joins must estimate whether every candidate for a preserved row
fails the residual predicate.
- Semi/anti joins need the probability that at least one candidate survives.
- Both require a match-multiplicity or preserved-row probability model.
The reproduced comparison also involves different input types:
- `l_quantity`: `Decimal128(15, 2)`
- `p_size`: `Int32`
The initial implementation would therefore need to handle compatible numeric
coercion or the cast expression introduced during physical planning.
For supported inner joins, the intended flow would be:
1. Estimate equality candidate pairs using the existing logic.
2. Map the residual filter columns into the compact `JoinFilter` schema.
3. Read and normalize the mapped min/max statistics.
4. Estimate the residual comparison probability.
5. Apply it with `Precision::with_estimated_selectivity`.
6. Continue through the existing projection and fetch adjustments.
For unsupported expressions or insufficient statistics, the estimator would
return no new selectivity and retain the previous join estimate rather than
applying a hard-coded default.
Given the ongoing expression-level statistics work in #21122:
@asolimando, would you recommend implementing the column-comparison
probability estimator within that expression-level framework, or keeping it
join-local for an initial inner-join-only PR?
I would also appreciate guidance on whether preserving existing estimates
for outer and semi/anti joins is an acceptable first scope.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
