Trivial WHERE filter not eliminated when combined with CTE

[davidhewitt]

Describe the bug

I am testing against Datafusion main (d68fca9).

With the query below I expect there to be no FilterExec because the condition is trivial x = x. But it is not eliminated.

To Reproduce

> explain with test AS (SELECT unnest(generate_series(1, 10)) as x)
select count(*) from test WHERE x = x;
+---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type     | plan                                                                                                                                                              |
+---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| logical_plan  | Projection: count(Int64(1)) AS count(*)                                                                                                                           |
|               |   Aggregate: groupBy=[[]], aggr=[[count(Int64(1))]]                                                                                                               |
|               |     SubqueryAlias: test                                                                                                                                           |
|               |       Projection:                                                                                                                                                 |
|               |         Filter: __unnest_placeholder(generate_series(Int64(1),Int64(10)),depth=1) = __unnest_placeholder(generate_series(Int64(1),Int64(10)),depth=1)             |
|               |           Unnest: lists[__unnest_placeholder(generate_series(Int64(1),Int64(10)))|depth=1] structs[]                                                              |
|               |             Projection: List([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) AS __unnest_placeholder(generate_series(Int64(1),Int64(10)))                                        |
|               |               EmptyRelation                                                                                                                                       |
| physical_plan | ProjectionExec: expr=[count(Int64(1))@0 as count(*)]                                                                                                              |
|               |   AggregateExec: mode=Final, gby=[], aggr=[count(Int64(1))]                                                                                                       |
|               |     CoalescePartitionsExec                                                                                                                                        |
|               |       AggregateExec: mode=Partial, gby=[], aggr=[count(Int64(1))]                                                                                                 |
|               |         ProjectionExec: expr=[]                                                                                                                                   |
|               |           CoalesceBatchesExec: target_batch_size=8192                                                                                                             |
|               |             FilterExec: __unnest_placeholder(generate_series(Int64(1),Int64(10)),depth=1)@0 = __unnest_placeholder(generate_series(Int64(1),Int64(10)),depth=1)@0 |
|               |               RepartitionExec: partitioning=RoundRobinBatch(8), input_partitions=1                                                                                |
|               |                 UnnestExec                                                                                                                                        |
|               |                   ProjectionExec: expr=[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as __unnest_placeholder(generate_series(Int64(1),Int64(10)))]                             |
|               |                     PlaceholderRowExec                                                                                                                            |
|               |                                                                                                                                                                   |
+---------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Expected behavior

No response

Additional context

No response

[alamb]

🤔 maybe we should add an expr simplifier rule that converts x = x to true if x is not null (because null = null would be null)

[adriangb]

But is that possible to evaluate via a simplifier? I'd think that in general we don't know that until execution time.

[alamb]

But is that possible to evaluate via a simplifier? I'd think that in general we don't know that until execution time.

we could simplify x = x to x IS NOT NULL which is likely much faster to evaluatie

[alamb]

Here is a simpler reproducer showing the x = x filter is still present and can be replaced with x IS NOT NULL:

> create table foo (x int)
as values (1), (2), (null);
0 row(s) fetched.
Elapsed 0.041 seconds.

> select * from foo;
+------+
| x    |
+------+
| 1    |
| 2    |
| NULL |
+------+
3 row(s) fetched.
Elapsed 0.002 seconds.

> select * from foo where x = x;
+---+
| x |
+---+
| 1 |
| 2 |
+---+
2 row(s) fetched.
Elapsed 0.009 seconds.


> select * from foo where x IS NOT NULL;
+---+
| x |
+---+
| 1 |
| 2 |
+---+
2 row(s) fetched.
Elapsed 0.002 seconds.

> explain select * from foo where x = x;
+---------------+-------------------------------+
| plan_type     | plan                          |
+---------------+-------------------------------+
| physical_plan | ┌───────────────────────────┐ |
|               | │    CoalesceBatchesExec    │ |
|               | │    --------------------   │ |
|               | │     target_batch_size:    │ |
|               | │            8192           │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │         FilterExec        │ |
|               | │    --------------------   │ |
|               | │      predicate: x = x     │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │       DataSourceExec      │ |
|               | │    --------------------   │ |
|               | │         bytes: 176        │ |
|               | │       format: memory      │ |
|               | │          rows: 1          │ |
|               | └───────────────────────────┘ |
|               |                               |
+---------------+-------------------------------+
1 row(s) fetched.
Elapsed 0.006 seconds.

So a sketch for the solution to this issue is:

1. Add a rule in ExprSimplifier for <expr> = <expr> --> <expr> IS NOT NULL in this match statement:

   datafusion/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

   Lines 730 to 738 in 2cd6ed9

   	Ok(match expr {
   	//
   	// Rules for Eq
   	//
   	// true = A --> A
   	// false = A --> !A
   	// null = A --> null
   	Expr::BinaryExpr(BinaryExpr {

2. Add tests in slt (perhaps like above)

[alamb]

As this now has a description and suggested implementation I think it is a good first issue for someone who wants to implement an optimization

[ding-young]

take