You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "kumarUjjawal (via GitHub)" <gi...@apache.org> on 2026/06/16 11:21:15 UTC
[PR] feat: add OR pre-selection short-circuit [datafusion]
kumarUjjawal opened a new pull request, #22979:
URL: https://github.com/apache/datafusion/pull/22979
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
- Closes #22342.
## Rationale for this change
`BinaryExpr` already uses pre-selection for `AND` when only a small set of LHS rows can affect the final result. This adds the matching optimization for `OR` when most LHS rows are already true.
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
## What changes are included in this PR?
This PR extends pre-selection short-circuiting to `OR`.
For `OR`, the RHS is evaluated only for rows where the LHS is false. Rows where the LHS is true are filled directly as true. The existing `AND` path is kept and the scatter logic is shared.
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
## Are these changes tested?
Yes
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
## Are there any user-facing changes?
No Public API Change
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-5073505073
Thanks @kumarUjjawal and @Dandandan and @kosiew
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-4725768640
```
case pr branch main main / pr branch
━━━━━━━━━━━━━━━━━━━━━━━━ ━━━━━━━━━━━━ ━━━━━━━━━━━━ ━━━━━━━━━━━━━━━
all_true 31.812 ns 32.251 ns 1.01x
──────────────────────── ──────────── ──────────── ───────────────
one_false_first 178.400 us 474.120 us 2.66x
──────────────────────── ──────────── ──────────── ───────────────
one_false_last 198.490 us 474.650 us 2.39x
──────────────────────── ──────────── ──────────── ───────────────
one_false_middle 197.900 us 474.040 us 2.40x
──────────────────────── ──────────── ──────────── ───────────────
one_false_middle_left 194.520 us 473.940 us 2.44x
──────────────────────── ──────────── ──────────── ───────────────
one_false_middle_right 198.680 us 474.080 us 2.39x
──────────────────────── ──────────── ──────────── ───────────────
all_false_in_or 474.700 us 473.610 us 1.00x
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-4994961381
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/22979?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `94.24460%` with `8 lines` in your changes missing coverage. Please review.
:warning: Please [upload](https://docs.codecov.com/docs/codecov-uploader) report for BASE (`main@95de385`). [Learn more](https://docs.codecov.io/docs/error-reference?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#section-missing-base-commit) about missing BASE report.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/22979?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/physical-expr/src/expressions/binary.rs](https://app.codecov.io/gh/apache/datafusion/pull/22979?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fexpressions%2Fbinary.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9leHByZXNzaW9ucy9iaW5hcnkucnM=) | 94.24% | [6 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/22979?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #22979 +/- ##
=======================================
Coverage ? 80.65%
=======================================
Files ? 1086
Lines ? 366203
Branches ? 366203
=======================================
Hits ? 295367
Misses ? 53241
Partials ? 17595
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/22979?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-4834550956
@alamb happy to take a look, but I'm on vacation until next week
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-4718352422
@neilconway do you have time to review this PR?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #22979:
URL: https://github.com/apache/datafusion/pull/22979
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#discussion_r3466404016
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -302,41 +302,50 @@ impl PhysicalExpr for BinaryExpr {
let rhs = self.right.evaluate(batch)?;
return Ok(rhs);
}
- ShortCircuitStrategy::PreSelection(selection) => {
- // The function `evaluate_selection` was not called for filtering and calculation,
- // as it takes into account cases where the selection contains null values.
- let batch = filter_record_batch(batch, selection)?;
- let right_ret = self.right.evaluate(&batch)?;
+ ShortCircuitStrategy::PreSelection { mask, fill_value } => {
+ // `mask` selects the rows whose result depends on the RHS; the
+ // unselected rows are all `fill_value` (see `ShortCircuitStrategy`).
+ //
+ // Use `filter_record_batch` directly because `evaluate_selection`
+ // scatters the RHS back to the original batch length.
+ let selection_batch = filter_record_batch(batch, &mask)?;
+ let right_ret = self.right.evaluate(&selection_batch)?;
match &right_ret {
ColumnarValue::Array(array) => {
- // When the array on the right is all true or all false, skip the scatter process
let boolean_array = array.as_boolean();
- if boolean_array.null_count() == 0 && !boolean_array.has_false() {
- return Ok(lhs);
- } else if boolean_array.null_count() == 0
- && !boolean_array.has_true()
- {
- // If the right-hand array is returned at this point,the lengths will be inconsistent;
- // returning a scalar can avoid this issue
- return Ok(ColumnarValue::Scalar(ScalarValue::Boolean(
- Some(false),
- )));
+ // If the RHS is uniform on the selected rows, the whole
+ // expression collapses and no scatter is needed.
+ if boolean_array.null_count() == 0 {
+ let rhs_value = if !boolean_array.has_false() {
Review Comment:
Small readability thought: the uniform RHS detection could be a bit flatter by encoding the two valid uniform cases directly.
```rust
let rhs_value = match (boolean_array.has_true(), boolean_array.has_false()) {
(true, false) => Some(true),
(false, true) => Some(false),
_ => None,
};
```
I think this makes the mixed case easier to spot at a glance and avoids the nested `if` / `else if`.
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -961,62 +985,54 @@ fn check_short_circuit<'a>(
ShortCircuitStrategy::None
}
-/// Creates a new boolean array based on the evaluation of the right expression,
-/// but only for positions where the left_result is true.
+/// Collapses a pre-selected expression whose RHS is uniformly `rhs_value` across
+/// every selected row, avoiding a scatter:
+/// - when it equals `fill_value`, every row is `fill_value` (a scalar);
+/// - otherwise the selected rows already equal the RHS, which matches the LHS
+/// there, and the unselected rows are the LHS value too, so the result is `lhs`.
+fn uniform_pre_selection_result(
+ rhs_value: bool,
+ fill_value: bool,
+ lhs: ColumnarValue,
+) -> ColumnarValue {
+ if rhs_value == fill_value {
+ ColumnarValue::Scalar(ScalarValue::Boolean(Some(fill_value)))
+ } else {
+ lhs
+ }
+}
+
+/// Creates a boolean array by scattering compact RHS results into the positions
+/// selected by `mask`.
///
-/// This function is used for short-circuit evaluation optimization of logical AND operations:
-/// - When left_result has few true values, we only evaluate the right expression for those positions
-/// - Values are copied from right_array where left_result is true
-/// - All other positions are filled with false values
+/// This function is used for short-circuit evaluation optimization of logical AND/OR operations:
+/// - Only selected rows are evaluated on the RHS
+/// - Values are copied from `right_result` where `mask` is true
+/// - All other positions are filled with `fill_value` (`false` for AND, `true` for OR)
///
/// # Parameters
-/// - `left_result` Boolean array with selection mask (typically from left side of AND)
+/// - `mask` Boolean array with the rows whose result depends on the RHS
/// - `right_result` Result of evaluating right side of expression (only for selected positions)
+/// - `fill_value` The value for the unselected positions (`false` for AND, `true` for OR)
///
/// # Returns
-/// A combined ColumnarValue with values from right_result where left_result is true
-///
-/// # Example
-/// Initial Data: { 1, 2, 3, 4, 5 }
-/// Left Evaluation
-/// (Condition: Equal to 2 or 3)
-/// ↓
-/// Filtered Data: {2, 3}
-/// Left Bitmap: { 0, 1, 1, 0, 0 }
-/// ↓
-/// Right Evaluation
-/// (Condition: Even numbers)
-/// ↓
-/// Right Data: { 2 }
-/// Right Bitmap: { 1, 0 }
-/// ↓
-/// Combine Results
-/// Final Bitmap: { 0, 1, 0, 0, 0 }
-///
-/// # Note
-/// Perhaps it would be better to modify `left_result` directly without creating a copy?
-/// In practice, `left_result` should have only one owner, so making changes should be safe.
-/// However, this is difficult to achieve under the immutable constraints of [`Arc`] and [`BooleanArray`].
+/// A combined `ColumnarValue` with the same length as `mask`.
fn pre_selection_scatter(
- left_result: &BooleanArray,
+ mask: &BooleanArray,
right_result: Option<&BooleanArray>,
+ fill_value: bool,
) -> Result<ColumnarValue> {
- let result_len = left_result.len();
+ let result_len = mask.len();
let mut result_array_builder = BooleanArray::builder(result_len);
- // keep track of current position we have in right boolean array
let mut right_array_pos = 0;
Review Comment:
`pre_selection_scatter` now has two very similar `SlicesIterator` loops, with the main difference being how selected rows are filled. It might be worth folding this into one loop and choosing the selected-row behavior inside it.
That would keep the invariant in one place: gaps get `fill_value`, while selected rows get RHS values or nulls. It may also help avoid future drift between the AND and OR paths.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-4834981893
Thanks @neilconway .
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add OR pre-selection short-circuit [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22979:
URL: https://github.com/apache/datafusion/pull/22979#issuecomment-4720890739
@kumarUjjawal I can take a look; have you run benchmarks / evaluated what the performance is like?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org