Skip to main content

ic_db/store/query/aggregate/
numeric.rs

1//! Integer/decimal sums and averages over one exact total, without numeric coercion.
2use super::{super::Plan, Aggregate, Completed, GroupValue, Query, Reducer};
3use crate::{
4    Decimal, Entity, EntitySchema, Error, FieldType, IndexValue, TypeBody, TypeSchema, U256, Value,
5    ValueSchema, codec::Encoder,
6};
7use ethnum::I256;
8use ic_storage::Memory;
9
10impl<E: Entity, M: Memory> Query<'_, E, M> {
11    /// Sum one integer or Decimal field into a single-field result record with the same field
12    /// name and optionality. Scalar newtype inputs use their declared primitive.
13    /// The result may preserve the exact input newtype. A primitive integer result may widen within
14    /// the same signed/unsigned family. Unsigned results may widen to U256.
15    /// Decimal results preserve the source's declared scale; coefficients accumulate
16    /// exactly in I256 and must fit i128 at completion. No rescaling or rounding.
17    /// Empty/all-absent input returns `None`; present zero returns a record.
18    /// Signed accumulation uses I256, so cancelling prefixes do not cause narrow
19    /// overflow. Unsigned accumulation uses checked U256. The final total must fit
20    /// the declared result width. No decimal/float conversion or rounding occurs.
21    /// # Errors
22    /// Refuses unsupported/narrower/cross-signedness result shapes, cursors, DISTINCT,
23    /// input ordering and group modifiers. Work exhaustion returns `Limit` without
24    /// a prefix total; numeric overflow returns `ArithmeticOverflow`. Output bytes
25    /// count the completed result record, with `RowTooLarge` on overflow of that budget.
26    /// # Panics
27    /// Supplier corruption traps without repair.
28    pub fn sum<R: Value>(self) -> Result<Aggregate<Option<R>>, Error> {
29        let (plan, reducer) = self.numeric_plan::<R>(None, Operation::Sum)?;
30        self.scalar_value(&plan, reducer)
31    }
32
33    /// Sum one integer or Decimal operand per exact grouping record, retaining absent keys
34    /// and all-absent groups. R selects the same explicit result widening as sum.
35    /// Group predicates use R's result type; e.g. Nat128 totals require u128 operands.
36    /// Complete every group before filtering, ordering and output limits.
37    /// # Errors
38    /// Scalar sum shape/range errors and grouped query work/state/output bounds apply.
39    /// Overflow in any group refuses the whole query, even if that group would be
40    /// filtered out or fall beyond the output limit. Finalization is bounded to
41    /// 32 groups and charged to the retained-state byte cap.
42    /// # Panics
43    /// Supplier corruption traps without repair.
44    pub fn group_sum<K: Value, R: Value>(self) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
45        let (plan, reducer) = self.numeric_plan::<R>(Some(K::definition()), Operation::Sum)?;
46        self.group_values(&plan, reducer)
47    }
48
49    /// Average an integer or Decimal field (including a scalar newtype) into a single-field Decimal record.
50    /// Preserve the field name and optionality. A primitive Decimal selects scale 0–28;
51    /// a Decimal newtype result preserves the exact input newtype and its scale.
52    /// Ignore absent operands, returning `None` for empty/all-absent input.
53    /// Divide the exact total by the present count once, rounding to nearest with
54    /// ties to even at the result scale. No floating-point conversion or scale fallback.
55    /// # Errors
56    /// Refuses nonnumeric inputs, non-Decimal results, changed optionality, cursors,
57    /// DISTINCT, input ordering and group modifiers. Work exhaustion returns `Limit`;
58    /// an unrepresentable rounded coefficient returns `ArithmeticOverflow`.
59    /// Output-byte bounds match [`Self::sum`]. No partial average is returned.
60    /// # Panics
61    /// Supplier corruption traps without repair.
62    pub fn avg<R: Value>(self) -> Result<Aggregate<Option<R>>, Error> {
63        let (plan, reducer) = self.numeric_plan::<R>(None, Operation::Average)?;
64        self.scalar_value(&plan, reducer)
65    }
66
67    /// Average per group using [`Self::avg`]'s Decimal scale and rounding contract.
68    /// Finalize all groups before filtering, ordering and output limits; these
69    /// operations compare the rounded Decimal results. Retain all-absent groups.
70    /// # Errors
71    /// Scalar average admission/range errors and grouped work/state/output bounds
72    /// apply. Overflow in an excluded group still refuses the whole query.
73    /// # Panics
74    /// Supplier corruption traps without repair.
75    pub fn group_avg<K: Value, R: Value>(self) -> Result<Aggregate<Vec<GroupValue<K, R>>>, Error> {
76        let (plan, reducer) = self.numeric_plan::<R>(Some(K::definition()), Operation::Average)?;
77        self.group_values(&plan, reducer)
78    }
79
80    // One admission path for synchronous, grouped and retained numeric terminals.
81    pub(super) fn numeric_plan<R: Value>(
82        &self,
83        group: Option<&TypeSchema>,
84        operation: Operation,
85    ) -> Result<(Plan<'static>, Reducer), Error> {
86        let mut plan = self.aggregate_plan(group, group.is_some())?;
87        let state = NumericAggregate::admit(E::SCHEMA, R::definition(), operation)?;
88        plan.selected |= 1 << state.position;
89        Ok((plan, Reducer::Numeric(state)))
90    }
91}
92
93#[derive(Clone, Copy)]
94#[repr(u8)]
95pub(super) enum Operation {
96    // Stable job-binding tags; preserve the original sum identity.
97    Sum = 1,
98    Average = 2,
99}
100
101#[derive(Clone)]
102pub(in crate::store::query) struct NumericAggregate {
103    pub(super) position: usize,
104    source_scale: u32,
105    output: ValueSchema,
106    total: Total,
107    count: u64,
108    pub(super) operation: Operation,
109}
110#[derive(Clone)]
111enum Total {
112    Signed(I256),
113    Unsigned(U256),
114}
115impl NumericAggregate {
116    fn admit(
117        entity: &EntitySchema,
118        output: &TypeSchema,
119        operation: Operation,
120    ) -> Result<Self, Error> {
121        let TypeBody::Record([result]) = output.body else {
122            return Err(Error::InvalidQuery);
123        };
124        let (position, source) = entity
125            .fields
126            .iter()
127            .enumerate()
128            .find(|(_, field)| field.name == result.name)
129            .ok_or(Error::InvalidQuery)?;
130        if source.optional != result.optional {
131            return Err(Error::InvalidQuery);
132        }
133        let input = crate::key::operand_type(source.value);
134        // A named result keeps the exact stored field contract, as in a projection.
135        if matches!(result.value, FieldType::Named(_)) {
136            super::admit_projection(entity, output)?;
137        }
138        let result_type = crate::key::operand_type(result.value);
139        let source_scale = match input {
140            FieldType::Decimal { scale } => scale,
141            _ => 0,
142        };
143        let signed = if matches!(operation, Operation::Average) {
144            if !matches!(result_type, FieldType::Decimal { scale: 0..=28 }) {
145                return Err(Error::InvalidQuery);
146            }
147            match input {
148                FieldType::Decimal { .. } => true,
149                value => integer(value).ok_or(Error::InvalidQuery)?.0,
150            }
151        } else {
152            match (input, result_type) {
153                (FieldType::Decimal { scale: source }, FieldType::Decimal { scale: result })
154                    if source == result =>
155                {
156                    true
157                }
158                (source, result) => {
159                    let (signed, bits) = integer(source).ok_or(Error::InvalidQuery)?;
160                    let (result_signed, result_bits) =
161                        integer(result).ok_or(Error::InvalidQuery)?;
162                    if signed != result_signed || bits > result_bits {
163                        return Err(Error::InvalidQuery);
164                    }
165                    signed
166                }
167            }
168        };
169        Ok(Self {
170            position,
171            source_scale,
172            output: ValueSchema {
173                value: result.value,
174                optional: result.optional,
175            },
176            total: if signed {
177                Total::Signed(I256::ZERO)
178            } else {
179                Total::Unsigned(U256::ZERO)
180            },
181            count: 0,
182            operation,
183        })
184    }
185
186    pub(super) fn push(&mut self, values: &[IndexValue<'_>]) -> Result<(), Error> {
187        let value = values[self.position];
188        if value == IndexValue::Absent {
189            return Ok(());
190        }
191        match &mut self.total {
192            Total::Signed(total) => {
193                let value = match value {
194                    IndexValue::Int8(n) => i128::from(n),
195                    IndexValue::Int16(n) => i128::from(n),
196                    IndexValue::Int32(n) => i128::from(n),
197                    IndexValue::Int64(n) => i128::from(n),
198                    IndexValue::Int128(n) => n,
199                    IndexValue::Decimal(n) => n
200                        .coefficient_at_scale(self.source_scale)
201                        .ok_or(Error::Corrupt)?,
202                    _ => return Err(Error::Corrupt),
203                };
204                // Both synchronous and retained scans bound input counts; sums
205                // remain checked independently of that resource proof.
206                *total = total
207                    .checked_add(I256::from(value))
208                    .ok_or(Error::ArithmeticOverflow)?;
209            }
210            Total::Unsigned(total) => {
211                let value = match value {
212                    IndexValue::Nat8(n) => U256::from(n),
213                    IndexValue::Nat16(n) => U256::from(n),
214                    IndexValue::Nat32(n) => U256::from(n),
215                    IndexValue::Nat64(n) => U256::from(n),
216                    IndexValue::Nat128(n) => U256::from(n),
217                    IndexValue::U256(n) => n,
218                    _ => return Err(Error::Corrupt),
219                };
220                *total = total.checked_add(value).ok_or(Error::ArithmeticOverflow)?;
221            }
222        }
223        self.count = self.count.checked_add(1).ok_or(Error::ArithmeticOverflow)?;
224        Ok(())
225    }
226
227    // The job binding supplies admitted type/scale/operation metadata. Store only
228    // the exact accumulator and presence count, never a second schema or value AST.
229    pub(super) fn checkpoint(&self) -> (u64, [u8; 32]) {
230        (
231            self.count,
232            match self.total {
233                Total::Signed(n) => n.to_be_bytes(),
234                Total::Unsigned(n) => n.to_be_bytes(),
235            },
236        )
237    }
238
239    pub(super) fn restore(&mut self, count: u64, total: [u8; 32]) {
240        self.count = count;
241        self.total = match self.total {
242            Total::Signed(_) => Total::Signed(I256::from_be_bytes(total)),
243            Total::Unsigned(_) => Total::Unsigned(U256::from_be_bytes(total)),
244        };
245    }
246
247    pub(super) fn retained_bytes(&self) -> usize {
248        // Total payload plus the average's denominator. Fixed metadata remains
249        // bounded by the group cap, as for count/extrema reducers.
250        32 + if matches!(self.operation, Operation::Average) {
251            8
252        } else {
253            0
254        }
255    }
256
257    pub(super) fn output(&self) -> ValueSchema {
258        self.output
259    }
260
261    pub(super) fn finish(mut self) -> Result<Completed, Error> {
262        if self.count == 0 {
263            return Ok(Completed::Value(None));
264        }
265        let result_type = crate::key::operand_type(self.output.value);
266        if matches!(self.operation, Operation::Average) {
267            let FieldType::Decimal { scale } = result_type else {
268                return Err(Error::Corrupt);
269            };
270            let numerator = match self.total {
271                Total::Signed(n) => n,
272                // A nonnegative integer total this large cannot produce a Decimal
273                // coefficient fitting i128 even after division by the retained
274                // job's maximum one million inputs (synchronous scans use 512).
275                Total::Unsigned(n) => n.try_into().map_err(|_| Error::ArithmeticOverflow)?,
276            };
277            self.total = Total::Signed(rounded_average(
278                numerator,
279                self.count,
280                self.source_scale,
281                scale,
282            )?);
283        }
284        let mut output = Encoder::new();
285        let mut key = Vec::new();
286        if self.output.optional {
287            output.boolean(true)?;
288        }
289        // The ordinary owned codec supplies result bytes; checked conversion occurs
290        // only after complete accumulation, never once per input or work chunk.
291        macro_rules! encode {
292            ($method:ident, $variant:ident, $value:expr) => {{
293                let value = $value.try_into().map_err(|_| Error::ArithmeticOverflow)?;
294                output.$method(value)?;
295                IndexValue::$variant(value).append_component(self.output.optional, &mut key);
296            }};
297        }
298        match (self.total, result_type) {
299            (Total::Signed(n), FieldType::Int8) => encode!(int8, Int8, n),
300            (Total::Signed(n), FieldType::Int16) => encode!(int16, Int16, n),
301            (Total::Signed(n), FieldType::Int32) => encode!(int32, Int32, n),
302            (Total::Signed(n), FieldType::Int64) => encode!(int64, Int64, n),
303            (Total::Signed(n), FieldType::Int128) => encode!(int128, Int128, n),
304            (Total::Signed(n), FieldType::Decimal { scale }) => {
305                let coefficient = n.try_into().map_err(|_| Error::ArithmeticOverflow)?;
306                let value = Decimal::try_new(coefficient, scale).ok_or(Error::Corrupt)?;
307                output.decimal(value, scale)?;
308                IndexValue::Decimal(value).append_component(self.output.optional, &mut key);
309            }
310            (Total::Unsigned(n), FieldType::Nat8) => encode!(nat8, Nat8, n),
311            (Total::Unsigned(n), FieldType::Nat16) => encode!(nat16, Nat16, n),
312            (Total::Unsigned(n), FieldType::Nat32) => encode!(nat32, Nat32, n),
313            (Total::Unsigned(n), FieldType::Nat64) => encode!(nat64, Nat64, n),
314            (Total::Unsigned(n), FieldType::Nat128) => encode!(nat128, Nat128, n),
315            (Total::Unsigned(n), FieldType::U256) => {
316                output.u256(n)?;
317                IndexValue::U256(n).append_component(self.output.optional, &mut key);
318            }
319            _ => return Err(Error::Corrupt),
320        }
321        Ok(Completed::Value(Some((key, output.finish()))))
322    }
323}
324
325fn rounded_average(
326    total: I256,
327    count: u64,
328    source_scale: u32,
329    result_scale: u32,
330) -> Result<I256, Error> {
331    // One million signed 128-bit inputs plus 28 decimal scale digits fit I256.
332    // For unsigned totals, a scale-up overflow cannot hide a fitting i128 result:
333    // division by at most one million cannot bring that magnitude into range.
334    // The scale-down denominator and twice-remainder also fit comfortably.
335    let factor = I256::from(10_i128.pow(source_scale.abs_diff(result_scale)));
336    let (numerator, denominator) = if result_scale >= source_scale {
337        (
338            total.checked_mul(factor).ok_or(Error::ArithmeticOverflow)?,
339            I256::from(count),
340        )
341    } else {
342        (total, I256::from(count) * factor)
343    };
344    let quotient = numerator / denominator;
345    let twice_remainder = (numerator % denominator).abs() * 2;
346    let round = twice_remainder > denominator
347        || (twice_remainder == denominator && quotient % 2 != I256::ZERO);
348    Ok(if round {
349        quotient
350            + if numerator < I256::ZERO {
351                I256::MINUS_ONE
352            } else {
353                I256::ONE
354            }
355    } else {
356        quotient
357    })
358}
359
360fn integer(value: FieldType) -> Option<(bool, u16)> {
361    Some(match value {
362        FieldType::Nat8 => (false, 8),
363        FieldType::Int8 => (true, 8),
364        FieldType::Nat16 => (false, 16),
365        FieldType::Int16 => (true, 16),
366        FieldType::Nat32 => (false, 32),
367        FieldType::Int32 => (true, 32),
368        FieldType::Nat64 => (false, 64),
369        FieldType::Int64 => (true, 64),
370        FieldType::Nat128 => (false, 128),
371        FieldType::Int128 => (true, 128),
372        FieldType::U256 => (false, 256),
373        _ => return None,
374    })
375}