jayzhan211 commented on PR #24456:
URL: https://github.com/apache/datafusion/pull/24456#issuecomment-6384138773
@Dandandan I ran this branch on JOB, TPC-DS SF1 and TPC-H SF10 to see where
it stands. The enumeration works well. On the queries where I could hand-write
a good join order, it recovers almost all of that gain:
| Query | Enumeration off | Enumeration on | Hand-written order |
|---|---|---|---|
| JOB 17b/c/d/f | 4.5–6.8 s | 0.16–0.27 s | 0.16–0.25 s |
| JOB 16a–d | 2.3–5.2 s | 0.13–0.36 s | 0.13–0.38 s |
| TPC-DS q72 | 1.42 s | 0.06 s | 0.08 s |
| TPC-H q18 | 0.67 s | 0.37 s | 0.41 s |
TPC-DS and TPC-H have no real regressions against the commit this branch is
based on. On JOB, though, 21 queries get more than 1.2x slower (19d 4.6x, 5b
4.5x, 5a 3.7x, 2c 3.3x, 18a 2.1x). I found two causes, and neither is in the
search itself.
**1. The new `IN` list estimate in `FilterExec`.** `in_list_selectivity`
divides the number of literals by `max_distinct_count`, which falls back to the
row count when the column has no NDV. Most Parquet files don't carry NDV, so a
string `IN` list is treated as if every value were unique. In 19d, `ci.note IN
(4 values)` is estimated at 11 rows, but 815K rows match. Every join above it
is then estimated at about 11 rows, so the search has nothing to go on. The
same happens with an `OR` of equalities (18a). It also changes plans with
enumeration turned off: 9a goes from 0.25 s to 1.7–2.7 s.
Skipping the estimate when there is no real distinct count fixes it:
```diff
let stats = column_statistics.get(column.index())?;
+ // Without a real distinct count, `max_distinct_count` falls back to
the row
+ // count, which treats every value as unique; leave such a column to
the default.
+ stats.distinct_count.get_value()?;
let distinct = *max_distinct_count(num_rows, stats).get_value()?;
```
With that change, JOB runs at 0.65x of the base by geomean (46.6 s down to
18.6 s in total). 62 queries are faster, 3 are slower by more than 1.2x, and
results are identical on all 113 queries.
**2. Rebuilt joins lose statistics on cast keys.** `key_expr` puts
`CAST(col)` directly into the join's `on`, but `estimate_join_statistics` only
reads keys that are plain columns (`equijoin_column_indices`). The rebuilt join
then reports a much larger estimate than before, and `JoinSelection` picks the
wrong build side. In 2c it builds on `title` (2.5M rows) instead of the empty
side, and 16 ms becomes 53 ms. Computing the cast in a projection below the
join, as the physical planner does, or letting the join statistics look through
lossless casts would both fix it.
The other two queries still slower after the first fix are small:
- 4c (71 to 88 ms): the new order is about as good as the written one by
intermediate rows, but the big `movie_keyword` join now hashes two keys from
the same equivalence class, `movie_id = movie_id` and `CAST(t.id) =
CAST(mk.movie_id)`. The second is already implied by the join below it. That
join takes 66 ms where the base plan's equivalent takes 32 ms. Keeping one key
per equivalence class when rebuilding a join would avoid it.
- 23b (183 to 225 ms): the rebuilt plan builds on `movie_keyword` (4.52M
rows) against a side that produces 6 rows. `JoinSelection` compares bytes
before rows, and that side reports 45 MB for an estimated 164K rows, more than
the 36 MB of the `movie_keyword` scan. The inflated size doesn't come from this
PR: on main, inner join statistics keep each input column's `byte_size`
unscaled, and the semi join above adds them up. So this one needs a statistics
fix on main rather than a change here.
Where it falls short of the hand-written order (8c, 8d, 17e), the cause is
filter and fan-out estimates, not the search.
Setup: M4 Pro, 12 threads, Parquet files, best of 3 runs. Other work was
running on the machine, so differences under about 10% are noise.
I'm happy to keep working on top of this PR.
cc @2010YOUY01 since you're working on join ordering.
--
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]
