Support "pre-image" for pruning predicate evaluation

[alamb]

Is your feature request related to a problem or challenge?

As mentioned in #18319, it is much easier for optimizers to reason about predicates of the form <col> op <constant> expressions. They often can't optimize anywhere near as well if they have a scalar function wrapping them

This includes DataFusion's PruningPredicate

For example the predicate looking for a particular year

WHERE EXTRACT (YEAR FROM k) = 2024

Can be rewritten as

k >= 2024-01-01 AND k < 2025-01-01.

And then k is easier to pushdown and subject to range analysis, etc.

The ClickHouse paper : https://www.vldb.org/pvldb/vol17/p3731-schulze.pdf calles these "preimage" (from the mathematical term) for this rewrite (I think toYear(k) is the equivalent of EXTRACT(YEAR from k))

Second, some functions can compute the preimage of a given function result. This is used to replace comparisons of constants with function calls on the key columns by comparing the key column value with the preimage. For example, toYear(k) = 2024 can be replaced by k >= 2024-01-01 && k < 2025-01-01.

Describe the solution you'd like

I would like DataFusion to do this rewrite too

Describe alternatives you've considered

This might be possible to do by implementing ScalarUDFImpl::simplify for date_part 👍
https://github.com/apache/datafusion/blob/main/datafusion/functions/src/datetime/date_part.rs

Additional context

No response

[sdf-jkl]

take

[sdf-jkl]

Hey @alamb, I don't think this can be implemented using ScalarUDFImpl::simplify, since this simplification is on the predicate expression side. The solution can be something like unwrap_cast for date_part within simplify expressions framework, like you mentioned in #18319.

[sdf-jkl]

@alamb, I checked the clickhouse implementation of preimage and they only support the toYear and toYYYYMM functions.

The duckdb date_part_simplification is similar to ScalarUDF::simplify - it does not actually simplify the predicate expression like the date_trunc pr you mentioned.

We can only support date_part('year', col) simplification/preimage in DataFusion.

What kind of function simplification support do we have in DataFusion in general?

I think we can extend ScalarUDF API to add another function(or extend ScalarUDF::simplify).

Something like simplify_predicate_function(info, args, op, const) to try to move the function call to the right side of the predicate expression:

func(<col>) op <constant> -> <col> op func(<constant>)/(<col> >= <constant> and <col> < <constant+1>)`

[alamb]

What kind of function simplification support do we have in DataFusion in general?

We have a pretty substantial simplification library here https://github.com/apache/datafusion/tree/main/datafusion/optimizer/src/simplify_expressions

Something like simplify_predicate_function(info, args, op, const) to try to move the function call to the right side of the predicate expression:

Maybe we could extend this:
https://github.com/apache/datafusion/blob/main/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

[adriangb]

Perhaps related: I had a TODO to make an issue to port duckdb/duckdb#18457

[sdf-jkl]

Perhaps related: I had a TODO to make an issue to port duckdb/duckdb#18457

• Optimize the evaluation of DATE_TRUNC(<col>) == <constant>) when pushed down #18319 ?