Rich-T-kid commented on code in PR #12218:
URL: https://github.com/apache/arrow-rs/pull/12218#discussion_r4581263025
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,194 @@
+// 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 crate::concat::concat;
+use crate::filter::{FilterPredicate, FilterSelection};
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, RunArray, cast::AsArray, new_empty_array};
+use arrow_buffer::{ArrowNativeType, RunEndBuffer, ScalarBuffer};
+use arrow_schema::{ArrowError, DataType};
+use std::{mem, sync::Arc};
+
+/// Incrementally builds a run-end encoded array without materializing its
rows.
+///
+/// Run ends are rebased into the output while value arrays are retained as
+/// source ranges and concatenated only when the output is finished.
+#[derive(Debug)]
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ source: Option<ArrayRef>,
+ /// Value arrays referenced by `ranges`.
+ sources: Vec<ArrayRef>,
+ /// Logical run ends in the buffered output.
+ run_ends: Vec<R::Native>,
+ /// `(source, start, end)` ranges of physical values to concatenate.
+ ranges: Vec<(usize, usize, usize)>,
+ /// Source and physical index of the buffered tail run.
+ last: Option<(usize, usize)>,
+ data_type: DataType,
+}
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ sources: vec![],
+ run_ends: vec![],
+ ranges: vec![],
+ last: None,
+ data_type,
+ }
+ }
+
+ /// Append a logical slice, optionally reusing precomputed physical bounds.
+ ///
+ /// Only the first physical run can extend the current output tail.
+ fn copy_from(
+ &mut self,
+ array: &RunArray<R>,
+ offset: usize,
+ len: usize,
+ physical: Option<(usize, usize)>,
+ ) -> Result<(), ArrowError> {
+ let out = self.run_ends.last().map_or(0, |x| x.as_usize());
+ out.checked_add(len)
+ .and_then(R::Native::from_usize)
+ .ok_or(ArrowError::RunEndIndexOverflowError)?;
+ let run_ends = array.run_ends();
+ let ends = run_ends.values();
+ let vals = array.values();
+ if !self.sources.last().is_some_and(|x| Arc::ptr_eq(x, vals)) {
+ self.sources.push(vals.clone());
+ }
+ let source = self.sources.len() - 1;
+ let (first, last) = physical.unwrap_or_else(|| {
+ (
+ array.get_physical_index(offset),
+ array.get_physical_index(offset + len - 1),
+ )
+ });
+ let merge = self.last == Some((source, first));
+ if !merge && offset == 0 && len == array.len() && run_ends.max_value()
== len {
+ self.run_ends
+ .extend(ends.iter().map(|x| R::Native::usize_as(out +
x.as_usize())));
+ self.ranges.push((source, 0, ends.len()));
+ } else {
+ let selection_start = run_ends.offset() + offset;
+ let selection_end = selection_start + len;
+ let end = |index: usize| {
+ let end = ends[index].as_usize().min(selection_end) -
selection_start;
+ R::Native::usize_as(out + end)
+ };
+ if merge {
+ *self.run_ends.last_mut().unwrap() = end(first);
+ } else {
+ self.run_ends.push(end(first));
+ }
+ self.run_ends.extend((first + 1..=last).map(end));
+ let start = first + usize::from(merge);
+ if start <= last {
+ if let Some((s, _, end)) = self.ranges.last_mut()
+ && *s == source
+ && *end == start
+ {
+ *end = last + 1;
+ } else {
+ self.ranges.push((source, start, last + 1));
+ }
+ }
+ }
+ self.last = Some((source, last));
+ Ok(())
+ }
+}
+impl<R: RunEndIndexType + std::fmt::Debug> InProgressArray for
InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ }
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
+ let error = || ArrowError::InvalidArgumentError("RunArray source not
set".into());
+ let source = self.source.take().ok_or_else(error)?;
Review Comment:
we should just inline this
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,194 @@
+// 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 crate::concat::concat;
+use crate::filter::{FilterPredicate, FilterSelection};
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, RunArray, cast::AsArray, new_empty_array};
+use arrow_buffer::{ArrowNativeType, RunEndBuffer, ScalarBuffer};
+use arrow_schema::{ArrowError, DataType};
+use std::{mem, sync::Arc};
+
+/// Incrementally builds a run-end encoded array without materializing its
rows.
+///
+/// Run ends are rebased into the output while value arrays are retained as
+/// source ranges and concatenated only when the output is finished.
+#[derive(Debug)]
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ source: Option<ArrayRef>,
+ /// Value arrays referenced by `ranges`.
+ sources: Vec<ArrayRef>,
+ /// Logical run ends in the buffered output.
+ run_ends: Vec<R::Native>,
+ /// `(source, start, end)` ranges of physical values to concatenate.
+ ranges: Vec<(usize, usize, usize)>,
+ /// Source and physical index of the buffered tail run.
+ last: Option<(usize, usize)>,
+ data_type: DataType,
+}
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ sources: vec![],
+ run_ends: vec![],
+ ranges: vec![],
+ last: None,
+ data_type,
+ }
+ }
+
+ /// Append a logical slice, optionally reusing precomputed physical bounds.
+ ///
+ /// Only the first physical run can extend the current output tail.
+ fn copy_from(
Review Comment:
we could use a better doc comment, also more comments for the complex bits
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,194 @@
+// 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 crate::concat::concat;
+use crate::filter::{FilterPredicate, FilterSelection};
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, RunArray, cast::AsArray, new_empty_array};
+use arrow_buffer::{ArrowNativeType, RunEndBuffer, ScalarBuffer};
+use arrow_schema::{ArrowError, DataType};
+use std::{mem, sync::Arc};
+
+/// Incrementally builds a run-end encoded array without materializing its
rows.
+///
+/// Run ends are rebased into the output while value arrays are retained as
+/// source ranges and concatenated only when the output is finished.
+#[derive(Debug)]
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ source: Option<ArrayRef>,
+ /// Value arrays referenced by `ranges`.
+ sources: Vec<ArrayRef>,
+ /// Logical run ends in the buffered output.
+ run_ends: Vec<R::Native>,
+ /// `(source, start, end)` ranges of physical values to concatenate.
+ ranges: Vec<(usize, usize, usize)>,
+ /// Source and physical index of the buffered tail run.
+ last: Option<(usize, usize)>,
+ data_type: DataType,
+}
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ sources: vec![],
+ run_ends: vec![],
+ ranges: vec![],
+ last: None,
+ data_type,
+ }
+ }
+
+ /// Append a logical slice, optionally reusing precomputed physical bounds.
+ ///
+ /// Only the first physical run can extend the current output tail.
+ fn copy_from(
+ &mut self,
+ array: &RunArray<R>,
+ offset: usize,
+ len: usize,
+ physical: Option<(usize, usize)>,
+ ) -> Result<(), ArrowError> {
+ let out = self.run_ends.last().map_or(0, |x| x.as_usize());
+ out.checked_add(len)
+ .and_then(R::Native::from_usize)
+ .ok_or(ArrowError::RunEndIndexOverflowError)?;
+ let run_ends = array.run_ends();
+ let ends = run_ends.values();
+ let vals = array.values();
+ if !self.sources.last().is_some_and(|x| Arc::ptr_eq(x, vals)) {
+ self.sources.push(vals.clone());
+ }
+ let source = self.sources.len() - 1;
+ let (first, last) = physical.unwrap_or_else(|| {
+ (
+ array.get_physical_index(offset),
+ array.get_physical_index(offset + len - 1),
+ )
+ });
+ let merge = self.last == Some((source, first));
+ if !merge && offset == 0 && len == array.len() && run_ends.max_value()
== len {
+ self.run_ends
+ .extend(ends.iter().map(|x| R::Native::usize_as(out +
x.as_usize())));
+ self.ranges.push((source, 0, ends.len()));
+ } else {
+ let selection_start = run_ends.offset() + offset;
+ let selection_end = selection_start + len;
+ let end = |index: usize| {
+ let end = ends[index].as_usize().min(selection_end) -
selection_start;
+ R::Native::usize_as(out + end)
+ };
+ if merge {
+ *self.run_ends.last_mut().unwrap() = end(first);
+ } else {
+ self.run_ends.push(end(first));
+ }
+ self.run_ends.extend((first + 1..=last).map(end));
+ let start = first + usize::from(merge);
+ if start <= last {
+ if let Some((s, _, end)) = self.ranges.last_mut()
+ && *s == source
+ && *end == start
+ {
+ *end = last + 1;
+ } else {
+ self.ranges.push((source, start, last + 1));
+ }
+ }
+ }
+ self.last = Some((source, last));
+ Ok(())
+ }
+}
+impl<R: RunEndIndexType + std::fmt::Debug> InProgressArray for
InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ }
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
+ let error = || ArrowError::InvalidArgumentError("RunArray source not
set".into());
+ let source = self.source.take().ok_or_else(error)?;
+ let result = self.copy_from(source.as_run::<R>(), offset, len, None);
+ self.source = Some(source);
+ result
+ }
+ fn copy_rows_by_filter_from(
+ &mut self,
+ source: ArrayRef,
+ filter: &FilterPredicate,
+ ) -> Result<(), ArrowError> {
+ super::check_filter_len(filter, source.len())?;
+ if filter.count() == 0 {
+ return Ok(());
+ }
+ let array = source.as_run::<R>();
+ // Nullable dense selections are cheaper through the filter kernel.
+ if array.values().null_count() != 0 && filter.count() > source.len() /
128 {
+ let filtered = filter.filter(array)?;
+ return self.copy_from(filtered.as_run::<R>(), 0, filter.count(),
None);
+ }
+ let run_ends = array.run_ends();
+ let ends = run_ends.values();
+ let mut physical = array.get_start_physical_index();
+ // Filter selections are ordered, so scan the run ends only once.
+ let mut copy = |start: usize, end: usize| {
+ let start_logical = run_ends.offset() + start;
+ while ends[physical].as_usize() <= start_logical {
+ physical += 1;
+ }
+ let first = physical;
+ let end_logical = run_ends.offset() + end;
+ while ends[physical].as_usize() < end_logical {
+ physical += 1;
+ }
+ self.copy_from(array, start, end - start, Some((first, physical)))
+ };
+ match filter.selection() {
+ FilterSelection::None => Ok(()),
+ FilterSelection::All { len } => copy(0, len),
+ FilterSelection::Slices(x) => x.try_for_each(|(start, end)|
copy(start, end)),
+ FilterSelection::Indices(x) => x.try_for_each(|i| copy(i, i + 1)),
+ }
+ }
+ fn finish(&mut self) -> Result<ArrayRef, ArrowError> {
+ if self.run_ends.is_empty() {
+ return Ok(new_empty_array(&self.data_type));
+ }
+ let slices = self
+ .ranges
+ .drain(..)
+ .map(|(source, start, end)| {
+ let values = &self.sources[source];
+ if start != 0 || end != values.len() {
+ values.slice(start, end - start)
+ } else {
+ values.clone()
+ }
+ })
+ .collect::<Vec<_>>();
+ let values = concat(&slices.iter().map(|x|
x.as_ref()).collect::<Vec<_>>())?;
Review Comment:
we should be able to avoid this `concat` call
##########
arrow-select/src/coalesce/run_end.rs:
##########
@@ -0,0 +1,194 @@
+// 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 crate::concat::concat;
+use crate::filter::{FilterPredicate, FilterSelection};
+use arrow_array::types::RunEndIndexType;
+use arrow_array::{Array, ArrayRef, RunArray, cast::AsArray, new_empty_array};
+use arrow_buffer::{ArrowNativeType, RunEndBuffer, ScalarBuffer};
+use arrow_schema::{ArrowError, DataType};
+use std::{mem, sync::Arc};
+
+/// Incrementally builds a run-end encoded array without materializing its
rows.
+///
+/// Run ends are rebased into the output while value arrays are retained as
+/// source ranges and concatenated only when the output is finished.
+#[derive(Debug)]
+pub(crate) struct InProgressRunArray<R: RunEndIndexType> {
+ source: Option<ArrayRef>,
+ /// Value arrays referenced by `ranges`.
+ sources: Vec<ArrayRef>,
+ /// Logical run ends in the buffered output.
+ run_ends: Vec<R::Native>,
+ /// `(source, start, end)` ranges of physical values to concatenate.
+ ranges: Vec<(usize, usize, usize)>,
+ /// Source and physical index of the buffered tail run.
+ last: Option<(usize, usize)>,
+ data_type: DataType,
+}
+impl<R: RunEndIndexType> InProgressRunArray<R> {
+ pub(crate) fn new(data_type: DataType) -> Self {
+ Self {
+ source: None,
+ sources: vec![],
+ run_ends: vec![],
+ ranges: vec![],
+ last: None,
+ data_type,
+ }
+ }
+
+ /// Append a logical slice, optionally reusing precomputed physical bounds.
+ ///
+ /// Only the first physical run can extend the current output tail.
+ fn copy_from(
+ &mut self,
+ array: &RunArray<R>,
+ offset: usize,
+ len: usize,
+ physical: Option<(usize, usize)>,
+ ) -> Result<(), ArrowError> {
+ let out = self.run_ends.last().map_or(0, |x| x.as_usize());
+ out.checked_add(len)
+ .and_then(R::Native::from_usize)
+ .ok_or(ArrowError::RunEndIndexOverflowError)?;
+ let run_ends = array.run_ends();
+ let ends = run_ends.values();
+ let vals = array.values();
+ if !self.sources.last().is_some_and(|x| Arc::ptr_eq(x, vals)) {
+ self.sources.push(vals.clone());
+ }
+ let source = self.sources.len() - 1;
+ let (first, last) = physical.unwrap_or_else(|| {
+ (
+ array.get_physical_index(offset),
+ array.get_physical_index(offset + len - 1),
+ )
+ });
+ let merge = self.last == Some((source, first));
+ if !merge && offset == 0 && len == array.len() && run_ends.max_value()
== len {
+ self.run_ends
+ .extend(ends.iter().map(|x| R::Native::usize_as(out +
x.as_usize())));
+ self.ranges.push((source, 0, ends.len()));
+ } else {
+ let selection_start = run_ends.offset() + offset;
+ let selection_end = selection_start + len;
+ let end = |index: usize| {
+ let end = ends[index].as_usize().min(selection_end) -
selection_start;
+ R::Native::usize_as(out + end)
+ };
+ if merge {
+ *self.run_ends.last_mut().unwrap() = end(first);
+ } else {
+ self.run_ends.push(end(first));
+ }
+ self.run_ends.extend((first + 1..=last).map(end));
+ let start = first + usize::from(merge);
+ if start <= last {
+ if let Some((s, _, end)) = self.ranges.last_mut()
+ && *s == source
+ && *end == start
+ {
+ *end = last + 1;
+ } else {
+ self.ranges.push((source, start, last + 1));
+ }
+ }
+ }
+ self.last = Some((source, last));
+ Ok(())
+ }
+}
+impl<R: RunEndIndexType + std::fmt::Debug> InProgressArray for
InProgressRunArray<R> {
+ fn set_source(&mut self, source: Option<ArrayRef>) {
+ self.source = source;
+ }
+ fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(),
ArrowError> {
+ let error = || ArrowError::InvalidArgumentError("RunArray source not
set".into());
+ let source = self.source.take().ok_or_else(error)?;
+ let result = self.copy_from(source.as_run::<R>(), offset, len, None);
+ self.source = Some(source);
+ result
+ }
+ fn copy_rows_by_filter_from(
Review Comment:
we should remove this trait impl, it can be added up in a follow up. for now
`copy_rows` should be enough
--
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]