kumarUjjawal commented on code in PR #25740: URL: https://github.com/apache/datafusion/pull/25740#discussion_r4577250238
########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { + self.keys + .push(ScalarValue::try_from_array(keys, row)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, row)?.compacted()); + } + + Ok(()) + } + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + + assert_eq_or_internal_err!(states.len(), 1, "expects single state"); + + let map_arr = as_map_array(states[0].as_ref())?; + let offsets = map_arr.value_offsets(); + let map_keys = map_arr.keys(); + let map_values = map_arr.values(); + + for row in 0..map_arr.len() { + // Partial states are nullable so empty groups can produce a NULL map + if map_arr.is_null(row) { + continue; + } + for idx in offsets[row] as usize..offsets[row + 1] as usize { + self.keys + .push(ScalarValue::try_from_array(map_keys, idx)?.compacted()); + self.values + .push(ScalarValue::try_from_array(map_values, idx)?.compacted()); + } + } + + Ok(()) + } + + fn state(&mut self) -> Result<Vec<ScalarValue>> { + Ok(vec![self.evaluate()?]) + } + + fn evaluate(&mut self) -> Result<ScalarValue> { + let map_type = self.map_type(); + + if self.keys.is_empty() { + return ScalarValue::try_new_null(&map_type); + } + + // Arrow maps cannot represent null keys (same rule as the `map` function) + if self.keys.iter().any(ScalarValue::is_null) { + return exec_err!("map key cannot be null"); + } + + let (keys, values) = + Self::dedup_first_wins(self.keys.clone(), self.values.clone()); + + let keys = ScalarValue::iter_to_array(keys)?; + let values = ScalarValue::iter_to_array(values)?; + + let DataType::Map(entries_field, ordered) = &map_type else { + return internal_err!("map_agg expected Map type, got {map_type}"); + }; + let DataType::Struct(entry_fields) = entries_field.data_type() else { + return internal_err!( + "map_agg expected struct entries, got {}", + entries_field.data_type() + ); + }; + + let entries = + StructArray::try_new(entry_fields.clone(), vec![keys, values], None)?; + + let Ok(num_entries) = i32::try_from(entries.len()) else { + return internal_err!( + "map_agg produced {} entries which exceeds the map offset range", + entries.len() + ); + }; + let offsets = OffsetBuffer::new(ScalarBuffer::from(vec![0_i32, num_entries])); + let map_array = MapArray::try_new( + Arc::clone(entries_field), + offsets, + entries, + None, + *ordered, + )?; + + Ok(ScalarValue::Map(Arc::new(map_array))) + } + + fn size(&self) -> usize { + // ScalarValue::size already counts the enum itself, so spare capacity is + // accounted for separately to avoid double counting the held values + size_of_val(self) + + (size_of::<ScalarValue>() * (self.keys.capacity() + self.values.capacity())) + + self + .keys + .iter() + .chain(self.values.iter()) + .map(|s| s.size() - size_of::<ScalarValue>()) + .sum::<usize>() + } +} + +/// Accumulator used when `map_agg` has an `ORDER BY`. Stores the ordering column +/// values alongside each pair so the input can be globally sorted (across +/// partitions). +#[derive(Debug)] +pub struct OrderSensitiveMapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + /// Ordering-expression values for each pair, parallel to `keys`/`values`. + ordering_values: Vec<Vec<ScalarValue>>, + /// Data types of the ordering expressions, used to build the state field. + ordering_dtypes: Vec<DataType>, + /// The `ORDER BY` requirement inside the aggregate. + ordering_req: LexOrdering, + /// When true the input already satisfies `ordering_req`, so the pairs do + /// not have to be sorted again before de-duplication. + is_input_pre_ordered: bool, + /// Whether the input is ordered in the reverse direction of `ordering_req`. + reverse: bool, +} + +impl OrderSensitiveMapAggAccumulator { + /// Create a new accumulator for `map_agg(key, value ORDER BY ...)`. + /// + /// `ordering_dtypes` must hold one data type per entry of `ordering_req`. + pub fn new( + key_type: DataType, + value_type: DataType, + ordering_dtypes: Vec<DataType>, + ordering_req: LexOrdering, + is_input_pre_ordered: bool, + reverse: bool, + ) -> Self { + Self { + key_type, + value_type, + keys: Vec::new(), + values: Vec::new(), + ordering_values: Vec::new(), + ordering_dtypes, + ordering_req, + is_input_pre_ordered, + reverse, + } + } + + /// Sort options of each ordering expression, used when sorting the pairs + /// and when merging partial states. + fn sort_options(&self) -> Vec<SortOptions> { + self.ordering_req + .iter() + .map(|s| if self.reverse { !s.options } else { s.options }) Review Comment: **Medium · The reversal fix requested by kumarUjjawal in threads/r4356179949.md (now marked resolved) is only correct when the input is pre-ordered: `sort_options()` flips the options, which are already reversed, back to the user's original order, and then `sorted_deduped` reverses the rows again. Any reversed accumulator that is not pre-ordered therefore de-duplicates and emits entries in the reverse of the requested order.** Failure scenario: `reverse_expr` passes reversed `order_bys` plus `is_reversed=true`, and the physical planner copies the reversed exprs into the Final/FinalPartitioned aggregate with `is_input_pre_ordered=false` (physical_planner.rs:2193). update_aggr_exprs.rs:194 can also produce a reversed expr with beneficial_ordering(false). Example: `SELECT g, map_agg(k, v ORDER BY v) FROM (SELECT * FROM (VALUES (1,'a',20),(1,'b',5),(1,'a',10)) t(g,k,v) ORDER BY v DESC) GROUP BY g` with hash repartitioning. The final `evaluate` sorts ascending, then iterates in reverse, so it keeps a=20 and returns `{a: 20, b: 5}` instead of `{b: 5, a: 10}`. array_agg sorts by the reversed `ordering_req` as given and reverses only on output. The new unit test hard-codes an ASC requirement with reverse=true and pre-ordered input, a combination the optimizer never builds, and the SLT test collapses to Single mode, so neither covers this path. ########## datafusion/sqllogictest/test_files/map_agg.slt: ########## @@ -0,0 +1,229 @@ +# 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. + +####### +# Tests for the map_agg aggregate function. +####### + +# A map is built from all input rows. +query ? +SELECT map_agg(v, m) FROM (VALUES (1, 10), (2, 20), (3, 30), (4, 40)) t(v, m) +---- +{1: 10, 2: 20, 3: 30, 4: 40} + +# NULL values are kept in the map. +query ? +SELECT map_agg(v, m) FROM (VALUES (1, 10), (2, NULL), (3, 30)) t(v, m) +---- +{1: 10, 2: NULL, 3: 30} + +# Null keys cannot be represented in an Arrow map. +statement error DataFusion error: Execution error: map key cannot be null +SELECT map_agg(v, m) FROM (VALUES (1, 10), (NULL, 20)) t(v, m) + +# Empty input produces a NULL map, like array_agg. +query ? +SELECT map_agg(v, m) FROM (VALUES (1, 10)) t(v, m) WHERE false +---- +NULL + +# Each group collects its own key/value pairs into one map. +query T? +SELECT k, map_agg(v, m) +FROM (VALUES + ('a', 1, 10), + ('a', 2, 20), + ('b', 3, 30) +) t(k, v, m) +GROUP BY k +ORDER BY k +---- +a {1: 10, 2: 20} +b {3: 30} + +# duplicate group keys: each group keeps only its first pair per key +query T? +SELECT k, map_agg(k,v) +FROM (VALUES + ('a', 1), + ('a', 2), + ('b', 3) +) t(k, v ) +GROUP BY k +ORDER BY k +---- +a {a: 1} +b {b: 3} + +# ORDER BY inside the aggregate controls the map entry order +query ? +SELECT map_agg(k, v ORDER BY v) +FROM (VALUES + ('a', 3), + ('b', 1), + ('c', 2) +) t(k, v) +---- +{b: 1, c: 2, a: 3} + +# ORDER BY DESC reverses the entry order. +query ? +SELECT map_agg(k, v ORDER BY v DESC) +FROM (VALUES ('a', 3), ('b', 1), ('c', 2)) t(k, v) +---- +{a: 3, c: 2, b: 1} + +# Ordering by the key puts the entries in key order. +query ? +SELECT map_agg(k, v ORDER BY k) +FROM (VALUES ('c', 3), ('a', 1), ('b', 2)) t(k, v) +---- +{a: 1, b: 2, c: 3} + +# Multiple ordering expressions are applied left to right. +query ? +SELECT map_agg(k, v ORDER BY g, v DESC) +FROM (VALUES + ('a', 1, 'x'), + ('b', 5, 'x'), + ('c', 3, 'y') +) t(k, v, g) +---- +{b: 5, a: 1, c: 3} + +# The ordering may reference a column that is neither the key nor the value. +query ? +SELECT map_agg(k, v ORDER BY o) +FROM (VALUES ('a', 10, 3), ('b', 20, 1), ('c', 30, 2)) t(k, v, o) +---- +{b: 20, c: 30, a: 10} + +# With an ORDER BY the pairs are sorted before de-duplication, so the pair that +# sorts first wins -- unlike the unordered accumulator, which keeps the first +# input row. +query ? +SELECT map_agg(k, v ORDER BY v) +FROM (VALUES ('a', 20), ('b', 5), ('a', 10)) t(k, v) +---- +{b: 5, a: 10} + +# Reverse-preordered input must still use the first pair in the requested +# ordering, not the first physical row. +query ? +SELECT map_agg(k, v ORDER BY v) +FROM ( + SELECT * FROM (VALUES ('a', 20), ('b', 5), ('a', 10)) t(k, v) + ORDER BY v DESC +) t +---- +{b: 5, a: 10} + +# The default null ordering is NULLS LAST for ascending order, so NULL ordering +# values sort to the end. +query ? +SELECT map_agg(k, v ORDER BY v) +FROM (VALUES ('a', 1), ('b', NULL), ('c', 2)) t(k, v) +---- +{a: 1, c: 2, b: NULL} + +# NULLS FIRST moves them to the front. +query ? +SELECT map_agg(k, v ORDER BY v NULLS FIRST) +FROM (VALUES ('a', 1), ('b', NULL), ('c', 2)) t(k, v) +---- +{b: NULL, a: 1, c: 2} + +# NULL keys cannot be represented in an Arrow map, so the ordered accumulator +# skips the whole pair instead of failing like the unordered one. +query ? Review Comment: **Medium · The ordered `update_batch` now rejects NULL keys with an error (map_agg.rs:579), as kumarUjjawal asked in threads/r4356179954.md, but the SLT test still expects the NULL-key pair to be dropped silently. The module docs (map_agg.rs:50-52) and the inline comment at map_agg.rs:577 still describe the old skip behavior.** Failure scenario: `SELECT map_agg(k, v ORDER BY v) FROM (VALUES ('a', 1), (NULL, 2)) t(k, v)` now fails with `null key's are not allowed in map_agg`, while the test expects `{a: 1}`. The sqllogictest fails, and the docs tell users rows are dropped. The error text also differs from the unordered path's `map key cannot be null` and has a stray apostrophe. ########## datafusion/functions-aggregate/src/utils.rs: ########## @@ -4,11 +4,11 @@ use std::sync::Arc; -use arrow::array::{Array, ArrayRef, Float32Array, Float64Array, RecordBatch}; -use arrow::compute::{cast, max, min}; +use arrow::array::{Array, Float32Array, Float64Array, ArrayRef, MapArray, RecordBatch, StructArray}; use arrow::datatypes::{DataType, Schema}; +use arrow::compute::{cast, max, min}; use datafusion_common::{ - Result, ScalarValue, downcast_value, exec_datafusion_err, exec_err, + Result, ScalarValue, DataFusionError,downcast_value, exec_datafusion_err, exec_err, Review Comment: **Medium · The edit to the import block adds an unused `DataFusionError` import (`DataFusionError,downcast_value` with no space), leaves `use` items out of formatter order, and misindents `Some(current) =>` in `resolve_group_value` (around line 277). The reviewer's cleanup request in threads/r4356179945.md was not completed cleanly.** Failure scenario: The 'Check cargo fmt' CI job is failing on this PR, and `DataFusionError` is never used in utils.rs, which triggers an unused-import warning (an error under `-D warnings`). The PR cannot merge until rustfmt is run and the import is removed. ########## datafusion/sqllogictest/test_files/aggregate_order_by.slt: ########## @@ -0,0 +1,9 @@ +query ? Review Comment: **Medium · This new SLT file has no Apache license header, and it is a leftover probe file (renamed from tmp_order_probe.slt) that only tests array_agg and string_agg and has nothing to do with map_agg.** Failure scenario: The 'Check License Header' CI job is failing. The file also adds unrelated, duplicate test coverage to the repo. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { + self.keys + .push(ScalarValue::try_from_array(keys, row)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, row)?.compacted()); + } + + Ok(()) + } + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + + assert_eq_or_internal_err!(states.len(), 1, "expects single state"); + + let map_arr = as_map_array(states[0].as_ref())?; + let offsets = map_arr.value_offsets(); + let map_keys = map_arr.keys(); + let map_values = map_arr.values(); + + for row in 0..map_arr.len() { + // Partial states are nullable so empty groups can produce a NULL map + if map_arr.is_null(row) { + continue; + } + for idx in offsets[row] as usize..offsets[row + 1] as usize { + self.keys + .push(ScalarValue::try_from_array(map_keys, idx)?.compacted()); + self.values + .push(ScalarValue::try_from_array(map_values, idx)?.compacted()); + } + } + + Ok(()) + } + + fn state(&mut self) -> Result<Vec<ScalarValue>> { + Ok(vec![self.evaluate()?]) + } + + fn evaluate(&mut self) -> Result<ScalarValue> { + let map_type = self.map_type(); + + if self.keys.is_empty() { + return ScalarValue::try_new_null(&map_type); + } + + // Arrow maps cannot represent null keys (same rule as the `map` function) + if self.keys.iter().any(ScalarValue::is_null) { + return exec_err!("map key cannot be null"); + } + + let (keys, values) = + Self::dedup_first_wins(self.keys.clone(), self.values.clone()); + + let keys = ScalarValue::iter_to_array(keys)?; + let values = ScalarValue::iter_to_array(values)?; + + let DataType::Map(entries_field, ordered) = &map_type else { + return internal_err!("map_agg expected Map type, got {map_type}"); + }; + let DataType::Struct(entry_fields) = entries_field.data_type() else { + return internal_err!( + "map_agg expected struct entries, got {}", + entries_field.data_type() + ); + }; + + let entries = + StructArray::try_new(entry_fields.clone(), vec![keys, values], None)?; + + let Ok(num_entries) = i32::try_from(entries.len()) else { + return internal_err!( + "map_agg produced {} entries which exceeds the map offset range", + entries.len() + ); + }; + let offsets = OffsetBuffer::new(ScalarBuffer::from(vec![0_i32, num_entries])); + let map_array = MapArray::try_new( + Arc::clone(entries_field), + offsets, + entries, + None, + *ordered, + )?; + + Ok(ScalarValue::Map(Arc::new(map_array))) + } + + fn size(&self) -> usize { + // ScalarValue::size already counts the enum itself, so spare capacity is + // accounted for separately to avoid double counting the held values + size_of_val(self) + + (size_of::<ScalarValue>() * (self.keys.capacity() + self.values.capacity())) + + self + .keys + .iter() + .chain(self.values.iter()) + .map(|s| s.size() - size_of::<ScalarValue>()) + .sum::<usize>() + } +} + +/// Accumulator used when `map_agg` has an `ORDER BY`. Stores the ordering column +/// values alongside each pair so the input can be globally sorted (across +/// partitions). +#[derive(Debug)] +pub struct OrderSensitiveMapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + /// Ordering-expression values for each pair, parallel to `keys`/`values`. + ordering_values: Vec<Vec<ScalarValue>>, + /// Data types of the ordering expressions, used to build the state field. + ordering_dtypes: Vec<DataType>, + /// The `ORDER BY` requirement inside the aggregate. + ordering_req: LexOrdering, + /// When true the input already satisfies `ordering_req`, so the pairs do + /// not have to be sorted again before de-duplication. + is_input_pre_ordered: bool, + /// Whether the input is ordered in the reverse direction of `ordering_req`. + reverse: bool, +} + +impl OrderSensitiveMapAggAccumulator { + /// Create a new accumulator for `map_agg(key, value ORDER BY ...)`. + /// + /// `ordering_dtypes` must hold one data type per entry of `ordering_req`. + pub fn new( + key_type: DataType, + value_type: DataType, + ordering_dtypes: Vec<DataType>, + ordering_req: LexOrdering, + is_input_pre_ordered: bool, + reverse: bool, + ) -> Self { + Self { + key_type, + value_type, + keys: Vec::new(), + values: Vec::new(), + ordering_values: Vec::new(), + ordering_dtypes, + ordering_req, + is_input_pre_ordered, + reverse, + } + } + + /// Sort options of each ordering expression, used when sorting the pairs + /// and when merging partial states. + fn sort_options(&self) -> Vec<SortOptions> { + self.ordering_req + .iter() + .map(|s| if self.reverse { !s.options } else { s.options }) + .collect() + } + + /// Sorts the accumulated pairs by their ordering values, then applies + /// first-wins de-duplication. Returns the surviving keys, values, and + /// ordering values, all aligned so they describe the same rows. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn sorted_deduped(&self) -> Result<OrderSensitiveMapAggRows> { + let mut rows: Vec<usize> = (0..self.keys.len()).collect(); + + if !self.is_input_pre_ordered { + let sort_options = self.sort_options(); + let mut cmp_err = Ok(()); + rows.sort_by(|&a, &b| { + compare_rows( + &self.ordering_values[a], + &self.ordering_values[b], + &sort_options, + ) + .unwrap_or_else(|e| { + cmp_err = Err(e); + std::cmp::Ordering::Equal + }) + }); + cmp_err?; + } + + // Keep the first occurrence of each key in sorted order, and project the + // keys, values, and ordering values through the same surviving indices + // so all three stay aligned. + let mut seen = HashSet::with_capacity(rows.len()); + let mut keys = Vec::new(); + let mut values = Vec::new(); + let mut ordering_values = Vec::new(); + let row_indices = if self.reverse { + rows.iter().rev().copied().collect::<Vec<_>>() + } else { + rows + }; + for i in row_indices { + if seen.insert(&self.keys[i]) { + keys.push(self.keys[i].clone()); + values.push(self.values[i].clone()); + ordering_values.push(self.ordering_values[i].clone()); + } + } + + Ok(OrderSensitiveMapAggRows { + keys, + values, + ordering_values, + }) + } + + /// Builds the `List<Struct<ordering...>>` state column from the given + /// ordering values. These must be the de-duplicated ordering values that + /// align with the map state, so both pieces of state describe the same rows. + fn evaluate_orderings( + &self, + ordering_values: &[Vec<ScalarValue>], + ) -> Result<ScalarValue> { + let fields = ordering_fields(&self.ordering_req, &self.ordering_dtypes); + let struct_field = Fields::from(fields.clone()); + + let mut column_wise: Vec<ArrayRef> = Vec::with_capacity(fields.len()); + for (col_idx, field) in fields.iter().enumerate() { + if ordering_values.is_empty() { + column_wise.push(arrow::array::new_empty_array(field.data_type())); + } else { + let col_vals = ordering_values.iter().map(|row| row[col_idx].clone()); + column_wise.push(ScalarValue::iter_to_array(col_vals)?); + } + } + + let struct_array = StructArray::try_new(struct_field, column_wise, None)?; + Ok(SingleRowListArrayBuilder::new(Arc::new(struct_array)).build_list_scalar()) + } +} + +/// Keys, values, and ordering values of the rows that survive sorting and +/// first-wins de-duplication. The three vectors are parallel. +#[derive(Debug)] +struct OrderSensitiveMapAggRows { + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ordering_values: Vec<Vec<ScalarValue>>, +} + +impl Accumulator for OrderSensitiveMapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + if values.len() < 2 { + return exec_err!("map_agg expects at least 2 columns, got {}", values.len()); + } + let keys = &values[0]; + let vals = &values[1]; + let ordering_cols = &values[2..]; + + for i in 0..keys.len() { + // NULL keys cannot exist in a map; skip the whole pair. + if keys.is_null(i) { + return exec_err!("null key's are not allowed in map_agg"); + } + self.keys + .push(ScalarValue::try_from_array(keys, i)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, i)?.compacted()); + self.ordering_values.push( + get_row_at_idx(ordering_cols, i)? + .into_iter() + .map(|v| v.compacted()) + .collect(), + ); + } + Ok(()) + } + + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + if states.len() != 2 { + return exec_err!( + "map_agg ordered merge expects 2 state columns, got {}", + states.len() + ); + } + + let map_array = states[0].as_map(); + let orderings = states[1].as_list::<i32>(); + + // Each partition contributes one map row plus a parallel list of + // ordering-value structs. Collect them, then merge by ordering. + let mut partition_keys: Vec<VecDeque<ScalarValue>> = + vec![take(&mut self.keys).into()]; + let mut partition_orderings: Vec<VecDeque<Vec<ScalarValue>>> = + vec![take(&mut self.ordering_values).into()]; + let mut partition_values: Vec<VecDeque<ScalarValue>> = + vec![take(&mut self.values).into()]; + + // Push keys and values from each partition's state into the merge buffers. + for row in 0..map_array.len() { + if map_array.is_null(row) { + continue; + } + let (mut keys, mut values) = map_row_to_scalars(map_array, row)?; + let mut ord_vals = struct_to_rows(orderings.value(row).as_struct())?; + + keys.iter_mut().for_each(ScalarValue::compact); + values.iter_mut().for_each(ScalarValue::compact); + ord_vals.iter_mut().flatten().for_each(ScalarValue::compact); + + partition_keys.push(keys.into()); + partition_values.push(values.into()); + partition_orderings.push(ord_vals.into()); + } + + // Merge keys and values along the ordering. `merge_ordered_arrays` + // merges a single value stream; run it once for keys and once for + // values using the same ordering inputs so they stay aligned. + let sort_options = self.sort_options(); + + let (merged_keys, merged_orderings) = merge_ordered_arrays( + &mut partition_keys, + &mut partition_orderings.clone(), Review Comment: **Medium · The ordered `merge_batch` deep-clones every partition's ordering vectors (`&mut partition_orderings.clone()`) so it can run `merge_ordered_arrays` twice, once for keys and once for values.** Failure scenario: Each merge allocates a full copy of every `Vec<ScalarValue>` ordering row across all incoming partitions, doubling the memory and CPU spent merging large groups. A single merge over `(key, value)` pairs, for example packed as a struct scalar or merged by index, would avoid the copy. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { + self.keys + .push(ScalarValue::try_from_array(keys, row)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, row)?.compacted()); + } + + Ok(()) + } + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + + assert_eq_or_internal_err!(states.len(), 1, "expects single state"); + + let map_arr = as_map_array(states[0].as_ref())?; + let offsets = map_arr.value_offsets(); + let map_keys = map_arr.keys(); + let map_values = map_arr.values(); + + for row in 0..map_arr.len() { + // Partial states are nullable so empty groups can produce a NULL map + if map_arr.is_null(row) { + continue; + } + for idx in offsets[row] as usize..offsets[row + 1] as usize { + self.keys + .push(ScalarValue::try_from_array(map_keys, idx)?.compacted()); + self.values + .push(ScalarValue::try_from_array(map_values, idx)?.compacted()); + } + } + + Ok(()) + } + + fn state(&mut self) -> Result<Vec<ScalarValue>> { + Ok(vec![self.evaluate()?]) + } + + fn evaluate(&mut self) -> Result<ScalarValue> { + let map_type = self.map_type(); + + if self.keys.is_empty() { + return ScalarValue::try_new_null(&map_type); + } + + // Arrow maps cannot represent null keys (same rule as the `map` function) + if self.keys.iter().any(ScalarValue::is_null) { + return exec_err!("map key cannot be null"); + } + + let (keys, values) = + Self::dedup_first_wins(self.keys.clone(), self.values.clone()); Review Comment: **Medium · `MapAggAccumulator::evaluate`, which `state()` also calls, clones the entire `keys` and `values` vectors and then clones every key again into the `HashSet` inside `dedup_first_wins`.** Failure scenario: Every partial-state emission and every final evaluation copies all accumulated scalars about three times, including heap-backed strings and nested values. The ordered path already uses a `HashSet<&ScalarValue>` over borrowed keys (line 509), which avoids this. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { + self.keys + .push(ScalarValue::try_from_array(keys, row)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, row)?.compacted()); + } + + Ok(()) + } + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + + assert_eq_or_internal_err!(states.len(), 1, "expects single state"); + + let map_arr = as_map_array(states[0].as_ref())?; + let offsets = map_arr.value_offsets(); + let map_keys = map_arr.keys(); + let map_values = map_arr.values(); + + for row in 0..map_arr.len() { + // Partial states are nullable so empty groups can produce a NULL map + if map_arr.is_null(row) { + continue; + } + for idx in offsets[row] as usize..offsets[row + 1] as usize { + self.keys + .push(ScalarValue::try_from_array(map_keys, idx)?.compacted()); + self.values + .push(ScalarValue::try_from_array(map_values, idx)?.compacted()); + } + } + + Ok(()) + } + + fn state(&mut self) -> Result<Vec<ScalarValue>> { + Ok(vec![self.evaluate()?]) + } + + fn evaluate(&mut self) -> Result<ScalarValue> { + let map_type = self.map_type(); + + if self.keys.is_empty() { + return ScalarValue::try_new_null(&map_type); + } + + // Arrow maps cannot represent null keys (same rule as the `map` function) + if self.keys.iter().any(ScalarValue::is_null) { + return exec_err!("map key cannot be null"); + } + + let (keys, values) = + Self::dedup_first_wins(self.keys.clone(), self.values.clone()); + + let keys = ScalarValue::iter_to_array(keys)?; + let values = ScalarValue::iter_to_array(values)?; + + let DataType::Map(entries_field, ordered) = &map_type else { Review Comment: **Medium · `MapAggAccumulator::evaluate` re-implements the Map-type destructuring, StructArray construction, i32 offset check and `MapArray::try_new` that `build_single_map` (lines 702-749) already provides.** Failure scenario: About 30 lines are duplicated, so a fix to map construction (for example to nullability or offsets) has to be made in two places. `evaluate` could call `build_single_map(keys, values, ...)` and convert the result to a scalar. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { + self.keys + .push(ScalarValue::try_from_array(keys, row)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, row)?.compacted()); + } + + Ok(()) + } + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + + assert_eq_or_internal_err!(states.len(), 1, "expects single state"); + + let map_arr = as_map_array(states[0].as_ref())?; + let offsets = map_arr.value_offsets(); + let map_keys = map_arr.keys(); + let map_values = map_arr.values(); + + for row in 0..map_arr.len() { + // Partial states are nullable so empty groups can produce a NULL map + if map_arr.is_null(row) { + continue; + } + for idx in offsets[row] as usize..offsets[row + 1] as usize { Review Comment: **Medium · `MapAggAccumulator::merge_batch` hand-rolls the offset-based loop that splits a map row into key and value scalars, even though this PR adds `utils::map_row_to_scalars` for exactly that and the ordered accumulator uses it.** Failure scenario: The same decoding logic lives in two places within one PR, and the two copies can drift apart, for example in the compaction handling the reviewer asked for. The loop can be replaced with `map_row_to_scalars(map_arr, row)` followed by compaction. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { Review Comment: **Medium · Both accumulators convert every input row into individual `ScalarValue`s, calling `try_from_array` and `compacted()` per cell, and sort and de-duplicate over `Vec<ScalarValue>`, while `OrderSensitiveArrayAggAccumulator` keeps whole ArrayRef batches and uses a RowConverter.** Failure scenario: On large groups this costs a heap allocation per string or nested cell plus `ScalarValue` comparisons in `compare_rows` during the sort. It is orders of magnitude slower and more memory-hungry than array_agg's batch-based design, which map_agg could reuse by storing key and value arrays and taking or interleaving them by sorted index. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); + }; + + let ordering_dtypes = ordering + .iter() + .map(|e| e.expr.data_type(acc_args.schema)) + .collect::<Result<Vec<_>>>()?; + + Ok(Box::new(OrderSensitiveMapAggAccumulator::new( + key_type, + value_type, + ordering_dtypes, + ordering, + self.is_input_pre_ordered, + acc_args.is_reversed, + ))) + } + + fn order_sensitivity(&self) -> AggregateOrderSensitivity { + AggregateOrderSensitivity::SoftRequirement + } + + fn reverse_expr(&self) -> datafusion_expr::ReversedUDAF { + datafusion_expr::ReversedUDAF::Reversed(map_agg_udaf()) + } + + fn with_beneficial_ordering( + self: Arc<Self>, + beneficial_ordering: bool, + ) -> Result<Option<Arc<dyn AggregateUDFImpl>>> { + Ok(Some(Arc::new(Self { + signature: self.signature.clone(), + is_input_pre_ordered: beneficial_ordering, + }))) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Accumulates key/value pairs for [`MapAgg`]. +/// +/// Input rows are kept as parallel [`ScalarValue`] lists and concatenated into +/// the map in [`Self::evaluate`]; partial states are single-row [`MapArray`] +/// scalars that are split back into rows in [`Self::merge_batch`]. +#[derive(Debug)] +pub struct MapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + /// Input keys in arrival order, parallel to `values`. + keys: Vec<ScalarValue>, + /// Input values in arrival order, parallel to `keys`. + values: Vec<ScalarValue>, +} + +impl MapAggAccumulator { + /// Create a new map_agg accumulator for the given key and value types + pub fn try_new(key_type: DataType, value_type: DataType) -> Result<Self> { + Ok(Self { + key_type, + value_type, + keys: vec![], + values: vec![], + }) + } + /// Keeps only the first occurrence of each key, preserving input order. + /// + /// Returns the surviving keys and values as two aligned vectors. + #[allow(clippy::allow_attributes, clippy::mutable_key_type)] // ScalarValue has interior mutability but is intentionally used as hash key + fn dedup_first_wins( + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + ) -> (Vec<ScalarValue>, Vec<ScalarValue>) { + // First pass: mark each position that is the first occurrence of its key. + let mut seen = HashSet::with_capacity(keys.len()); + let keep: Vec<bool> = keys.iter().map(|k| seen.insert(k.clone())).collect(); + + // Second pass: keep only the first-occurrence positions. + let out_keys = keys + .into_iter() + .zip(&keep) + .filter_map(|(k, &keep)| keep.then_some(k)) + .collect(); + let out_values = values + .into_iter() + .zip(&keep) + .filter_map(|(v, &keep)| keep.then_some(v)) + .collect(); + (out_keys, out_values) + } + /// The `DataType::Map` this accumulator evaluates to + fn map_type(&self) -> DataType { + MapAgg::map_data_type(&self.key_type, &self.value_type) + } +} + +impl Accumulator for MapAggAccumulator { + fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> { + assert_eq_or_internal_err!(values.len(), 2, "map_agg expects (key, value)"); + + let keys = &values[0]; + let vals = &values[1]; + assert_eq_or_internal_err!(keys.len(), vals.len(), "key/value length mismatch"); + + for row in 0..keys.len() { + self.keys + .push(ScalarValue::try_from_array(keys, row)?.compacted()); + self.values + .push(ScalarValue::try_from_array(vals, row)?.compacted()); + } + + Ok(()) + } + fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> { + if states.is_empty() { + return Ok(()); + } + + assert_eq_or_internal_err!(states.len(), 1, "expects single state"); + + let map_arr = as_map_array(states[0].as_ref())?; + let offsets = map_arr.value_offsets(); + let map_keys = map_arr.keys(); + let map_values = map_arr.values(); + + for row in 0..map_arr.len() { + // Partial states are nullable so empty groups can produce a NULL map + if map_arr.is_null(row) { + continue; + } + for idx in offsets[row] as usize..offsets[row + 1] as usize { + self.keys + .push(ScalarValue::try_from_array(map_keys, idx)?.compacted()); + self.values + .push(ScalarValue::try_from_array(map_values, idx)?.compacted()); + } + } + + Ok(()) + } + + fn state(&mut self) -> Result<Vec<ScalarValue>> { + Ok(vec![self.evaluate()?]) + } + + fn evaluate(&mut self) -> Result<ScalarValue> { + let map_type = self.map_type(); + + if self.keys.is_empty() { + return ScalarValue::try_new_null(&map_type); + } + + // Arrow maps cannot represent null keys (same rule as the `map` function) + if self.keys.iter().any(ScalarValue::is_null) { + return exec_err!("map key cannot be null"); + } + + let (keys, values) = + Self::dedup_first_wins(self.keys.clone(), self.values.clone()); + + let keys = ScalarValue::iter_to_array(keys)?; + let values = ScalarValue::iter_to_array(values)?; + + let DataType::Map(entries_field, ordered) = &map_type else { + return internal_err!("map_agg expected Map type, got {map_type}"); + }; + let DataType::Struct(entry_fields) = entries_field.data_type() else { + return internal_err!( + "map_agg expected struct entries, got {}", + entries_field.data_type() + ); + }; + + let entries = + StructArray::try_new(entry_fields.clone(), vec![keys, values], None)?; + + let Ok(num_entries) = i32::try_from(entries.len()) else { + return internal_err!( + "map_agg produced {} entries which exceeds the map offset range", + entries.len() + ); + }; + let offsets = OffsetBuffer::new(ScalarBuffer::from(vec![0_i32, num_entries])); + let map_array = MapArray::try_new( + Arc::clone(entries_field), + offsets, + entries, + None, + *ordered, + )?; + + Ok(ScalarValue::Map(Arc::new(map_array))) + } + + fn size(&self) -> usize { + // ScalarValue::size already counts the enum itself, so spare capacity is + // accounted for separately to avoid double counting the held values + size_of_val(self) + + (size_of::<ScalarValue>() * (self.keys.capacity() + self.values.capacity())) + + self + .keys + .iter() + .chain(self.values.iter()) + .map(|s| s.size() - size_of::<ScalarValue>()) + .sum::<usize>() + } +} + +/// Accumulator used when `map_agg` has an `ORDER BY`. Stores the ordering column +/// values alongside each pair so the input can be globally sorted (across +/// partitions). +#[derive(Debug)] +pub struct OrderSensitiveMapAggAccumulator { + /// Data type of the map keys. + key_type: DataType, + /// Data type of the map values. + value_type: DataType, + keys: Vec<ScalarValue>, + values: Vec<ScalarValue>, + /// Ordering-expression values for each pair, parallel to `keys`/`values`. + ordering_values: Vec<Vec<ScalarValue>>, + /// Data types of the ordering expressions, used to build the state field. + ordering_dtypes: Vec<DataType>, + /// The `ORDER BY` requirement inside the aggregate. + ordering_req: LexOrdering, + /// When true the input already satisfies `ordering_req`, so the pairs do + /// not have to be sorted again before de-duplication. + is_input_pre_ordered: bool, + /// Whether the input is ordered in the reverse direction of `ordering_req`. + reverse: bool, +} + +impl OrderSensitiveMapAggAccumulator { + /// Create a new accumulator for `map_agg(key, value ORDER BY ...)`. + /// + /// `ordering_dtypes` must hold one data type per entry of `ordering_req`. + pub fn new( + key_type: DataType, + value_type: DataType, + ordering_dtypes: Vec<DataType>, + ordering_req: LexOrdering, + is_input_pre_ordered: bool, + reverse: bool, + ) -> Self { + Self { + key_type, + value_type, + keys: Vec::new(), + values: Vec::new(), + ordering_values: Vec::new(), + ordering_dtypes, + ordering_req, + is_input_pre_ordered, + reverse, + } + } + + /// Sort options of each ordering expression, used when sorting the pairs + /// and when merging partial states. + fn sort_options(&self) -> Vec<SortOptions> { + self.ordering_req + .iter() + .map(|s| if self.reverse { !s.options } else { s.options }) + .collect() Review Comment: **High · Apply reversal only once in non-preordered final accumulators** For reverse-sorted input, the physical planner copies the reversed aggregate expression into both Partial and Final stages, but the final accumulator remains non-preordered. Here the sort options are flipped back to the SQL direction, then `sorted_deduped()` reverses the sorted indices again. Consequently, an ASC aggregate can return DESC entries and keep the larger duplicate value across partitions. The reversal requested by kumarUjjawal in `threads/r4356179949.md` still needs consistent final-stage handling and a partial/final regression test. ########## datafusion/functions-aggregate/src/map_agg.rs: ########## @@ -0,0 +1,1036 @@ +// 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. + +//! `MAP_AGG` aggregate implementation: [`MapAgg`] +//! +//! Aggregates key/value pairs into a `Map`, analogous to how `array_agg` +//! aggregates values into a `List`. +//! +//! # Accumulators +//! +//! Two accumulators implement the function, selected in +//! [`MapAgg::accumulator`] by whether the aggregate carries an `ORDER BY`: +//! +//! * [`MapAggAccumulator`] keeps the pairs in input order and serializes its +//! state as a single `Map` column. +//! * [`OrderSensitiveMapAggAccumulator`] additionally records the values of the +//! ordering expressions for every pair. Its state therefore has two columns, +//! the `Map` plus a `List<Struct<ordering...>>` that lets partial states from +//! every partition be merged on the ordering by `merge_batch`, so the final +//! entry order stays deterministic under parallelism. +//! +//! [`MapAgg::order_sensitivity`] is [`AggregateOrderSensitivity::SoftRequirement`], +//! so when a plan's input already satisfies the ordering the accumulator is +//! marked through [`AggregateUDFImpl::with_beneficial_ordering`] and the pairs +//! are not sorted again. +//! +//! # De-duplication +//! +//! Arrow maps hold at most one value per key, so duplicate keys are removed +//! when the accumulator evaluates. The *first* pair wins, where "first" means +//! first in input order for [`MapAggAccumulator`] and first in the sorted +//! order for [`OrderSensitiveMapAggAccumulator`]. +//! +//! # Nulls +//! +//! Arrow maps cannot represent `NULL` keys: [`MapAggAccumulator`] fails with +//! `map key cannot be null` when one is evaluated, while +//! [`OrderSensitiveMapAggAccumulator`] drops such pairs as it collects input. +//! `NULL` values are ordinary map values and are kept. An empty group +//! evaluates to a `NULL` map, matching `array_agg`. + +use std::collections::{HashSet, VecDeque}; +use std::mem::{size_of, size_of_val, take}; +use std::sync::Arc; + +use arrow::array::{Array, ArrayRef, AsArray, MapArray, StructArray}; +use arrow::buffer::{NullBuffer, OffsetBuffer, ScalarBuffer}; +use arrow::compute::SortOptions; +use arrow::datatypes::{DataType, Field, FieldRef, Fields}; + +use datafusion_common::cast::as_map_array; +use datafusion_common::utils::{ + SingleRowListArrayBuilder, compare_rows, get_row_at_idx, take_function_args, +}; +use datafusion_common::{ + Result, ScalarValue, assert_eq_or_internal_err, exec_err, internal_err, +}; +use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs}; +use datafusion_expr::utils::format_state_name; +use datafusion_expr::{ + Accumulator, AggregateUDFImpl, Documentation, Signature, Volatility, +}; +use datafusion_functions_aggregate_common::merge_arrays::merge_ordered_arrays; +use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity; +use datafusion_functions_aggregate_common::utils::ordering_fields; +use datafusion_macros::user_doc; +use datafusion_physical_expr_common::sort_expr::LexOrdering; + +use crate::utils::{map_row_to_scalars, struct_to_rows}; + +make_udaf_expr_and_func!( + MapAgg, + map_agg, + key value, + "Aggregates keys and values into a map", + map_agg_udaf +); + +#[user_doc( + doc_section(label = "General Functions"), + description = "Returns a map created from the key and value expression elements. \ +For each row, the key expression becomes a map key and the value expression becomes the corresponding map value. \ +Entries appear in input order, or in the order given by the optional `ORDER BY`. \ +When a key repeats, only the first entry for that key is kept.", + syntax_example = "map_agg(key, value [ORDER BY expression])", + sql_example = r#"```sql +> SELECT map_agg(column_key, column_value) FROM table_name; ++-------------------------------------+ +| map_agg(column_key, column_value) | ++-------------------------------------+ +| {key1: value1, key2: value2, ...} | ++-------------------------------------+ +```"#, + argument( + name = "key", + description = "Expression used as the map key. Can be a column or any valid expression." + ), + argument( + name = "value", + description = "Expression used as the map value. Can be a column or any valid expression." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +/// MAP_AGG aggregate expression +pub struct MapAgg { + /// Accepts two arguments of any type: the key and the value. + signature: Signature, + /// Whether the input is known to arrive already ordered by the `ORDER BY` + /// inside the aggregate. + is_input_pre_ordered: bool, +} + +impl Default for MapAgg { + fn default() -> Self { + Self { + signature: Signature::any(2, Volatility::Immutable), + is_input_pre_ordered: false, + } + } +} + +impl MapAgg { + /// Create a new MAP_AGG aggregate function + pub fn new() -> Self { + Self::default() + } + + /// Build the Arrow `Map` data type for `map_agg(key, value)` + fn map_data_type(key_type: &DataType, value_type: &DataType) -> DataType { + DataType::Map( + Arc::new(Field::new( + "entries", + DataType::Struct(Fields::from(vec![ + Field::new("key", key_type.clone(), false), + Field::new("value", value_type.clone(), true), + ])), + false, + )), + false, + ) + } +} + +impl AggregateUDFImpl for MapAgg { + fn name(&self) -> &str { + "map_agg" + } + + fn signature(&self) -> &Signature { + &self.signature + } + + fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> { + let [key_type, value_type] = take_function_args(self.name(), arg_types)?; + Ok(Self::map_data_type(key_type, value_type)) + } + + fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<FieldRef>> { + let map_type = Self::map_data_type( + args.input_fields[0].data_type(), + args.input_fields[1].data_type(), + ); + + let mut fields = vec![ + Field::new( + format_state_name(args.name, "map_agg"), + // Nullable so empty groups can produce a NULL map + map_type, + true, + ) + .into(), + ]; + + if args.ordering_fields.is_empty() { + return Ok(fields); + } + + let orderings = args.ordering_fields.to_vec(); + fields.push( + Field::new_list( + format_state_name(args.name, "map_agg_orderings"), + Field::new_list_field(DataType::Struct(Fields::from(orderings)), true), + false, + ) + .into(), + ); + + Ok(fields) + } + + fn accumulator(&self, acc_args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> { + let [key_field, value_field] = + take_function_args(self.name(), acc_args.expr_fields)?; + let key_type = key_field.data_type().clone(); + let value_type = value_field.data_type().clone(); + + let Some(ordering) = LexOrdering::new(acc_args.order_bys.to_vec()) else { + return MapAggAccumulator::try_new(key_type, value_type) + .map(|acc| Box::new(acc) as _); Review Comment: **Medium · Honor reversal in the unordered window accumulator** When `get_best_fitting_window()` reverses a `map_agg(k, v) OVER (ORDER BY ord ...)` window to reuse reverse-sorted input, its aggregate has no internal `order_bys`, so this branch selects an accumulator that ignores `is_reversed`. Even for a full-partition frame, duplicate keys then retain the last value in the requested window order rather than the first. Either support reversal in `MapAggAccumulator` or stop advertising reversal for this path. ########## datafusion/sqllogictest/test_files/map_agg.slt: ########## @@ -0,0 +1,229 @@ +# 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. + +####### +# Tests for the map_agg aggregate function. +####### + +# A map is built from all input rows. +query ? +SELECT map_agg(v, m) FROM (VALUES (1, 10), (2, 20), (3, 30), (4, 40)) t(v, m) +---- +{1: 10, 2: 20, 3: 30, 4: 40} + +# NULL values are kept in the map. +query ? +SELECT map_agg(v, m) FROM (VALUES (1, 10), (2, NULL), (3, 30)) t(v, m) +---- +{1: 10, 2: NULL, 3: 30} + +# Null keys cannot be represented in an Arrow map. +statement error DataFusion error: Execution error: map key cannot be null +SELECT map_agg(v, m) FROM (VALUES (1, 10), (NULL, 20)) t(v, m) + +# Empty input produces a NULL map, like array_agg. +query ? +SELECT map_agg(v, m) FROM (VALUES (1, 10)) t(v, m) WHERE false +---- +NULL + +# Each group collects its own key/value pairs into one map. +query T? +SELECT k, map_agg(v, m) +FROM (VALUES + ('a', 1, 10), + ('a', 2, 20), + ('b', 3, 30) +) t(k, v, m) +GROUP BY k +ORDER BY k +---- +a {1: 10, 2: 20} +b {3: 30} + +# duplicate group keys: each group keeps only its first pair per key +query T? +SELECT k, map_agg(k,v) +FROM (VALUES + ('a', 1), + ('a', 2), + ('b', 3) +) t(k, v ) +GROUP BY k +ORDER BY k +---- +a {a: 1} +b {b: 3} + +# ORDER BY inside the aggregate controls the map entry order +query ? +SELECT map_agg(k, v ORDER BY v) +FROM (VALUES + ('a', 3), + ('b', 1), + ('c', 2) +) t(k, v) +---- +{b: 1, c: 2, a: 3} + +# ORDER BY DESC reverses the entry order. +query ? +SELECT map_agg(k, v ORDER BY v DESC) +FROM (VALUES ('a', 3), ('b', 1), ('c', 2)) t(k, v) +---- +{a: 3, c: 2, b: 1} + +# Ordering by the key puts the entries in key order. +query ? +SELECT map_agg(k, v ORDER BY k) +FROM (VALUES ('c', 3), ('a', 1), ('b', 2)) t(k, v) +---- +{a: 1, b: 2, c: 3} + +# Multiple ordering expressions are applied left to right. +query ? +SELECT map_agg(k, v ORDER BY g, v DESC) +FROM (VALUES + ('a', 1, 'x'), + ('b', 5, 'x'), + ('c', 3, 'y') +) t(k, v, g) +---- +{b: 5, a: 1, c: 3} + +# The ordering may reference a column that is neither the key nor the value. +query ? +SELECT map_agg(k, v ORDER BY o) +FROM (VALUES ('a', 10, 3), ('b', 20, 1), ('c', 30, 2)) t(k, v, o) +---- +{b: 20, c: 30, a: 10} + +# With an ORDER BY the pairs are sorted before de-duplication, so the pair that +# sorts first wins -- unlike the unordered accumulator, which keeps the first +# input row. +query ? +SELECT map_agg(k, v ORDER BY v) +FROM (VALUES ('a', 20), ('b', 5), ('a', 10)) t(k, v) +---- +{b: 5, a: 10} + +# Reverse-preordered input must still use the first pair in the requested +# ordering, not the first physical row. +query ? +SELECT map_agg(k, v ORDER BY v) +FROM ( + SELECT * FROM (VALUES ('a', 20), ('b', 5), ('a', 10)) t(k, v) + ORDER BY v DESC +) t +---- +{b: 5, a: 10} + +# The default null ordering is NULLS LAST for ascending order, so NULL ordering +# values sort to the end. +query ? +SELECT map_agg(k, v ORDER BY v) +FROM (VALUES ('a', 1), ('b', NULL), ('c', 2)) t(k, v) +---- +{a: 1, c: 2, b: NULL} + +# NULLS FIRST moves them to the front. +query ? +SELECT map_agg(k, v ORDER BY v NULLS FIRST) +FROM (VALUES ('a', 1), ('b', NULL), ('c', 2)) t(k, v) +---- +{b: NULL, a: 1, c: 2} + +# NULL keys cannot be represented in an Arrow map, so the ordered accumulator +# skips the whole pair instead of failing like the unordered one. +query ? +SELECT map_agg(k, v ORDER BY v) FROM (VALUES ('a', 1), (NULL, 2)) t(k, v) +---- +{a: 1} Review Comment: **Medium · Expect an error in the ordered NULL-key SQL test** `OrderSensitiveMapAggAccumulator::update_batch()` now rejects NULL keys, so this query returns an execution error rather than `{a: 1}`. The newly added SLT therefore fails against the implementation. Change it to an error assertion and update the stale NULL-key documentation that still describes silently dropping pairs. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
