Potentially improve join performance by implementing a version of the take kernel that accepts an iterator of indices
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
Collecting the filtered indices to a PrimitiveArray takes a lot of memory and time. Using an Iterator based design instead would save a lot of intermediate memory and potentially speed up the join operation due to fewer cache misses and less copying.
### Describe the solution you'd like
Create a version of arrow's compute::take kernel that accepts an iterator of indices. Benchmark and figure out where it's worth using Iterators over PrimitiveArrays.
### Describe alternatives you've considered
_No response_
### Additional context
I have tried to create a POC but I seem to get different results whenever I benchmark it and I couldn't figure out what's wrong. I also had lots of trouble with taking the ownership of the values array of PrimitiveArrays which are guaranteed to not have nulls (namely the indices cache and the mask produced by the filter).
Furthermore, it's possible to use the mask's `.values().set_indices()` iterator to generate indices to be used in the join, because the left-right index pairs are a function of the index of the mask in the form of `(index % left_batch.num_rows(), index / left_batch.num_rows())` and it vectorizes nicely.
I plan to share the entirety of my POC ([here's a potential implementation of take_with_iter](https://gist.github.com/alihan-synnada/4c327b873ea4152cfde0e2816a59bc94)) and benchmarks once I can tame them and generate the same results deterministically.
Contributor guide
Research direction
Start by reading the proposed take_with_iter implementation and the Arrow compute::take kernel, then inspect the join path that collects filtered indices into a PrimitiveArray. Reproduce the existing join results and establish deterministic benchmarks before comparing iterator-based indices, including the mask values().set_indices() approach. Done means matching results with measured evidence that the iterator design improves performance or memory use where applied.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100