Skip to main content

ic_db/store/query/aggregate/jobs/
mod.rs

1//! Retained aggregates: exact input revision, atomic progress, explicit retry.
2mod checkpoint;
3mod distinct;
4mod extrema;
5mod grouped;
6pub(super) mod pages;
7mod storage;
8pub use pages::{GroupCursor, GroupPage};
9pub use storage::AggregateJobs;
10
11use super::{
12    super::{Database, Plan, Query, QueryCursor, Request, execute_inner},
13    Accumulator, Reducer, decode_record,
14    numeric::Operation,
15};
16use crate::{Entity, EntitySchema, Error, Timestamp, Value};
17use ic_storage::Memory;
18use sha2::{Digest, Sha256};
19use storage::Record;
20
21const MAX_CANDIDATES: u64 = 1_000_000;
22const MAX_LIFETIME_MS: i64 = 3_600_000;
23
24/// Opaque retained-job identity. The host must check caller authorization separately.
25#[derive(Clone, Debug, PartialEq, Eq)]
26pub struct JobHandle {
27    incarnation: [u8; 16],
28    slot: u8,
29    generation: u64,
30}
31impl JobHandle {
32    /// Encode an exact, bounded transport handle; no query or accumulator travels in it.
33    #[must_use]
34    pub fn to_bytes(&self) -> Vec<u8> {
35        let mut bytes = vec![1, self.slot];
36        bytes.extend(self.incarnation);
37        bytes.extend(self.generation.to_le_bytes());
38        bytes
39    }
40
41    /// Decode framing; the job store also validates incarnation and slot generation.
42    /// # Errors
43    /// Refuses unsupported, malformed, zero or oversized handles.
44    pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
45        if bytes.len() != 26 || bytes[0] != 1 || !(1..=storage::SLOTS).contains(&bytes[1]) {
46            return Err(Error::InvalidJob);
47        }
48        let incarnation = bytes[2..18].try_into().map_err(|_| Error::InvalidJob)?;
49        let generation = u64::from_le_bytes(bytes[18..].try_into().map_err(|_| Error::InvalidJob)?);
50        if incarnation == [0; 16] || generation == 0 {
51            return Err(Error::InvalidJob);
52        }
53        Ok(Self {
54            incarnation,
55            slot: bytes[1],
56            generation,
57        })
58    }
59}
60
61/// Only Complete contains a result. Running never exposes a prefix as an exact total.
62#[derive(Debug, PartialEq, Eq)]
63pub enum JobOutcome<T> {
64    /// More input remains, or exhaustion has not yet been observed.
65    Running,
66    /// Exact result for the captured source revision, retained until expiry/cancellation.
67    Complete(T),
68    /// The source entity changed before completion. Start a new job explicitly.
69    Invalidated,
70    /// The host-captured time reached the fixed expiry. Cleanup is explicit.
71    Expired,
72}
73/// Saved progress. Older sequences do not rescan; revision and expiry checks still apply.
74#[derive(Debug)]
75pub struct JobStep<T> {
76    /// Supply this sequence on the next advance. Newly created jobs start at zero.
77    pub sequence: u64,
78    /// Entity revision captured at creation, including for completed historical results.
79    pub source_revision: u64,
80    /// Cumulative examined primary/index candidates, including residual nonmatches.
81    pub examined: u64,
82    /// Cumulative source row/key bytes, excluding supplier traversal/allocator overhead.
83    pub input_bytes: u64,
84    /// Encoded returned result/page size; zero while no result is available.
85    pub output_bytes: usize,
86    /// Explicit progress, completion, invalidation or expiry.
87    pub outcome: JobOutcome<T>,
88}
89
90impl JobStep<()> {
91    // Conversion and output refusal happen before saving the prepared checkpoint.
92    // A refused result must leave the previous checkpoint available for retry.
93    fn finish_and_save<T, M: Memory>(
94        self,
95        jobs: &mut AggregateJobs<M>,
96        handle: &JobHandle,
97        record: &Record,
98        limit: usize,
99        finish: impl FnOnce() -> Result<(T, usize), Error>,
100    ) -> Result<JobStep<T>, Error> {
101        let (outcome, output_bytes) = match self.outcome {
102            JobOutcome::Running => (JobOutcome::Running, 0),
103            JobOutcome::Invalidated => (JobOutcome::Invalidated, 0),
104            JobOutcome::Expired => (JobOutcome::Expired, 0),
105            JobOutcome::Complete(()) => {
106                let (value, bytes) = finish()?;
107                if bytes > limit {
108                    return Err(Error::RowTooLarge);
109                }
110                (JobOutcome::Complete(value), bytes)
111            }
112        };
113        jobs.save(handle, record)?;
114        Ok(JobStep {
115            sequence: self.sequence,
116            source_revision: self.source_revision,
117            examined: self.examined,
118            input_bytes: self.input_bytes,
119            output_bytes,
120            outcome,
121        })
122    }
123}
124
125impl<E: Entity, M: Memory> Query<'_, E, M> {
126    /// Retain an exact count job without scanning input. Expiry must be after the
127    /// host-captured `now` and at most one hour later. No write freeze is acquired.
128    /// Reconstruct this fluent query on every advance; predicates/access path bind
129    /// the job, while the per-call work limit may change. Limit never truncates input.
130    /// # Errors
131    /// Ordinary count admission, invalid expiry, or all 16 retained slots occupied.
132    /// # Panics
133    /// Supplier mutation failures trap the enclosing message.
134    pub fn start_count(
135        self,
136        jobs: &mut AggregateJobs<M>,
137        now: Timestamp,
138        expires: Timestamp,
139    ) -> Result<JobHandle, Error> {
140        self.start_count_job(jobs, now, expires, None)
141    }
142
143    /// Retain the count of present values in a named top-level field, of any stored
144    /// type. Empty values count; absent values do not. The field binds the job,
145    /// even for a required field. Uses `start_count`'s limits and expiry contract.
146    /// # Errors
147    /// Refuses unknown fields and ordinary count-job admission failures.
148    /// # Panics
149    /// Supplier mutation failures trap the enclosing message.
150    pub fn start_count_field(
151        self,
152        field: &str,
153        jobs: &mut AggregateJobs<M>,
154        now: Timestamp,
155        expires: Timestamp,
156    ) -> Result<JobHandle, Error> {
157        self.start_count_job(jobs, now, expires, Some(field))
158    }
159
160    fn start_count_job(
161        self,
162        jobs: &mut AggregateJobs<M>,
163        now: Timestamp,
164        expires: Timestamp,
165        field: Option<&str>,
166    ) -> Result<JobHandle, Error> {
167        let plan = self.aggregate_plan(None, false)?;
168        let mut reducer = self.count_reducer(field)?;
169        if self.request.bytes < 8 {
170            return Err(Error::RowTooLarge);
171        }
172        start(
173            jobs,
174            field_binding(binding(&plan, &reducer)?, field),
175            self.db.revision_by_id(E::SCHEMA.id)?,
176            now,
177            expires,
178            &Accumulator::Scalar(&mut reducer),
179        )
180    }
181
182    /// Advance count within `work_limit` (1..=512) and 64 KiB of source row/key
183    /// bytes. Each job admits at most one million examined candidates. A budget
184    /// boundary returns Running; it never changes the mathematical input set.
185    /// Supply zero first, then the last returned sequence. An older sequence only
186    /// reads saved progress; a future sequence refuses. Source changes invalidate
187    /// running jobs, including on retries; completed results keep their boundary.
188    /// # Errors
189    /// Refuses a foreign query/handle, future sequence, backward host time, resource
190    /// bounds or corruption without changing progress. No automatic restart.
191    /// # Panics
192    /// Supplier mutation failures trap the enclosing message.
193    pub fn resume_count(
194        self,
195        jobs: &mut AggregateJobs<M>,
196        handle: &JobHandle,
197        sequence: u64,
198        now: Timestamp,
199    ) -> Result<JobStep<u64>, Error> {
200        self.resume_count_job(jobs, handle, sequence, now, None)
201    }
202
203    /// Advance the present-field count with `resume_count`'s bounds, revision,
204    /// retry and expiry rules. Empty/all-absent input completes with zero.
205    /// # Errors
206    /// Refuses changed fields, row-count jobs and ordinary count resume failures.
207    /// # Panics
208    /// Supplier mutation failures trap the enclosing message.
209    pub fn resume_count_field(
210        self,
211        field: &str,
212        jobs: &mut AggregateJobs<M>,
213        handle: &JobHandle,
214        sequence: u64,
215        now: Timestamp,
216    ) -> Result<JobStep<u64>, Error> {
217        self.resume_count_job(jobs, handle, sequence, now, Some(field))
218    }
219
220    fn resume_count_job(
221        self,
222        jobs: &mut AggregateJobs<M>,
223        handle: &JobHandle,
224        sequence: u64,
225        now: Timestamp,
226        field: Option<&str>,
227    ) -> Result<JobStep<u64>, Error> {
228        let plan = self.aggregate_plan(None, false)?;
229        let mut record = jobs.load(handle)?;
230        let mut reducer = self.count_reducer(field)?;
231        let expected = field_binding(binding(&plan, &reducer)?, field);
232        let bytes = self.request.bytes;
233        prepare(
234            self.db,
235            E::SCHEMA,
236            self.request,
237            &plan,
238            Accumulator::Scalar(&mut reducer),
239            &mut record,
240            expected,
241            sequence,
242            now,
243        )?
244        .finish_and_save(jobs, handle, &record, bytes, || {
245            Ok((reducer.finish()?.into_count()?, 8))
246        })
247    }
248
249    /// Retain an integer/Decimal sum job with synchronous sum's exact result shape.
250    /// Same expiry, capacity and query-binding contract as [`Self::start_count`].
251    /// # Errors
252    /// Refuses unsupported sum shapes, query admission, expiry or occupied capacity.
253    /// # Panics
254    /// Supplier mutation failures trap the enclosing message.
255    pub fn start_sum<R: Value>(
256        self,
257        jobs: &mut AggregateJobs<M>,
258        now: Timestamp,
259        expires: Timestamp,
260    ) -> Result<JobHandle, Error> {
261        self.start_numeric::<R>(jobs, now, expires, Operation::Sum)
262    }
263
264    /// Advance exact sum under count's work/retry/invalidation contract. Check the
265    /// declared result width only after all input completes, allowing signed
266    /// prefixes to cancel across messages. Empty/all-absent input completes as None.
267    /// # Errors
268    /// Count's refusals plus arithmetic overflow or completed-result byte limits.
269    /// A refused finalization preserves the previous checkpoint.
270    /// # Panics
271    /// Supplier mutation failures trap the enclosing message.
272    pub fn resume_sum<R: Value>(
273        self,
274        jobs: &mut AggregateJobs<M>,
275        handle: &JobHandle,
276        sequence: u64,
277        now: Timestamp,
278    ) -> Result<JobStep<Option<R>>, Error> {
279        self.resume_numeric::<R>(jobs, handle, sequence, now, Operation::Sum)
280    }
281
282    /// Retain an exact integer/Decimal average. R declares one Decimal field
283    /// with the source name and optionality, and its desired result scale (0–28).
284    /// Shares count/sum's expiry, capacity and revision contract. Average versus
285    /// sum and the result scale are bound to the job; they cannot change on resume.
286    /// # Errors
287    /// Refuses unsupported average shapes, query admission, expiry or occupied capacity.
288    /// # Panics
289    /// Supplier mutation failures trap the enclosing message.
290    pub fn start_avg<R: Value>(
291        self,
292        jobs: &mut AggregateJobs<M>,
293        now: Timestamp,
294        expires: Timestamp,
295    ) -> Result<JobHandle, Error> {
296        self.start_numeric::<R>(jobs, now, expires, Operation::Average)
297    }
298
299    /// Advance average under count's bounded work/retry/invalidation contract.
300    /// Retain the exact total and present count across steps; divide and round once
301    /// at completion to the declared Decimal scale, nearest with ties to even.
302    /// Empty/all-absent input completes as None. Never average rounded page means.
303    /// # Errors
304    /// Count's refusals plus arithmetic overflow or completed-result byte limits.
305    /// A refused finalization preserves the prior exact checkpoint; no scale fallback.
306    /// # Panics
307    /// Supplier mutation failures trap the enclosing message.
308    pub fn resume_avg<R: Value>(
309        self,
310        jobs: &mut AggregateJobs<M>,
311        handle: &JobHandle,
312        sequence: u64,
313        now: Timestamp,
314    ) -> Result<JobStep<Option<R>>, Error> {
315        self.resume_numeric::<R>(jobs, handle, sequence, now, Operation::Average)
316    }
317
318    fn start_numeric<R: Value>(
319        self,
320        jobs: &mut AggregateJobs<M>,
321        now: Timestamp,
322        expires: Timestamp,
323        operation: Operation,
324    ) -> Result<JobHandle, Error> {
325        let (plan, mut reducer) = self.numeric_plan::<R>(None, operation)?;
326        start(
327            jobs,
328            binding(&plan, &reducer)?,
329            self.db.revision_by_id(E::SCHEMA.id)?,
330            now,
331            expires,
332            &Accumulator::Scalar(&mut reducer),
333        )
334    }
335
336    fn resume_numeric<R: Value>(
337        self,
338        jobs: &mut AggregateJobs<M>,
339        handle: &JobHandle,
340        sequence: u64,
341        now: Timestamp,
342        operation: Operation,
343    ) -> Result<JobStep<Option<R>>, Error> {
344        let (plan, reducer) = self.numeric_plan::<R>(None, operation)?;
345        self.resume_value(jobs, handle, sequence, now, (plan, reducer))
346    }
347
348    fn resume_value<R: Value>(
349        self,
350        jobs: &mut AggregateJobs<M>,
351        handle: &JobHandle,
352        sequence: u64,
353        now: Timestamp,
354        admitted: (Plan<'_>, Reducer),
355    ) -> Result<JobStep<Option<R>>, Error> {
356        let (plan, mut reducer) = admitted;
357        let mut record = jobs.load(handle)?;
358        let expected = binding(&plan, &reducer)?;
359        let limit = self.request.bytes;
360        prepare(
361            self.db,
362            E::SCHEMA,
363            self.request,
364            &plan,
365            Accumulator::Scalar(&mut reducer),
366            &mut record,
367            expected,
368            sequence,
369            now,
370        )?
371        .finish_and_save(jobs, handle, &record, limit, || {
372            let bytes = reducer.finish()?.into_value()?;
373            let size = bytes.as_ref().map_or(0, Vec::len);
374            let value = bytes.as_deref().map(decode_record).transpose()?;
375            Ok((value, size))
376        })
377    }
378}
379fn field_binding(binding: [u8; 32], field: Option<&str>) -> [u8; 32] {
380    let Some(field) = field else { return binding };
381    let mut hash = Sha256::new();
382    hash.update(b"ic-db:field-count-job:v1\0");
383    hash.update(binding);
384    hash.update((field.len() as u32).to_le_bytes());
385    hash.update(field.as_bytes());
386    hash.finalize().into()
387}
388
389fn binding(plan: &Plan<'_>, reducer: &Reducer) -> Result<[u8; 32], Error> {
390    let mut hash = Sha256::new();
391    // Algorithm identity is independent of the row schema. Changing checkpoint or
392    // accumulation semantics requires a new identity and explicit resume support.
393    hash.update(b"ic-db:scalar-job:v1\0");
394    hash.update(plan.binding);
395    match reducer {
396        // A field-count terminal adds its admitted field identity with field_binding.
397        Reducer::Count { .. } => hash.update([0]),
398        Reducer::Numeric(state) => {
399            hash.update([state.operation as u8, state.position as u8]);
400            let output = state.output();
401            let mut bytes = Vec::new();
402            crate::schema::encode_type(&mut bytes, output.value, output.optional, false)?;
403            hash.update(bytes);
404        }
405        // New payload identities; existing count/sum/average bindings stay stable.
406        Reducer::Extremum {
407            position, maximum, ..
408        } => {
409            hash.update([if *maximum { 4 } else { 3 }, *position as u8]);
410        }
411        _ => return Err(Error::InvalidQuery),
412    }
413    Ok(hash.finalize().into())
414}
415
416fn start<M: Memory>(
417    jobs: &mut AggregateJobs<M>,
418    binding: [u8; 32],
419    revision: u64,
420    now: Timestamp,
421    expires: Timestamp,
422    accumulator: &Accumulator<'_>,
423) -> Result<JobHandle, Error> {
424    let lifetime = expires
425        .as_millis()
426        .checked_sub(now.as_millis())
427        .ok_or(Error::Limit)?;
428    if !(1..=MAX_LIFETIME_MS).contains(&lifetime) {
429        return Err(Error::Limit);
430    }
431    let (count, state) = accumulator.checkpoint()?;
432    jobs.insert(Record {
433        generation: 0,
434        binding,
435        revision,
436        expires,
437        observed: now,
438        sequence: 0,
439        examined: 0,
440        input_bytes: 0,
441        phase: JobOutcome::Running,
442        cursor: Vec::new(),
443        count,
444        state,
445    })
446}
447
448// One shared concrete execution path. Type conversion happens before save, outside
449// this function. Preparation errors never persist a partial accumulator or cursor.
450#[expect(
451    clippy::too_many_arguments,
452    reason = "explicit admitted query and checkpoint inputs keep the shared resume boundary local"
453)]
454fn prepare<M: Memory>(
455    db: &Database<M>,
456    entity: &EntitySchema,
457    request: Request<'_>,
458    plan: &Plan<'_>,
459    mut accumulator: Accumulator<'_>,
460    record: &mut Record,
461    expected: [u8; 32],
462    sequence: u64,
463    now: Timestamp,
464) -> Result<JobStep<()>, Error> {
465    if record.binding != expected || sequence > record.sequence {
466        return Err(Error::InvalidJob);
467    }
468    if now < record.observed {
469        return Err(Error::TimestampRegression);
470    }
471    accumulator.restore(entity, record)?;
472    if now >= record.expires && !matches!(record.phase, JobOutcome::Expired) {
473        record.phase = JobOutcome::Expired;
474        record.sequence += 1;
475    } else if matches!(record.phase, JobOutcome::Running) {
476        if db.revision_by_id(entity.id)? != record.revision {
477            record.phase = JobOutcome::Invalidated;
478            record.sequence += 1;
479        } else if sequence == record.sequence {
480            let cursor = if record.cursor.is_empty() {
481                None
482            } else {
483                let cursor = QueryCursor::from_bytes(&record.cursor)?;
484                if cursor.binding != plan.binding {
485                    return Err(Error::Corrupt);
486                }
487                plan.validate_position(entity, &cursor.position)?;
488                Some(cursor)
489            };
490            let request = Request {
491                cursor: cursor.as_ref(),
492                work: request
493                    .work
494                    .min((MAX_CANDIDATES - record.examined) as usize),
495                ..request
496            };
497            let mut bytes = 0;
498            let page = execute_inner(
499                &db.map,
500                entity,
501                &request,
502                plan,
503                Some(&mut accumulator),
504                Some(&mut bytes),
505            )?;
506            record.examined += page.examined as u64;
507            record.input_bytes += bytes as u64;
508            record.cursor = page
509                .next
510                .as_ref()
511                .map_or_else(Vec::new, QueryCursor::to_bytes);
512            record.phase = if page.next.is_none() {
513                JobOutcome::Complete(())
514            } else {
515                JobOutcome::Running
516            };
517            record.sequence += 1;
518            (record.count, record.state) = accumulator.checkpoint()?;
519        }
520    }
521    record.observed = now;
522    let outcome = match record.phase {
523        JobOutcome::Running => JobOutcome::Running,
524        JobOutcome::Invalidated => JobOutcome::Invalidated,
525        JobOutcome::Expired => JobOutcome::Expired,
526        JobOutcome::Complete(()) => JobOutcome::Complete(()),
527    };
528    Ok(JobStep {
529        sequence: record.sequence,
530        source_revision: record.revision,
531        examined: record.examined,
532        input_bytes: record.input_bytes,
533        output_bytes: 0,
534        outcome,
535    })
536}