adriangb opened a new pull request, #25476: URL: https://github.com/apache/datafusion/pull/25476
## Which issue does this PR close? - Closes https://github.com/apache/datafusion/issues/25457. Part of the leaf-pushdown EPIC: https://github.com/apache/datafusion/issues/25459 ## Rationale for this change `x BETWEEN low AND high` evaluated `x` two times. A volatile `x` gives a different value each evaluation, so the query returned the wrong rows. ```sql CREATE TABLE v AS SELECT value AS a FROM generate_series(1, 100000); SELECT count(*) FROM v WHERE random() BETWEEN 0.4 AND 0.6; ``` Observed on `main` at `0e292dcbfd`: ```text +----------+ | count(*) | +----------+ | 36022 | +----------+ ``` Expected about 20000. One draw of `random()` keeps the rows with `0.4 <= r <= 0.6`. The observed 36000 is `P(r1 >= 0.4) * P(r2 <= 0.6)`, which is `0.6 * 0.6`. So each row drew two values. The plan on `main` shows the duplication: ```text > EXPLAIN SELECT count(*) FROM v WHERE random() BETWEEN 0.4 AND 0.6; logical_plan 03)----Filter: random() >= Float64(0.4) AND random() <= Float64(0.6) physical_plan 05)--------FilterExec: random() >= 0.4 AND random() <= 0.6 ``` With this PR: ```text +----------+ | count(*) | +----------+ | 20129 | +----------+ > EXPLAIN SELECT count(*) FROM v WHERE random() BETWEEN 0.4 AND 0.6; logical_plan 03)----Filter: random() BETWEEN Float64(0.4) AND Float64(0.6) physical_plan 05)--------FilterExec: random() BETWEEN 0.4 AND 0.6 ``` `NOT BETWEEN` had the same fault. It returned about 64000 rows and now returns about 80000. PostgreSQL evaluates `random() BETWEEN 0.4 AND 0.6` one time. This is unverified here, because no PostgreSQL server was available. ### Where the value was duplicated Two places expanded `BETWEEN` and each one cloned the value: 1. `SimplifyExpressions` rewrote `Expr::Between` into `a >= low AND a <= high` in `datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs`. 2. The physical planner did the same rewrite for any `Expr::Between` that reached it, in `datafusion/physical-expr/src/planner.rs`. It reused one `Arc<dyn PhysicalExpr>` for both sides, but `evaluate` still ran two times. ### Other shapes that were checked These shapes were checked with a volatile operand. Only `COALESCE` duplicates the operand in the final physical plan. The other shapes evaluate the operand one time. | Shape | Duplicates a volatile operand | | --- | --- | | `x BETWEEN low AND high` | yes, fixed here | | `x NOT BETWEEN low AND high` | yes, fixed here | | `COALESCE(x, y)` | yes, see the follow-up below | | `x IN (a, b, c)` | no, `InListExpr` holds one value expression | | `CASE x WHEN a THEN ... END` | no, `CaseExpr` evaluates the base one time | | `x IS DISTINCT FROM y` | no, a plain binary comparison | | `nullif(x, y)`, `greatest(x, y)` | no, scalar function arguments | ## What changes are included in this PR? Three commits. 1. A new `BetweenExpr` physical expression in `datafusion/physical-expr/src/expressions/between.rs`. It evaluates the value one time and compares that single result against both bounds. It also gets protobuf support, so a plan that holds it still serializes. 2. `SimplifyExpressions` keeps `BETWEEN` together when the value is volatile, and `create_physical_expr` lowers that shape to `BetweenExpr`. 3. The tests. ### Why this approach Three options were considered. - Keep `BETWEEN` unexpanded for a volatile value and give the physical planner a node that evaluates the value one time. This is the option in this PR. - Rewrite the volatile shape into some other expression that already evaluates one time. The expression language has no such form without a projection. - Add a pass that hoists a repeated volatile subexpression into a projection column, like `CommonSubexprEliminate` does for other expressions. That pass skips volatile expressions on purpose, because it cannot tell one syntactic occurrence from another. Changing it is a much larger job and it does not remove the duplication that the physical planner adds on its own. A value that is not volatile keeps the rewrite into two comparisons. The optimizer, the interval analysis and the pruning predicates all understand plain binary comparisons but not `BetweenExpr`. `create_physical_expr` is also public, and a caller that builds a filter for pruning without running the logical optimizer must keep the form that pruning understands. So the plans for every `BETWEEN` that is not volatile are unchanged. ### New public API `BetweenExpr` and the `between` builder in `datafusion_physical_expr::expressions`, plus the `PhysicalBetweenNode` protobuf message. A physical expression type is unavoidable here, because nothing in the physical expression set evaluates one value and uses it two times. The type is kept minimal: four accessors, `evaluate`, and the protobuf hooks. ## What is the testing strategy for this PR? - Unit tests in `datafusion/physical-expr/src/expressions/between.rs` for inclusive bounds, `NOT BETWEEN`, nulls, a scalar value, and the display forms. - A protobuf roundtrip test in `datafusion/proto/tests/cases/plans/filters.rs`. - `between_evaluates_a_volatile_value_one_time_per_row` in `datafusion/core/tests/user_defined/user_defined_scalar_functions.rs`. A volatile UDF counts the rows it produces values for. Over 100 rows the count must be 100. Without the fix the test fails with `evaluated the volatile value 200 times for 100 rows`. - sqllogictest cases in `datafusion/sqllogictest/test_files/expr.slt`. The row count of `random() BETWEEN 0.4 AND 0.6` over 100000 rows must be between 18000 and 22000. Two evaluations give about 36000, so the bound separates the two behaviours. `NOT BETWEEN` must be between 78000 and 82000. Two `EXPLAIN` cases pin the plan of a volatile `BETWEEN` and of a plain `BETWEEN`. Commands and results: ```text cargo test --profile ci -p datafusion-physical-expr -p datafusion-optimizer -p datafusion-proto -p datafusion-proto-models 882, 26, 1755, 17, 264, 6, 5, 13, 4 passed; 0 failed cargo test --profile ci -p datafusion --test user_defined_integration --test core_integration 1170 passed; 0 failed 91 passed; 0 failed cargo test --profile ci -p datafusion-sqllogictest --test sqllogictests 520/520 files completed, 0 failures cargo clippy --profile ci --all-targets --workspace --features "avro,integration-tests,extended_tests" -- -D warnings clean ``` No snapshot outside the new `expr.slt` block changed. ## Follow-ups `COALESCE` has the same fault through a different rewrite. `coalesce.rs::simplify` turns `coalesce(a, b)` into `CASE WHEN a IS NOT NULL THEN a ELSE b END`, which names `a` two times. The fix is not the same, because `coalesce` has no runtime kernel. `invoke_with_args` returns `internal_err!("coalesce should have been simplified to case")`, so the rewrite cannot simply be skipped. Reproduction on `main` at `0e292dcbfd`: ```sql CREATE TABLE v AS SELECT value AS a FROM generate_series(1, 100000); SELECT count(*), count(c) FROM (SELECT coalesce(nullif(floor(random() * 2), 0), -1) AS c FROM v); ``` ```text Arrow error: Invalid argument error: Column 'c' is declared as non-nullable but contains null values ``` `coalesce` returns a non-null value when its last argument is a non-null literal, so the column is declared non-nullable. The null test and the returned value are two different draws, so the result can be null. ## Are there any user-facing changes? Yes. `BETWEEN` and `NOT BETWEEN` over a volatile value now return the right rows. The `EXPLAIN` output for that shape shows `BETWEEN` instead of two comparisons. `BetweenExpr` and the `between` builder are new public API. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
