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}
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 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 pub fn start_count(
138 self,
139 jobs: &mut AggregateJobs<M>,
140 now: Timestamp,
141 expires: Timestamp,
142 ) -> Result<JobHandle, Error> {
143 self.start_count_job(jobs, now, expires, None)
144 }
145
146 pub fn start_count_field(
154 self,
155 field: &str,
156 jobs: &mut AggregateJobs<M>,
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<M>,
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::SCHEMA.id)?,
179 now,
180 expires,
181 vec![0; 32],
182 )
183 }
184
185 pub fn resume_count(
197 self,
198 jobs: &mut AggregateJobs<M>,
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 pub fn resume_count_field(
213 self,
214 field: &str,
215 jobs: &mut AggregateJobs<M>,
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<M>,
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 pub fn start_sum<R: Value>(
259 self,
260 jobs: &mut AggregateJobs<M>,
261 now: Timestamp,
262 expires: Timestamp,
263 ) -> Result<JobHandle, Error> {
264 self.start_numeric::<R>(jobs, now, expires, Operation::Sum)
265 }
266
267 pub fn resume_sum<R: Value>(
276 self,
277 jobs: &mut AggregateJobs<M>,
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 pub fn start_avg<R: Value>(
294 self,
295 jobs: &mut AggregateJobs<M>,
296 now: Timestamp,
297 expires: Timestamp,
298 ) -> Result<JobHandle, Error> {
299 self.start_numeric::<R>(jobs, now, expires, Operation::Average)
300 }
301
302 pub fn resume_avg<R: Value>(
312 self,
313 jobs: &mut AggregateJobs<M>,
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<M>,
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::SCHEMA.id)?,
333 now,
334 expires,
335 vec![0; 32],
336 )
337 }
338
339 fn resume_numeric<R: Value>(
340 self,
341 jobs: &mut AggregateJobs<M>,
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<M>,
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 hash.update(b"ic-db:scalar-job:v1\0");
399 hash.update(plan.binding);
400 match reducer {
401 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 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#[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}