Weijun-H commented on code in PR #26589:
URL: https://github.com/apache/datafusion/pull/26589#discussion_r4581490626
##########
datafusion/physical-expr/src/expressions/case.rs:
##########
@@ -259,16 +428,54 @@ struct ProjectedCaseBody {
}
impl ProjectedCaseBody {
- /// Returns a projection when evaluating the derived body can avoid unused
input columns.
- fn projection_for(&self, batch: &RecordBatch) -> Option<Vec<usize>> {
+ /// Returns the batch to evaluate the derived body against, when doing so
can avoid
+ /// filtering unused input columns.
+ fn project_batch(&self, batch: &RecordBatch) ->
Result<Option<RecordBatch>> {
+ if !self.supports_projection {
+ return Ok(None);
+ }
let projection = self
.projection
.iter()
.copied()
.filter(|index| *index < batch.num_columns())
.collect::<Vec<_>>();
- (self.supports_projection && projection.len() < batch.num_columns())
- .then_some(projection)
+ if self.precomputed.is_empty() {
+ return if projection.len() < batch.num_columns() {
+ Ok(Some(batch.project(&projection)?))
+ } else {
+ Ok(None)
+ };
+ }
+
+ let schema = batch.schema();
+ let mut fields = Vec::with_capacity(projection.len() +
self.precomputed.len());
+ let mut columns = Vec::with_capacity(fields.capacity());
+ for index in projection {
+ fields.push(Arc::clone(&schema.fields()[index]));
+ columns.push(Arc::clone(batch.column(index)));
+ }
+ for expr in &self.precomputed {
+ let column = expr.evaluate(batch)?.into_array(batch.num_rows())?;
+ // The array may not match the plan-time field exactly (nested
nullability or
+ // metadata); only the expressions in the body read this schema.
+ let field = expr.return_field(&schema)?;
+ let nullable = field.is_nullable() || column.null_count() > 0;
+ fields.push(Arc::new(
+ field
+ .as_ref()
+ .clone()
+ .with_data_type(column.data_type().clone())
+ .with_nullable(nullable),
+ ));
+ columns.push(column);
+ }
+ let options =
RecordBatchOptions::new().with_row_count(Some(batch.num_rows()));
+ Ok(Some(RecordBatch::try_new_with_options(
+ Arc::new(Schema::new_with_metadata(fields,
schema.metadata().clone())),
Review Comment:
The tests do not assert metadata preservation. Could an existing precompute
test add schema metadata and assert it on the `project_batch` output?
##########
datafusion/physical-expr/src/expressions/case.rs:
##########
@@ -1209,10 +1412,9 @@ impl CaseExpr {
)?))
}
}
- } else if let Some(projection) = projected.projection_for(batch) {
+ } else if let Some(projected_batch) = projected.project_batch(batch)? {
Review Comment:
With a single `WHEN` and mixed true/false rows, the `WHEN` was already
evaluated on the full batch above, but its candidates are precomputed again
here and filtered into both branches without being read. For `CASE WHEN s['a']
> 1 THEN x ELSE y END`, `s['a']` is computed twice. Could this path precompute
only what `THEN`/`ELSE` read? Fine as a follow-up.
##########
datafusion/physical-expr/src/expressions/case.rs:
##########
@@ -118,41 +155,80 @@ struct CaseBody {
impl CaseBody {
/// Derives a [ProjectedCaseBody] from this [CaseBody].
- fn project(&self) -> Result<ProjectedCaseBody> {
- // Determine the set of columns that are used in all the expressions
of the case body.
+ fn project(&self, schema: &Schema) -> Result<ProjectedCaseBody> {
+ // Lambda bodies are evaluated against batches of a different shape, so
+ // expressions are only precomputed when the body contains no lambdas.
+ let can_precompute = !self.exprs().any(|e| {
Review Comment:
This guard has no test. In `CASE WHEN s['a'] > 1 THEN array_transform(arr, v
-> v + 1) WHEN s['a'] = 0 THEN [] END` over `[arr, s]`, the lambda variable `v`
(index 2) takes a slot in the renumbering but is filtered out of the projected
batch, so without the guard `s['a']` would be rewritten to column 2 while it
lands at column 1. A projection test on this shape asserting nothing is
precomputed would cover it.
##########
datafusion/physical-expr/src/expressions/case.rs:
##########
@@ -2060,6 +2270,454 @@ mod tests {
Ok(())
}
+ /// A batch with columns `x: Int32` and `s: Struct<a: Int32, b: Int32, c:
Utf8>`.
+ fn case_test_batch_with_struct() -> Result<RecordBatch> {
+ let struct_array = StructArray::from(vec![
+ (
+ Arc::new(Field::new("a", DataType::Int32, true)),
+ Arc::new(Int32Array::from(vec![Some(1), Some(2), None,
Some(4)]))
+ as ArrayRef,
+ ),
+ (
+ Arc::new(Field::new("b", DataType::Int32, true)),
+ Arc::new(Int32Array::from(vec![10, 20, 30, 40])) as ArrayRef,
+ ),
+ (
+ Arc::new(Field::new("c", DataType::Utf8, true)),
+ Arc::new(StringArray::from(vec!["p", "q", "r", "s"])) as
ArrayRef,
+ ),
+ ]);
+ let schema = Schema::new(vec![
+ Field::new("x", DataType::Int32, true),
+ Field::new("s", struct_array.data_type().clone(), true),
+ ]);
+ Ok(RecordBatch::try_new(
+ Arc::new(schema),
+ vec![
+ Arc::new(Int32Array::from(vec![100, 200, 300, 400])),
+ Arc::new(struct_array),
+ ],
+ )?)
+ }
+
+ fn get_field_expr(
+ base: Arc<dyn PhysicalExpr>,
+ name: &str,
+ schema: &Schema,
+ ) -> Result<Arc<dyn PhysicalExpr>> {
+ Ok(Arc::new(ScalarFunctionExpr::try_new(
+ datafusion_functions::core::get_field(),
+ vec![base, lit(name)],
+ schema,
+ Arc::new(ConfigOptions::default()),
+ )?))
+ }
+
+ /// Building and evaluating a nested `CASE` must not be exponential in the
nesting
+ /// depth when each level reads a different field.
+ #[test]
+ fn nested_case_with_distinct_struct_fields() -> Result<()> {
+ let fields = (0..=40)
+ .map(|i| Field::new(format!("f{i}"), DataType::Int32, true))
+ .collect::<Vec<_>>();
+ let columns = (0..=40)
+ .map(|i| Arc::new(Int32Array::from(vec![i, i + 1])) as ArrayRef)
+ .collect::<Vec<_>>();
+ let s = StructArray::new(fields.into(), columns, None);
+ let schema = Arc::new(Schema::new(vec![Field::new(
+ "s",
+ s.data_type().clone(),
+ true,
+ )]));
+ let batch = RecordBatch::try_new(Arc::clone(&schema),
vec![Arc::new(s)])?;
+
+ let s = col("s", &schema)?;
+ let mut expr = get_field_expr(Arc::clone(&s), "f0", &schema)?;
+ for i in 1..=40 {
+ let when = binary(
+ get_field_expr(Arc::clone(&s), &format!("f{i}"), &schema)?,
+ Operator::Eq,
+ lit(-1i32),
+ &schema,
+ )?;
+ expr = Arc::new(CaseExpr::try_new(
+ None,
+ vec![(when, lit(1i32))],
+ Some(expr),
+ )?);
+ }
+
+ let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
+ assert_eq!(as_int32_array(&result)?, &Int32Array::from(vec![0, 1]));
+ Ok(())
+ }
+
+ /// A batch with a column `s: Struct<a: Int32, m: Map<Utf8, Int32>>`.
+ fn case_test_batch_with_struct_map() -> Result<RecordBatch> {
+ let mut map_builder =
+ MapBuilder::new(None, StringBuilder::new(), Int32Builder::new());
+ for (key, value) in [("k", 1), ("k", 2), ("j", 3)] {
+ map_builder.keys().append_value(key);
+ map_builder.values().append_value(value);
+ map_builder.append(true)?;
+ }
+ let map_array = map_builder.finish();
+ let struct_array = StructArray::from(vec![
+ (
+ Arc::new(Field::new("a", DataType::Int32, true)),
+ Arc::new(Int32Array::from(vec![1, 2, 3])) as ArrayRef,
+ ),
+ (
+ Arc::new(Field::new("m", map_array.data_type().clone(), true)),
+ Arc::new(map_array) as ArrayRef,
+ ),
+ ]);
+ let schema = Schema::new(vec![Field::new(
+ "s",
+ struct_array.data_type().clone(),
+ true,
+ )]);
+ Ok(RecordBatch::try_new(
+ Arc::new(schema),
+ vec![Arc::new(struct_array)],
+ )?)
+ }
+
+ /// `CASE WHEN s['a'] = 1 THEN <then> WHEN s['a'] = 2 THEN <then> END`
+ fn case_with_struct_map_lookup(
+ then: Arc<dyn PhysicalExpr>,
+ schema: &Schema,
+ ) -> Result<CaseExpr> {
+ let s_a = get_field_expr(col("s", schema)?, "a", schema)?;
+ CaseExpr::try_new(
+ None,
+ vec![
+ (
+ binary(Arc::clone(&s_a), Operator::Eq, lit(1i32), schema)?,
+ Arc::clone(&then),
+ ),
+ (binary(s_a, Operator::Eq, lit(2i32), schema)?, then),
+ ],
+ None,
+ )
+ }
+
+ #[test]
+ fn case_does_not_precompute_flat_map_lookup() -> Result<()> {
+ let batch = case_test_batch_with_struct_map()?;
+ let schema = batch.schema();
+
+ // get_field(s, 'm', 'k')
+ let s_m_k: Arc<dyn PhysicalExpr> =
Arc::new(ScalarFunctionExpr::try_new(
+ datafusion_functions::core::get_field(),
+ vec![col("s", &schema)?, lit("m"), lit("k")],
+ &schema,
+ Arc::new(ConfigOptions::default()),
+ )?);
+ let expr = case_with_struct_map_lookup(s_m_k, &schema)?;
+
+ match &expr.eval_method {
+ EvalMethod::NoExpression(projected) => {
+ let projected = projected.project(&expr.body, &schema)?;
+ assert!(projected.supports_projection);
+ assert_eq!(projected.projection, vec![0]);
+ assert!(projected.precomputed.is_empty());
+ }
+ method => panic!("expected NoExpression, got {method:?}"),
+ }
+
+ let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
+ assert_eq!(
+ as_int32_array(&result)?,
+ &Int32Array::from(vec![Some(1), Some(2), None])
+ );
+ Ok(())
+ }
+
+ #[test]
+ fn case_precomputes_map_base_of_nested_lookup() -> Result<()> {
+ let batch = case_test_batch_with_struct_map()?;
+ let schema = batch.schema();
+ let s = col("s", &schema)?;
+ let s_a = get_field_expr(Arc::clone(&s), "a", &schema)?;
+ let s_m = get_field_expr(s, "m", &schema)?;
+
+ // get_field(get_field(s, 'm'), 'k')
+ let s_m_k = get_field_expr(Arc::clone(&s_m), "k", &schema)?;
+ let expr = case_with_struct_map_lookup(s_m_k, &schema)?;
+
+ match &expr.eval_method {
+ EvalMethod::NoExpression(projected) => {
+ let projected = projected.project(&expr.body, &schema)?;
+ assert!(projected.supports_projection);
+ assert!(projected.projection.is_empty());
+ assert_eq!(projected.precomputed, vec![s_a, s_m]);
+ }
+ method => panic!("expected NoExpression, got {method:?}"),
+ }
+
+ let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
+ assert_eq!(
+ as_int32_array(&result)?,
+ &Int32Array::from(vec![Some(1), Some(2), None])
+ );
+ Ok(())
+ }
+
+ /// The plan may declare a struct column non-nullable while the batch has
null
+ /// structs, which makes the precomputed fields nullable.
+ #[test]
+ fn case_precomputes_fields_of_null_structs_declared_non_nullable() ->
Result<()> {
+ let fields = arrow::datatypes::Fields::from(vec![
+ Field::new("a", DataType::Int32, false),
+ Field::new("b", DataType::Int32, false),
+ ]);
+ let struct_array = StructArray::new(
+ fields.clone(),
+ vec![
+ Arc::new(Int32Array::from(vec![1, 2, 3])),
+ Arc::new(Int32Array::from(vec![10, 20, 30])),
+ ],
+ Some(arrow::buffer::NullBuffer::from(vec![true, true, false])),
+ );
+ let batch_schema = Arc::new(Schema::new(vec![Field::new(
+ "s",
+ DataType::Struct(fields.clone()),
+ true,
+ )]));
+ let batch = RecordBatch::try_new(batch_schema,
vec![Arc::new(struct_array)])?;
+ let plan_schema =
+ Schema::new(vec![Field::new("s", DataType::Struct(fields),
false)]);
+
+ let s = col("s", &plan_schema)?;
+ let s_a = get_field_expr(Arc::clone(&s), "a", &plan_schema)?;
+ let s_b = get_field_expr(s, "b", &plan_schema)?;
+
+ // CASE WHEN s['a'] = 1 THEN s['b'] WHEN s['a'] > 1 THEN 0 END
+ let expr = CaseExpr::try_new(
+ None,
+ vec![
+ (
+ binary(Arc::clone(&s_a), Operator::Eq, lit(1i32),
&plan_schema)?,
+ Arc::clone(&s_b),
+ ),
+ (
+ binary(Arc::clone(&s_a), Operator::Gt, lit(1i32),
&plan_schema)?,
+ lit(0i32),
+ ),
+ ],
+ None,
+ )?;
+
+ match &expr.eval_method {
+ EvalMethod::NoExpression(projected) => {
+ let projected = projected.project(&expr.body, &plan_schema)?;
+ assert_eq!(projected.precomputed, vec![s_a, s_b]);
+ }
+ method => panic!("expected NoExpression, got {method:?}"),
+ }
+
+ let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
+ assert_eq!(
+ as_int32_array(&result)?,
+ &Int32Array::from(vec![Some(10), Some(0), None])
+ );
+ Ok(())
+ }
+
+ #[test]
+ fn case_without_expr_precomputes_struct_fields() -> Result<()> {
+ let batch = case_test_batch_with_struct()?;
+ let schema = batch.schema();
+ let s = col("s", &schema)?;
+ let s_a = get_field_expr(Arc::clone(&s), "a", &schema)?;
+ let s_b = get_field_expr(Arc::clone(&s), "b", &schema)?;
+
+ // CASE WHEN s['a'] = 1 THEN s['b'] WHEN s['a'] > 1 THEN x ELSE s['a']
END
+ let expr = CaseExpr::try_new(
+ None,
+ vec![
+ (
+ binary(Arc::clone(&s_a), Operator::Eq, lit(1i32),
&schema)?,
+ Arc::clone(&s_b),
+ ),
+ (
+ binary(Arc::clone(&s_a), Operator::Gt, lit(1i32),
&schema)?,
+ col("x", &schema)?,
+ ),
+ ],
+ Some(Arc::clone(&s_a)),
+ )?;
+
+ match &expr.eval_method {
+ EvalMethod::NoExpression(projected) => {
+ let projected = projected.project(&expr.body, &schema)?;
+ assert!(projected.supports_projection);
+ assert_eq!(projected.projection, vec![0]);
+ assert_eq!(projected.precomputed, vec![s_a, s_b]);
+ }
+ method => panic!("expected NoExpression, got {method:?}"),
+ }
+
+ let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
+ let result = as_int32_array(&result)?;
+ let expected = Int32Array::from(vec![Some(10), Some(200), None,
Some(400)]);
+ assert_eq!(&expected, result);
+ Ok(())
+ }
+
+ #[test]
+ fn case_with_expr_precomputes_struct_fields() -> Result<()> {
+ let batch = case_test_batch_with_struct()?;
+ let schema = batch.schema();
+ let s = col("s", &schema)?;
+ let s_a = get_field_expr(Arc::clone(&s), "a", &schema)?;
+ let s_c = get_field_expr(Arc::clone(&s), "c", &schema)?;
+
+ // CASE s['a'] WHEN 1 THEN s['c'] WHEN 4 THEN 'four' END
+ let expr = CaseExpr::try_new(
+ Some(Arc::clone(&s_a)),
+ vec![(lit(1i32), Arc::clone(&s_c)), (lit(4i32), lit("four"))],
+ None,
+ )?;
+
+ match &expr.eval_method {
+ EvalMethod::WithExpression(projected) => {
+ let projected = projected.project(&expr.body, &schema)?;
+ assert!(projected.supports_projection);
+ assert!(projected.projection.is_empty());
+ assert_eq!(projected.precomputed, vec![s_a, s_c]);
+ }
+ method => panic!("expected WithExpression, got {method:?}"),
+ }
+
+ let result = expr.evaluate(&batch)?.into_array(batch.num_rows())?;
+ let result = as_string_array(&result);
+ let expected = StringArray::from(vec![Some("p"), None, None,
Some("four")]);
+ assert_eq!(&expected, result);
+ Ok(())
+ }
+
+ #[test]
+ fn case_expr_or_expr_precomputes_struct_fields() -> Result<()> {
+ let batch = case_test_batch_with_struct()?;
+ let schema = batch.schema();
+ let s = col("s", &schema)?;
+ let s_a = get_field_expr(Arc::clone(&s), "a", &schema)?;
+ let s_b = get_field_expr(Arc::clone(&s), "b", &schema)?;
+
+ // CASE WHEN s['a'] > 1 THEN s['b'] / s['a'] ELSE x END
+ let expr = CaseExpr::try_new(
+ None,
+ vec![(
+ binary(Arc::clone(&s_a), Operator::Gt, lit(1i32), &schema)?,
+ binary(
+ Arc::clone(&s_b),
+ Operator::Divide,
Review Comment:
`s_a` is never zero here, so this doesn't show the division stays inside the
branch. `s_b / (s_a - 1)` puts a zero denominator on the unselected first row;
the expected result becomes `[100, 20, 300, 13]`.
##########
datafusion/physical-expr/src/expressions/case.rs:
##########
@@ -211,10 +302,79 @@ impl CaseBody {
Ok(ProjectedCaseBody {
projection,
+ precomputed: precomputed.into_iter().collect(),
body: projected_body,
supports_projection,
})
}
+
+ /// Iterates over all the top-level expressions of this case body.
+ fn exprs(&self) -> impl Iterator<Item = &Arc<dyn PhysicalExpr>> {
+ self.expr
+ .iter()
+ .chain(self.when_then_expr.iter().flat_map(|(w, t)| [w, t]))
+ .chain(self.else_expr.iter())
+ }
+}
+
+/// Returns true if `expr` is a cheap, non-volatile expression over columns
and literals,
+/// such as a struct field access, that can be evaluated for the whole input
batch ahead of
+/// the `CASE` branches.
+///
+/// Expressions with [`ExpressionPlacement::MoveTowardsLeafNodes`] placement
may be pushed
Review Comment:
Question: the `MoveTowardsLeafNodes` docs say cheap and pushable to leaves,
but not that the expression is safe to evaluate on rows a `CASE` branch does
not select. A custom non-volatile expression with this placement that errors on
some values would now be evaluated for every row, e.g. `CASE WHEN x > 0 THEN
checked(y) WHEN x < -100 THEN 0 END` with `x = -1, y = 0` returns NULL on main
but errors here (from reading the code, not run). Should this be limited to
`get_field`, or should the placement docs state the requirement?
##########
datafusion/sqllogictest/test_files/case.slt:
##########
@@ -1016,3 +1016,65 @@ FROM (VALUES ('abc')) t(s);
statement ok
DROP VIEW guarded_cast;
+
+# Struct field accesses in CASE branches are evaluated ahead of the branches,
+# while fallible branch expressions over them are still guarded.
+statement ok
+CREATE TABLE struct_case AS VALUES
+ (1, named_struct('a', 0, 'b', 'zero', 'l', [named_struct('x', 1)])),
+ (2, named_struct('a', 2, 'b', 'two', 'l', [named_struct('x', 2)])),
+ (3, named_struct('a', NULL, 'b', 'null', 'l', NULL)),
+ (4, named_struct('a', 5, 'b', 'five', 'l', [])),
+ (5, NULL);
+
+query IT?I
+SELECT column1,
+ CASE WHEN column2['a'] = 0 THEN column2['b']
+ WHEN column2['a'] > 1 THEN upper(column2['b'])
+ ELSE 'other' END,
+ CASE column2['a'] WHEN 2 THEN column2['l'] WHEN 5 THEN
[named_struct('x', 5)] END,
+ CASE WHEN column2['a'] <> 0 THEN 10 / column2['a'] ELSE column1 END
+FROM struct_case
+ORDER BY column1;
+----
+1 zero NULL 1
+2 TWO [{x: 2}] 5
+3 other NULL 3
+4 FIVE [{x: 5}] 2
+5 other NULL 5
+
+# A struct used as a whole alongside its fields
+query I?
+SELECT column1,
+ CASE WHEN column2['a'] = 2 THEN column2 WHEN column2['a'] = 5 THEN NULL
END
+FROM struct_case
+ORDER BY column1;
+----
+1 NULL
+2 {a: 2, b: two, l: [{x: 2}]}
+3 NULL
+4 NULL
+5 NULL
+
+statement ok
+DROP TABLE struct_case;
+
+# Map lookups are not evaluated ahead of the branches: they may fail for rows
+# that no branch selects
+statement ok
+create table mt as values (1, map(['a', 'b'], [10, 20])), (2, map(['c'],
[30]));
+
+query I
+SELECT CASE WHEN column1 < 0 THEN column2[7] WHEN column1 > 100 THEN
column2[8] ELSE 0 END FROM mt
+----
+0
+0
+
+query I
+SELECT CASE WHEN column1 < 0 THEN column2['a'] WHEN column1 > 100 THEN
column2['b'] ELSE 0 END FROM mt
Review Comment:
No row selects either branch, so this never performs a lookup and is already
covered by the query above. Selecting rows, e.g. `WHEN column1 = 1 THEN
column2['a'] WHEN column1 = 2 THEN column2['c'] ELSE 0` (expecting `10`, `30`),
would check normal lookups after the exclusion.
--
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]