Implement support for Decimal with 256 bits of precision.

[alamb]

Note: migrated from original JIRA: https://issues.apache.org/jira/browse/ARROW-10602

The specification now supports it and there are basic implementations in C++/Java

The basic idea would be to:

1. Study the C++ implementation that allows both i128 and i256 backing
2. Propose a Rust implementation
3. Implement said Rust implementation (ideally by breaking it down into smaller issues that the community could help with)

[alexlee85]

It's been over a year ......

[alamb]

Thanks for the nudge @alexlee85 -- I left some ideas on how to proceed. Let's see if we can find someone to help!

[viirya]

I'm looking around at Decimal support in C++. Roughly I think we have some subtasks:

• Add Decimal128 API and use it in DecimalArray and DecimalBuilder #1870
• Add Decimal256 API #1913
• Support Decimal256Builder and Decimal256Array #1999
• Rename DecimalArray/DecimalBuilder to Decimal128Array/Decimal128Builder #2101
• Pass generate_decimal256_case arrow integration test #2093
• Do value validation for Decimal256 #2112
• Use ArrayAccessor in Decimal128Iter and Decimal256Iter #2138
• Check precision and scale against maximum value when constructing Decimal128 and Decimal256 #2139
• Rename DataType::Decimal to DataType::Decimal128 #2228
• Impl FromIterator for Decimal256Array #2248
  and IPC & Parquet works if needed, etc.

In C++ implementations, there are Decimal128 and Decimal256 classes. They are used in Decimal128Builder and Decimal256Builder APIs. So users can construct 128/256-decimal values during building the arrays. Although Decimal128Array and Decimal256Array don't provide APIs to get Decimal128 and Decimal256 values directly now.

Basically in Decimal128 and Decimal256 classes, decimal value is represented in an uint64_t array. I think we can follow this up to have Decimal with 256 bits.

In current Rust implementations, we use i128 in DecimalBuilder and DecimalArray APIs. To maintain consistency on Decimal related APIs, we need to change from i128 to Decimal128 in these APIs.

I think we may also need some works in IPC and Parquet for the new Decimal256 support.

[viirya]

I plan to tackle these issues one by one.

[alamb]

In current Rust implementations, we use i128 in DecimalBuilder and DecimalArray APIs. To maintain consistency on Decimal related APIs, we need to change from i128 to Decimal128 in these APIs.

What do you think about using generics (so the APIs are compatible).

So for functions that take i128 like

fn decimal_thing(val: i128) {
...
}

Could be something like

fn decimal_thing(val: impl Into<i128>) {
}

This may be a silly idea that won't make sense as you start implementation 🤔

[viirya]

I think you mean to make Decimal128 to be compatible with i128 so it won't break existing user code?

It makes sense to me.

[alamb]

@viirya has completed this work I believe, including enabling integration tests 🎉 with other arrow implementations
apache/arrow#13685