You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "sunchao (via GitHub)" <gi...@apache.org> on 2023/01/27 18:18:30 UTC
[GitHub] [arrow-rs] sunchao opened a new issue, #3620: Implement short-circuiting for filter evaluation
sunchao opened a new issue, #3620:
URL: https://github.com/apache/arrow-rs/issues/3620
**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
<!--
A clear and concise description of what the problem is. Ex. I'm always frustrated when [...]
(This section helps Arrow developers understand the context and *why* for this feature, in addition to the *what*)
-->
Currently for common expressions such as `AND` or `OR`, we don't apply any short-circuiting and therefore the same columnar batch need to be fully evaluated on every predicate.
For instance, consider an expression:
```sql
a = 'FOO' AND b = 42
```
We would evaluate each batch on both predicates, and apply bit-and on the result `BooleanArray` from both side. Similarly for `OR`.
This would not be efficient in many cases, nor correct (see https://github.com/apache/arrow-datafusion/issues/5093 for a bug report). A more efficient approach, is perhaps to only apply the second predicate on the **remaining rows** from the evaluation of the first predicate. This could be especially effective if the first predicate has low selectivity.
Note, sometimes it would still be beneficial to evaluate the full batch to take advantage of SIMD. For a detailed analysis, please check https://dl.acm.org/doi/abs/10.1145/3465998.3466009.
This approach has been adopted by other popular engines such as Velox, Databricks Photon, etc.
**Describe the solution you'd like**
<!--
A clear and concise description of what you want to happen.
-->
Implement the short-circuiting logic in both `arrow-rs` and `arrow-datafusion`. This could introduce a lot of API changes since we may need to introduce an extra parameter `SelectivityVector` for related compute kernels (e.g., `is_null`). We also need to change `arrow-datafusion`'s [`PhysicalExpr::evaluate`](https://github.com/apache/arrow-datafusion/blob/master/datafusion/physical-expr/src/physical_expr.rs#L47) to take the `SelectivityVector` into account. Note similar features has been done for `CASE WHEN` with the introduction of a separate `evaluate_selection` method. See https://github.com/apache/arrow-datafusion/pull/2068 for more details.
**Describe alternatives you've considered**
<!--
A clear and concise description of any alternative solutions or features you've considered.
-->
N/A
**Additional context**
<!--
Add any other context or screenshots about the feature request here.
-->
N/A
--
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-rs] alamb commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591204643
> the exact same principle also holds for null masks
I think they are "almost always" the same. For example the (non null) values of [`or_kleen`](https://docs.rs/arrow/latest/arrow/compute/fn.or_kleene.html)'s depend on the null values of its input
However, it is an excellent point that for many kernels, the implementation is probably exactly the same after "AND"ing together the validity mask and selection vector.
--
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-rs] alamb commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591205217
Related discussion: https://github.com/apache/arrow-rs/pull/4393#issuecomment-1590979057
--
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
Re: [I] Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-2284167073
> Now the potentially interesting observation is the exact same principle also holds for null masks, we shouldn't spend time performing expensive evaluation on null slots. I think we currently do in some cases, but this should be easy to fix.
This was a prescient comment. Here's also a recent (DaMoN 2024) evaluation of NULL representations:
"NULLS! Revisiting Null Representation in Modern Columnar Formats"
https://db.cs.cmu.edu/papers/2024/zeng-damon24.pdf
--
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-rs] tustvold commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591072494
Thinking about this a bit more, the intention of a selection vector is to allow a kernel to skip an expensive computation, such as a string comparison or regex evaluation, when **the result is unimportant because we know it is going to be discarded**. For some kernels the cost of consulting the selection vector will outweigh any savings, especially for kernels like integer comparison where it interferes with vectorisation.
Now the potentially interesting observation is the exact same principle also holds for null masks, we shouldn't spend time performing expensive evaluation on null slots. I think we currently do in some cases, but this should be easy to fix.
This then leads to the obvious question, if a false value in a selection vector indicates that the result doesn't matter, how would the semantics of an operation under a selection vector differ from the semantics of an operation with the arrays first passed to [`nullif`](https://docs.rs/arrow-select/latest/arrow_select/nullif/fn.nullif.html) with the selection vector. As the result is irrelevant, why would its null-ness matter?
--
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-rs] tustvold commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1407009615
> how do you detect whether certain code change would break SIMD
I tend use godbolt with mocked up functions a lot, and then confirm any changes with benchmarks. Very occasionally I use gdb to disassemble symbols, as certain things like inlining heuristics are hard to mock up
--
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-rs] alamb commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1503415765
Here is a discussion in DataFusion about something similar: https://github.com/apache/arrow-datafusion/issues/5944
--
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-rs] alamb commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591269120
What about something like this (where you conditionally generate an error if the row is included in the computation)?
```sql
CASE
WHEN x IS NOT NULL
THEN x
ELSE x / 0 -- <--- should never be hit / error
END
```
--
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-rs] alamb commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1407430459
> For example, late materialization with support for a form of this short-circuiting, was recently added to the parquet reader. We could theoretically build upon this base, without needing to make more intrusive modifications.
I believe this refers to https://docs.rs/parquet/31.0.0/parquet/arrow/arrow_reader/struct.RowSelector.html and https://docs.rs/parquet/31.0.0/parquet/arrow/arrow_reader/struct.RowSelection.html
--
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-rs] sunchao commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1406991366
Thanks @tustvold !
Yes, I think it's a good idea to start with a PoC in DataFusion only. I'll try to see if we can get some good numbers with the approach using some synthetic benchmarks :)
One question: how do you detect whether certain code change would break SIMD? is there any convenient way of doing that?
I'll take a look at the lazy materialization on Parquet side and see how it can interact with this feature.
> I think it would be really cool to support this, but my experience fighting LLVM over null masks, the speed of the filter kernels, and the reality that a lot of queries end up bottlenecked on sorting or decoding, makes me think there may be mileage in the naive approach. I'm not expert on query engines though, so happy to defer to others 😄
Agree. My feeling is also that many queries are actually bottlenecked on somewhere else like join or aggregation. It just caught my attention while I'm looking at DataFusion and `arrow-rs`.
--
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-rs] tustvold commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591290859
> where you conditionally generate an error if the row is included in the computation
I think you would need something that would side-effect for nulls in order to cause an issue for the approach of encoding the selection vector as a null mask. I'm struggling to think of a kernel within arrow-rs where this would be the case...
--
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-rs] viirya commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "viirya (via GitHub)" <gi...@apache.org>.
viirya commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1407114988
I think `cargo asm` can be used to check the resulting assembly to check if SIMD is applied.
--
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-rs] tustvold commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591214105
> For example the (non null) values of [or_kleen](https://docs.rs/arrow/latest/arrow/compute/fn.or_kleene.html)'s depend on the null values of its input
A value not being in the selection mask implies **it is going to be discarded regardless of the output of the current kernel**. I'm therefore not sure why it would ever matter? What am I missing here?
--
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-rs] alamb commented on issue #3620: Evaluate Kernel under Selection / Short-Circuiting Filter Evaluation
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1591262673
> A value not being in the selection mask implies it is going to be discarded regardless of the output of the current kernel. I'm therefore not sure why it would ever matter? What am I missing here?
Correct -- I thought you were asking if there were semantic differences between a selection vector and a null mask and so I was providing an example where there would be. I probably misunderstood this:
> This then leads to the obvious question, if a false value in a selection vector indicates that the result doesn't matter, how would the semantics of an operation under a selection vector differ from the semantics of an operation with the arrays first passed to [nullif](https://docs.rs/arrow-select/latest/arrow_select/nullif/fn.nullif.html) with the selection vector. As the result is irrelevant, why would its null-ness matter?
--
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-rs] jhorstmann commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "jhorstmann (via GitHub)" <gi...@apache.org>.
jhorstmann commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1408245376
This paper about [Fused Table Scans](https://hpi.de/plattner/projects/hyrise/Document/import_epic/fused_table_scans.pdf/034329e1cb81f93285fe60dc9fbdd0fc.html?cHash=a824b24b878effff04018ba05d1095b0) describes a vectorized implementation of evaluating two predicates more efficiently. The first predicate is evaluted into indices instead of a bitmap, these indices are then used to gather data into simd registers for the second predicate.
The improvement probably depends on the selectivity of the first predicate and doing this optimally would require some statistics about the input arrays.
--
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-rs] tustvold commented on issue #3620: Implement short-circuiting for filter evaluation
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on issue #3620:
URL: https://github.com/apache/arrow-rs/issues/3620#issuecomment-1406951690
One thing to perhaps be aware of is that we are entirely reliant on LLVM to vectorise various kernels. I have found that _any_ branch in the body of the loop, even something as simple as `Iterator::next`, causes it to fail to vectorise the loop.
This has led to a number of tricks such as `PrimitiveArray::unary` and `MutableBuffer::collect_bool` that help it vectorise correctly, by ignoring the null mask. I suspect a selection vector would run into similar challenges. Whilst I don't doubt that custom SIMD kernels could apply selection masks and null masks "for free", I have not found a good way to get LLVM to figure this out.
As such I wonder if a first step might be to implement this solely within DataFusion, in particular using the `filter` kernel to eagerly apply the selection to the values if the next expression is not side-effect free, or if selectivity has fallen below some threshold? We can then go from there if this filtering starts to become a major bottleneck?
This would also allow us to potentially investigate less intrusive changes, depending on where the filter overheads manifest. For example, late materialization of this form was recently added to the parquet reader. We could theoretically build upon this base, without needing to make more intrusive modifications.
--
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