Epic: Implement Narrow integer encoding #10020

This Epic is for implementing narrow integer encoding, an encoding that keeps an array's logical dtype while storing its values in a narrower integer child.

For example, an I64 array with values between [-128, 127] can be stored as an I8 child and still read as I64. This reduces the storage and memory footprint significantly, and compute kernels may be able to run directly on the narrow child without widening first.

Status

Proposed.

Goal

The goal is to store integer data at only the necessary width as far as possible through compute. This seems to be a low-hanging compression and compute win for integer types, and may be applicable to decimal types in the future as well.

Today, you can can shrink an integer array in two ways:

1. Cast it to a narrower type. This is a schema change and changes overflow behavior, so it is a non-starter.
2. Compress it (e.g. with bitpacking). Bitpacking minimizes storage, but compute decodes values to logical width.

Narrowing would be a relatively low-cost intermediate between casting and bitpacking. The logical dtype of a narrowed array would stay the same, but compute would run over the narrowed values when possible. Narrower values -> more values per SIMD lane -> higher throughput.

Design

NarrowArray is a wrapper array with no buffers. It has a logical integer dtype and one child slot.

NarrowArray(dtype = Primtive(I64)
└ values: PrimitiveArray(ptype = I8, _))

We call the dtype of the NarrowArray original_dtype, since it is the original dtype of the child before narrowing. We call the dtype of the child narrow_dtype.

For now, we can enforce the following invariants:

1. original_dtype and narrow_dtype are both integers
2. sgn(original_dtype) == sgn(narrow_dtype)
3. width(original_dtype) > width(narrow_dtype)
4. Validity lives in the child. The parent derives it.
5. The child is a canonical primitive integer array (for now). The child could in principle could be any array tree with a logical integer dtype narrower than the original dtype.

Encoding

NarrowArray::encode(primitive) computes the non-null min/max and picks the smallest fitting type of the same signedness. It casts the values once or returns the input unchanged if nothing smaller fits.

Canonicalization

NarrowArray::execute() simply the child to the original_dtype while preserving its validity. This is guaranteed to be lossless, since sgn(original_dtype) == sgn(narrow_dtype) and width(original_dtype) > width(narrow_dtype).

Compute

One of the main benefits of this encoding is that compute over the narrowed child should be more performant in many cases than compute over the original array.

Unresolved questions

• None yet.