apache / apache/datafusion

Improve the performance of early exit evaluation in binary_expr

Open
#15,631 14 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

@acking-you 's wonderful PR https://github.com/apache/datafusion/pull/15462 adds short circuiting to boolean operation evaluation which makes evaluating some complex expressions much faster.

However, to do so it uses the `count_ones` function to check

![Image](https://github.com/user-attachments/assets/4f5216b6-683f-414e-9c91-203d670c0149)

We have theorized it should be faster to simply check if there are any set bits in the array rather than using count_zeros, however @acking-you found that this is not easy to do as Rust generates very optimized code for count_ones

You can see an example of this analysis
https://github.com/apache/datafusion/pull/15462#issuecomment-2784190060

### Describe the solution you'd like

Now that we have benchmarks for binary_op it would be great to see if we can optimize this codepath more

### Describe alternatives you've considered

Roughly speaking you can run the benchmarks with

```shell
cargo bench --profile=profiling --bench binary_op
```

And then profile that with your favorite tool

For example, you can use samply like this:
```shell
samply record target/profiling/deps/binary_op-cce23ddc74cdfa3a --bench
```

### Additional context

_No response_

Contributor guide

Open the contributing guide

Research direction

Start with the binary_op benchmarks and run `cargo bench --profile=profiling --bench binary_op`; review the short-circuiting change in PR 15462 and its profiling discussion. Use a profiler such as samply to investigate early-exit evaluation in `binary_expr`, and consider the work done when the benchmark demonstrates a measurable improvement.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.