Rich-T-kid commented on code in PR #12218:
URL: https://github.com/apache/arrow-rs/pull/12218#discussion_r4560702142
##########
arrow-select/src/coalesce.rs:
##########
@@ -82,6 +85,7 @@ fn has_sparse_filter_copy(data_type: &DataType) -> bool {
| DataType::List(_)
| DataType::LargeList(_)
)
+ || matches!(data_type, DataType::RunEndEncoded(_, _))
Review Comment:
Removed RunEndEncoded from the sparse-filter capability set and added an
assertion that REE schemas take the materialized filter path. Fixed in
2193a4bfaf.
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,280 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use super::InProgressArray;
+use arrow_array::cast::AsArray;
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, PrimitiveArray, RunArray, make_array,
new_empty_array};
+use arrow_buffer::ArrowNativeType;
+use arrow_cmp::{DynComparator, make_comparator};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType, SortOptions};
+use std::collections::HashMap;
+use std::fmt::{Debug, Formatter};
+
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ /// The current source used by [`Self::copy_rows`].
+ source: Option<ArrayRef>,
+ /// The data type to use when producing an empty array.
+ data_type: DataType,
Review Comment:
Moved data_type to the final field. Fixed in 2193a4bfaf.
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,280 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use super::InProgressArray;
+use arrow_array::cast::AsArray;
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, PrimitiveArray, RunArray, make_array,
new_empty_array};
+use arrow_buffer::ArrowNativeType;
+use arrow_cmp::{DynComparator, make_comparator};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType, SortOptions};
+use std::collections::HashMap;
+use std::fmt::{Debug, Formatter};
+
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ /// The current source used by [`Self::copy_rows`].
+ source: Option<ArrayRef>,
+ /// The data type to use when producing an empty array.
+ data_type: DataType,
+ /// The cumulative logical end of each output run.
+ run_ends: Vec<R::Native>,
+ /// Value arrays referenced by the output runs.
+ sources: Vec<ArrayRef>,
+ /// The `(source, physical index)` of each output run value.
+ indices: Vec<(usize, usize)>,
+ /// Comparators cached for pairs of value arrays.
+ comparators: HashMap<(usize, usize), DynComparator>,
+ /// The value array for the current source.
+ current_source: Option<usize>,
Review Comment:
Simplified the state to sources plus output runs and removed the comparator
cache/current-source tracking. Each copied slice now compares only its first
run with the previous output run. Fixed in 2193a4bfaf.
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,280 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use super::InProgressArray;
+use arrow_array::cast::AsArray;
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, PrimitiveArray, RunArray, make_array,
new_empty_array};
+use arrow_buffer::ArrowNativeType;
+use arrow_cmp::{DynComparator, make_comparator};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType, SortOptions};
+use std::collections::HashMap;
+use std::fmt::{Debug, Formatter};
+
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ /// The current source used by [`Self::copy_rows`].
+ source: Option<ArrayRef>,
+ /// The data type to use when producing an empty array.
+ data_type: DataType,
+ /// The cumulative logical end of each output run.
+ run_ends: Vec<R::Native>,
+ /// Value arrays referenced by the output runs.
+ sources: Vec<ArrayRef>,
+ /// The `(source, physical index)` of each output run value.
+ indices: Vec<(usize, usize)>,
+ /// Comparators cached for pairs of value arrays.
+ comparators: HashMap<(usize, usize), DynComparator>,
+ /// The value array for the current source.
+ current_source: Option<usize>,
+ /// The number of logical rows copied into the output.
+ len: usize,
+}
+
+impl<R: RunEndIndexType> Debug for InProgressRunArray<R> {
+ fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
+ f.write_str("InProgressRunArray")
+ }
+}
+
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ data_type,
+ run_ends: Vec::new(),
+ sources: Vec::new(),
+ indices: Vec::new(),
+ comparators: HashMap::new(),
+ current_source: None,
+ len: 0,
+ }
+ }
+
+ fn append_run(&mut self, source: usize, index: usize, len: usize) ->
Result<(), ArrowError> {
+ let next_len = self
+ .len
+ .checked_add(len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let run_end = R::Native::from_usize(next_len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+
+ if let Some(&(last_source, last_index)) = self.indices.last() {
+ if (last_source, last_index) == (source, index) {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ return Ok(());
+ }
+ let key = (last_source, source);
+ if !self.comparators.contains_key(&key) {
+ let comparator = make_comparator(
+ self.sources[last_source].as_ref(),
+ self.sources[source].as_ref(),
+ SortOptions::default(),
+ )?;
+ self.comparators.insert(key, comparator);
+ }
+ if self.comparators[&key](last_index, index).is_eq() {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ *self.indices.last_mut().unwrap() = (source, index);
+ return Ok(());
+ }
+ }
+
+ self.len = next_len;
+ self.run_ends.push(run_end);
+ self.indices.push((source, index));
+ Ok(())
+ }
+}
+
+impl<R: RunEndIndexType> InProgressArray for InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ self.current_source = None;
+ }
+
+ /// Copies a logical row range directly into the output runs.
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
Review Comment:
Reworked copy_rows to compare only the first selected run against the prior
output boundary; all remaining runs in the slice are appended directly. Fixed
in 2193a4bfaf.
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,280 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use super::InProgressArray;
+use arrow_array::cast::AsArray;
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, PrimitiveArray, RunArray, make_array,
new_empty_array};
+use arrow_buffer::ArrowNativeType;
+use arrow_cmp::{DynComparator, make_comparator};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType, SortOptions};
+use std::collections::HashMap;
+use std::fmt::{Debug, Formatter};
+
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ /// The current source used by [`Self::copy_rows`].
+ source: Option<ArrayRef>,
+ /// The data type to use when producing an empty array.
+ data_type: DataType,
+ /// The cumulative logical end of each output run.
+ run_ends: Vec<R::Native>,
+ /// Value arrays referenced by the output runs.
+ sources: Vec<ArrayRef>,
+ /// The `(source, physical index)` of each output run value.
+ indices: Vec<(usize, usize)>,
+ /// Comparators cached for pairs of value arrays.
+ comparators: HashMap<(usize, usize), DynComparator>,
+ /// The value array for the current source.
+ current_source: Option<usize>,
+ /// The number of logical rows copied into the output.
+ len: usize,
+}
+
+impl<R: RunEndIndexType> Debug for InProgressRunArray<R> {
+ fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
+ f.write_str("InProgressRunArray")
+ }
+}
+
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ data_type,
+ run_ends: Vec::new(),
+ sources: Vec::new(),
+ indices: Vec::new(),
+ comparators: HashMap::new(),
+ current_source: None,
+ len: 0,
+ }
+ }
+
+ fn append_run(&mut self, source: usize, index: usize, len: usize) ->
Result<(), ArrowError> {
+ let next_len = self
+ .len
+ .checked_add(len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let run_end = R::Native::from_usize(next_len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+
+ if let Some(&(last_source, last_index)) = self.indices.last() {
+ if (last_source, last_index) == (source, index) {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ return Ok(());
+ }
+ let key = (last_source, source);
+ if !self.comparators.contains_key(&key) {
+ let comparator = make_comparator(
+ self.sources[last_source].as_ref(),
+ self.sources[source].as_ref(),
+ SortOptions::default(),
+ )?;
+ self.comparators.insert(key, comparator);
+ }
+ if self.comparators[&key](last_index, index).is_eq() {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ *self.indices.last_mut().unwrap() = (source, index);
+ return Ok(());
+ }
+ }
+
+ self.len = next_len;
+ self.run_ends.push(run_end);
+ self.indices.push((source, index));
+ Ok(())
+ }
+}
+
+impl<R: RunEndIndexType> InProgressArray for InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ self.current_source = None;
+ }
+
+ /// Copies a logical row range directly into the output runs.
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
+ if len == 0 {
+ return Ok(());
+ }
+ let source = self.source.clone().ok_or_else(|| {
+ ArrowError::InvalidArgumentError("InProgressRunArray source not
set".into())
+ })?;
+ let array = source.as_run::<R>();
+ let run_ends = array.run_ends();
+ let selection_start =
run_ends.offset().checked_add(offset).ok_or_else(|| {
+ ArrowError::InvalidArgumentError("RunArray selection
overflow".into())
+ })?;
+ let selection_end = selection_start.checked_add(len).ok_or_else(|| {
+ ArrowError::InvalidArgumentError("RunArray selection
overflow".into())
+ })?;
+ let first = array.get_physical_index(offset);
+ let last = array.get_physical_index(offset + len - 1);
+
+ let source_idx = match self.current_source {
+ Some(idx) => idx,
+ None => {
+ let values = array.values();
+ let idx = self
+ .sources
+ .iter()
+ .position(|source| std::sync::Arc::ptr_eq(source, values))
Review Comment:
Imported Arc and removed the fully qualified Arc calls. Fixed in 2193a4bfaf.
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,280 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use super::InProgressArray;
+use arrow_array::cast::AsArray;
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, PrimitiveArray, RunArray, make_array,
new_empty_array};
+use arrow_buffer::ArrowNativeType;
+use arrow_cmp::{DynComparator, make_comparator};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType, SortOptions};
+use std::collections::HashMap;
+use std::fmt::{Debug, Formatter};
+
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ /// The current source used by [`Self::copy_rows`].
+ source: Option<ArrayRef>,
+ /// The data type to use when producing an empty array.
+ data_type: DataType,
+ /// The cumulative logical end of each output run.
+ run_ends: Vec<R::Native>,
+ /// Value arrays referenced by the output runs.
+ sources: Vec<ArrayRef>,
+ /// The `(source, physical index)` of each output run value.
+ indices: Vec<(usize, usize)>,
+ /// Comparators cached for pairs of value arrays.
+ comparators: HashMap<(usize, usize), DynComparator>,
+ /// The value array for the current source.
+ current_source: Option<usize>,
+ /// The number of logical rows copied into the output.
+ len: usize,
+}
+
+impl<R: RunEndIndexType> Debug for InProgressRunArray<R> {
+ fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
+ f.write_str("InProgressRunArray")
+ }
+}
+
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ data_type,
+ run_ends: Vec::new(),
+ sources: Vec::new(),
+ indices: Vec::new(),
+ comparators: HashMap::new(),
+ current_source: None,
+ len: 0,
+ }
+ }
+
+ fn append_run(&mut self, source: usize, index: usize, len: usize) ->
Result<(), ArrowError> {
+ let next_len = self
+ .len
+ .checked_add(len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let run_end = R::Native::from_usize(next_len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+
+ if let Some(&(last_source, last_index)) = self.indices.last() {
+ if (last_source, last_index) == (source, index) {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ return Ok(());
+ }
+ let key = (last_source, source);
+ if !self.comparators.contains_key(&key) {
+ let comparator = make_comparator(
+ self.sources[last_source].as_ref(),
+ self.sources[source].as_ref(),
+ SortOptions::default(),
+ )?;
+ self.comparators.insert(key, comparator);
+ }
+ if self.comparators[&key](last_index, index).is_eq() {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ *self.indices.last_mut().unwrap() = (source, index);
+ return Ok(());
+ }
+ }
+
+ self.len = next_len;
+ self.run_ends.push(run_end);
+ self.indices.push((source, index));
+ Ok(())
+ }
+}
+
+impl<R: RunEndIndexType> InProgressArray for InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ self.current_source = None;
+ }
+
+ /// Copies a logical row range directly into the output runs.
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
+ if len == 0 {
+ return Ok(());
+ }
+ let source = self.source.clone().ok_or_else(|| {
+ ArrowError::InvalidArgumentError("InProgressRunArray source not
set".into())
+ })?;
+ let array = source.as_run::<R>();
+ let run_ends = array.run_ends();
+ let selection_start =
run_ends.offset().checked_add(offset).ok_or_else(|| {
+ ArrowError::InvalidArgumentError("RunArray selection
overflow".into())
+ })?;
+ let selection_end = selection_start.checked_add(len).ok_or_else(|| {
+ ArrowError::InvalidArgumentError("RunArray selection
overflow".into())
+ })?;
+ let first = array.get_physical_index(offset);
+ let last = array.get_physical_index(offset + len - 1);
+
+ let source_idx = match self.current_source {
+ Some(idx) => idx,
+ None => {
+ let values = array.values();
+ let idx = self
+ .sources
+ .iter()
+ .position(|source| std::sync::Arc::ptr_eq(source, values))
+ .unwrap_or_else(|| {
+ self.sources.push(values.clone());
+ self.sources.len() - 1
+ });
+ self.current_source = Some(idx);
+ idx
+ }
+ };
+
+ let run_len = |index: usize| {
+ let start = index
+ .checked_sub(1)
+ .map(|idx| run_ends.values()[idx].as_usize())
+ .unwrap_or_default()
+ .max(selection_start);
+ let end = run_ends.values()[index].as_usize().min(selection_end);
+ end - start
+ };
+ self.append_run(source_idx, first, run_len(first))?;
+
+ let key = (source_idx, source_idx);
+ if first != last && !self.comparators.contains_key(&key) {
+ self.comparators.insert(
+ key,
+ make_comparator(
+ array.values().as_ref(),
+ array.values().as_ref(),
+ Default::default(),
+ )?,
+ );
+ }
+ for index in first + 1..=last {
+ let next_len = self
+ .len
+ .checked_add(run_len(index))
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let run_end = R::Native::from_usize(next_len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let last_index = self.indices.last().unwrap().1;
+ if self.comparators[&key](last_index, index).is_eq() {
+ *self.run_ends.last_mut().unwrap() = run_end;
+ *self.indices.last_mut().unwrap() = (source_idx, index);
+ } else {
+ self.run_ends.push(run_end);
+ self.indices.push((source_idx, index));
+ }
+ self.len = next_len;
+ }
+ Ok(())
+ }
+
+ /// Builds the run-end and value arrays directly from the accumulated runs.
+ fn finish(&mut self) -> Result<ArrayRef, ArrowError> {
Review Comment:
finish now drains the recorded runs once, extending each value and
collecting its run end in the same sweep. Fixed in 2193a4bfaf.
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,280 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF)
under one or more contributor license agreements
+
+use super::InProgressArray;
+use arrow_array::cast::AsArray;
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, PrimitiveArray, RunArray, make_array,
new_empty_array};
+use arrow_buffer::ArrowNativeType;
+use arrow_cmp::{DynComparator, make_comparator};
+use arrow_data::transform::MutableArrayData;
+use arrow_schema::{ArrowError, DataType, SortOptions};
+use std::collections::HashMap;
+use std::fmt::{Debug, Formatter};
+
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ /// The current source used by [`Self::copy_rows`].
+ source: Option<ArrayRef>,
+ /// The data type to use when producing an empty array.
+ data_type: DataType,
+ /// The cumulative logical end of each output run.
+ run_ends: Vec<R::Native>,
+ /// Value arrays referenced by the output runs.
+ sources: Vec<ArrayRef>,
+ /// The `(source, physical index)` of each output run value.
+ indices: Vec<(usize, usize)>,
+ /// Comparators cached for pairs of value arrays.
+ comparators: HashMap<(usize, usize), DynComparator>,
+ /// The value array for the current source.
+ current_source: Option<usize>,
+ /// The number of logical rows copied into the output.
+ len: usize,
+}
+
+impl<R: RunEndIndexType> Debug for InProgressRunArray<R> {
+ fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
+ f.write_str("InProgressRunArray")
+ }
+}
+
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ data_type,
+ run_ends: Vec::new(),
+ sources: Vec::new(),
+ indices: Vec::new(),
+ comparators: HashMap::new(),
+ current_source: None,
+ len: 0,
+ }
+ }
+
+ fn append_run(&mut self, source: usize, index: usize, len: usize) ->
Result<(), ArrowError> {
+ let next_len = self
+ .len
+ .checked_add(len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let run_end = R::Native::from_usize(next_len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+
+ if let Some(&(last_source, last_index)) = self.indices.last() {
+ if (last_source, last_index) == (source, index) {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ return Ok(());
+ }
+ let key = (last_source, source);
+ if !self.comparators.contains_key(&key) {
+ let comparator = make_comparator(
+ self.sources[last_source].as_ref(),
+ self.sources[source].as_ref(),
+ SortOptions::default(),
+ )?;
+ self.comparators.insert(key, comparator);
+ }
+ if self.comparators[&key](last_index, index).is_eq() {
+ self.len = next_len;
+ *self.run_ends.last_mut().unwrap() = run_end;
+ *self.indices.last_mut().unwrap() = (source, index);
+ return Ok(());
+ }
+ }
+
+ self.len = next_len;
+ self.run_ends.push(run_end);
+ self.indices.push((source, index));
+ Ok(())
+ }
+}
+
+impl<R: RunEndIndexType> InProgressArray for InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ self.current_source = None;
+ }
+
+ /// Copies a logical row range directly into the output runs.
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
+ if len == 0 {
+ return Ok(());
+ }
+ let source = self.source.clone().ok_or_else(|| {
+ ArrowError::InvalidArgumentError("InProgressRunArray source not
set".into())
+ })?;
+ let array = source.as_run::<R>();
+ let run_ends = array.run_ends();
+ let selection_start =
run_ends.offset().checked_add(offset).ok_or_else(|| {
+ ArrowError::InvalidArgumentError("RunArray selection
overflow".into())
+ })?;
+ let selection_end = selection_start.checked_add(len).ok_or_else(|| {
+ ArrowError::InvalidArgumentError("RunArray selection
overflow".into())
+ })?;
+ let first = array.get_physical_index(offset);
+ let last = array.get_physical_index(offset + len - 1);
+
+ let source_idx = match self.current_source {
+ Some(idx) => idx,
+ None => {
+ let values = array.values();
+ let idx = self
+ .sources
+ .iter()
+ .position(|source| std::sync::Arc::ptr_eq(source, values))
+ .unwrap_or_else(|| {
+ self.sources.push(values.clone());
+ self.sources.len() - 1
+ });
+ self.current_source = Some(idx);
+ idx
+ }
+ };
+
+ let run_len = |index: usize| {
+ let start = index
+ .checked_sub(1)
+ .map(|idx| run_ends.values()[idx].as_usize())
+ .unwrap_or_default()
+ .max(selection_start);
+ let end = run_ends.values()[index].as_usize().min(selection_end);
+ end - start
+ };
+ self.append_run(source_idx, first, run_len(first))?;
+
+ let key = (source_idx, source_idx);
+ if first != last && !self.comparators.contains_key(&key) {
+ self.comparators.insert(
+ key,
+ make_comparator(
+ array.values().as_ref(),
+ array.values().as_ref(),
+ Default::default(),
+ )?,
+ );
+ }
+ for index in first + 1..=last {
+ let next_len = self
+ .len
+ .checked_add(run_len(index))
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let run_end = R::Native::from_usize(next_len)
+ .ok_or_else(|| ArrowError::InvalidArgumentError("Run end
overflow".into()))?;
+ let last_index = self.indices.last().unwrap().1;
+ if self.comparators[&key](last_index, index).is_eq() {
+ *self.run_ends.last_mut().unwrap() = run_end;
+ *self.indices.last_mut().unwrap() = (source_idx, index);
+ } else {
+ self.run_ends.push(run_end);
+ self.indices.push((source_idx, index));
+ }
+ self.len = next_len;
+ }
+ Ok(())
+ }
+
+ /// Builds the run-end and value arrays directly from the accumulated runs.
+ fn finish(&mut self) -> Result<ArrayRef, ArrowError> {
+ if self.run_ends.is_empty() {
+ return Ok(new_empty_array(&self.data_type));
+ }
+
+ let data = self.sources.iter().map(|x|
x.to_data()).collect::<Vec<_>>();
+ let mut values =
+ MutableArrayData::try_new(data.iter().collect(), false,
self.indices.len())?;
+ let mut ranges = self.indices.iter().copied().peekable();
+ while let Some((source, start)) = ranges.next() {
+ let mut end = start + 1;
+ while ranges
+ .next_if(|&(next_source, next)| next_source == source && next
== end)
+ .is_some()
+ {
+ end += 1;
+ }
+ values.try_extend(source, start, end)?;
+ }
+ let values = make_array(values.freeze());
+ let run_ends =
PrimitiveArray::<R>::from_iter_values(self.run_ends.drain(..));
+ let result = RunArray::<R>::try_new(&run_ends, values.as_ref())?;
+
+ self.sources.clear();
+ self.indices.clear();
+ self.comparators.clear();
+ self.current_source = None;
+ self.len = 0;
+ Ok(std::sync::Arc::new(result))
+ }
+
+ fn size(&self) -> usize {
+ self.sources
+ .iter()
+ .map(|x| x.get_array_memory_size())
+ .sum::<usize>()
+ + self.run_ends.capacity() * size_of::<R::Native>()
+ + self.sources.capacity() * size_of::<ArrayRef>()
+ + self.indices.capacity() * size_of::<(usize, usize)>()
+ }
+}
+
+#[cfg(test)]
+mod tests {
Review Comment:
Added focused tests for partial first/last run boundaries and subranges of a
sliced RunArray. Fixed in 2193a4bfaf.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]