Skip to content

feat(arrow-select): add minify kernel to drop unreferenced buffer data - #12184

Draft
adriangb wants to merge 6 commits into
apache:mainfrom
adriangb:minify-kernel
Draft

feat(arrow-select): add minify kernel to drop unreferenced buffer data#12184
adriangb wants to merge 6 commits into
apache:mainfrom
adriangb:minify-kernel

Conversation

@adriangb

@adriangb adriangb commented Nov 11, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

Which issue does this PR close?

Rationale for this change

Sliced arrays, view arrays, dictionaries and dense unions can keep memory alive that their rows do not reference. Downstream users (for example DataFusion spilling) each work around this on their own. The issue asks for one kernel in arrow-select.

What changes are included in this PR?

A new arrow_select::minify module with minify(&dyn Array) -> Result<ArrayRef, ArrowError>. The result is logically equal to the input, has offset zero, and its buffers hold only referenced data. minify recurses into children, dictionary values and run-end encoded values.

Type Behavior
Primitive (incl. decimal, temporal, interval), Boolean, FixedSizeBinary Copy the visible range. Boolean bit offsets become zero.
Null buffers Copy the visible bits. Drop the buffer if it has no nulls.
Utf8 / LargeUtf8 / Binary / LargeBinary Rebase offsets to zero and copy only the bytes of valid rows. Null rows get an empty range.
Utf8View / BinaryView Merge the distinct byte ranges of the valid views. Keep a data buffer only if the views reference all of its bytes. Copy the other ranges once into new buffers, so views that share bytes keep sharing them. Unreferenced buffers go away. Null rows get an empty view.
List / LargeList / Map Keep only the child ranges of valid rows, rebase offsets, recurse. Null rows get an empty range.
ListView / LargeListView Merge the child ranges of the valid views into disjoint ranges and copy them back to back (drops gaps). Overlapping views stay shared. Null rows get offset and size zero.
FixedSizeList, Struct, sparse Union Recurse into the (already sliced) children.
Dense Union Keep each referenced child row once, in ascending child order, and remap offsets. Rows that share a child row keep sharing it. A child that the rows use in full stays shared. The children are gathered with gather_ranges, not take.
RunEndEncoded Narrow runs and values to the slice, rebase run ends, recurse. Gathered rows (for example dictionary values) go through gather_run, which keeps the runs of the input and copies each run value once, also when many gathered ranges hit one run.
Dictionary Prune unreferenced values like garbage_collect_dictionary, but gather the kept values with gather_ranges, then recurse into keys and values.

Reuse policy: minify copies a buffer only when its allocation is larger than the visible data needs (rounded up to 64 bytes). Already-minimal arrays are returned without copies, so minify(minify(a)) copies nothing. New allocations also round up to 64 bytes, so a tiny input whose buffers are already exact-size can grow slightly.

Null rows: minify always gives null rows of byte, list, map and list view arrays an empty value range (and null rows of byte view arrays an empty view), as #9970 proposed. There is no option for this. A fast path keeps it cheap. One O(rows) check over the offsets and the null bitmap finds out if any null row has a non-empty range. If none has (including arrays with no nulls), minify slices or copies the referenced range in one piece. Otherwise it copies the child range of each run of valid rows, so contiguous runs stay single copies. The result has no reclaimable null ranges, so a second call copies nothing.

Open questions for reviewers:

  • Moving the IPC writer logic onto this kernel is left for a follow-up.
  • A shared buffer counts as oversized, so minify copies it even if other arrays keep it alive. The docs call this out.
  • A buffer that appears more than once inside the input (two struct columns over one array, two dictionaries over one values array) could be copied once per reference. Equal struct columns now share one minified column. If the result would still use more memory than the input, minify returns the input unchanged.
  • Null rows of struct and fixed size list arrays, and unselected rows of sparse union children, keep their child data. The module doc lists this under Limitations.

Are these changes tested?

Yes. Unit tests cover every type above, null rows with non-empty ranges (bytes, map, and a list of strings with nulls at both levels, also inside a dictionary and a struct), the no-null fast path, plus nested combinations: dictionary of Utf8View, dictionary of list, dictionary inside struct and list children, run-end encoded dictionary, fixed-size list of struct, dense union of lists, and lists over sliced children. A shared check helper slices each array several ways and asserts that the result:

  • is logically equal to the slice and passes validate_full,
  • has offset zero and the same data type,
  • allocates no more (and for small slices strictly less) buffer memory than the slice,
  • reuses all buffers when minified a second time.

