Support `IN` lists with more than three constants in predicates for bloom filters

[alamb]

Is your feature request related to a problem or challenge?

BloomFilter support was added in #7821 by @hengfeiyang ❤️

There is partial support for optimizing queries that have IN List predicates,. as suggested by @Ted-Jiang : #7821 (comment) and tested via https://github.com/apache/arrow-datafusion/blob/0d7cab055cb39d6df751e070af5a0bf5444e3849/datafusion/core/src/datasource/physical_plan/parquet/row_groups.rs#L1056-L1084

However, this only supports queries where there are three or fewer items in the IN list:

SELECT * 
FROM parquet_file 
WHERE col IN ('foo', 'bar', 'baz')

It only works for small numbers of constants because the current implementation only checks for predicates like col = 'foo' OR col = 'bar'. The reason this works for InLists is that with small numbers of items ( 3) are rewritten to OR chains) by this code in the optimizer:

https://github.com/apache/arrow-datafusion/blob/0d7cab055cb39d6df751e070af5a0bf5444e3849/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs#L500-L549

Thus, the the current bloom filter code will not work for queries with large numbers (more than the THRESHOLD_INLINE_INLIST) of constants in the IN list, such as

SELECT * 
FROM parquet_file 
WHERE col IN (
  'constant1',
  'constant2',
  ..,
  'constant99',
  'constant100',
)

Describe the solution you'd like

I would like the bloom filter code to directly support InListExpr and thus also support IN / NOT IN queries with large numbers of constants

In terms of implementation, after #8437 is merged and #8376 is closed, this should be a straightforward matter of:

1. Adding support in LiteralGurantee code (see Add LiteralGuarantee on columns to extract conditions required for PhysicalExpr expressions to evaluate to true #8437 )
2. Add tests in LiteralGurantee
3. Add a integration test for Bloom filters in datafusion/core/src/datasource/physical_plan/parquet/row_groups.rs

Describe alternatives you've considered

No response

Additional context

Found while I was working on #8376

[my-vegetable-has-exploded]

I'd like to have a try.

[alamb]

@my-vegetable-has-exploded -- thank you -- can you please implement it in terms of LiteralGuarantee #8437 ?

[hengfeiyang]

@alamb @my-vegetable-has-exploded I found if there are more than three values the bloomfilter also can't work.

This works

SELECT *  FROM tbl where (trace_id='3c7dbf90d1a66e3faffa344519c3bac3' OR trace_id='1' OR trace_id='2') LIMIT 150;

This doesn't works

SELECT *  FROM tbl where (trace_id='3c7dbf90d1a66e3faffa344519c3bac3' OR trace_id='1' OR trace_id='2' OR trace_id='3') LIMIT 150;

This is the same problem, because more than three values will convert OR to InList.

[my-vegetable-has-exploded]

I think we can use Short-circuit evaluation here, if left satisfy some condition, we can skip right.
https://github.com/apache/arrow-datafusion/blob/5e8b0e09228925b01c8bcc7afe448a7487347872/datafusion/core/src/datasource/physical_plan/parquet/row_groups.rs#L217-L232
If needed, I can open pr to do it. Thanks.

[alamb]

I think we can use Short-circuit evaluation here, if left satisfy some condition, we can skip right.

I am in the middle of rewriting the bloom filter implementation to be more general (see #8442).

I believe the new (not yet merged) code correctly handles predicates like where trace_id='3c7dbf90d1a66e3faffa344519c3bac3' OR trace_id='1' OR trace_id='2' OR trace_id='3'

However, the new code does not handle explicit IN expressions

This ticket was perhaps a bit over eager -- basically I recommend not changing the existing implementation as I am rewriting it.

However, if you would like to change the existing code, that is also fine, I will manage the conflicts as part of my PRs.

[my-vegetable-has-exploded]

I recommend not changing the existing implementation as I am rewriting it.

Get it.

[alamb]

The relevant PRs have been merged now, so I think it would be possible to add support to LiteralGuarantees which would automatically add support for BloomFilters (once #8442 is merged)

[my-vegetable-has-exploded]

thanks @hengfeiyang @alamb

[domyway]

if items more than 10 , it still can’t use bloom filter

[my-vegetable-has-exploded]

if items more than 10 , it still can’t use bloom filter

Can you provide an example of reproducing the problem？ Thanks.