Rewrite large OR chains as `IN` lists

[alamb]

Is your feature request related to a problem or challenge?

Sometimes automatic tools create queries like this (where <VAL> is a different value)

 WHERE ((tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR (tenant = '<VAL>') OR ...

DataFusion's evaluation of an OR chain is fairly slow as it evaluates the tree recursively and creates an Array for each intermediate node.

DataFusion's evaluation if IN lists is much faster (builds one hash table and then checks it), so the equivalent predicate written using IN will be much faster:

WHERE tenant IN ('<VAL>', '<VAL>', '<VAL>', '<VAL>', '<VAL>', '<VAL>', '<VAL>', '<VAL>', .....)

There is some heuristic threshold over which it is faster to evaluate using OR rather than IN

https://github.com/apache/arrow-datafusion/blob/b578c5819fc05801f2972dd427fbc13cf4773ea8/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs#L45

And DataFusion rewrites queries from IN to OR when the number of constants is too low

https://github.com/apache/arrow-datafusion/blob/b578c5819fc05801f2972dd427fbc13cf4773ea8/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs#L414-L445

There is no corresponding rule to rewrite queries from OR to IN` when the number of constants is high

Describe the solution you'd like

I would like to add a rewrite rule that rewrites queries like

WHERE ((tenant = '<VAL>') OR (tenant = '<VAL>')....

WHERE tenant = ('<VAL>', '<VAL>', ...)

When:

1. There are more than the InList threshold

Example

❯ create table foo(x int) as values (1), (2);
0 rows in set. Query took 0.080 seconds.

The OR chain is executed as is:

❯ explain select * from foo where x = 1 OR x = 2 OR x = 3 OR x = 4 OR x = 5 OR x = 6 OR x = 7 OR x = 8 OR x = 9 OR x = 10 OR x = 12 OR x = 13 OR x = 14 OR x = 15 OR x = 16 OR x = 17 OR x = 18 OR x = 19;
+---------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type     | plan                                                                                                                                                                                                                                                                                                                                                                                  |
+---------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| logical_plan  | Filter: foo.x = Int32(1) OR foo.x = Int32(2) OR foo.x = Int32(3) OR foo.x = Int32(4) OR foo.x = Int32(5) OR foo.x = Int32(6) OR foo.x = Int32(7) OR foo.x = Int32(8) OR foo.x = Int32(9) OR foo.x = Int32(10) OR foo.x = Int32(12) OR foo.x = Int32(13) OR foo.x = Int32(14) OR foo.x = Int32(15) OR foo.x = Int32(16) OR foo.x = Int32(17) OR foo.x = Int32(18) OR foo.x = Int32(19) |
|               |   TableScan: foo projection=[x]                                                                                                                                                                                                                                                                                                                                                       |
| physical_plan | CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                                                                                                                           |
|               |   FilterExec: x@0 = 1 OR x@0 = 2 OR x@0 = 3 OR x@0 = 4 OR x@0 = 5 OR x@0 = 6 OR x@0 = 7 OR x@0 = 8 OR x@0 = 9 OR x@0 = 10 OR x@0 = 12 OR x@0 = 13 OR x@0 = 14 OR x@0 = 15 OR x@0 = 16 OR x@0 = 17 OR x@0 = 18 OR x@0 = 19                                                                                                                                                             |
|               |     MemoryExec: partitions=16, partition_sizes=[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]                                                                                                                                                                                                                                                                                       |
|               |                                                                                                                                                                                                                                                                                                                                                                                       |
+---------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
2 rows in set. Query took 0.040 seconds.

This query will go much faster;

❯ explain select * from foo where x IN (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19);
+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| plan_type     | plan                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |
+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| logical_plan  | Filter: foo.x IN ([Int32(1), Int32(2), Int32(3), Int32(4), Int32(5), Int32(6), Int32(7), Int32(8), Int32(9), Int32(10), Int32(11), Int32(12), Int32(13), Int32(14), Int32(15), Int32(16), Int32(17), Int32(18), Int32(19)])                                                                                                                                                                                                                                                                                                                                                                                        |
|               |   TableScan: foo projection=[x]                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| physical_plan | CoalesceBatchesExec: target_batch_size=8192                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
|               |   FilterExec: Use x@0 IN (SET) ([Literal { value: Int32(1) }, Literal { value: Int32(2) }, Literal { value: Int32(3) }, Literal { value: Int32(4) }, Literal { value: Int32(5) }, Literal { value: Int32(6) }, Literal { value: Int32(7) }, Literal { value: Int32(8) }, Literal { value: Int32(9) }, Literal { value: Int32(10) }, Literal { value: Int32(11) }, Literal { value: Int32(12) }, Literal { value: Int32(13) }, Literal { value: Int32(14) }, Literal { value: Int32(15) }, Literal { value: Int32(16) }, Literal { value: Int32(17) }, Literal { value: Int32(18) }, Literal { value: Int32(19) }]) |
|               |     MemoryExec: partitions=16, partition_sizes=[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|               |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
+---------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
2 rows in set. Query took 0.008 seconds.

Describe alternatives you've considered

No response

Additional context

No response

[alamb]

I think this is a good first issue because it is well specified and the code can follow the existing patterns

[parkma99]

I am going work it

[parkma99]

Sorry,I think it's to hard for me.😭

[aprimadi]

@alamb can I work on this?

[alamb]

Sorry,I think it's to hard for me.😭

No worries -- thank you @parkma99 for trying!

@alamb can I work on this?

Sure -- thanks @aprimadi -- feel free!