apache / apache/arrow

[C++] Avoid producing run-end encoded arrays with runs that have a length longer than INT_MAX

Open
#34,237 3 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

## Hypothesis

Limiting the length of runs (not the length of logical arrays) is going to prevent multi-language integration pains at a very low storage/memory cost — compresssing ~2B elements into a single run already yields a great compression factor. If we need to produce longer runs we can simply append multiple `< INT_MAX`-sized runs.

## The spec on array lengths

https://arrow.apache.org/docs/dev/format/Columnar.html#array-lengths

> Array lengths are represented in the Arrow metadata as a 64-bit signed integer. An implementation of Arrow is considered valid even if it only supports lengths up to the maximum 32-bit signed integer, though. If using Arrow in a multi-language environment, we recommend limiting lengths to 2 31 - 1 elements or less. Larger data sets can be represented using multiple array chunks.

The solution proposed by the spec for languages that don't support 64-bit integers is to use multiple array chunks. Chunking the physical arrays of a run-end encoded logical array is much easier when we don't have to split in the middle of a run. So limiting the runs at `INT_MAX` means we only have to worry about the regular split of logical length.

### Component(s)

C++

Contributor guide

Open the contributing guide

Research direction

Read the Arrow array-lengths specification linked in the issue, then locate the C++ run-end encoded array construction and chunking paths. Confirm that produced runs are no longer than INT_MAX while logical array lengths and chunking behavior remain valid; add or update relevant tests once those paths are identified.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
data-engineering
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.