LuciferYang commented on code in PR #1352:
URL: https://github.com/apache/paimon-rust/pull/1352#discussion_r4521047368
##########
crates/paimon/src/table/aggregator/collect.rs:
##########
@@ -34,119 +37,252 @@ pub(crate) struct CollectAgg {
field_name: String,
element: FieldRef,
distinct: bool,
+ /// A positive limit keeps the first N elements in merge order, a
+ /// negative one keeps the last |N|.
+ count_limit: i32,
java_uses_equaliser: bool,
+ /// Row encoder for distinct elements that Java collects into a
+ /// `LinkedHashSet`. `None` for other columns, and for element types
+ /// arrow-row cannot encode, which keep the linear comparison.
+ key_encoder: Option<RowConverter>,
seen_input: bool,
+ /// The elements are a DELETE value kept as-is, so they may hold
+ /// duplicates or exceed the limit until the next merge.
raw_accumulator: bool,
elements: Vec<ArrayRef>,
+ /// Encoded keys of `elements` when `key_encoder` is set; `None` until
+ /// rebuilt after a retract.
+ element_keys: Option<HashSet<Box<[u8]>>>,
+}
+
+/// One side of Java's merge, with the encoded keys of its elements when
+/// the column deduplicates through a set.
+struct Operand {
+ elements: Vec<ArrayRef>,
+ keys: Option<Rows>,
+ has_duplicate: bool,
}
impl CollectAgg {
pub(crate) fn new(
field_name: &str,
data_type: &DataType,
distinct: bool,
+ count_limit: i32,
) -> crate::Result<Self> {
- if !matches!(data_type, DataType::Array(_)) {
+ let DataType::Array(array_type) = data_type else {
return Err(unsupported_type_error("collect", field_name,
data_type));
- }
+ };
let ArrowDataType::List(element) = paimon_type_to_arrow(data_type)?
else {
unreachable!("ARRAY must map to Arrow List")
};
+ // Java `FieldCollectAgg#needsEqualiser`: constructed types and
+ // BINARY/VARBINARY (Rust has no GEOMETRY/GEOGRAPHY).
+ let java_uses_equaliser = matches!(
+ array_type.element_type(),
+ DataType::Array(_)
+ | DataType::Vector(_)
+ | DataType::Multiset(_)
+ | DataType::Map(_)
+ | DataType::Row(_)
+ | DataType::Binary(_)
+ | DataType::VarBinary(_)
+ );
+ let key_encoder = if distinct && !java_uses_equaliser {
+
RowConverter::new(vec![SortField::new(element.data_type().clone())]).ok()
+ } else {
+ None
+ };
Ok(Self {
field_name: field_name.to_string(),
- java_uses_equaliser: matches!(
- element.data_type(),
- ArrowDataType::Struct(_)
- | ArrowDataType::List(_)
- | ArrowDataType::LargeList(_)
- | ArrowDataType::Map(_, _)
- | ArrowDataType::Binary
- | ArrowDataType::LargeBinary
- | ArrowDataType::FixedSizeBinary(_)
- ),
element,
distinct,
+ count_limit,
+ java_uses_equaliser,
+ key_encoder,
seen_input: false,
raw_accumulator: false,
elements: Vec::new(),
+ element_keys: None,
})
}
- fn preserve_raw(&mut self, array: &dyn Array, row_idx: usize) ->
crate::Result<()> {
+ fn limit(&self) -> usize {
+ self.count_limit.unsigned_abs() as usize
+ }
+
+ fn list<'a>(&self, array: &'a dyn Array) -> crate::Result<&'a ListArray> {
+ array
+ .as_any()
+ .downcast_ref::<ListArray>()
+ .ok_or_else(|| Error::DataInvalid {
+ message: format!(
+ "collect column '{}' requires Arrow List, got {:?}",
+ self.field_name,
+ array.data_type()
+ ),
+ source: None,
+ })
+ }
+
+ /// The input row's elements as one array, or `None` for a null cell.
+ fn input_values(&self, array: &dyn Array, row_idx: usize) ->
crate::Result<Option<ArrayRef>> {
if array.is_null(row_idx) {
- return Ok(());
+ return Ok(None);
}
- let list =
- array
- .as_any()
- .downcast_ref::<ListArray>()
- .ok_or_else(|| Error::DataInvalid {
- message: format!(
- "collect column '{}' requires Arrow List, got {:?}",
- self.field_name,
- array.data_type()
- ),
- source: None,
- })?;
- let values = list.value(row_idx);
- self.elements = (0..values.len())
- .map(|index| values.slice(index, 1))
- .collect();
- self.seen_input = true;
- self.raw_accumulator = true;
- Ok(())
+ Ok(Some(self.list(array)?.value(row_idx)))
}
- fn normalize_raw_for_agg(&mut self) {
- if !self.raw_accumulator || !self.distinct || self.java_uses_equaliser
{
- return;
+ fn concat_elements(&self, elements: &[ArrayRef]) ->
crate::Result<ArrayRef> {
+ if elements.is_empty() {
+ return Ok(new_empty_array(self.element.data_type()));
}
- let mut distinct: Vec<ArrayRef> = Vec::new();
- for element in std::mem::take(&mut self.elements) {
- if !distinct
- .iter()
- .any(|existing| existing.as_ref() == element.as_ref())
- {
- distinct.push(element);
- }
+ let slices: Vec<&dyn Array> = elements.iter().map(|e|
e.as_ref()).collect();
+ concat(&slices).map_err(|e| Error::DataInvalid {
+ message: format!(
+ "Failed to build collect result for '{}': {e}",
+ self.field_name
+ ),
+ source: Some(Box::new(e)),
+ })
+ }
+
+ fn encode_keys(&self, values: &ArrayRef) -> crate::Result<Option<Rows>> {
+ let Some(encoder) = &self.key_encoder else {
+ return Ok(None);
+ };
+ encoder
+ .convert_columns(std::slice::from_ref(values))
+ .map(Some)
+ .map_err(|e| Error::DataInvalid {
+ message: format!(
+ "Failed to encode collect elements for '{}': {e}",
+ self.field_name
+ ),
+ source: Some(Box::new(e)),
+ })
+ }
+ fn operand(&self, elements: Vec<ArrayRef>, has_duplicate: bool) ->
crate::Result<Operand> {
+ let keys = if self.key_encoder.is_some() {
+ self.encode_keys(&self.concat_elements(&elements)?)?
+ } else {
+ None
+ };
+ Ok(Operand {
+ elements,
+ keys,
+ has_duplicate,
+ })
+ }
+
+ fn input_operand(&self, values: &ArrayRef) -> crate::Result<Operand> {
+ Ok(Operand {
+ elements: (0..values.len())
+ .map(|index| values.slice(index, 1))
+ .collect(),
+ keys: self.encode_keys(values)?,
+ has_duplicate: true,
+ })
+ }
+
+ /// The accumulator as Java's merge would have collected it so far, so
+ /// that the input can be appended without rebuilding the collection.
+ fn take_collected(&mut self) -> crate::Result<Merged> {
+ let elements = std::mem::take(&mut self.elements);
+ let keys = match (self.element_keys.take(),
self.key_encoder.is_some()) {
+ (Some(keys), _) => Some(keys),
+ (None, true) => self
+ .encode_keys(&self.concat_elements(&elements)?)?
+ .map(|rows| rows.iter().map(|row|
row.as_ref().into()).collect()),
+ (None, false) => None,
+ };
+ Ok(Merged { elements, keys })
+ }
+
+ /// Java's private `agg(first, firstHasDuplicate, second,
+ /// secondHasDuplicate)`: a positive limit collects `first` then
+ /// `second`; a negative one collects both backwards, `second` first,
+ /// and reverses the result.
+ fn merge(&self, first: &Operand, second: &Operand) -> Merged {
+ let mut merged = Merged {
+ elements: Vec::new(),
+ keys: self.key_encoder.as_ref().map(|_| HashSet::new()),
+ };
+ if self.count_limit >= 0 {
+ self.collect(&mut merged, first, false);
+ self.collect(&mut merged, second, false);
+ } else {
+ self.collect(&mut merged, second, true);
+ self.collect(&mut merged, first, true);
+ merged.elements.reverse();
}
- self.elements = distinct;
- self.raw_accumulator = false;
+ merged
}
- fn collect(&mut self, array: &dyn Array, row_idx: usize) ->
crate::Result<()> {
- if array.is_null(row_idx) {
- return Ok(());
+ /// Java `collect`: add the operand's elements until the collection
+ /// holds |count-limit| of them, skipping duplicates when distinct.
+ fn collect(&self, merged: &mut Merged, operand: &Operand, backwards: bool)
{
+ // Java `checkDuplicateUntil`: with the equaliser, an operand known
+ // to be duplicate-free is checked only against what was collected
+ // before it.
+ let check_until = if operand.has_duplicate {
+ usize::MAX
+ } else {
+ merged.elements.len()
+ };
+ let len = operand.elements.len();
+ for index in (0..len).map(|i| if backwards { len - 1 - i } else { i })
{
+ if merged.elements.len() >= self.limit() {
+ break;
+ }
+ let element = &operand.elements[index];
+ if self.distinct {
+ let duplicate = match (&mut merged.keys, &operand.keys) {
+ (Some(seen), Some(rows)) =>
!seen.insert(rows.row(index).as_ref().into()),
Review Comment:
Fixed in 47799ec5. The keys for FLOAT/DOUBLE elements map every NaN to the
canonical NaN before row encoding, and `retract` treats two NaNs as equal. The
stored elements keep their original bits, and 0.0 and -0.0 stay distinct.
`distinct_doubles_merge_nan_payloads_like_java` covers your case (`[NaN(1),
NaN(2)]` then `[5.0]` with `count-limit=2` gives `[NaN(1), 5.0]`) and a retract
by a NaN with another payload. A replay of 105k random steps with DOUBLE
elements (0.0, -0.0 and two NaN payloads, including retracts) against Java
master's `FieldCollectAgg` matches on every step.
This covers FLOAT/DOUBLE elements. ROW elements with FLOAT/DOUBLE fields
still compare NaN payloads bit by bit, while Java's generated equaliser uses
`Double.compare`. That predates this PR; I'll open a separate issue for it.
##########
crates/paimon/src/table/aggregator/collect.rs:
##########
@@ -156,71 +292,66 @@ impl FieldAggregator for CollectAgg {
self.seen_input = false;
self.raw_accumulator = false;
self.elements.clear();
+ self.element_keys = None;
}
+ /// Java `agg(acc, input)` is `agg(acc, false, input, true)`.
fn agg(&mut self, array: &dyn Array, row_idx: usize) -> crate::Result<()> {
- self.normalize_raw_for_agg();
- self.collect(array, row_idx)
+ let Some(values) = self.input_values(array, row_idx)? else {
+ return self.normalize_raw();
+ };
+ let input = self.input_operand(&values)?;
+ let merged = if self.raw_accumulator || self.count_limit < 0 {
+ let elements = std::mem::take(&mut self.elements);
+ let accumulator = self.operand(elements, false)?;
+ self.merge(&accumulator, &input)
+ } else {
+ // Java would copy the accumulator unchanged before the input,
+ // so the input can be appended.
+ let mut merged = self.take_collected()?;
+ self.collect(&mut merged, &input, false);
+ merged
+ };
+ self.store(merged);
+ Ok(())
}
fn replace_with_delete(&mut self, array: &dyn Array, row_idx: usize) ->
crate::Result<()> {
+ // Java keeps the DELETE value as it is until the next merge.
self.reset();
- self.preserve_raw(array, row_idx)
+ if let Some(values) = self.input_values(array, row_idx)? {
+ self.elements = (0..values.len())
+ .map(|index| values.slice(index, 1))
+ .collect();
+ self.seen_input = true;
+ self.raw_accumulator = true;
+ }
+ Ok(())
}
+ /// Java `aggReversed(acc, input)` is `agg(input, true, acc, false)`:
+ /// the older input comes first.
fn agg_reversed(&mut self, array: &dyn Array, row_idx: usize) ->
crate::Result<()> {
- // Java FieldCollectAgg overrides aggReversed to preserve accumulator
- // order (and the distinct state) instead of prepending the input.
- self.normalize_raw_for_agg();
- self.collect(array, row_idx)
- }
-
- fn agg_reversed_via_agg(&mut self, array: &dyn Array, row_idx: usize) ->
crate::Result<()> {
- // FieldIgnoreRetractAgg inherits the default reverse method, so it
- // calls collect.agg(older, current), not collect.aggReversed. Preserve
- // the current elements while prepending the older operand.
- let current = std::mem::take(&mut self.elements);
- let current_seen = self.seen_input;
- self.seen_input = false;
- self.raw_accumulator = false;
- if self.distinct && self.java_uses_equaliser {
- // Java copies the older accumulator unchanged for complex/binary
- // elements, then deduplicates only the newer input against it.
- self.preserve_raw(array, row_idx)?;
- } else {
- self.collect(array, row_idx)?;
- }
- for element in current {
- if !self.distinct
- || !self
- .elements
- .iter()
- .any(|existing| existing.as_ref() == element.as_ref())
- {
- self.elements.push(element);
- }
- }
- self.seen_input |= current_seen;
- self.raw_accumulator = false;
+ let Some(values) = self.input_values(array, row_idx)? else {
+ return self.normalize_raw();
+ };
+ let input = self.input_operand(&values)?;
+ let elements = std::mem::take(&mut self.elements);
+ let accumulator = self.operand(elements, false)?;
+ let merged = self.merge(&input, &accumulator);
Review Comment:
Fixed in 47799ec5. Elements are kept in a `VecDeque`. Without `distinct`,
`agg` and `agg_reversed` append or prepend the input and cut to the limit. With
`distinct` on element types that Java merges through a `LinkedHashSet`, they
append or prepend without merging, and the merge runs when the array is read or
once it grows past twice its last merged size. 20,000 single-element late
updates now take about 3 ms without `distinct` and about 10 ms with `distinct`
on INT elements (2 ms and 4.4 s on main). Distinct ROW and BINARY elements
still compare each update against the whole array, as Java's equaliser path
does.
--
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]