Casting support for RunEndEncoded arrays #8589

vegarsti · 2025-10-11T05:36:43Z

Which issue does this PR close?

Contribues towards the RunEndEncoded (REE) epic [Epic] Implement RunArray (Run Length Encoding (RLE) / Run End Encoding (REE) support) #3520, but no specific issue for casting.
Replaces PRs Implemented casting for RunEnd Encoding #7713 and [Draft] Implemented casting for RunEnd Encoding (pt2) #8384.

Rationale for this change

This PR implements casting support for RunEndEncoded arrays in Apache Arrow.

Any attempt to cast run-end indices to a narrower integer type will fail immediately if it would result in overflow
Narrowing conversions (e.g., from Int64 to Int16) will always fail if any values exceed the target type’s bounds
Upcasts (e.g., Int16 → Int32 -> Int64) are allowed, as they are lossless.
Widening conversions (e.g., from Int16 to Int64) are allowed, as they are inherently lossless

What changes are included in this PR?

Users can now cast RunEndEncoded arrays using the standard arrow_cast::cast() function

run_end_encoded_cast(): Casts values within existing RunEndEncoded arrays to different types
cast_to_run_end_encoded(): Converts regular arrays to RunEndEncoded format with run-end encoding
Updated can_cast_types() to support RunEndEncoded compatibility rules. Downcasting is not allowed.

Are these changes tested?

Yes!

Are there any user-facing changes?

No breaking changes, just new functionality

vegarsti · 2025-10-11T06:26:59Z

Raised this PR to get Richard Baah's excellent work over the line! cc @albertlockett @brancz @alamb @Rich-T-kid

brancz

I think we're getting close to the finish line with these changes!

brancz · 2025-10-11T14:41:51Z

arrow-cast/src/cast/run_array.rs

