First class FixedSizeBinary support

[brancz]

Problem or motivation

We've come across FixedSizeBinary shape issues a couple of times. Some of them we could cover with a uuid extension type, but it comes up more and more often. In our case most recently to store trigrams as FixedSizeBinary(3).

• Tracking Issue: Uuid Extension Type #6854
• DType::from_arrow panics with unimplemented! for Duration, Interval and FixedSizeBinary instead of returning an error #8346
• Convert FixedSizeBinary scalars to fixed-size lists, not Binary #9886
• Add fixed-size binary support #8865

Proposed solution

@joseph-isaacs mentioned there are a few possible solutions and we just need to decide on the path we want to go. We discussed in yesterday's TSC call that we should open this issue to list them out and make a decision.

Additional context

No response

[joseph-isaacs]

I think are two parts we need to decide for the type

1. What is the semantics of this, is it just a DType::Binary where all rows have a set number of bytes, or do we want other semantics
   a. We might want over-alignment guarantees [This could be quite useful]. We could align powers of two?

2. How does this fit in with fixed sized list and the already existing List and and Binary type
   a. Do we prefer one type with a optional size or another new type FixedSizeBinary?
   b. Should we use an extension type over Binary?
   c. Name FixedSizeBinary, FixedSizeBytes, Maybe we want to later allow FixedSizeBits?

Then we also need to design the canonical type for this.

Does this look like arrow with a single contiguous buffer of len * size or would we add something to allow cheap filtering and taking/selecting.

Final aside. Should we then impl all of our fixed sized types using this (i.e. Primitive, Decimal, VarBinView), then lots of kernels need only be implemented once.

[brancz]

Should we then impl all of our fixed sized types using this (i.e. Primitive, Decimal, VarBinView), then lots of kernels need only be implemented once.

What would be the steps going backwards from this to make this backward compatible?

[joseph-isaacs]

What would be the steps going backwards from this to make this backward compatible?

I think that this is likely not work de-railing this issue over. Once we figure out FSB I think we could review this

[brancz]

In that case I would propose:

1. Not sure, off hand sounds fine, but not sure what the other consequences would be.
   a. Yes, default power of two, but entirely configurable by the user. I can also imagine use cases where for size reasons not aligning at all would be what users would want, but certainly not by default.

a. Yes
b. I don't think so, I think even if there were no technical issues with this, it might communicate confusingly to users
c. No strong opinion, but would suggest FixedSizeBinary since we already have Binary.

The most primitive version seems like the right fit for the canonical type.

Yes, like arrow, size * len. Why would this not enable cheap filtering/taking? Perhaps missing a detail here.

Based on the previous comment, sounds good, let's revisit once fsb exists.

[joseph-isaacs]

1. I would think we would only align if its a power of two otherwise not for size reasons.
2. _
   a. yes to new type vs changing an existing one
   b. I mostly agree but there is cost to how many dtypes we have.

Why would this not enable cheap filtering/taking? Perhaps missing a detail here.

Consider if you want to remove a middle value you then must move all subsequent values left by 1
A list view allows swapping values without copying the actual values, We could have a values and offsets array (with constant lens).