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