comphead commented on code in PR #27471:
URL: https://github.com/apache/datafusion/pull/27471#discussion_r4590300506
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -556,69 +583,31 @@ impl PhysicalExpr for BinaryExpr {
let lhs = self.left.evaluate(batch)?;
// Check if we can apply short-circuit evaluation.
- match check_short_circuit(&lhs, &self.op) {
- ShortCircuitStrategy::None => {}
- ShortCircuitStrategy::ReturnLeft => return Ok(lhs),
- ShortCircuitStrategy::ReturnRight => {
- let rhs = self.right.evaluate(batch)?;
- return Ok(rhs);
- }
- 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) => {
- let boolean_array = array.as_boolean();
- // 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() {
- Some(true)
- } else if !boolean_array.has_true() {
- Some(false)
- } else {
- None
- };
- if let Some(rhs_value) = rhs_value {
- return Ok(uniform_pre_selection_result(
- rhs_value, fill_value, lhs,
- ));
- }
- }
-
- return pre_selection_scatter(
- &mask,
- Some(boolean_array),
- fill_value,
- );
- }
- ColumnarValue::Scalar(scalar) => {
- if let ScalarValue::Boolean(v) = scalar {
- // A scalar RHS applies uniformly to all selected
rows.
- if let Some(v) = v {
- return Ok(uniform_pre_selection_result(
- *v, fill_value, lhs,
- ));
- } else {
- return pre_selection_scatter(&mask, None,
fill_value);
- }
- } else {
- return internal_err!(
- "Expected boolean scalar value, found:
{right_ret:?}"
- );
- }
- }
+ if self.op == Operator::Or {
+ match check_short_circuit_for_or(&lhs, self.right_is_volatile()) {
+ ShortCircuitStrategy::None => {}
+ ShortCircuitStrategy::ReturnLeft => return Ok(lhs),
+ ShortCircuitStrategy::ReturnRight => {
+ let rhs = self.right.evaluate(batch)?;
+ return Ok(rhs);
+ }
+ ShortCircuitStrategy::PreSelection { mask, fill_value } => {
+ return self.evaluate_pre_selection(batch, lhs, &mask,
fill_value);
}
}
}
- let rhs = self.right.evaluate(batch)?;
+ let rhs = match self.right.evaluate(batch) {
Review Comment:
`or_rows_to_retry` repeats what `check_short_circuit_for_or` already
computes. With the RHS treated as volatile it returns `PreSelection` exactly
when some rows are decided and some are not, which is when the retry can help.
A guard keeps this `OR`-only and removes the helper, its `op` parameter, the
dead `undecided > 0` check and both `unreachable!`s in library code:
```rust
let rhs = match self.right.evaluate(batch) {
Ok(rhs) => rhs,
// A deterministic RHS may fail on rows the LHS already decided
// (e.g. `x = 0 OR 1 / x > 1`), so retry on the undecided rows only.
Err(e) if self.op == Operator::Or => {
return match check_short_circuit_for_or(&lhs, true) {
ShortCircuitStrategy::PreSelection { mask, .. } => {
self.evaluate_pre_selection(batch, lhs, &mask)
}
_ => Err(e),
};
}
Err(e) => return Err(e),
};
```
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -1194,6 +1185,71 @@ impl BinaryExpr {
}
}
+ /// Evaluates the RHS of `OR` only on the rows selected by `mask` (the rows
+ /// whose result depends on the RHS); the other rows are `fill_value`.
+ fn evaluate_pre_selection(
+ &self,
+ batch: &RecordBatch,
+ lhs: ColumnarValue,
+ mask: &BooleanArray,
+ fill_value: bool,
+ ) -> Result<ColumnarValue> {
+ // 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) => {
+ let boolean_array = array.as_boolean();
+ // 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() {
+ Some(true)
+ } else if !boolean_array.has_true() {
+ Some(false)
+ } else {
+ None
+ };
+ if let Some(rhs_value) = rhs_value {
+ return Ok(uniform_pre_selection_result(
+ rhs_value, fill_value, lhs,
+ ));
+ }
+ }
+
+ let scattered =
+ pre_selection_scatter(mask, Some(boolean_array),
fill_value)?;
+ // Selected rows may have a NULL LHS (`NULL OR x`), so combine
+ // with the LHS; unselected rows are `fill_value` on both
sides.
+ if lhs.data_type() == DataType::Boolean
Review Comment:
`lhs.data_type() == DataType::Boolean` always holds here, since both callers
only reach this with a Boolean array LHS, so `if let ColumnarValue::Array(lhs)
= &lhs && lhs.null_count() > 0` is enough.
`fill_value` is also always `true` (`check_short_circuit_for_or` only builds
`PreSelection { fill_value: true }`, and the retry passes a literal). This
combine step and the comment above it rely on that. Dropping the parameter here
and the field from `PreSelection` would make the `OR`-only contract explicit.
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -1534,6 +1616,15 @@ fn not_false(array: &BooleanArray) -> BooleanArray {
BooleanArray::new(values, None)
}
+/// A null-free mask of the rows of `array` that are `false` or `NULL`.
+fn not_true(array: &BooleanArray) -> BooleanArray {
Review Comment:
Nit: `!values | !nulls` is `!(values & nulls)`, so
`BooleanArray::new(!&(array.values() & nulls.inner()), None)` builds one fewer
buffer.
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -44,13 +44,28 @@ use kernels::{
};
/// Binary expression
-#[derive(Debug, Clone, Eq)]
+#[derive(Clone, Eq)]
pub struct BinaryExpr {
left: Arc<dyn PhysicalExpr>,
op: Operator,
right: Arc<dyn PhysicalExpr>,
/// Specifies whether an error is returned on overflow or not
fail_on_overflow: bool,
+ /// Whether `right` is volatile, computed once in [`BinaryExpr::new`] for
+ /// `OR` so it is not walked for every batch. `None` for other operators.
+ right_volatility: Option<bool>,
Review Comment:
This cache needs a manual `Debug` (only to keep the `Debug` snapshots in
`dynamic_filters/mod.rs` and `physical_planner.rs` unchanged), a
`right_is_volatile` fallback that cannot run (it is only called for `OR`, and
every `OR` goes through `new`), and the destructure in `try_to_proto`. It also
walks the whole RHS on every `new`, including each optimizer rebuild through
`with_new_children`.
The `AND` sibling classifies lazily per batch instead
(`rows_to_filter_before` runs `is_cheap_and_infallible` last). Doing the same
here, by checking `is_volatile(&self.right)` only in the mixed-batch branch
above the threshold (for example a `impl FnOnce() -> bool` argument to
`check_short_circuit_for_or`), drops all of the above. If the cache stays, a
plain `bool` set to `op == Or && is_volatile(&right)` removes the `Option` and
the helper.
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -7351,4 +7435,472 @@ mod tests {
BooleanArray::from_iter(vec![Some(true), Some(true), Some(true),
Some(true)]);
assert_eq!(eq_result.into_array(4).unwrap().as_boolean(), &expected);
}
+
+ /// Tests that the right side of `OR` is only evaluated on the rows
+ /// that need it, for every selectivity (not only those that hit the
+ /// [`PRE_SELECTION_THRESHOLD`] heuristics).
+ ///
+ /// The right side is a [`Probe`] that knows which rows it is allowed to
see.
+ mod short_circuit {
+ use super::*;
+ use datafusion_common::exec_err;
+ use std::fmt::{Display, Formatter};
+ use std::hash::Hasher;
+ use std::ops::Range;
+ use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
+
+ const N: usize = 1000;
+
+ /// Fraction of rows that need the right side. Covers the extremes and
+ /// values around the threshold, so changing
[`PRE_SELECTION_THRESHOLD`]
+ /// won't make the tests irrelevant.
+ const SELECTIVITIES: &[f32] = &[
+ 0.0,
+ 0.01,
+ 0.1,
+ 0.25,
+ 0.5,
+ 0.75,
+ 0.9,
+ 0.99,
+ 1.0,
+ PRE_SELECTION_THRESHOLD / 2.0,
+ PRE_SELECTION_THRESHOLD,
+ PRE_SELECTION_THRESHOLD * 2.0,
+ 1.0 - PRE_SELECTION_THRESHOLD / 2.0,
+ 1.0 - PRE_SELECTION_THRESHOLD,
+ 1.0 - PRE_SELECTION_THRESHOLD * 2.0,
+ ];
+
+ // -------------------------------------------------------------------
+ // 1. stateful RHS: evaluated exactly once on each needed row
+ // (the probe panics if it sees any other row)
+ // -------------------------------------------------------------------
+
+ #[test]
+ fn or_stateful_rhs_only_evaluated_on_needed_rows() {
+ let batch = batch();
+ for &s in SELECTIVITIES {
+ // `col_1 >= s OR probe`: only rows where col_1 < s need the
probe
+ let probe = Probe::new(Mode::Stateful, 0.0..s);
Review Comment:
The ten tests could be one table-driven test:
- `or_rhs_not_evaluated_when_lhs_all_true` (and its nested twin) is the `s =
0.0` entry of `SELECTIVITIES` here, since the probe panics on any unneeded row.
- The `*_with_null_lhs` tests differ only in the batch, and the `expected`
closure is repeated six times. A loop over `(mode, nested, batch)` with one
`expected` helper also adds the missing nested plus NULL case.
- `SELECTIVITIES` contains 0.1 and 0.9 twice (`PRE_SELECTION_THRESHOLD /
2.0` and `1.0 - PRE_SELECTION_THRESHOLD / 2.0`).
- `RowCountRecorder` in this module already records rows per call. A
volatile flag on it could replace most of `Probe` and its manual
`PartialEq`/`Hash`/`Display`.
- The `FailOnUnneeded` cases are plain SQL (`x = 0 OR 1 / x > 1` at a few
zero ratios, nested, NULL LHS), so they fit in `select.slt` next to the
existing query. Only the volatile row-count checks need Rust.
- Nit: `Mode::Stateful` and `or_stateful_*` are driven by
`is_volatile_node`, so `Volatile` would match `right_is_volatile`.
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -7351,4 +7435,472 @@ mod tests {
BooleanArray::from_iter(vec![Some(true), Some(true), Some(true),
Some(true)]);
assert_eq!(eq_result.into_array(4).unwrap().as_boolean(), &expected);
}
+
+ /// Tests that the right side of `OR` is only evaluated on the rows
+ /// that need it, for every selectivity (not only those that hit the
+ /// [`PRE_SELECTION_THRESHOLD`] heuristics).
+ ///
+ /// The right side is a [`Probe`] that knows which rows it is allowed to
see.
+ mod short_circuit {
+ use super::*;
+ use datafusion_common::exec_err;
+ use std::fmt::{Display, Formatter};
+ use std::hash::Hasher;
+ use std::ops::Range;
+ use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
+
+ const N: usize = 1000;
+
+ /// Fraction of rows that need the right side. Covers the extremes and
+ /// values around the threshold, so changing
[`PRE_SELECTION_THRESHOLD`]
+ /// won't make the tests irrelevant.
+ const SELECTIVITIES: &[f32] = &[
+ 0.0,
+ 0.01,
+ 0.1,
+ 0.25,
+ 0.5,
+ 0.75,
+ 0.9,
+ 0.99,
+ 1.0,
+ PRE_SELECTION_THRESHOLD / 2.0,
+ PRE_SELECTION_THRESHOLD,
+ PRE_SELECTION_THRESHOLD * 2.0,
+ 1.0 - PRE_SELECTION_THRESHOLD / 2.0,
+ 1.0 - PRE_SELECTION_THRESHOLD,
+ 1.0 - PRE_SELECTION_THRESHOLD * 2.0,
+ ];
+
+ // -------------------------------------------------------------------
+ // 1. stateful RHS: evaluated exactly once on each needed row
+ // (the probe panics if it sees any other row)
+ // -------------------------------------------------------------------
+
+ #[test]
+ fn or_stateful_rhs_only_evaluated_on_needed_rows() {
+ let batch = batch();
+ for &s in SELECTIVITIES {
+ // `col_1 >= s OR probe`: only rows where col_1 < s need the
probe
+ let probe = Probe::new(Mode::Stateful, 0.0..s);
+ let expr = or(col_1_gt_eq(s), Arc::clone(&probe) as _);
+
+ let result = evaluate(&expr, &batch).unwrap();
+
+ let expected: BooleanArray = col_1(&batch)
+ .iter()
+ .map(|v| match v {
+ // the probe returns NULL for NULL, and NULL OR NULL
is NULL
+ None => None,
+ Some(v) if v >= s => Some(true),
+ Some(v) => Some(probe_value(v)),
+ })
+ .collect();
+ assert_eq!(result, expected, "selectivity={s}");
+ assert_eq!(
+ probe.rows.load(Relaxed),
+ needed_rows(&batch, 0.0..s),
+ "selectivity={s}"
+ );
+ }
+ }
+
+ #[test]
+ fn nested_or_stateful_rhs_only_evaluated_on_needed_rows() {
+ let batch = batch();
+ for &s in SELECTIVITIES {
+ // `col_1 >= s OR (col_1 < s/2 OR probe)`:
+ // only rows where s/2 <= col_1 < s need the probe
+ let probe = Probe::new(Mode::Stateful, s / 2.0..s);
+ let expr = or(
+ col_1_gt_eq(s),
+ or(col_1_lt(s / 2.0), Arc::clone(&probe) as _),
+ );
+
+ let result = evaluate(&expr, &batch).unwrap();
+
+ let expected: BooleanArray = col_1(&batch)
+ .iter()
+ .map(|v| match v {
+ // the probe returns NULL for NULL, and NULL OR NULL
is NULL
+ None => None,
+ Some(v) if v >= s || v < s / 2.0 => Some(true),
+ Some(v) => Some(probe_value(v)),
+ })
+ .collect();
+ assert_eq!(result, expected, "selectivity={s}");
+ assert_eq!(
+ probe.rows.load(Relaxed),
+ needed_rows(&batch, s / 2.0..s),
+ "selectivity={s}"
+ );
+ }
+ }
+
+ #[test]
+ fn or_stateful_rhs_only_evaluated_on_needed_rows_with_null_lhs() {
Review Comment:
No test checks the new combine at line 1226. The probe returns NULL exactly
where `col_1` is NULL, so every NULL-LHS row computes `NULL OR NULL`, and the
scatter alone already gives that. As far as I can tell, removing the
`or_kleene` block would keep all new tests green, although `NULL OR false` must
be NULL and the scatter gives `false`.
Two small additions would cover it with existing infrastructure:
- In `test_or_preselection_matches_kleene`, add a nullable `c` such as
`[None, true, true, true, true, true, true, false, true, true]`. Row 0 then
hits `NULL OR false` on the mixed `d`, and the uniform `d` cases cover the
shortcut paths.
- For the retry path in `select.slt` (expected values worked out by hand,
not run):
```
statement ok
create table t2(x int, y int) as values (0, 0), (NULL, 1), (NULL, 2), (1, 1);
query B
SELECT x = 0 OR 1 / y < 1 FROM t2;
----
true
NULL
true
false
```
--
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]