Epic: Implement Narrow integer encoding

[mhk197]

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.

[connortsui20]

I think this makes a lot of sense. We would want to use these in our nested types like List and ListView, where the offsets should probably just be I64 always but encoded as narrow.

The only tradeoff I can see is that there will then be an additional "layer" between an encoding and full canonicalization. For example, if we want to execute a Add(5, Narrow(BitPacked)), to get to the full width we potentially need an extra execute step to get from Narrow(BitPacked) to Narrow(Primitive) to Primitive.

But this might actually be a good thing! Because we can have Narrow do an execute_parent with Add and potentially keep the whole array in the narrow form if we know that it won't overflow the smaller width.

[robert3005]

This Narrow array needs all the forwarding rules so we don't force a copy here