+            (false, false) => match value_type {
+                // Primitive types
+                DataType::Boolean => {
+                    cast_array.as_boolean().value(i) == cast_array.as_boolean().value(i - 1)


Can we invert all these comparisons instead? As in switch on value types, and then cast once and perform all iterations. I find this both hard to read, and we probably perform extra unnecessary work because of that (it's possible the compiler might optimize it away, but I don't think so).

Excellent idea!

Did a quick and dirty one now in 88c0d8a, there might be a common trait I could use for arrays to avoid repeating a lot of the code - I haven't found that yet.

Casting then iterating instead of casting within the loop is a very good idea, sounds obvious after hearing it!

Did a second iteration this morning in 2358010 (I've replaced the commit above). Tried to follow a somewhat similar approach as is done with dictionaries.

Added a macro in 692f6ea

Implement casting between REE arrays and other Arrow types. REE-to-REE casting validates run-end upcasts only (Int16→Int32, Int16→Int64, Int32→Int64) to prevent invalid sequences.

Implement casting between REE arrays and other Arrow types. REE-to-REE casting validates run-end upcasts only (Int16→Int32, Int16→Int64, Int32→Int64) to prevent invalid sequences. rebased changes

…entify runs

tustvold · 2025-10-12T22:20:03Z

Is there some way we can avoid the quadratic codegen with code paths parameterized on both run end type and value type? Perhaps it'd be possible to identify where the transitions are, perhaps using the comparison kernels and comparing the array with a slice offset by one, and then use this to construct the indexes and a filter to construct the values array?

Have we done any empirical quantification into the impact this has on code bloat / compile times?

Edit: https://docs.rs/arrow-ord/latest/arrow_ord/partition/fn.partition.html is the function I'm thinking of.

vegarsti · 2025-10-13T06:31:01Z

Have we done any empirical quantification into the impact this has on code bloat / compile times?

I have not! Happy to do that though. Any pointers to how you'd like me to do that, from previous PRs for example? Or does a basic comparison of compile time and binary size on main and this branch suffice?

tustvold · 2025-10-13T08:46:27Z

Or does a basic comparison of compile time and binary size on main and this branch suffice?

Just this, quadratic codegen is typically severe enough to be easily measurable.

vegarsti · 2025-10-13T10:18:53Z

The compile time increased by 2 seconds.

         cargo build --release
main     569.35s user 23.69s system 863% cpu 1:08.66 total
branch   567.33s user 23.96s system 891% cpu 1:06.33 total

The size of libarrow_cast.rlib increased by 279kb (3.82%)

         libarrow_cast.rlib size
main     7,316,832
branch   7,596,568

tustvold · 2025-10-13T10:21:47Z

Yeah... That's quite bad for a single kernel, especially given the relatively niche usage of RunEndEncodedArrays, I hope you can understand that we need to be careful to keep this under control.

What did you think of my suggestion about using the partition kernel to compute the run ends? It might actually be faster and would largely eliminate the additional codegen.

It would mean making arrow-cast depend on arrow-ord, which is a bit meh, but perhaps unavoidable. It could possibly be a feature flag. 🤔

vegarsti · 2025-10-13T11:14:08Z

I understand! I haven't had time to look into your suggestion, but I will.

Out of curiosity, though, the approach in this PR seems quite similar to the code for dictionaries. Does the dictionary code similarly bloat the binary, and if so, why is that acceptable but not for REE?

tustvold · 2025-10-13T11:23:03Z

Out of curiosity, though, the approach in this PR seems quite similar to the code for dictionaries. Does the dictionary code similarly bloat the binary, and if so, why is that acceptable but not for REE?

Dictionaries run into similar challenges, and a lot of effort has been expended trying to mitigate the bloat they cause. For example #3616 #4705 #4701 to name a few. Ultimately it's a compromise, there isn't a way to avoid this bloat and support dictionaries so we pay the tax, with run-end encoded arrays the tax isn't necessary and so it is better we don't pay it.

vegarsti · 2025-10-13T11:31:16Z

Out of curiosity, though, the approach in this PR seems quite similar to the code for dictionaries. Does the dictionary code similarly bloat the binary, and if so, why is that acceptable but not for REE?

Dictionaries run into similar challenges, and a lot of effort has been expended trying to mitigate the bloat they cause. For example #3616 #4705 #4701 to name a few. Ultimately it's a compromise, there isn't a way to avoid this bloat and support dictionaries so we pay the tax, with run-end encoded arrays the tax isn't necessary and so it is better we don't pay it.

Thanks for the context!

brancz · 2025-10-13T19:41:00Z

We're talking about the pack_runs macro right? I realize it's nice as a macro, but it also seems fine to just write out by hand.

tustvold · 2025-10-13T19:47:45Z

The fact it is a macro is not the issue here, the problem is code generation based with complexity <Number of Index Types> * <Number of Value Types> which results in slow compilation and binary bloat. Whether this is achieved with macros, generics or copy paste doesn't change this 😄

brancz · 2025-10-14T08:50:14Z

Got it. The way I see it, there are two paths. Either:

We manage to get it to work with arrow_ord's partition and avoid the amount of code required altogether (whether by macro or not)
We do it via macro but put ree casting behind a feature flag, so users who wants this can opt into it (although it feels a little strange to hide features that are very reasonable and available for other types behind a feature flag, but I don't feel strongly one way or another as we'd just enable it and move on).

@vegarsti can you give the arrow-ord partitioning a try so we understand whether this would be a workable path?

vegarsti · 2025-10-14T10:04:52Z

Yeah, I will give the arrow-ord partitioning a try. Some time this week! It seems like a good approach, thanks @tustvold!

As for the feature flag, to me that seems a bit complicated - either the REE type should be supported or not, imo? Also, unless I'm missing something, whether to put this in a feature flag would apply to the whole REE epic #3520, so that should (eventually) be raised there.

It would be great with some guidelines for the arrow-rs project with regard to the tradeoff between features and size/compile times. I'm guessing opinions might vary a bit between maintainers as well. Guidelines might make it easier to come to alignment in such discussions.

In any case, maybe we get around this issue with the arrow-ord approach 🙏🏻

vegarsti · 2025-10-15T13:23:10Z

Okay I have the scaffolding but tests fail. Stay tuned 👀

github-actions bot added the arrow Changes to the arrow crate label Oct 11, 2025

This was referenced Oct 11, 2025

[Draft] Implemented casting for RunEnd Encoding (pt2) #8384

Draft

Convert RunEndEncoded to Parquet #8069

Draft

vegarsti changed the title ~~Casting to/from RunEndEncoded arrays~~ Casting support for RunEndEncoded arrays Oct 11, 2025

vegarsti force-pushed the cast-run-end-encoded-arrays branch 2 times, most recently from 87e543d to f9ae6f9 Compare October 11, 2025 06:25

brancz reviewed Oct 11, 2025

View reviewed changes

rich-t-kid-datadog and others added 10 commits October 12, 2025 07:49

Implemented casting for RunEnd Encoding

ca051e2

Implemented casting for RunEnd Encoding

60c52b4

feat: Add Run-End Encoded array casting with overflow protection

0a6d865

Implement casting between REE arrays and other Arrow types. REE-to-REE casting validates run-end upcasts only (Int16→Int32, Int16→Int64, Int32→Int64) to prevent invalid sequences.

feat: Add Run-End Encoded array casting with overflow protection

8b434d4

Implement casting between REE arrays and other Arrow types. REE-to-REE casting validates run-end upcasts only (Int16→Int32, Int16→Int64, Int32→Int64) to prevent invalid sequences. rebased changes

Use type specific zero-copy comparisons in cast_to_run_end_encoded

77cda81

Move tests in mod run_end_encoded_tests into mod tests

b666a97

panic if REE in cast_to_run_end_encoded

6eafcea

Use unreachable macro

3c2e837

Simplify some assertions

d1e5120

Extract populate_run_ends_and_values, which casts then iterates to id…

2358010

…entify runs

vegarsti force-pushed the cast-run-end-encoded-arrays branch from 88c0d8a to 2358010 Compare October 12, 2025 05:49

vegarsti added 2 commits October 12, 2025 08:39

Add missing Float16 and Decimal types to can_cast_to_run_end_encoded

7ed2872

Use a macro for packing runs

692f6ea

Casting support for RunEndEncoded arrays #8589

Are you sure you want to change the base?

Casting support for RunEndEncoded arrays #8589

Uh oh!

Conversation

vegarsti commented Oct 11, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Which issue does this PR close?

Rationale for this change

What changes are included in this PR?

Are these changes tested?

Are there any user-facing changes?

Uh oh!

vegarsti commented Oct 11, 2025

Uh oh!

brancz left a comment

Choose a reason for hiding this comment

Uh oh!

brancz Oct 11, 2025

Choose a reason for hiding this comment

Uh oh!

vegarsti Oct 11, 2025

Choose a reason for hiding this comment

Uh oh!

vegarsti Oct 11, 2025

Choose a reason for hiding this comment

Uh oh!

vegarsti Oct 12, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vegarsti Oct 12, 2025

Choose a reason for hiding this comment

Uh oh!

tustvold commented Oct 12, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vegarsti commented Oct 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tustvold commented Oct 13, 2025

Uh oh!

vegarsti commented Oct 13, 2025

Uh oh!

tustvold commented Oct 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vegarsti commented Oct 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tustvold commented Oct 13, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vegarsti commented Oct 13, 2025

Uh oh!

brancz commented Oct 13, 2025

Uh oh!

tustvold commented Oct 13, 2025

Uh oh!

brancz commented Oct 14, 2025

Uh oh!

vegarsti commented Oct 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vegarsti commented Oct 15, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

vegarsti commented Oct 11, 2025 •

edited

Loading

vegarsti Oct 12, 2025 •

edited

Loading

tustvold commented Oct 12, 2025 •

edited

Loading

vegarsti commented Oct 13, 2025 •

edited

Loading

tustvold commented Oct 13, 2025 •

edited

Loading

vegarsti commented Oct 13, 2025 •

edited

Loading

tustvold commented Oct 13, 2025 •

edited

Loading

vegarsti commented Oct 14, 2025 •

edited

Loading