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::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#[derive(Clone, Debug, PartialEq, Eq)]
23pub struct JobHandle {
24 incarnation: [u8; 16],
25 slot: u8,
26 generation: u64,
27}
28impl JobHandle {
29 #[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 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#[derive(Debug, PartialEq, Eq)]
59pub enum JobOutcome<T> {
60 Running,
62 Complete(T),
64 Invalidated,
66 Expired,
68}
69#[derive(Debug)]
71pub struct JobStep<T> {
72 pub sequence: u64,
74 pub source_revision: u64,
76 pub examined: u64,
78 pub input_bytes: u64,
80 pub output_bytes: usize,
82 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 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 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 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 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 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 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 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 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 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 hash.update(b"ic-db:scalar-job:v1\0");
395 hash.update(plan.binding);
396 match reducer {
397 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 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#[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}