Tracking Issue: Add Narrow encoding for integers and decimals #10733

This is a tracking issue for adding a Narrow encoding for integers and decimals, which stores logical values that can fit in a smaller bit width or precision in a smaller logical dtype.

• Adapted from Epic: Implement Narrow integer encoding #10020

Motivation

We have the concept of "narrowing" data in a few places.

• In the compressor, if we have a Primitive integer array that does not contain very large values, we will call a narrow() method on the primitive array to shrink the logical dtype to fit the values. For example, if my values are all in [-128, 127], but the dtype is I64, then I can narrow this to I8. We use this with list offsets, for example. Note that this changes the dtype of the array.
• Narrowing can also happen with explicit casts (which are fallible), but this also changes the dtype.
• In the canonical decimal encoding, there is currently implicit narrowing of the buffer when possible. This is arguably very wrong, see Tracking Issue: Fix Canonical Decimal #10701 for more details.

Ideally, we want a way to keep the logical type of these values while having a better physical encoding that narrows data internally. This is why we want a Narrow encoding.

Design

The Narrow encoding will have a single array child that has a narrower logical dtype. For integers, the narrowing is defined over the power-of-two bit-width. For decimals, the narrowing is defined over the precision of the decimal dtype (though there are constraints due to scale needing to be less than or equal to precision). Note that validity of the array will be derived from the child.

For example, I can narrow-encode an I64 array with a child of I8 (if it fits). Or, I can narrow-encode a Decimal(18, 2) (with 64-bit buffer) with a child of Decimal(9, 2) (that has 32-bit buffer).

We can constrain the child of the Narrow array such that it must actually shrink the amount of data we need to store. This is only relevant for Decimal: having a Narrow(Decimal(17, 2)) with dtype Decimal(18, 2) is completely pointless because it doesn't actually save any space. This is something we might be able to relax in the future, but it seems like a reasonable constraint for now.

Note that the compressor narrowing an internal child does not need to change. This is because list offsets, dictionary codes, run-end ends, patch indices, and the parts of DecimalByteParts have dtypes that their parent encoding chooses, so a narrow integer dtype there is "correct" by default, and these children technically do not need a Narrow.

Compute

A consequence of making narrowing a physical concern rather than a logical one is that we will need to forward lots of compute into the narrow array's child.

Kernels run on the child at the narrow width and widen only when the result needs it. Any operation without a kernel falls back to canonicalization, which widens the child to the logical dtype.

Serialization

Narrow can start off as an in-memory encoding with no serialized form, and once we are confident it is correct, we can stabilize it and add it to preview edition. Integers and decimals share one wire ID, vortex.narrow, whose metadata stores the child dtype: the PType of an integer child or the precision of a decimal child.

Relation to DecimalByteParts v2

Ideally, vortex.narrow enters a preview edition together with DecimalByteParts v2, and later core together with it.

For decimal columns, we want the final compressor output to be a Narrow over DecimalByteParts. Right now, decimals whose values need more than 64 bits get no compression beyond implicit narrowing, because DBPv1 can only store values up to 64 bits. For example, a Decimal(50, 2) column whose values fit in 128 bits is stored as a plain i128 buffer instead of an i256 one. If we remove the implicit narrowing (again, see #10701), those values are stored at the full canonical width.

A Narrow over an i128 child brings back today's size, but only DBPv2 actually compresses these values, since it splits them into a 64-bit most significant part and u64 lower parts. So once we add Narrow to replace Decimal's implicit narrowing, we will also want DecimalByteParts v2.

Steps

• Integer Narrow in memory, with compute forwarding (rewrite of feat(array): add Narrow integer encoding #10223 and feat(array): push arithmetic and selection through Narrow #10332)
• Replace PrimitiveArrayExt::narrow with NarrowArray::encode_values for internal children such as list offsets and dictionary codes (first part of feat(compress): retain Narrow integer children through compression #10333)
• Benchmarks for compute over integer and decimal Narrow
• Decimal Narrow in memory (needed by Tracking Issue: Fix Canonical Decimal #10701)
• vortex.narrow wire format for integers and decimals in a preview edition together with DecimalByteParts v2, with the compressor wrapping top-level integer and decimal columns in Narrow (second part of feat(compress): retain Narrow integer children through compression #10333)
• vortex.narrow and DecimalByteParts v2 in a core edition

Unresolved questions

• Should we store the entire DecimalDType in the Narrow metadata, which includes scale? It is kind of pointless because the scale is always the same, but it also doesn't really hurt.
  • No, the metadata stores only the child precision. The scale and nullability of the child always equal those of the parent, so storing them only lets a file hold an invalid child. The format is in no edition yet, so this can still change.
• Should List and ListView offsets always have an I64 dtype, with Narrow providing the narrow physical width? (From the discussion on Epic: Implement Narrow integer encoding #10020.)

Implementation history

• Research: [DO NOT MERGE] Research notes on extension types, Decimal and casts #10633
• feat(array): add Narrow integer encoding #10223
• feat(array): push arithmetic and selection through Narrow #10332
• feat(compress): retain Narrow integer children through compression #10333