apache / apache/arrow-rs

RunEndBuffer::get_physical_indices scans beyond the requested range

Open
#10,846 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 18h
Merged PRs (30d)
169

Description

### Describe the bug

`RunEndBuffer::get_physical_indices` keeps visiting later physical runs after it has mapped every requested logical index. A tiny prefix selection from a large run-end buffer therefore scales with the entire backing buffer. A small logical slice can also scan runs beyond its end.

### To reproduce

On `900ec3ee38276ab651e210c4a85b38f8a8a61bcf`, compare:

```rust
use arrow_buffer::RunEndBuffer;

let run_count = 1_048_576;
let run_ends = (1..=run_count as i32).collect::>();
let buffer = RunEndBuffer::new(run_ends.into(), 0, run_count);
assert_eq!(buffer.get_physical_indices(&[0_u32, 2]).unwrap(), [0, 2]);

let sliced = buffer.slice(run_count / 2, 3);
assert_eq!(
sliced.get_physical_indices(&[0_u32, 2]).unwrap(),
[run_count / 2, run_count / 2 + 2],
);
```

The results are correct, but the implementation scans many runs after the last requested one. Dedicated benchmarks cover these cases and an all-index control at 1,024 and 1,048,576 runs.

### Expected behavior

Stop visiting physical runs once no remaining requested index can use them. Preserve original physical indices, reordered/duplicate requests, slices, and bounds errors.

### Additional context

AI assistance: Codex helped investigate the implementation and generate the benchmark, reproduction, and report.

Contributor guide

Open the contributing guide

Research direction

Start at the RunEndBuffer::get_physical_indices entry point and reproduce the prefix and sliced selections from the issue on commit 900ec3ee38276ab651e210c4a85b38f8a8a61bcf. Run the dedicated benchmarks, including the all-index controls at 1,024 and 1,048,576 runs. Done means later physical runs are not visited while results, duplicates, reordering, slices, and bounds errors remain correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.