You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "RyanMarcus (via GitHub)" <gi...@apache.org> on 2024/11/18 21:27:05 UTC
[PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
RyanMarcus opened a new pull request, #6752:
URL: https://github.com/apache/arrow-rs/pull/6752
# Which issue does this PR close?
Helps address part of " Support REE in cast kernels" in #3520
# Rationale for this change
Adds support for (limited) casting/conversion of REE arrays.
# What changes are included in this PR?
* Adds casting to change the type of the run ends in an REE array (e.g., convert from storing each run end as a Int16 to a Int32)
* Adds casting from REE arrays of all primitive types to a "flat" array (which is a `PrimitiveArray` under the hood).
# Are there any user-facing changes?
Currently, `can_cast_type` basically returns false for anything involving an REE array. This PR implements a subset of important casts, but not all of them. Users may be surprised that, for example, a REE array of Int32 can be converted to an array of Int32, but an REE array of Utf8 can't be converted to a Utf8 array (yet).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850621440
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
+ // array is initially transformed into a flat array of the same
+ // type, then casted to the (potentially) new type. For example,
+ // casting a run encoded array of Float32 to Float64 will first
+ // create a primitive array of Float32s, then convert that primitive
+ // array to Float64.
+ cast_with_options(&run_array_to_flat(ree_array)?, to_type, cast_options)
+ }
+ }
+}
+
+/// "Unroll" a run-end encoded array of primitive values into a primitive array.
+/// This function should be efficient for long run lenghts due to the use of
+/// Builder's `append_value_n`. Uses `PrimitiveBuilder`, so does not do any
+/// interpretation.
+fn typed_run_array_to_primitive<R: RunEndIndexType, T: ArrowPrimitiveType>(
+ arr: TypedRunArray<R, PrimitiveArray<T>>,
+) -> ArrayRef {
+ let mut builder = PrimitiveArray::<T>::builder(
+ arr.run_ends()
+ .values()
+ .last()
+ .map(|end| end.as_usize())
+ .unwrap_or(0),
+ );
+
+ // copy all values into the builder
+ let mut last = 0;
+ for (run_end, val) in arr
+ .run_ends()
+ .values()
+ .iter()
+ .zip(arr.values().values().iter().copied())
+ {
+ let run_end = run_end.as_usize();
+ let run_length = run_end - last;
+ builder.append_value_n(val, run_length);
+ last = run_end;
+ }
+ let mut result = builder.finish();
+
+ // if we have null values, decode them as well
+ if let Some(null_buffer) = arr.values().nulls() {
+ let mut nbb = NullBufferBuilder::new(builder.len());
+
+ let mut last = 0;
+ for (run_end, val) in arr.run_ends().values().iter().zip(null_buffer.iter()) {
+ let run_end = run_end.as_usize();
+ let run_length = run_end - last;
+ if val {
+ nbb.append_n_non_nulls(run_length);
+ } else {
+ nbb.append_n_nulls(run_length);
+ }
+
+ last = run_end;
+ }
+
+ let nb = nbb.finish();
+ result = PrimitiveArray::<T>::new(result.values().clone(), nb);
+ }
+
+ // TODO: this slice could be optimized by only copying the relevant parts of
Review Comment:
Not tested but I _think_ this should work. My concern with the slicing logic, is such things have a storied history of subtle bugs.
```
let min_end = arr.offset();
let max_end = arr.offset() + arr.length();
let last = min_end;
for (run_end, val) in arr.run_ends().values().iter().zip(null_buffer.iter()) {
let run_end = clamp(run_end.as_usize(), min_end, max_end);
let run_length = run_end - last;
if val {
nbb.append_n_non_nulls(run_length);
} else {
nbb.append_n_nulls(run_length);
}
last = run_end;
}
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2484542440
As you suspected @tustvold , `MutableArrayData` enabled an implementation that was much smaller! And should reuse all the existing generics codegen from `transform`.
In order to make this efficient, we need a `extend_n` function on `MutableArrayData` that copies the same bits many times. Here is a dummy (working) implementation:
```rust
pub fn extend_n(&mut self, index: usize, start: usize, end: usize, n: usize) {
for _ in 0..n {
self.extend(index, start, end);
}
}
```
I can see that `MutableArrayData` uses some kind of dynamic dispatch magic for each call to `extend` which I don't fully understand, but I understand enough to know that my current `extend_n` is no good. I'll mark this PR as a draft until I figure it out.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1851025127
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
Just to be clear, the standard is only `Int16`, `Int32`, and `Int64`, no `Int8` (which is reflected in the code). I think `Int16` / the smaller integer types are actually the most common (this is also the case in Parquet's dictionary run length encoding).
I didn't realize that even this amount of extra codegen was an issue. If I am literally the only user of this feature, we simply shouldn't do this at all. Honestly, this won't even solve my problem, since a 30%-2x slowdown on some types means I will just have to implement the full thing in my own code anyway. Luckily in my project, we are significantly less constrained by code size.
Probably the "right thing" to do is somehow split up cast into pieces, so people can opt into what they need, either with feature flags or with more subcrates, but I think that's a pretty large refactor.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2486663538
What is the average run length in that case?
We could specialise primitives, and there are ways we can reduce codegen - e.g. only specialize i32 run ends and only specialise on ArrowNativeType not ArrowPrimitiveType like we do for dictionaries.
Ultimately given how few people use RunArray, we need to err on the side of keeping codegen manageable
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2486570327
I've added a more efficient `extend_n` function that works by passing the count parameter `n` to each closure. But I realized that in the worst case scenario, where each run length is 1, this approach will still do interpretation for every value.
A simple benchmark converting a REE array of i32s to a primitive array:
```
With PrimitiveBuilder:
cast run end to flat time: [34.395 ms 34.453 ms 34.519 ms]
With MutableArrayData:
cast run end to flat time: [48.710 ms 48.869 ms 49.067 ms]
```
... so the avoiding the interpretation overhead seems to cause a 30% speedup. Does a 30% performance improvement in the worst case justify the extra codegen, @tustvold ?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850601711
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
I imagine copying Int16 data up to Int32 would have a pretty large performance penalty in this case. For `DictionaryArray`, each access to the values is potentially random and therefore a cache miss, but for REE we will always read the run ends and the values sequentially. So my guess is that an extra data copy like that would 2x the runtime. Does that make sense or should I write a bench?
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
Review Comment:
You mean [this trait?](https://docs.rs/arrow/latest/arrow/array/trait.AsArray.html) I don't think there's an `as_run_array` or similar. I can add it, but the overall line count will go up.
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
Review Comment:
This enables converting REE arrays of one type to another, for example from Int32 runs and Float64 data to Int16 runs and Float32 data. See `test_run_end_to_run_end` for an example.
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
Review Comment:
When we construct a `PrimitiveArray` from the run ends buffer, we have to construct the `PrimitiveArray` from the *inner* buffer, which doesn't have the offset information. So we have to re-slice it here. Added some code to `test_run_end_to_run_end` to confirm this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2486929566
My benchmark is a worst-case scenario, so every run length is 1, and thus the average is 1 as well. Not a realistic scenario, but illustrative of the worst case.
If we increase all run lengths to 10 (which is the average in my application, at least) and keeping the logical data size the same, the results are:
```
With PrimitiveBuilder:
cast run end to flat time: [11.740 ms 11.778 ms 11.818 ms]
With MutableArrayData:
cast run end to flat time: [21.837 ms 21.917 ms 22.000 ms]
```
Both approaches get faster, but the relative gap is larger.
The current version hits the compromise you mentioned: the specialized kernel is used for {i/u/f}{8/16/32/64}, and the interpretation-powered one is used for the rest.
I am not fully confident I correctly modified all of the `MutableArrayData` to handle internals, but the tests at least pass. If you want, I can swap back to the "dummy" version I proposed earlier, since the specialized kernel should hit the most common cases.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2484457349
I know you just gave it as an example, but `take` would be significantly slower since it would require materializing an index array, which can't be trivially computed from the run ends (unlike for dictionaries, where the values are the indices).
I took a brief look at the other existing kernels and didn't see anything that looked promising. If you can point me to something specific I'm happy to take a look!
I'm not currently familiar with MutableDataArray, let me take a look and get back to you.
One mitigating factor to the extra codegen is the fact that this is limited to the `cast` subcrate. We could also add an `arrow-cast-ree` or similar, if that's a concern.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2484462775
Just looked at `MutableArrayData` which seems like a perfect candidate for `Copy` types. Let me try to change my implementation to that, I agree it has potential to cut down a lot on codegen.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2489608964
See https://github.com/apache/arrow-rs/pull/6752#discussion_r1851025127 -- I don't think this is worthwhile if minimizing codegen is such a high priority. If someone else is looking at this PR, feel free to use my kernels for your REE arrays!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2486668039
What is the average run length in that case?
We could specialise primitives, and there are ways we can reduce codegen - e.g. only specialize i32 run ends and only specialise on ArrowNativeType not ArrowPrimitiveType like we do for dictionaries.
Ultimately given how few people use RunArray, we need to err on the side of keeping codegen manageable
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#issuecomment-2487896539
> If you want, I can swap back to the "dummy" version I proposed earlier, since the specialized kernel should hit the most common cases.
Let's swap it back
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850629425
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
Review Comment:
Or even just pass re_array.run_ends() to the cast kernel directly...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850611402
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
> I imagine copying Int16 data up to Int32 would have a pretty large performance penalty in this case
I think we have to be pragmatic here, ultimately Int8 and Int16 are somewhat useless, only able to support arrays of maximum length 128 and 32768 respectively. I'm honestly not entirely sure why they were standardised...
Another option might be to fallback to ArrayData for the Int8, Int16 and Int64 cases. We really need to try to keep this change small
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus closed pull request #6752: Adds partial `cast` support for run-end encoded arrays
URL: https://github.com/apache/arrow-rs/pull/6752
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "RyanMarcus (via GitHub)" <gi...@apache.org>.
RyanMarcus commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850602203
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
Review Comment:
Or compilation, I guess.
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
+ // array is initially transformed into a flat array of the same
+ // type, then casted to the (potentially) new type. For example,
+ // casting a run encoded array of Float32 to Float64 will first
+ // create a primitive array of Float32s, then convert that primitive
+ // array to Float64.
+ cast_with_options(&run_array_to_flat(ree_array)?, to_type, cast_options)
+ }
+ }
+}
+
+/// "Unroll" a run-end encoded array of primitive values into a primitive array.
+/// This function should be efficient for long run lenghts due to the use of
+/// Builder's `append_value_n`. Uses `PrimitiveBuilder`, so does not do any
+/// interpretation.
+fn typed_run_array_to_primitive<R: RunEndIndexType, T: ArrowPrimitiveType>(
+ arr: TypedRunArray<R, PrimitiveArray<T>>,
+) -> ArrayRef {
+ let mut builder = PrimitiveArray::<T>::builder(
Review Comment:
Ah, good idea -- this indeed reduced latency by a few ms!
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
+ // array is initially transformed into a flat array of the same
+ // type, then casted to the (potentially) new type. For example,
+ // casting a run encoded array of Float32 to Float64 will first
+ // create a primitive array of Float32s, then convert that primitive
+ // array to Float64.
+ cast_with_options(&run_array_to_flat(ree_array)?, to_type, cast_options)
+ }
+ }
+}
+
+/// "Unroll" a run-end encoded array of primitive values into a primitive array.
+/// This function should be efficient for long run lenghts due to the use of
+/// Builder's `append_value_n`. Uses `PrimitiveBuilder`, so does not do any
+/// interpretation.
+fn typed_run_array_to_primitive<R: RunEndIndexType, T: ArrowPrimitiveType>(
+ arr: TypedRunArray<R, PrimitiveArray<T>>,
+) -> ArrayRef {
+ let mut builder = PrimitiveArray::<T>::builder(
+ arr.run_ends()
+ .values()
+ .last()
+ .map(|end| end.as_usize())
+ .unwrap_or(0),
+ );
+
+ // copy all values into the builder
+ let mut last = 0;
+ for (run_end, val) in arr
+ .run_ends()
+ .values()
+ .iter()
+ .zip(arr.values().values().iter().copied())
+ {
+ let run_end = run_end.as_usize();
+ let run_length = run_end - last;
+ builder.append_value_n(val, run_length);
+ last = run_end;
+ }
+ let mut result = builder.finish();
+
+ // if we have null values, decode them as well
+ if let Some(null_buffer) = arr.values().nulls() {
+ let mut nbb = NullBufferBuilder::new(builder.len());
+
+ let mut last = 0;
+ for (run_end, val) in arr.run_ends().values().iter().zip(null_buffer.iter()) {
+ let run_end = run_end.as_usize();
+ let run_length = run_end - last;
+ if val {
+ nbb.append_n_non_nulls(run_length);
+ } else {
+ nbb.append_n_nulls(run_length);
+ }
+
+ last = run_end;
+ }
+
+ let nb = nbb.finish();
+ result = PrimitiveArray::<T>::new(result.values().clone(), nb);
+ }
+
+ // TODO: this slice could be optimized by only copying the relevant parts of
Review Comment:
I was having a hard time getting the logic right for a case like this:
run ends: [5, 10]
slice offset: 3 len: 5
... because you have to take 2 of the first value and then 3 of the second value. I can give it a shot if you want but I think it'll just be a source of bugs.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850613279
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
Review Comment:
I think that would be a good addition, happy for that to be a separate PR though, there are many other places that could use AsArray though in this diff
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1851067294
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
> this is also the case in Parquet's dictionary run length encoding
Parquet is run length, this is run end, and consequently the primitive type constrains the maximum length of the array, as opposed to the maximum length of a run.
I'm sorry that we can't just add more codegen, but it has been a perennial issue for us that the full arrow specification is a combinatorial explosion, and so we have to pick some compute-optimised versions, and accept that space-optimised variants may incur a slight performance penalty. We should probably do a better job documenting this
> code size.
It's actually build time that is the biggest pain point, there was a time when half the build time of the entire workspace was just the dictionary comparison kernels 😅
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1849853557
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
Do we need all 3 or could we just handle int32 and cast Int8 and Int16 to this. This is what we do for DictionaryArray?
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
Review Comment:
Using AsArray may be more concise
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
+ // array is initially transformed into a flat array of the same
+ // type, then casted to the (potentially) new type. For example,
+ // casting a run encoded array of Float32 to Float64 will first
+ // create a primitive array of Float32s, then convert that primitive
+ // array to Float64.
+ cast_with_options(&run_array_to_flat(ree_array)?, to_type, cast_options)
+ }
+ }
+}
+
+/// "Unroll" a run-end encoded array of primitive values into a primitive array.
+/// This function should be efficient for long run lenghts due to the use of
+/// Builder's `append_value_n`. Uses `PrimitiveBuilder`, so does not do any
+/// interpretation.
+fn typed_run_array_to_primitive<R: RunEndIndexType, T: ArrowPrimitiveType>(
+ arr: TypedRunArray<R, PrimitiveArray<T>>,
+) -> ArrayRef {
+ let mut builder = PrimitiveArray::<T>::builder(
+ arr.run_ends()
+ .values()
+ .last()
+ .map(|end| end.as_usize())
+ .unwrap_or(0),
+ );
+
+ // copy all values into the builder
+ let mut last = 0;
+ for (run_end, val) in arr
+ .run_ends()
+ .values()
+ .iter()
+ .zip(arr.values().values().iter().copied())
+ {
+ let run_end = run_end.as_usize();
+ let run_length = run_end - last;
+ builder.append_value_n(val, run_length);
+ last = run_end;
+ }
+ let mut result = builder.finish();
+
+ // if we have null values, decode them as well
+ if let Some(null_buffer) = arr.values().nulls() {
+ let mut nbb = NullBufferBuilder::new(builder.len());
+
+ let mut last = 0;
+ for (run_end, val) in arr.run_ends().values().iter().zip(null_buffer.iter()) {
+ let run_end = run_end.as_usize();
+ let run_length = run_end - last;
+ if val {
+ nbb.append_n_non_nulls(run_length);
+ } else {
+ nbb.append_n_nulls(run_length);
+ }
+
+ last = run_end;
+ }
+
+ let nb = nbb.finish();
+ result = PrimitiveArray::<T>::new(result.values().clone(), nb);
+ }
+
+ // TODO: this slice could be optimized by only copying the relevant parts of
Review Comment:
I _think_ this should be as simple as clamping the run end in the loop to be in the sliced range
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
+ // array is initially transformed into a flat array of the same
+ // type, then casted to the (potentially) new type. For example,
+ // casting a run encoded array of Float32 to Float64 will first
+ // create a primitive array of Float32s, then convert that primitive
+ // array to Float64.
+ cast_with_options(&run_array_to_flat(ree_array)?, to_type, cast_options)
+ }
+ }
+}
+
+/// "Unroll" a run-end encoded array of primitive values into a primitive array.
+/// This function should be efficient for long run lenghts due to the use of
+/// Builder's `append_value_n`. Uses `PrimitiveBuilder`, so does not do any
+/// interpretation.
+fn typed_run_array_to_primitive<R: RunEndIndexType, T: ArrowPrimitiveType>(
+ arr: TypedRunArray<R, PrimitiveArray<T>>,
+) -> ArrayRef {
+ let mut builder = PrimitiveArray::<T>::builder(
Review Comment:
You don't even need to use the builder here, you could just use a Vec and the PrimitiveArray constructor. This has a good chance of being faster as Vec has lots of specialized optimisations
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
Review Comment:
Why is this slicing needed?
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
+ let re = cast_with_options(&re, re_t.data_type(), cast_options)?;
+
+ // TODO: we shouldn't need to validate the new run length array
+ // since we can assume we are converting from a valid one, but
+ // there's no "unchecked" variant yet
+ let result: Arc<dyn Array> = match re.data_type() {
+ DataType::Int16 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int16Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int32 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int32Array>().unwrap(),
+ &values,
+ )?),
+ DataType::Int64 => Arc::new(RunArray::try_new(
+ re.as_any().downcast_ref::<Int64Array>().unwrap(),
+ &values,
+ )?),
+ _ => Err(ArrowError::ComputeError(format!(
+ "Invalid run end type requested during cast: {:?}",
+ re.data_type()
+ )))?,
+ };
+
+ Ok(result.slice(ree_array.run_ends().offset(), ree_array.run_ends().len()))
+ }
+ // We match against the native types in order to use an optimized kernel
+ (DataType::Int8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Int64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Int64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt8, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt8Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::UInt64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<UInt64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float16, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float16Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float32, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float32Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ (DataType::Float64, _) => cast_with_options(
+ &typed_run_array_to_primitive(ree_array.downcast::<Float64Array>().unwrap()),
+ to_type,
+ cast_options,
+ ),
+ // For all other types, we use an interpretation-based approach
+ _ => {
+ // TODO this could be somewhat inefficent, since the run encoded
Review Comment:
I don't see an obvious way around this without unbounded codegen
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
Review Comment:
Why is this necessary?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1851067294
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
> this is also the case in Parquet's dictionary run length encoding
Parquet is run length, this is run end, and consequently the primitive type constrains the maximum length of the array, as opposed to the maximum length of a run.
I'm sorry that we can't just add more codegen, but it has been a perennial issue for us that the full arrow specification is a combinatorial explosion, and so we have to pick some compute-optimised versions, and accept that space-optimised variants may incur a slight performance penalty. We should probably do a better job documenting this
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850611402
##########
arrow-cast/src/cast/mod.rs:
##########
@@ -759,6 +763,12 @@ pub fn cast_with_options(
"Casting from type {from_type:?} to dictionary type {to_type:?} not supported",
))),
},
+ (RunEndEncoded(re_t, _dt), _) => match re_t.data_type() {
Review Comment:
> I imagine copying Int16 data up to Int32 would have a pretty large performance penalty in this case
I think we have to be pragmatic here, ultimately Int8 and Int16 are somewhat useless, only able to support arrays of maximum length 128 and 32768 respectively. I'm honestly not entirely sure why they were standardised...
Another option might be to fallback to ArrayData for those cases.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Adds partial `cast` support for run-end encoded arrays [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on code in PR #6752:
URL: https://github.com/apache/arrow-rs/pull/6752#discussion_r1850616243
##########
arrow-cast/src/cast/runend.rs:
##########
@@ -0,0 +1,330 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::sync::Arc;
+
+use arrow_array::{
+ builder::ArrayBuilder, make_array, types::RunEndIndexType, Array, ArrayRef, ArrowPrimitiveType,
+ Float16Array, Float32Array, Float64Array, Int16Array, Int32Array, Int64Array, Int8Array,
+ PrimitiveArray, RunArray, TypedRunArray, UInt16Array, UInt32Array, UInt64Array, UInt8Array,
+};
+use arrow_buffer::{ArrowNativeType, NullBufferBuilder};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType};
+
+use crate::cast_with_options;
+
+use super::CastOptions;
+
+/// Attempt to cast a run-encoded array into a new type.
+///
+/// `K` is the *current* run end index type
+pub(crate) fn run_end_cast<K: RunEndIndexType>(
+ array: &dyn Array,
+ to_type: &DataType,
+ cast_options: &CastOptions,
+) -> Result<ArrayRef, ArrowError> {
+ let ree_array = array
+ .as_any()
+ .downcast_ref::<RunArray<K>>()
+ .ok_or_else(|| {
+ ArrowError::ComputeError(
+ "Internal Error: Cannot cast run end array to RunArray of the expected type"
+ .to_string(),
+ )
+ })?;
+
+ let curr_value_type = ree_array.values().data_type();
+
+ match (curr_value_type, to_type) {
+ // Potentially convert to a new value or run end type
+ (_, DataType::RunEndEncoded(re_t, dt)) => {
+ let values = cast_with_options(ree_array.values(), dt.data_type(), cast_options)?;
+ let re = PrimitiveArray::<K>::new(ree_array.run_ends().inner().clone(), None);
Review Comment:
```suggestion
let re = ree_array.run_ends().clone();
```
?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org