Make Clickbench Q29 5x faster for datafusion

[zhuqi-lucas]

Is your feature request related to a problem or challenge?

Our datafusion is 5x slower than duckdb for q29, it's easy for us to optimize to 5x faster, here is the try:

Extraction of Constants in Multiple AGG Calls

In ClickBench, some SQL queries can be optimized using RBO (Rule-Based Optimization) without changing semantics. For example, Q29 computes SUM(ResolutionWidth + constant) 90 times, requiring 90 columns in execution. Using the distributive property, we can rewrite it as:

Before Optimization

SELECT SUM(ResolutionWidth), SUM(ResolutionWidth + 1), ..., SUM(ResolutionWidth + 89) 
FROM hits;

After Optimization

SELECT SUM(ResolutionWidth), 
       SUM(ResolutionWidth) + 1 * COUNT(*), 
       ..., 
       SUM(ResolutionWidth) + 89 * COUNT(*) 
FROM hits;

This reduces redundant computations and improves execution efficiency.

Testing result:

Before rewrite:

cargo run --profile release-nonlto   --target aarch64-apple-darwin --bin dfbench -- clickbench  -p benchmarks/data/hits_partitioned -q 29
    Finished `release-nonlto` profile [optimized] target(s) in 0.26s
     Running `target/aarch64-apple-darwin/release-nonlto/dfbench clickbench -p benchmarks/data/hits_partitioned -q 29`
Running benchmarks with the following options: RunOpt { query: Some(29), common: CommonOpt { iterations: 3, partitions: None, batch_size: 8192, mem_pool_type: "fair", memory_limit: None, sort_spill_reservation_bytes: None, debug: false }, path: "benchmarks/data/hits_partitioned", queries_path: "benchmarks/queries/clickbench/queries.sql", output_path: None }
Q29: SELECT SUM("ResolutionWidth"), SUM("ResolutionWidth" + 1), SUM("ResolutionWidth" + 2), SUM("ResolutionWidth" + 3), SUM("ResolutionWidth" + 4), SUM("ResolutionWidth" + 5), SUM("ResolutionWidth" + 6), SUM("ResolutionWidth" + 7), SUM("ResolutionWidth" + 8), SUM("ResolutionWidth" + 9), SUM("ResolutionWidth" + 10), SUM("ResolutionWidth" + 11), SUM("ResolutionWidth" + 12), SUM("ResolutionWidth" + 13), SUM("ResolutionWidth" + 14), SUM("ResolutionWidth" + 15), SUM("ResolutionWidth" + 16), SUM("ResolutionWidth" + 17), SUM("ResolutionWidth" + 18), SUM("ResolutionWidth" + 19), SUM("ResolutionWidth" + 20), SUM("ResolutionWidth" + 21), SUM("ResolutionWidth" + 22), SUM("ResolutionWidth" + 23), SUM("ResolutionWidth" + 24), SUM("ResolutionWidth" + 25), SUM("ResolutionWidth" + 26), SUM("ResolutionWidth" + 27), SUM("ResolutionWidth" + 28), SUM("ResolutionWidth" + 29), SUM("ResolutionWidth" + 30), SUM("ResolutionWidth" + 31), SUM("ResolutionWidth" + 32), SUM("ResolutionWidth" + 33), SUM("ResolutionWidth" + 34), SUM("ResolutionWidth" + 35), SUM("ResolutionWidth" + 36), SUM("ResolutionWidth" + 37), SUM("ResolutionWidth" + 38), SUM("ResolutionWidth" + 39), SUM("ResolutionWidth" + 40), SUM("ResolutionWidth" + 41), SUM("ResolutionWidth" + 42), SUM("ResolutionWidth" + 43), SUM("ResolutionWidth" + 44), SUM("ResolutionWidth" + 45), SUM("ResolutionWidth" + 46), SUM("ResolutionWidth" + 47), SUM("ResolutionWidth" + 48), SUM("ResolutionWidth" + 49), SUM("ResolutionWidth" + 50), SUM("ResolutionWidth" + 51), SUM("ResolutionWidth" + 52), SUM("ResolutionWidth" + 53), SUM("ResolutionWidth" + 54), SUM("ResolutionWidth" + 55), SUM("ResolutionWidth" + 56), SUM("ResolutionWidth" + 57), SUM("ResolutionWidth" + 58), SUM("ResolutionWidth" + 59), SUM("ResolutionWidth" + 60), SUM("ResolutionWidth" + 61), SUM("ResolutionWidth" + 62), SUM("ResolutionWidth" + 63), SUM("ResolutionWidth" + 64), SUM("ResolutionWidth" + 65), SUM("ResolutionWidth" + 66), SUM("ResolutionWidth" + 67), SUM("ResolutionWidth" + 68), SUM("ResolutionWidth" + 69), SUM("ResolutionWidth" + 70), SUM("ResolutionWidth" + 71), SUM("ResolutionWidth" + 72), SUM("ResolutionWidth" + 73), SUM("ResolutionWidth" + 74), SUM("ResolutionWidth" + 75), SUM("ResolutionWidth" + 76), SUM("ResolutionWidth" + 77), SUM("ResolutionWidth" + 78), SUM("ResolutionWidth" + 79), SUM("ResolutionWidth" + 80), SUM("ResolutionWidth" + 81), SUM("ResolutionWidth" + 82), SUM("ResolutionWidth" + 83), SUM("ResolutionWidth" + 84), SUM("ResolutionWidth" + 85), SUM("ResolutionWidth" + 86), SUM("ResolutionWidth" + 87), SUM("ResolutionWidth" + 88), SUM("ResolutionWidth" + 89) FROM hits;
Query 29 iteration 0 took 341.5 ms and returned 1 rows
Query 29 iteration 1 took 320.7 ms and returned 1 rows
Query 29 iteration 2 took 303.0 ms and returned 1 rows
Query 29 avg time: 321.73 ms

