Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: add optimization rules for bitwise operations #5422

Closed
izveigor opened this issue Feb 27, 2023 · 0 comments · Fixed by #5423
Closed

feat: add optimization rules for bitwise operations #5422

izveigor opened this issue Feb 27, 2023 · 0 comments · Fixed by #5423
Labels
enhancement New feature or request

Comments

@izveigor
Copy link
Contributor

Thanks to the issue: #1619 Arrow-datafusion decided to add bitwise operation (using the standards of postgresql db). But, an optimizer of these expressions does not exist, therefore a lot of bitwise operations execute slowly due to useless work.

I decided to solve this problem.

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Corresponding issues and pull requests:
#3430
#1619

Describe the solution you'd like
Below, there are rules, on which it is built the optimizer:
First table (null and 0):

BitwiseAnd (&) BitwiseOr (|) BitwiseXor (^) BitwiseShiftRight (>>) BitwiseShiftLeft (<<)
A & null -> null A | null -> null A ^ null -> null A >> null -> null A << null -> null
null & A -> null null | A -> null null ^ A -> null null >> A -> null null << A -> null
A & 0 -> 0 A | 0 -> A A ^ 0 -> A A >> 0 -> A A << 0 -> A
0 & A -> 0 0 | A -> A 0 ^ A -> A - -

Second table (equality):
*if A not nullable

BitwiseAnd (&) BitwiseOr (|) BitwiseXor (^) BitwiseShiftRight (>>) BitwiseShiftLeft (<<)
A & A -> A A | A -> A A ^ A -> 0 - -

Third table (bitwise not (Negative, see https://github.com/apache/arrow-datafusion/blob/main/datafusion/expr/src/expr.rs#L122-L123)):
*If A not nullable
*! - Bitwise NOT (Negative)

BitwiseAnd (&) BitwiseOr (|) BitwiseXor (^) BitwiseShiftRight (>>) BitwiseShiftLeft (<<)
!A & A -> 0 !A | A -> -1 !A ^ A -> -1 - -
A & !A -> 0 A | !A -> -1 A ^ !A -> -1 - -

Fourth table (InList):
*If B not null
*Considering Commutativity

BitwiseAnd (&) BitwiseOr (|) BitwiseXor (^) BitwiseShiftRight (>>) BitwiseShiftLeft (<<)
A & (A & B) -> (A & B) A | (A | B) -> (A | B) A ^ (A ^ B) -> B - -

Fifth table (cross values):
*Some values were taken from fourth table.
*If A and B not nullable
*Considering Commutativity

- BitwiseAnd (&) (A & B) BitwiseOr (|) (A | B) BitwiseXor (^) (A ^ B) BitwiseShiftRight (>>) (A >> B) BitwiseShiftLeft (<<) (A << B)
BitwiseAnd (&) A & (A & B) -> (A & B) A | (A & B) -> A - - -
BitwiseOr (|) A & (A | B) -> A A | (A | B) -> (A | B) - - -
BitwiseXor (^) - - A ^ (A ^ B) -> B - -
BitwiseShiftRight (>>) - - - - -
BitwiseShiftLeft (<<) - - - - -

Describe alternatives you've considered
If bitwise operations are not very popular, that PR can slightly slow down performance.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant