You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "tustvold (via GitHub)" <gi...@apache.org> on 2024/03/17 02:10:55 UTC
[I] Adaptive Parquet Predicate Pushdown [arrow-rs]
tustvold opened a new issue, #5523:
URL: https://github.com/apache/arrow-rs/issues/5523
**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 `RowSelection` stores a list of `RowSelector`. This is optimised for the case of large runs of skipped or selected rows, allowing this to be pushed down to the underlying decoding machinery. Whilst this works very well for the use-case of skipping data based on the page index, where the selections are necessarily in the thousands of rows, it will potentially degrade in the presence of more granular predicate evaluation, e.g. as performed by `ArrowPredicate`.
**Describe the solution you'd like**
<!--
A clear and concise description of what you want to happen.
-->
In a similar vein to https://github.com/apache/arrow-rs/pull/1248, we should have different strategies based on the selectivity of the predicate. In particular I would like RowSelection to switch between a `RowSelector` approach that is pushed down to the underlying readers, and a late evaluation approach where it stores a `BooleanBuffer` that is applied to the columns after the fact
**Describe alternatives you've considered**
<!--
A clear and concise description of any alternative solutions or features you've considered.
-->
**Additional context**
<!--
Add any other context or screenshots about the feature request 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.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Adaptive Parquet Predicate Pushdown [arrow-rs]
Posted by "XiangpengHao (via GitHub)" <gi...@apache.org>.
XiangpengHao commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2427170751
take
--
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] Adaptive Parquet Predicate Pushdown [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2429364040
An important goal of this ticket, mentioned by @tustvold in https://github.com/apache/arrow-rs/issues/6454#issuecomment-2402118020, is that evaluating predicates in `ArrowFilter` (aka pushed down predicates) is never worse than decoding the columns first and then filtering them with the `filter` kernel
If we are able to achieve this goal, it would mean that query engines like DataFusion could push all predicates down into the predicate reader always.
At the moment, since it sometimes faster to apply filters after reading columns than it is via `ArrowPredicate` sometimes queries get slower when all predicates are pushed down.
When it makes sense to push predicates down depends on their actual selectivity, which is only known for sure during evaluation
Thus, I agree with the conclusion that implementing adaptivity in the lowest level scan will achieve the goal
--
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] Adaptive Parquet Predicate Pushdown [arrow-rs]
Posted by "XiangpengHao (via GitHub)" <gi...@apache.org>.
XiangpengHao commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2429470872
> is that evaluating predicates in ArrowFilter (aka pushed down predicates) is never worse than decoding the columns first and then filtering them with the filter kernel
This is an excellent summary of the goal, it also aligns well with my current project.
Since I have gone quite far on this, I want to share some of the issues I have encountered:
- [ ] very fast row selection, as described in this ticket.
- [ ] avoid decoding the predicate columns twice, potentially at the cost of higher memory usage
- [ ] adaptive `slice` or `filter` the resulting array, i.e., if the selection is sparse, we should `filter`/`take`, otherwise we should `slice`.
- [ ] coalesce the resulting record batches. Since filter is been pushed on to ParquetExec, there won't be a FilterExec therefore no CoalesceBatchExec, which requires the ParquetExec to emit coalesced record batches.
--
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] Adaptive Parquet Predicate Pushdown Evaluation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2841745792
I am (of course) filing tickets to help organize this better
- The overall goal is described here: https://github.com/apache/arrow-rs/issues/7456
--
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] Adaptive Parquet Predicate Pushdown [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2429542610
> adaptive slice or filter the resulting array, i.e., if the selection is sparse, we should filter/take, otherwise we should slice.
I think this is what @tustvold mentioned with the [`filter` kernels](https://docs.rs/arrow/latest/arrow/compute/kernels/filter/index.html) that also adaptively decide take / iterate / etc based on the actual selection
--
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] Adaptive Parquet Predicate Pushdown [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2429538011
> coalesce the resulting record batches. Since the filter is pushed to ParquetExec, we won't have FilterExec therefore no CoalesceBatchExec, which requires the ParquetExec to emit coalesced record batches.
There is a structure in datafusion for Coalescing which might help / provide inspiration / be good to port upstream: https://github.com/apache/datafusion/blob/c22abb4ac3f1af8bbdf176ef0198988fc7b0982c/datafusion/physical-plan/src/coalesce/mod.rs#L71
--
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] Adaptive Parquet Predicate Pushdown Evaluation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-3074832941
Here is a thought I had about how to tell when to decide when to use RowSelection vs BooleanArray that I mentioned to @XiangpengHao this afternoon but wanted to get into writing somewhere
The heuristic for deciding between the two representations likely needs the quantity "what is the average run length of selected portions of the mask"
One way to calculate "how many times does the mask change (namely, how many distinct RowSelector's would be needed) would be:
```rust
let mask: BooleanArray = evaluate_predicate();
// compute locations where the subsequent bit is not equal to the previous bit
let transitions = ne(mask.slice(0, mask.len() - 1), mask.slice(1, mask.len() - 1)
// the total number of row selections would be
let total_row_selections = transitions.count_ones();
// the average length of the selection can be obtained via the set bit iterator
```
--
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] Adaptive Parquet Predicate Pushdown Evaluation [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #5523: Adaptive Parquet Predicate Pushdown Evaluation
URL: https://github.com/apache/arrow-rs/issues/5523
--
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] Adaptive Parquet Predicate Pushdown [arrow-rs]
Posted by "XiangpengHao (via GitHub)" <gi...@apache.org>.
XiangpengHao commented on issue #5523:
URL: https://github.com/apache/arrow-rs/issues/5523#issuecomment-2427187531
I'll take a look at this. Here are some of my plans:
- [ ] Implement a benchmark, e.g., RowSelection with 100k selectors (as used in ClickBench q21), benchmark `and_then`, `from_filters` and `intersection`
- [ ] Implement a new RowSelection that uses a `BooleanBuffer` as the backend. Compare the performance.
- [ ] Decide the policy when to use which.
Some more context:
I have to switch to a boolean buffer based row selection to reduce the selection overhead in another project. So I kind of already have all the implementation ready. The remaining work for me is to figure out a way to contribute back to 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