After rewrite:

cargo run --profile release-nonlto   --target aarch64-apple-darwin --bin dfbench -- clickbench  -p benchmarks/data/hits_partitioned -q 29
    Finished `release-nonlto` profile [optimized] target(s) in 0.26s
     Running `target/aarch64-apple-darwin/release-nonlto/dfbench clickbench -p benchmarks/data/hits_partitioned -q 29`
Running benchmarks with the following options: RunOpt { query: Some(29), common: CommonOpt { iterations: 3, partitions: None, batch_size: 8192, mem_pool_type: "fair", memory_limit: None, sort_spill_reservation_bytes: None, debug: false }, path: "benchmarks/data/hits_partitioned", queries_path: "benchmarks/queries/clickbench/queries.sql", output_path: None }
Q29: SELECT SUM("ResolutionWidth"), SUM("ResolutionWidth") + 1 * COUNT(*), SUM("ResolutionWidth") + 2 * COUNT(*), SUM("ResolutionWidth") + 3 * COUNT(*), SUM("ResolutionWidth") + 4 * COUNT(*), SUM("ResolutionWidth") + 5 * COUNT(*), SUM("ResolutionWidth") + 6 * COUNT(*), SUM("ResolutionWidth") + 7 * COUNT(*), SUM("ResolutionWidth") + 8 * COUNT(*), SUM("ResolutionWidth") + 9 * COUNT(*), SUM("ResolutionWidth") + 10 * COUNT(*), SUM("ResolutionWidth") + 11 * COUNT(*), SUM("ResolutionWidth") + 12 * COUNT(*), SUM("ResolutionWidth") + 13 * COUNT(*), SUM("ResolutionWidth") + 14 * COUNT(*), SUM("ResolutionWidth") + 15 * COUNT(*), SUM("ResolutionWidth") + 16 * COUNT(*), SUM("ResolutionWidth") + 17 * COUNT(*), SUM("ResolutionWidth") + 18 * COUNT(*), SUM("ResolutionWidth") + 19 * COUNT(*), SUM("ResolutionWidth") + 20 * COUNT(*), SUM("ResolutionWidth") + 21 * COUNT(*), SUM("ResolutionWidth") + 22 * COUNT(*), SUM("ResolutionWidth") + 23 * COUNT(*), SUM("ResolutionWidth") + 24 * COUNT(*), SUM("ResolutionWidth") + 25 * COUNT(*), SUM("ResolutionWidth") + 26 * COUNT(*), SUM("ResolutionWidth") + 27 * COUNT(*), SUM("ResolutionWidth") + 28 * COUNT(*), SUM("ResolutionWidth") + 29 * COUNT(*), SUM("ResolutionWidth") + 30 * COUNT(*), SUM("ResolutionWidth") + 31 * COUNT(*), SUM("ResolutionWidth") + 32 * COUNT(*), SUM("ResolutionWidth") + 33 * COUNT(*), SUM("ResolutionWidth") + 34 * COUNT(*), SUM("ResolutionWidth") + 35 * COUNT(*), SUM("ResolutionWidth") + 36 * COUNT(*), SUM("ResolutionWidth") + 37 * COUNT(*), SUM("ResolutionWidth") + 38 * COUNT(*), SUM("ResolutionWidth") + 39 * COUNT(*), SUM("ResolutionWidth") + 40 * COUNT(*), SUM("ResolutionWidth") + 41 * COUNT(*), SUM("ResolutionWidth") + 42 * COUNT(*), SUM("ResolutionWidth") + 43 * COUNT(*), SUM("ResolutionWidth") + 44 * COUNT(*), SUM("ResolutionWidth") + 45 * COUNT(*), SUM("ResolutionWidth") + 46 * COUNT(*), SUM("ResolutionWidth") + 47 * COUNT(*), SUM("ResolutionWidth") + 48 * COUNT(*), SUM("ResolutionWidth") + 49 * COUNT(*), SUM("ResolutionWidth") + 50 * COUNT(*), SUM("ResolutionWidth") + 51 * COUNT(*), SUM("ResolutionWidth") + 52 * COUNT(*), SUM("ResolutionWidth") + 53 * COUNT(*), SUM("ResolutionWidth") + 54 * COUNT(*), SUM("ResolutionWidth") + 55 * COUNT(*), SUM("ResolutionWidth") + 56 * COUNT(*), SUM("ResolutionWidth") + 57 * COUNT(*), SUM("ResolutionWidth") + 58 * COUNT(*), SUM("ResolutionWidth") + 59 * COUNT(*), SUM("ResolutionWidth") + 60 * COUNT(*), SUM("ResolutionWidth") + 61 * COUNT(*), SUM("ResolutionWidth") + 62 * COUNT(*), SUM("ResolutionWidth") + 63 * COUNT(*), SUM("ResolutionWidth") + 64 * COUNT(*), SUM("ResolutionWidth") + 65 * COUNT(*), SUM("ResolutionWidth") + 66 * COUNT(*), SUM("ResolutionWidth") + 67 * COUNT(*), SUM("ResolutionWidth") + 68 * COUNT(*), SUM("ResolutionWidth") + 69 * COUNT(*), SUM("ResolutionWidth") + 70 * COUNT(*), SUM("ResolutionWidth") + 71 * COUNT(*), SUM("ResolutionWidth") + 72 * COUNT(*), SUM("ResolutionWidth") + 73 * COUNT(*), SUM("ResolutionWidth") + 74 * COUNT(*), SUM("ResolutionWidth") + 75 * COUNT(*), SUM("ResolutionWidth") + 76 * COUNT(*), SUM("ResolutionWidth") + 77 * COUNT(*), SUM("ResolutionWidth") + 78 * COUNT(*), SUM("ResolutionWidth") + 79 * COUNT(*), SUM("ResolutionWidth") + 80 * COUNT(*), SUM("ResolutionWidth") + 81 * COUNT(*), SUM("ResolutionWidth") + 82 * COUNT(*), SUM("ResolutionWidth") + 83 * COUNT(*), SUM("ResolutionWidth") + 84 * COUNT(*), SUM("ResolutionWidth") + 85 * COUNT(*), SUM("ResolutionWidth") + 86 * COUNT(*), SUM("ResolutionWidth") + 87 * COUNT(*), SUM("ResolutionWidth") + 88 * COUNT(*), SUM("ResolutionWidth") + 89 * COUNT(*) FROM hits;
Query 29 iteration 0 took 86.9 ms and returned 1 rows
Query 29 iteration 1 took 59.3 ms and returned 1 rows
Query 29 iteration 2 took 42.3 ms and returned 1 rows
Query 29 avg time: 62.85 ms

