1mod 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#[derive(Clone, Debug, PartialEq, Eq)]
26pub struct JobHandle {
27 incarnation: [u8; 16],
28 slot: u8,
29 generation: u64,
30}
31impl JobHandle {
32 #[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 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#[derive(Debug, PartialEq, Eq)]
63pub enum JobOutcome<T> {
64 Running,
66 Complete(T),
68 Invalidated,
70 Expired,
72}
73#[derive(Debug)]
75pub struct JobStep<T> {
76 pub sequence: u64,
78 pub source_revision: u64,
80 pub examined: u64,
82 pub input_bytes: u64,
84 pub output_bytes: usize,
86 pub outcome: JobOutcome<T>,
88}
89
90impl JobStep<()> {
91 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 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 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 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 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 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 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 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 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 hash.update(b"ic-db:scalar-job:v1\0");
394 hash.update(plan.binding);
395 match reducer {
396 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 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#[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}