You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "izveigor (via GitHub)" <gi...@apache.org> on 2023/02/27 18:08:12 UTC
[GitHub] [arrow-datafusion] izveigor opened a new issue, #5422: feat: add optimization rules for bitwise operations
izveigor opened a new issue, #5422:
URL: https://github.com/apache/arrow-datafusion/issues/5422
Thanks to the issue: https://github.com/apache/arrow-datafusion/issues/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:
https://github.com/apache/arrow-datafusion/pull/3430
https://github.com/apache/arrow-datafusion/issues/1619
**Describe the solution you'd like**
Below, there are rules, on which it is built the optimizer:
**First table (null and 0):**
<table>
<thead>
<th>BitwiseAnd (&)</th>
<th>BitwiseOr (|)</th>
<th>BitwiseXor (^)</th>
<th>BitwiseShiftRight (>>)</th>
<th>BitwiseShiftLeft (<<)</th>
</thead>
<tbody>
<tr>
<td>A & null -> null</td>
<td>A | null -> null</td>
<td>A ^ null -> null</td>
<td>A >> null -> null</td>
<td>A << null -> null</td>
</tr>
<tr>
<td>null & A -> null</td>
<td>null | A -> null</td>
<td>null ^ A -> null</td>
<td>null >> A -> null</td>
<td>null << A -> null</td>
</tr>
<tr>
<td>A & 0 -> 0</td>
<td>A | 0 -> A</td>
<td>A ^ 0 -> A</td>
<td>A >> 0 -> A</td>
<td>A << 0 -> A</td>
</tr>
<tr>
<td>0 & A -> 0</td>
<td>0 | A -> A</td>
<td>0 ^ A -> A</td>
<td>-</td>
<td>-</td>
</tr>
</tbody>
</table>
**Second table (equality):**
*if A not nullable
<table>
<thead>
<th>BitwiseAnd (&)</th>
<th>BitwiseOr (|)</th>
<th>BitwiseXor (^)</th>
<th>BitwiseShiftRight (>>)</th>
<th>BitwiseShiftLeft (<<)</th>
</thead>
<tbody>
<tr>
<td>A & A -> A</td>
<td>A | A -> A</td>
<td>A ^ A -> 0</td>
<td>-</td>
<td>-</td>
</tr>
</tbody>
</table>
**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)
<table>
<thead>
<th>BitwiseAnd (&)</th>
<th>BitwiseOr (|)</th>
<th>BitwiseXor (^)</th>
<th>BitwiseShiftRight (>>)</th>
<th>BitwiseShiftLeft (<<)</th>
</thead>
<tbody>
<tr>
<td>!A & A -> 0</td>
<td>!A | A -> -1</td>
<td>!A ^ A -> -1</td>
<td>-</td>
<td>-</td>
</tr>
<tr>
<td>A & !A -> 0</td>
<td>A | !A -> -1</td>
<td>A ^ !A -> -1</td>
<td>-</td>
<td>-</td>
</tr>
</tbody>
</table>
**Fourth table (InList):**
*If B not null
*Considering Commutativity
<table>
<thead>
<th>BitwiseAnd (&)</th>
<th>BitwiseOr (|)</th>
<th>BitwiseXor (^)</th>
<th>BitwiseShiftRight (>>)</th>
<th>BitwiseShiftLeft (<<)</th>
</thead>
<tbody>
<tr>
<td>A & (A & B) -> (A & B)</td>
<td>A | (A | B) -> (A | B)</td>
<td>A ^ (A ^ B) -> B</td>
<td>-</td>
<td>-</td>
</tr>
</tbody>
</table>
**Fifth table (cross values):**
*Some values were taken from fourth table.
*If A and B not nullable
*Considering Commutativity
<table>
<thead>
<th>-</th>
<th>BitwiseAnd (&) (A & B)</th>
<th>BitwiseOr (|) (A | B)</th>
<th>BitwiseXor (^) (A ^ B)</th>
<th>BitwiseShiftRight (>>) (A >> B)</th>
<th>BitwiseShiftLeft (<<) (A << B)</th>
</thead>
<tbody>
<tr>
<td><b>BitwiseAnd (&)</b></td>
<td>A & (A & B) -> (A & B)</td>
<td>A | (A & B) -> A</td>
<td>-</td>
<td>-</td>
<td>-</td>
</tr>
<tr>
<td><b>BitwiseOr (|)</b></td>
<td>A & (A | B) -> A</td>
<td>A | (A | B) -> (A | B)</td>
<td>-</td>
<td>-</td>
<td>-</td>
</tr>
<tr>
<td><b>BitwiseXor (^)</b></td>
<td>-</td>
<td>-</td>
<td>A ^ (A ^ B) -> B</td>
<td>-</td>
<td>-</td>
</tr>
<tr>
<td><b>BitwiseShiftRight (>>)</b></td>
<td>-</td>
<td>-</td>
<td>-</td>
<td>-</td>
<td>-</td>
</tr>
<tr>
<td><b>BitwiseShiftLeft (<<)</b></td>
<td>-</td>
<td>-</td>
<td>-</td>
<td>-</td>
<td>-</td>
</tr>
</tbody>
</table>
**Describe alternatives you've considered**
If bitwise operations are not very popular, that PR can slightly slow down performance.
--
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 closed issue #5422: feat: add optimization rules for bitwise operations
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #5422: feat: add optimization rules for bitwise operations
URL: https://github.com/apache/arrow-datafusion/issues/5422
--
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