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 = entity
125            .field_position(result.name)
126            .ok_or(Error::InvalidQuery)?;
127        let source = &entity.fields[position];
128        if source.optional != result.optional {
129            return Err(Error::InvalidQuery);
130        }
131        let input = crate::key::operand_type(source.value);
132        // A named result keeps the exact stored field contract, as in a projection.
133        if matches!(result.value, FieldType::Named(_)) {
134            super::admit_projection(entity, output)?;
135        }
136        let result_type = crate::key::operand_type(result.value);
137        let source_scale = match input {
138            FieldType::Decimal { scale } => scale,
139            _ => 0,
140        };
141        let signed = if matches!(operation, Operation::Average) {
142            if !matches!(result_type, FieldType::Decimal { scale: 0..=28 }) {
143                return Err(Error::InvalidQuery);
144            }
145            match input {
146                FieldType::Decimal { .. } => true,
147                value => integer(value).ok_or(Error::InvalidQuery)?.0,
148            }
149        } else {
150            match (input, result_type) {
151                (FieldType::Decimal { scale: source }, FieldType::Decimal { scale: result })
152                    if source == result =>
153                {
154                    true
155                }
156                (source, result) => {
157                    let (signed, bits) = integer(source).ok_or(Error::InvalidQuery)?;
158                    let (result_signed, result_bits) =
159                        integer(result).ok_or(Error::InvalidQuery)?;
160                    if signed != result_signed || bits > result_bits {
161                        return Err(Error::InvalidQuery);
162                    }
163                    signed
164                }
165            }
166        };
167        Ok(Self {
168            position,
169            source_scale,
170            output: ValueSchema {
171                value: result.value,
172                optional: result.optional,
173            },
174            total: if signed {
175                Total::Signed(I256::ZERO)
176            } else {
177                Total::Unsigned(U256::ZERO)
178            },
179            count: 0,
180            operation,
181        })
182    }
183
184    pub(super) fn push(&mut self, values: &[IndexValue<'_>]) -> Result<(), Error> {
185        let value = values[self.position];
186        if value == IndexValue::Absent {
187            return Ok(());
188        }
189        match &mut self.total {
190            Total::Signed(total) => {
191                let value = match value {
192                    IndexValue::Int8(n) => i128::from(n),
193                    IndexValue::Int16(n) => i128::from(n),
194                    IndexValue::Int32(n) => i128::from(n),
195                    IndexValue::Int64(n) => i128::from(n),
196                    IndexValue::Int128(n) => n,
197                    IndexValue::Decimal(n) => n
198                        .coefficient_at_scale(self.source_scale)
199                        .ok_or(Error::Corrupt)?,
200                    _ => return Err(Error::Corrupt),
201                };
202                // Both synchronous and retained scans bound input counts; sums
203                // remain checked independently of that resource proof.
204                *total = total
205                    .checked_add(I256::from(value))
206                    .ok_or(Error::ArithmeticOverflow)?;
207            }
208            Total::Unsigned(total) => {
209                let value = match value {
210                    IndexValue::Nat8(n) => U256::from(n),
211                    IndexValue::Nat16(n) => U256::from(n),
212                    IndexValue::Nat32(n) => U256::from(n),
213                    IndexValue::Nat64(n) => U256::from(n),
214                    IndexValue::Nat128(n) => U256::from(n),
215                    IndexValue::U256(n) => n,
216                    _ => return Err(Error::Corrupt),
217                };
218                *total = total.checked_add(value).ok_or(Error::ArithmeticOverflow)?;
219            }
220        }
221        self.count = self.count.checked_add(1).ok_or(Error::ArithmeticOverflow)?;
222        Ok(())
223    }
224
225    // The job binding supplies admitted type/scale/operation metadata. Store only
226    // the exact accumulator and presence count, never a second schema or value AST.
227    pub(super) fn checkpoint(&self) -> (u64, [u8; 32]) {
228        (
229            self.count,
230            match self.total {
231                Total::Signed(n) => n.to_be_bytes(),
232                Total::Unsigned(n) => n.to_be_bytes(),
233            },
234        )
235    }
236
237    pub(super) fn restore(&mut self, count: u64, total: [u8; 32]) {
238        self.count = count;
239        self.total = match self.total {
240            Total::Signed(_) => Total::Signed(I256::from_be_bytes(total)),
241            Total::Unsigned(_) => Total::Unsigned(U256::from_be_bytes(total)),
242        };
243    }
244
245    pub(super) fn retained_bytes(&self) -> usize {
246        // Total payload plus the average's denominator. Fixed metadata remains
247        // bounded by the group cap, as for count/extrema reducers.
248        32 + if matches!(self.operation, Operation::Average) {
249            8
250        } else {
251            0
252        }
253    }
254
255    pub(super) fn output(&self) -> ValueSchema {
256        self.output
257    }
258
259    pub(super) fn finish(mut self) -> Result<Completed, Error> {
260        if self.count == 0 {
261            return Ok(Completed::Value(None));
262        }
263        let result_type = crate::key::operand_type(self.output.value);
264        if matches!(self.operation, Operation::Average) {
265            let FieldType::Decimal { scale } = result_type else {
266                return Err(Error::Corrupt);
267            };
268            let numerator = match self.total {
269                Total::Signed(n) => n,
270                // A nonnegative integer total this large cannot produce a Decimal
271                // coefficient fitting i128 even after division by the retained
272                // job's maximum one million inputs (synchronous scans use 512).
273                Total::Unsigned(n) => n.try_into().map_err(|_| Error::ArithmeticOverflow)?,
274            };
275            self.total = Total::Signed(rounded_average(
276                numerator,
277                self.count,
278                self.source_scale,
279                scale,
280            )?);
281        }
282        let mut output = Encoder::new();
283        let mut key = Vec::new();
284        if self.output.optional {
285            output.boolean(true)?;
286        }
287        // The ordinary owned codec supplies result bytes; checked conversion occurs
288        // only after complete accumulation, never once per input or work chunk.
289        macro_rules! encode {
290            ($method:ident, $variant:ident, $value:expr) => {{
291                let value = $value.try_into().map_err(|_| Error::ArithmeticOverflow)?;
292                output.$method(value)?;
293                IndexValue::$variant(value).append_component(self.output.optional, &mut key);
294            }};
295        }
296        match (self.total, result_type) {
297            (Total::Signed(n), FieldType::Int8) => encode!(int8, Int8, n),
298            (Total::Signed(n), FieldType::Int16) => encode!(int16, Int16, n),
299            (Total::Signed(n), FieldType::Int32) => encode!(int32, Int32, n),
300            (Total::Signed(n), FieldType::Int64) => encode!(int64, Int64, n),
301            (Total::Signed(n), FieldType::Int128) => encode!(int128, Int128, n),
302            (Total::Signed(n), FieldType::Decimal { scale }) => {
303                let coefficient = n.try_into().map_err(|_| Error::ArithmeticOverflow)?;
304                let value = Decimal::try_new(coefficient, scale).ok_or(Error::Corrupt)?;
305                output.decimal(value, scale)?;
306                IndexValue::Decimal(value).append_component(self.output.optional, &mut key);
307            }
308            (Total::Unsigned(n), FieldType::Nat8) => encode!(nat8, Nat8, n),
309            (Total::Unsigned(n), FieldType::Nat16) => encode!(nat16, Nat16, n),
310            (Total::Unsigned(n), FieldType::Nat32) => encode!(nat32, Nat32, n),
311            (Total::Unsigned(n), FieldType::Nat64) => encode!(nat64, Nat64, n),
312            (Total::Unsigned(n), FieldType::Nat128) => encode!(nat128, Nat128, n),
313            (Total::Unsigned(n), FieldType::U256) => {
314                output.u256(n)?;
315                IndexValue::U256(n).append_component(self.output.optional, &mut key);
316            }
317            _ => return Err(Error::Corrupt),
318        }
319        Ok(Completed::Value(Some((key, output.finish()))))
320    }
321}
322
323fn rounded_average(
324    total: I256,
325    count: u64,
326    source_scale: u32,
327    result_scale: u32,
328) -> Result<I256, Error> {
329    // One million signed 128-bit inputs plus 28 decimal scale digits fit I256.
330    // For unsigned totals, a scale-up overflow cannot hide a fitting i128 result:
331    // division by at most one million cannot bring that magnitude into range.
332    // The scale-down denominator and twice-remainder also fit comfortably.
333    let factor = I256::from(10_i128.pow(source_scale.abs_diff(result_scale)));
334    let (numerator, denominator) = if result_scale >= source_scale {
335        (
336            total.checked_mul(factor).ok_or(Error::ArithmeticOverflow)?,
337            I256::from(count),
338        )
339    } else {
340        (total, I256::from(count) * factor)
341    };
342    let quotient = numerator / denominator;
343    let twice_remainder = (numerator % denominator).abs() * 2;
344    let round = twice_remainder > denominator
345        || (twice_remainder == denominator && quotient % 2 != I256::ZERO);
346    Ok(if round {
347        quotient
348            + if numerator < I256::ZERO {
349                I256::MINUS_ONE
350            } else {
351                I256::ONE
352            }
353    } else {
354        quotient
355    })
356}
357
358fn integer(value: FieldType) -> Option<(bool, u16)> {
359    Some(match value {
360        FieldType::Nat8 => (false, 8),
361        FieldType::Int8 => (true, 8),
362        FieldType::Nat16 => (false, 16),
363        FieldType::Int16 => (true, 16),
364        FieldType::Nat32 => (false, 32),
365        FieldType::Int32 => (true, 32),
366        FieldType::Nat64 => (false, 64),
367        FieldType::Int64 => (true, 64),
368        FieldType::Nat128 => (false, 128),
369        FieldType::Int128 => (true, 128),
370        FieldType::U256 => (false, 256),
371        _ => return None,
372    })
373}