You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "chloro-pn (via GitHub)" <gi...@apache.org> on 2024/07/29 17:56:47 UTC
[PR] Optimization of filter operation on ByteViewArray [arrow-rs]
chloro-pn opened a new pull request, #6154:
URL: https://github.com/apache/arrow-rs/pull/6154
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #.
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
Performing a `filter` operation on `ByteViewArray` only filters its `view` data members, but clones the entire `buffers`, which may result in the `ByteViewArray` holding some unnecessary `buffers`, which may prevent some memory resources from being released in a timely manner.
This PR records whether each `buffer` needs to be retained while filtering `view` data members, and updates the `buffers` of `ByteViewArray` using the recorded information.
The reason why this PR replaces unwanted `buffers` with empty `buffers` instead of deleting them directly is that this processing preserves the mapping relationship between `views` and `buffers`.
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!---
If there are any breaking changes to public APIs, please add the `breaking change` label.
-->
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "chloro-pn (via GitHub)" <gi...@apache.org>.
chloro-pn commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256691485
From the documentation of `gc`, it appears to do at least two things:
* Compress `data buffer` (expensive)
* Clean up the `buffers` based on the view list (cheap)
The modification of this PR does not perform expensive operations of compressing `data buffers`, it only releases the reference count of `buffers` that no longer need to be held (the resources held by `buffers` are managed based on Arc's reference counting mechanism)
So this PR cannot completely solve the problem you mentioned above (because compared to the `gc` method, it only does the less expensive part, for example, if all the `buffer` in the `buffers` hold different parts of the same `Bytes`, then this PR is meaningless because `Byte` will always be held), but it also does not introduce expensive overhead.
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #6154: Optimization of filter operation on ByteViewArray
URL: https://github.com/apache/arrow-rs/pull/6154
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "chloro-pn (via GitHub)" <gi...@apache.org>.
chloro-pn commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2294806472
It's okay, this is not an urgent 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
Re: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256927193
> Provide a new API instead of modifying the existing one, agree with this and leave the choice to the user.
I will try and write this up over the next day or two into something more coherent
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "chloro-pn (via GitHub)" <gi...@apache.org>.
chloro-pn commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256818105
My suggestion is that we can treat the **second** type of GC like the current GC (**third** type GC) as an independent method that users can choose to call.
The **first** type of GC in this PR can be placed in a new filter method, temporarily called `filter2`, to distinguish the old `filter` method. The `filter2` method can return some statistical information obtained during the filtering process, which can help users choose whether to perform other GC operations in the future. For example, we can return the number of empty `buffer`s and the proportion of empty `buffer`s in the `buffers` to guide users whether to perform the **second** type of GC.
Here, we can also obtain statistical information to guide users on whether to call the **third type** of GC, but I currently do not understand the implementation details of the **third** type of GC. I need to look at the source code later.
The reason for encapsulating the **first** type of GC into `filter2` instead of providing it as a standalone method like other types of GC is:
It is lightweight and can be processed together during the filtering process. Putting the **second** type of GC in the `filter` method is not more advantageous than calling it as an independent method.
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2260915140
I still have writing up the ideas into a more coherent form on my list, but I probably won't get to it for the next few days (I have too too many other projects in flight at the moment)
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "XiangpengHao (via GitHub)" <gi...@apache.org>.
XiangpengHao commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256701705
I think this is a clever PR and is complementary to the `gc` approach. If I understand correctly, it replaces unused buffers with empty buffers so they can be released.
There's a hierarchy of `gc`s: (1) replace unused buffer with empty buffer, without touching the view array (2) directly remove the unused buffers, but need to correct the buffer ids in the view array (3) complete gc, as implemented in the current `gc` function.
This PR makes the first approach, which is transparent to users and has relatively low overhead.
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-4814749830
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2292283299
I have not had a chance to write up these ideas yet, I apologize
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256644528
Thanks @chloro-pn. 🙏 We have gone back and forth on this idea while integrating StringView into datafusion
The StringViewArray has a `gc` method but this does require an extra copy of the views
https://docs.rs/arrow/latest/arrow/array/struct.GenericByteViewArray.html#method.gc
In fact @XiangpengHao used this API in https://github.com/apache/datafusion/pull/11587 to solve exactly the problem you are describing (too much unused data in the buffers)
However, what I worry about is that the heuristic to determine when to compact the string data / buffers will not be ideal for any particular usecase and that one princple of this crate is to give the user maximal control over performance
So I would like to propose we support two different modes for filter kernels:
1. Filter only views
2. Filter the views and copy matchings strings to a new buffer
@XiangpengHao I wonder if you have any thoughts to add 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
Re: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "chloro-pn (via GitHub)" <gi...@apache.org>.
chloro-pn commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256828520
> My concern with this approach (and with any of the "gc while filtering" approaches) is that it will work well for some use cases but be unavoidable overhead with other use cases.
>
> I think we need an API that allows callers to specify how they want the GC to be done
>
> What I have talked about with @XiangpengHao and a few others is making some sort of stateful filter API; Among other things such an API would give us a place to put options for filtering
>
> So maybe it would look like
>
> ```rust
> // create a new filterer
> let filterer = ArrayFilterer::new()
> // specify that GC should look for empty buffers
> .with_gc_strategy(GcStrategy::FindEmptyBuffers);
>
> // feed in arrays and their filters (BooleanArray)
> filterer.push(array1, filter1)?;
> filterer.push(array2, filter2)?;
>
> // Produce the final output array
> let filtered_array = filterer.build();
> ```
Provide a new API instead of modifying the existing one, agree with this and leave the choice to the user.
--
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: [PR] Optimization of filter operation on ByteViewArray [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6154:
URL: https://github.com/apache/arrow-rs/pull/6154#issuecomment-2256821863
My concern with this approach (and with any of the "gc while filtering" approaches) is that it will work well for some use cases but be unavoidable overhead with other use cases.
I think we need an API that allows callers to specify how they want the GC to be done
What I have talked about with @XiangpengHao and a few others is making some sort of stateful filter API; Among other things such an API would give us a place to put options for filtering
So maybe it would look like
```rust
// create a new filterer
let filterer = ArrayFilterer::new()
// specify that GC should look for empty buffers
.with_gc_strategy(GcStrategy::FindEmptyBuffers);
// feed in arrays and their filters (BooleanArray)
filterer.push(array1, filter1)?;
filterer.push(array2, filter2)?;
// Produce the final output array
let filtered_array = filterer.build();
```
--
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