Benchmarks are in arrow/benches/minify_kernels.rs.

How to review

Read the PR commit by commit:

  1. feat: add minify for flat types (reuse policy, null buffers, primitive, boolean, null, fixed size binary, byte and byte view arrays). The dispatch matches every DataType variant without a wildcard. Nested types return NotYetImplemented in this commit only.
  2. feat: add nested, union, dictionary and run-end encoded types. They share the gather_ranges path. The row selection helpers (list_view_child, dense_union_rows) exist from the commit that first needs them, so feat(arrow-select): add compacted_size, row_sizes and split_by_size next to minify #12190 can reuse them.
  3. bench: add the minify_kernels benchmark.
  4. fix: review follow-ups. Byte views count distinct referenced bytes and drop null row bytes and unused buffers (view_data, keeps_view_buffer). Aliased buffers cannot make the result larger than the input. The dense union lookup table spans only the visible offsets.
  5. fix: copy each run value once in gather_run, number dense union child rows in ascending order, use usize for view ranges, and make dictionary garbage collection O(keys + span of used keys).
  6. bench: more minify_kernels cases for small slices of large parents.

Are there any significant user-facing changes?

New public API only: arrow_select::minify::minify.

AI usage disclosure

Claude Code wrote the implementation, tests and this description under my direction.

🤖 Generated with Claude Code

@boring-cyborg boring-cyborg Bot added arrow-kernels Crates that transform arrow data (e.g. compute, cast) arrow-core Core crates related to representing arrow data labels Nov 11, 2026
@adriangb

adriangb commented Nov 11, 2026

Copy link
Copy Markdown
Contributor Author

Benchmark results for arrow/benches/minify_kernels.rs, on a GCP c4a-standard-16 VM. Each case slices 8192 rows from a parent of 100k rows unless noted.

Results
Case Time
i32 slice 571 ns
utf8 slice, no nulls 29.7 µs
utf8 slice, null ranges 54.0 µs
utf8view sparse 33.9 µs
list slice 258 µs
listview slice 18.8 µs
dense union slice 58.1 µs
dictionary, few referenced 31.5 µs
run-end encoded slice 2.72 µs
list, already minimal 8.5 µs
utf8, already minimal (alternating nulls) 11.7 µs
utf8, 4M rows, null ranges 181 ms

@adriangb adriangb mentioned this pull request Nov 11, 2026
Draft
@adriangb adriangb mentioned this pull request Nov 11, 2026
Draft
adriangb and others added 3 commits November 11, 2026 17:21
@adriangb @claude
feat(arrow-select): add minify kernel for flat types
ccaebff 
Sliced arrays and view arrays can keep memory alive that their rows do not
reference. Callers such as spilling and IPC writers each work around this on
their own.

`minify` returns a logically equal array with offset zero whose buffers hold
only referenced data. This commit adds the reuse policy and the null buffer
handling, and supports the flat types: primitive, temporal, decimal,
interval, boolean, null, fixed size binary, byte and byte view arrays. Null
rows of byte arrays get empty ranges. `view_data_len` and
`keeps_view_buffers` hold the view array decision, so that later code can
share it.

The dispatch matches every `DataType` variant without a wildcard, so a new
variant in arrow-schema fails to compile until `minify` handles it. Nested,
union, dictionary and run-end encoded types return `NotYetImplemented`.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
@adriangb @claude
feat(arrow-select): support nested, union, dictionary and run-end enc…
7c09ab9 
…oded types in `minify`

Sliced lists and maps share the full child array. Dictionaries can hold
values that no key references, and dense unions can hold child rows that no
row references. `minify` needs to recurse into these types to drop that
memory.

This commit adds List, LargeList, Map, FixedSizeList, Struct, ListView,
LargeListView, sparse and dense Union, Dictionary and RunEndEncoded. Null
rows of lists and maps get empty ranges. These types share one gather path,
`gather_ranges`. It gathers dense unions, list views and run-end encoded
arrays by their parts, so child rows that several rows share stay shared.
`list_view_child` and `dense_union_rows` hold the child row selection of
list views and dense unions, so that later code can share it.

