datafusion icon indicating copy to clipboard operation
datafusion copied to clipboard

Remove some Expr clones in `EliminateCrossJoin`(3%-5% faster planning)

Open alamb opened this issue 1 year ago • 0 comments

~Draft as it builds on https://github.com/apache/datafusion/pull/10427~

Which issue does this PR close?

Part of https://github.com/apache/datafusion/issues/10287

Rationale for this change

I am trying to avoid copying as much in EliminateCrossJoin to speed up planning.

One thing this rule does is quite a few Expr copies while checking exprs for join keys

What changes are included in this PR?

  1. Move management of join key exprs to JoinExprSet struct
  2. Reduce copying of clones internally to JoinExprSet
  3. New tests for JoinExprSet

Are these changes tested?

Existing CI

Are there any user-facing changes?

No functional changes

Performance tests show 3-5% faster for TPCH / TPDS queries

Details

++ critcmp main less_clone_in_eliminate_cross_join
group                                         less_clone_in_eliminate_cross_join     main
-----                                         ----------------------------------     ----
logical_aggregate_with_join                   1.00  1184.8±12.12µs        ? ?/sec    1.02  1207.4±14.82µs        ? ?/sec
logical_plan_tpcds_all                        1.00    156.8±1.94ms        ? ?/sec    1.01    158.1±2.46ms        ? ?/sec
logical_plan_tpch_all                         1.00     16.8±0.24ms        ? ?/sec    1.01     16.9±0.15ms        ? ?/sec
logical_select_all_from_1000                  1.00     17.9±0.11ms        ? ?/sec    1.04     18.7±0.13ms        ? ?/sec
logical_select_one_from_700                   1.00   815.1±20.51µs        ? ?/sec    1.00   813.6±10.21µs        ? ?/sec
logical_trivial_join_high_numbered_columns    1.00   752.3±14.99µs        ? ?/sec    1.02   764.2±14.21µs        ? ?/sec
logical_trivial_join_low_numbered_columns     1.00   736.0±10.70µs        ? ?/sec    1.01    745.7±7.27µs        ? ?/sec
physical_plan_tpcds_all                       1.00   1308.6±9.71ms        ? ?/sec    1.03   1349.1±7.72ms        ? ?/sec
physical_plan_tpch_all                        1.00     88.6±1.59ms        ? ?/sec    1.05     93.0±1.50ms        ? ?/sec
physical_plan_tpch_q1                         1.00      4.7±0.07ms        ? ?/sec    1.08      5.1±0.07ms        ? ?/sec
physical_plan_tpch_q10                        1.00      4.3±0.08ms        ? ?/sec    1.03      4.4±0.09ms        ? ?/sec
physical_plan_tpch_q11                        1.00      3.8±0.08ms        ? ?/sec    1.05      3.9±0.07ms        ? ?/sec
physical_plan_tpch_q12                        1.00      2.9±0.05ms        ? ?/sec    1.11      3.2±0.05ms        ? ?/sec
physical_plan_tpch_q13                        1.00      2.1±0.04ms        ? ?/sec    1.02      2.1±0.03ms        ? ?/sec
physical_plan_tpch_q14                        1.00      2.5±0.06ms        ? ?/sec    1.10      2.8±0.05ms        ? ?/sec
physical_plan_tpch_q16                        1.00      3.6±0.06ms        ? ?/sec    1.07      3.8±0.07ms        ? ?/sec
physical_plan_tpch_q17                        1.00      3.5±0.12ms        ? ?/sec    1.05      3.7±0.08ms        ? ?/sec
physical_plan_tpch_q18                        1.00      3.9±0.07ms        ? ?/sec    1.04      4.1±0.05ms        ? ?/sec
physical_plan_tpch_q19                        1.00      5.8±0.07ms        ? ?/sec    1.08      6.3±0.08ms        ? ?/sec
physical_plan_tpch_q2                         1.00      7.6±0.08ms        ? ?/sec    1.03      7.8±0.11ms        ? ?/sec
physical_plan_tpch_q20                        1.00      4.5±0.10ms        ? ?/sec    1.03      4.6±0.07ms        ? ?/sec
physical_plan_tpch_q21                        1.00      6.1±0.07ms        ? ?/sec    1.02      6.2±0.08ms        ? ?/sec
physical_plan_tpch_q22                        1.00      3.3±0.06ms        ? ?/sec    1.05      3.4±0.07ms        ? ?/sec
physical_plan_tpch_q3                         1.00      3.1±0.06ms        ? ?/sec    1.02      3.1±0.06ms        ? ?/sec
physical_plan_tpch_q4                         1.00      2.2±0.04ms        ? ?/sec    1.04      2.3±0.05ms        ? ?/sec
physical_plan_tpch_q5                         1.00      4.4±0.07ms        ? ?/sec    1.03      4.5±0.09ms        ? ?/sec
physical_plan_tpch_q6                         1.00  1479.7±35.88µs        ? ?/sec    1.09  1616.7±64.90µs        ? ?/sec
physical_plan_tpch_q7                         1.00      5.5±0.11ms        ? ?/sec    1.03      5.7±0.08ms        ? ?/sec
physical_plan_tpch_q8                         1.00      7.2±0.10ms        ? ?/sec    1.02      7.3±0.09ms        ? ?/sec
physical_plan_tpch_q9                         1.00      5.5±0.09ms        ? ?/sec    1.01      5.5±0.07ms        ? ?/sec
physical_select_all_from_1000                 1.00     58.7±0.33ms        ? ?/sec    1.04     61.1±0.87ms        ? ?/sec
physical_select_one_from_700                  1.00      3.6±0.03ms        ? ?/sec    1.02      3.6±0.05ms        ? ?/sec

alamb avatar May 08 '24 21:05 alamb