apache / apache/arrow

[C++][Compute] Allow reusing hash table across multiple `is_in` / SetLookup kernel calls

Open
#49,214 6 comments 0 reactions 0 assignees View on GitHub
Component: C++ Type: enhancement
Dominant language
C++
Stars
17.1k
Forks
4.3k
Avg merge
3d 13h
Merged PRs (30d)
88

Description

### Describe the enhancement requested

### Problem

The `is_in` kernel (and other set lookup operations) rebuilds the internal hash table (MemoTable) from `value_set` on **every invocation**, even when `value_set` is identical across calls. There is currently no API to pre-build and reuse the hash table.

This becomes a significant bottleneck when the same `value_set` is used to filter many arrays (e.g., in a streaming/batch processing pipeline).

### Use Case

In Ray Data Checkpointing, we want to use `pc.is_in` to perform an anti-join: filtering out already-processed row IDs from each incoming block of data. The checkpoint ID set (`value_set`) is the same across all blocks, but the hash table is rebuilt for every block.

```python
# value_set is the same across all calls — hash table is rebuilt each time
for block in blocks:
membership = pc.is_in(block["id"], value_set=checkpoint_ids)
filtered = block.filter(pc.invert(membership))
```

With 100M checkpoint IDs and 20 blocks, the hash table construction alone takes **~250s** (extrapolating from #36059 benchmarks), doing identical work 20 times.

### Benchmark

Building on the benchmarks from #36059, the cost of rebuilding becomes clear when multiplied across calls:

```python
import pyarrow as pa
import pyarrow.compute as pc
import numpy as np

value_set = pa.array(np.arange(10_000_000))
blocks = [pa.array(np.random.choice(np.arange(1000), 100)) for _ in range(20)]

# Current: ~25s total (rebuilds hash table 20 times)
for block in blocks:
pc.is_in(block, value_set)

# Ideal: ~1.3s (build once, probe 20 times)
```

### Proposed API

**Option A — Prepared/materialized value set object:**

```python
# Build hash table once
lookup = pc.SetLookup(value_set) # or pc.prepare_set(value_set)

# Reuse across calls — probes only, no rebuild
for block in blocks:
mask = lookup.is_in(block)
```

**Option B — Caching in SetLookupOptions:**

```python
options = pc.SetLookupOptions(value_set, cache=True)

# First call builds hash table; subsequent calls reuse it
for block in blocks:
mask = pc.is_in(block, options=options)
```

**Option C — Lower-level hash set exposure:**

```python
hash_set = pc.HashSet(value_set) # builds MemoTable

for block in blocks:
mask = hash_set.is_in(block)
# or: mask = pc.is_in(block, options=pc.SetLookupOptions(hash_set))
```

### Impact

This would benefit any workload that probes the same set repeatedly:

- Streaming anti-joins / semi-joins
- Incremental processing (checkpoint filtering)
- Repeated dictionary lookups
- Any ETL pipeline filtering against a static blocklist/allowlist

### Related

- #36059 — Performance of building up HashTable (MemoTable) in `is_in` kernel (addressed MemoTable speed, but not reuse)

### Component(s)

C++

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.