Histogram encoding: dense List(UInt64) bins dominate row width and buffered-batch memory

[madesroches-ubi]

Summary

Histograms are stored as a dense List(UInt64) of bins. Every bin costs 8 bytes whether or not it
was ever incremented, so a histogram's in-memory footprint is set by its declared bin count rather
than by how much data it actually represents. For views that carry several histogram columns this
dominates row width, and that width then multiplies through every operator that buffers batches.

Current Arrow type (rust/datafusion-extensions/src/histogram/accumulator.rs:331-341):

Field::new("start",  DataType::Float64, false),
Field::new("end",    DataType::Float64, false),
Field::new("min",    DataType::Float64, false),
Field::new("max",    DataType::Float64, false),
Field::new("sum",    DataType::Float64, false),
Field::new("sum_sq", DataType::Float64, false),
Field::new("count",  DataType::UInt64,  false),
Field::new("bins",   DataType::List(Arc::new(Field::new("bin", DataType::UInt64, false))), ...),

So one make_histogram(0, 100, 100, ...) column is 6*8 + 8 + 100*8 = 856 B/row, of which 800 B
(93%) is bins.

Why it matters

A view with four such columns is 3,424 B/row in memory. LZ4 + the Parquet integer encodings hide
this on disk -- these columns compress extremely well because most bins are zero -- so the on-disk
size gives no warning about the in-memory cost. A day partition of ~135k rows occupies ~15 MB on
disk and ~460 MB decoded.

That gap bites hardest in the k-way sorted merge path
(tasks/completed/1392_kway_merge_sorted_partitions_plan.md). Its memory model (§4) is
"k partial working sets + one final working set + k buffered batches in the
SortPreservingMergeExec + k open Parquet readers ... scales with k, not data volume" -- which holds,
but the constant is k * batch_size * row_width. With a 3.4 KB row that is
24 * 8192 * 3424 B ~= 642 MB for a 24-way merge at the default batch size, versus ~10 MB for a
merge of narrow rows. I hit exactly this on a per-process/per-minute frame-timing view with four
100-bin histogram columns: a day merge of 17.5 MB of input cost ~500 MB of RAM.

Nothing here is a bug -- the merge planned correctly, streamed, and used ordered aggregation. The
cost is purely the encoding's constant factor.

Possible directions

Roughly in increasing order of effort:

1. Narrower bin counters. UInt32 halves bin memory and is ample for per-minute bucketed
   counts; overflow could saturate or promote. Requires a stored-format migration.
2. Sparse / run-length bins. Histograms over latency-like distributions are mostly zeros outside
   a narrow band. Storing (index, count) pairs, or run-length encoding the zero runs, would cut
   typical footprint by an order of magnitude while keeping sum_histograms associativity.
3. Adaptive representation. Dense below some occupancy threshold, sparse above it, chosen per
   value -- keeps small/full histograms cheap and avoids a hard cliff.
4. Let the bin counter type be part of the histogram's declared type, so a view author can pick
   the width alongside start/end/bin_count instead of always paying u64.

Any of these needs sum_histograms to stay associative and commutative (it is merged repeatedly up
the partition rollup), and quantile_from_histogram / expand_histogram to keep working across the
old and new encodings during migration.

Workarounds today

For anyone hitting this before a format change: lowering datafusion.execution.batch_size for the
merge session scales the buffered-batch term down linearly, and reducing the declared bin count is
an immediate constant-factor win if the resolution is not needed.