You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2023/05/16 11:03:23 UTC
[GitHub] [arrow-datafusion] alamb opened a new issue, #6363: Rewrite large OR chains as `IN` lists
alamb opened a new issue, #6363:
URL: https://github.com/apache/arrow-datafusion/issues/6363
### 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 (ten
ant = '<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
DataFusion's evaluation if IN lists is much faster (builds one hash table and then checks it). This thus predicate will be much 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
Which 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
### Describe the solution you'd like
I would like to add a rewrite rule that rewrites queries like
```sql
WHERE ((tenant = '<VAL>') OR (tenant = '<VAL>')....
```
```sql
WHERE tenant = ('<VAL>', '<VAL>', ...)
```
When:
1. There are more than the[ InList threshold](https://github.com/apache/arrow-datafusion/blob/b578c5819fc05801f2972dd427fbc13cf4773ea8/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs#L45)
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on issue #6363: Rewrite large OR chains as `IN` lists
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #6363:
URL: https://github.com/apache/arrow-datafusion/issues/6363#issuecomment-1551440244
> 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!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] jackwener closed issue #6363: Rewrite large OR chains as `IN` lists
Posted by "jackwener (via GitHub)" <gi...@apache.org>.
jackwener closed issue #6363: Rewrite large OR chains as `IN` lists
URL: https://github.com/apache/arrow-datafusion/issues/6363
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] parkma99 commented on issue #6363: Rewrite large OR chains as `IN` lists
Posted by "parkma99 (via GitHub)" <gi...@apache.org>.
parkma99 commented on issue #6363:
URL: https://github.com/apache/arrow-datafusion/issues/6363#issuecomment-1551324692
Sorry,I think it's to hard for me.ðŸ˜
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] parkma99 commented on issue #6363: Rewrite large OR chains as `IN` lists
Posted by "parkma99 (via GitHub)" <gi...@apache.org>.
parkma99 commented on issue #6363:
URL: https://github.com/apache/arrow-datafusion/issues/6363#issuecomment-1549805617
I am going work it
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on issue #6363: Rewrite large OR chains as `IN` lists
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #6363:
URL: https://github.com/apache/arrow-datafusion/issues/6363#issuecomment-1549455620
I think this is a good first issue because it is well specified and the code can follow the existing patterns
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] aprimadi commented on issue #6363: Rewrite large OR chains as `IN` lists
Posted by "aprimadi (via GitHub)" <gi...@apache.org>.
aprimadi commented on issue #6363:
URL: https://github.com/apache/arrow-datafusion/issues/6363#issuecomment-1551386597
@alamb can I work on this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org