`minify`, `gathers_parts` and `gather_ranges` match every `DataType`
variant without a wildcard. The dispatch passes the list field and the
union fields to the helpers, so they need no `unreachable!` arm. Invalid
dictionary key, run end and time unit types return `InvalidArgumentError`.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
@adriangb
bench(arrow): add criterion benchmarks for minify
940d911 
The `minify` kernel has no benchmarks, so performance changes cannot be
measured. This adds `minify_kernels` with slices of 8192 rows from parents
of 100k rows for each main type, an already minimal input, null-heavy
strings with non-empty null ranges, and one large 4M-row case.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
adriangb added a commit to adriangb/datafusion that referenced this pull request Nov 12, 2026
@adriangb @claude
refactor: let SpillManager bound the bytes of the batches it writes
de72f27 
A spill batch has at most batch_size rows, whatever its size in bytes. A
merge of spill files reserves memory for the largest batch of each file,
so wide rows make that reservation larger than the pool. An operator
needs a way to bound the batches it spills by bytes.

This commit adds SpillManager::with_max_batch_bytes (crate-private) and
SpillPieces. A bounded writer cuts each appended batch into row ranges
by SpilledRowSizes, copies each range, and writes it as its own IPC
message. The recorded size of a bounded writer counts the IPC padding of
each buffer, so a batch read back never exceeds it.

A slice of a list, run-end encoded array, union or list view keeps whole
children or values, so its measured size is far above what the IPC reader
allocates for it. compact_batch copies each range into fresh buffers
that hold only its rows, so the measure is exact for every type and no
type has to be written whole. It uses arrow take, plus fixes for what
take keeps whole: view buffers, unused dictionary values and list view
children. Rows of a list view can share a child range, so it copies the
covered range once, and the halving of a piece stops when the halves do
not get smaller. arrow-rs minify (apache/arrow-rs#12184) replaces the
copy.

A dictionary that the rows of a split batch share is written once per
piece. A batch within the bound is written as before.

No operator sets a bound yet, and an unbounded writer records the same
size as before, so this commit changes no behavior.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
adriangb and others added 3 commits November 13, 2026 17:34
@adriangb @claude
fix(arrow-select): make minify smaller for shared view bytes and al…
f6a4396 
…iased buffers

Review found inputs where `minify` kept or created memory that the rows do not need.
Repeated views counted shared bytes once per view, so `minify` kept a 1 MB buffer for 100 distinct bytes or made `gc` write the bytes once per view.
Null view rows kept their bytes.
The slack of 64 bytes per data buffer kept thousands of unreferenced small buffers.
A buffer aliased twice inside one array was copied twice, so memory grew.
The dense union lookup table was as long as the child.

View arrays now merge the distinct ranges that valid views reference.
`minify` keeps a data buffer only if the views reference all of its bytes and it is not oversized.
It copies the other ranges once into new buffers and gives null rows an empty view.
Equal struct columns share one minified column.
If the result still uses more memory than the input, `minify` returns the input unchanged.
The dense union table spans only the visible offsets.
The module doc lists the parents that keep child data of null rows.
The `allocated` test helper counts each allocation once.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
@adriangb @claude
fix(arrow-select): copy each run value once and avoid O(parent) work …
1d2be7a 
…in `minify`

`gather_run` copied a run value once per gathered range. A list whose null rows keep their child ranges, or a dense union over a run-end encoded child, then gathered many ranges of one run. A 183 KB input reached a 1 GB peak, and the fallback returned the input unchanged although nothing was aliased.

A range that starts in the run where the previous range ended now extends that run.
Dense union child rows are numbered in ascending order, so gathered ranges never go back and coalesce.
The offsets keep the logical rows unchanged, and a child that is used in full stays shared.
`view_data` adds view offsets and lengths as `usize`, because a data buffer can be longer than `u32::MAX`.
Dictionary garbage collection costs O(keys + span of used keys) and not O(values).

New tests pin the run fix, the view range math, the fallback threshold, the null comparisons of `same_data`, the paths for all-valid null buffers, `push_range`, `gathers_parts` and the exact byte capacity of a gather.

Co-Authored-By: Claude Opus 5.5 <[email protected]>
@adriangb @claude
bench(arrow): add minify cases for small slices of large parents
ee4ca3d 
The cases cover already compact arrays, small slices of large utf8, view, dictionary and dense union parents, reversed views and arrays with one data buffer per row. `gc`, `take` and `garbage_collect_dictionary` run as baselines that do comparable work.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

arrow-core Core crates related to representing arrow data arrow-kernels Crates that transform arrow data (e.g. compute, cast)

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Minify Kernel

1 participant

@adriangb