Implement predicate pruning for not like expressions

[UBarney]

Which issue does this PR close?

• Closes Support predicate pruning for NOT LIKE expressions #14053 .

Rationale for this change

What changes are included in this PR?

For predicate col NOT LIKE 'foo%', we rewrite it as (col_min NOT LIKE 'foo%' OR col_max NOT LIKE 'foo%'). If both col_min and col_max have the prefix foo, we skip the entire row group (as we can be certain that all data in this row group has the prefix foo).

Are these changes tested?

Yes

Are there any user-facing changes?

No

[alamb]

FYI @adriangb

[adriangb]

I assume this should also work with no wildcards col not like 'foo'? Or do we optimize like expressions without wildcards into an equality check? If we don't already do that optimization we probably should 😄

[adriangb]

Love these fuzz tests! These 3 lines of code give me great confidence that this PR does the right thing 😄

[adriangb]

Just a general note, not necessarily for this PR: I do think we should somehow make these errors (also for the existing LIKE case) a bit better if there is any other reason they might be rejected? Or if this is the only reason, a more generic error might be better? I realize these errors likely never surface to users but I think it'd be unfortunate to see an error like this one when the actual reason it wasn't supported has nothing to do with it.

[UBarney]

Agree. Now it return Result<Arc<dyn PhysicalExpr>>

[adriangb]

Could you expand upon the examples here? My naive gut instinct (which I think is wrong, I tried before 😓) is that it should be able to truncate foo%bar to foo%. Maybe an example that can show what would go wrong if you tried that?

[UBarney]

Added a comment to explain why it goes wrong. Please take another look.

[adriangb]

Makes sense thanks. @findepi do you know if Trino handles this and if so does it do it in similar way?

[UBarney]

I assume this should also work with no wildcards col not like 'foo'?

Yes. add some test to demonstrate it
There's also an optimization to rewrite col not like 'foo' as col != 'foo'

> explain select * from values ('foo'), ('bar') where column1 not like 'foo';
+---------------+-------------------------------------------------------+
| plan_type     | plan                                                  |
+---------------+-------------------------------------------------------+
| logical_plan  | Filter: column1 != Utf8("foo")                        |
|               |   Values: (Utf8("foo")), (Utf8("bar"))                |
| physical_plan | CoalesceBatchesExec: target_batch_size=8192           |
|               |   FilterExec: column1@0 != foo                        |
|               |     DataSourceExec: partitions=1, partition_sizes=[1] |
|               |                                                       |
+---------------+-------------------------------------------------------+
2 row(s) fetched. 
Elapsed 0.006 seconds.