Describe the solution you'd like

No response

Describe alternatives you've considered

No response

Additional context

No response

[zhuqi-lucas]

Clickhouse also has the optimization:
https://github.com/ClickHouse/ClickHouse/pull/57853/files

[zhuqi-lucas]

take

[zhuqi-lucas]

Can anyone guide me how to do this in datafusion, i am not familiar with the rewrite now. So need some code reference.

cc @alamb @jonahgao @jayzhan211
Thanks!

[jayzhan211]

You can implement this in rewrite rule SimplifyExpressions in logical optimizer

datafusion/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

Lines 730 to 748 in 507f6b6

	Ok(match expr {
	//
	// Rules for Eq
	//
	// true = A --> A
	// false = A --> !A
	// null = A --> null
	Expr::BinaryExpr(BinaryExpr {
	left,
	op: Eq,
	right,
	}) if is_bool_lit(&left) && info.is_boolean_type(&right)? => {
	Transformed::yes(match as_bool_lit(&left)? {
	Some(true) => *right,
	Some(false) => Expr::Not(right),
	None => lit_bool_null(),
	})
	}

if there is sum(column + const_a) then you return sum(column) + const_a * count(*).

[zhuqi-lucas]

Thank you @jayzhan211 for the guide, i will try this!

[Dandandan]

Nice idea!
I think it makes sense to avoid doing this optimization when there is only a single case of this - otherwise the number of accumulators gets bigger (combined with group by this will lead to higher memory usage).

[alamb]

As long as this optimization is plausibly general purpose (not just for ClickBench) and the code required is isolated / doesn't add a bunch of complexity, I am in support of this optimization

Thank you @zhuqi-lucas

[alamb]

I found a duckdb implementation of a seemingling similar optimization: https://github.com/duckdb/duckdb/blob/7912713493b38b1eda162f29b7759d5024989a5f/src/optimizer/sum_rewriter.cpp#L25

[zhuqi-lucas]

Thank you @Dandandan @alamb for double check and confirm!

[Dandandan]

I found the rationale behind adding it in DuckDB was also ClickBench.

duckdb/duckdb#15017

As a randomly selected query, let's run this query from ClickBench:

😆

So we're now officially benchmaxxing!

[Dandandan]

I'm wondering if instead of this specialized

SUM(x + c) -> SUM(x) * COUNT() * c

We can do instead the more general (distributive property of summation - doesn't need to be a constant):

SUM(x + y) -> SUM(x) + SUM(y)

And have other optimizations follow (transform SUM(y) -> COUNT() * y when y is constant, common subexpression elimination, etc.)