adriangb commented on PR #25339: URL: https://github.com/apache/datafusion/pull/25339#issuecomment-5721552037
## DuckDB comparison, and what the Q08 number means To find out whether the remaining cost of this PR is acceptable, I measured the suite's eight queries in `datafusion-cli` (this branch, release) and in DuckDB 1.5.2 (`EXPLAIN ANALYZE`, three runs, median, Apple M4 Pro, same tables from the suite's `load.sql`). The two engines give the same result for all eight queries. ### At the suite's default sizes | Query | Shape | DataFusion | DuckDB | DuckDB / DF | |---|---|---|---|---| | Q01 | uncorrelated, non-nullable | 5 ms | 14 ms | 2.8x | | Q02 | uncorrelated, 1% NULL subquery | 3 ms | 13 ms | 4.2x | | Q03 | uncorrelated, 50% NULL outer | 2 ms | 13 ms | 6.6x | | Q04 | correlated, no NULL | < 1 ms | 117 ms | > 100x | | Q05 | correlated, 1% NULL outer | 1 ms | 116 ms | 116x | | Q06 | correlated, 50% NULL outer | 1 ms | 114 ms | 114x | | Q07 | correlated, 50% NULL subquery | 1 ms | 3540 ms | ~3500x | | Q08 | as Q06, plus an equality correlation | 12 ms | 22 ms | 1.8x | `datafusion-cli` reports milliseconds, so the sub-millisecond queries show as 1 ms. ### Each engine against itself Q06 and Q08 have the same NULL fraction. Q08 adds an equality correlation, which gives the join a scope key. Thus the ratio of the two shows what each engine gets from that key. | `NAJ_ROWS` | DF Q06 | DF Q08 | DF Q08/Q06 | DuckDB Q06 | DuckDB Q08 | DuckDB Q08/Q06 | |---|---|---|---|---|---|---| | 10,000 | 1 ms | 12 ms | 12x | 114 ms | 22 ms | 0.19x | | 30,000 | 1 ms | 38.5 ms | 38x | 329 ms | 49.7 ms | 0.15x | | 100,000 | 13 ms | 418.5 ms | 32x | 1110 ms | 147 ms | 0.13x | The equality correlation makes Q08 about 7x cheaper than Q06 in DuckDB. In DataFusion it makes Q08 more than 10x more expensive than Q06. So the Q08 number is not a property of the shape. It is a property of our scope-key path. The cause is visible in the pair counts. Without a scope key, the join now drops the build rows that are already UNKNOWN after each chunk of candidate pairs, so Q06 evaluates 240K pairs instead of 20.6M. With a scope key, the candidate pairs come from the hash lookup, and the marked rows are removed only after that lookup, so Q08 still enumerates 6.25M pairs and keeps 86K of them. Q08's cost grows with the square of the table size, while DuckDB's grows about linearly. DuckDB is faster than DataFusion for Q08 from about 100,000 rows. ### Conclusion - For the non-equality correlation, which is the bug this PR closes, the correct result is now nearly free: Q06 and Q07 cost about the same as Q04 (the same shape with no NULL), and about 30% more than the incorrect fast result on `main`. - For the uncorrelated shapes (Q01 to Q03) this PR changes nothing. - Q08 is a real gap, not a measurement artifact. It is pre-existing in the scope-key path, and this PR makes it visible because the other correlated queries are now fast. I suggest we track it as a follow-up: narrow the scope-key lookup with the UNKNOWN bitmap, so that the equality correlation reduces work instead of adding it. I am happy to file that follow-up issue. -- 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]
