apache / apache/arrow-rs

Expose vectorized hash table that work with `Array`s

Open
#6,996 3 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 14h
Merged PRs (30d)
167

Description

I just read the [Photon](https://cs.stanford.edu/~matei/papers/2022/sigmod_photon.pdf) paper from 2022 and saw their vectorized implementation for hash table, I also noticed that someone opened an issue in DataFusion https://github.com/apache/datafusion/issues/7095 for implementing it for group aggregate

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**
I would like to have `HashSet`/`HashMap` that would support all Hash table functionality but with Arrays as input.

Problem:
DataFusion has `array_agg` with distinct support, if you look at the implementation it just keep adding to `HashSet`
https://github.com/apache/datafusion/blob/6c9355d5be8b6045865fed67cb6d028b2dfc2e06/datafusion/functions-aggregate/src/array_agg.rs#L268-L281

this works but can be improved with computing all the hashes first, and then do probing in a tight loop

**Describe the solution you'd like**
It would be helpful to use there and in other places a HashSet/HashMap that can
1. Insert all values from an array
2. Check all values in array exists and return a BooleanArray for the result
3. Get all the values that match each key in the array

**Describe alternatives you've considered**
Implement it everywhere that need HashMap/HashSet or create external crate

**Additional context**
The way I see it there will be couple of implementation
1. Primitive/boolean
2. Bytes
3. Generic that will use `arrow-row`

I'm willing to create a PR for that. I see it as using internally the hashbrown raw API to implement that

Contributor guide

Open the contributing guide

Research direction

Start with datafusion/functions-aggregate/src/array_agg.rs around the distinct HashSet use, then review the Photon paper, arrow-row, and hashbrown raw API. Define the vectorized HashSet/HashMap behavior for primitive, boolean, bytes, and generic values, including bulk insertion, BooleanArray existence results, and matching keys; done means the API is usable for array_agg and relevant tests cover these operations.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.