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