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