mod aggregate;
mod distinct;
mod order;
mod range;
mod sort;
pub use aggregate::jobs::{AggregateJobs, GroupCursor, GroupPage, JobHandle, JobOutcome, JobStep};
pub use aggregate::{Aggregate, GroupCount, GroupOrder, GroupValue};
use super::{Database, Map, prefix, row_key, validate_index_entry};
use crate::{
Entity, EntitySchema, Error, FieldType, IndexSchema, IndexValue, TypeBody, TypeSchema, Value,
codec::Decoder, key, primary::RowKey, types::TypeGraph,
};
use ic_storage::Memory;
use sha2::{Digest, Sha256};
use std::marker::PhantomData;
const MAX_TERMS: usize = 8;
const MAX_WORK: usize = 512;
const MAX_OUTPUT: usize = 128 * 1024;
const MAX_COMPARISON_KEY: usize = 4096;
const MAX_DISTINCT_VALUES: usize = 32;
const MAX_STATE_BYTES: usize = 128 * 1024;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum SortDirection {
Ascending,
Descending,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[repr(u8)]
pub enum Comparison {
Eq = 0,
Ne = 1,
Lt = 2,
Le = 3,
Gt = 4,
Ge = 5,
StartsWith = 6,
EndsWith = 7,
Contains = 8,
}
impl Comparison {
fn admit(self, field: FieldType, optional: bool, value: IndexValue<'_>) -> Result<(), Error> {
value.admit(field, optional)?;
let field = key::operand_type(field);
if (matches!(self, Self::StartsWith | Self::EndsWith)
&& !matches!(field, FieldType::Text { .. } | FieldType::Blob { .. }))
|| (self == Self::Contains && !matches!(field, FieldType::Text { .. }))
{
return Err(Error::InvalidQuery);
}
if value == IndexValue::Absent && !matches!(self, Self::Eq | Self::Ne) {
return Err(Error::InvalidOperand);
}
Ok(())
}
fn accepts(self, actual: Option<&[u8]>, operand: Option<&[u8]>, optional: bool) -> bool {
if actual.is_none() {
return self.accepts_absent(operand.is_none());
}
match self {
Self::Eq => actual == operand,
Self::Ne => actual != operand,
Self::StartsWith | Self::EndsWith | Self::Contains => {
fn content(key: &[u8], optional: bool) -> Option<&[u8]> {
key.get(usize::from(optional)..)?.strip_suffix(&[0, 0])
}
actual
.and_then(|key| content(key, optional))
.zip(operand.and_then(|key| content(key, optional)))
.is_some_and(|(actual, operand)| match self {
Self::StartsWith => actual.starts_with(operand),
Self::EndsWith => actual
.strip_suffix(operand)
.is_some_and(|prefix| prefix.last() != Some(&0)),
_ => memchr::memmem::find(actual, operand).is_some(),
})
}
_ if actual.is_none() || operand.is_none() => false,
Self::Lt => actual < operand,
Self::Le => actual <= operand,
Self::Gt => actual > operand,
Self::Ge => actual >= operand,
}
}
fn accepts_absent(self, other_absent: bool) -> bool {
match self {
Self::Eq => other_absent,
Self::Ne => !other_absent,
_ => false,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct QueryCursor {
binding: [u8; 32],
position: Vec<u8>,
inclusive: bool,
}
impl QueryCursor {
pub(super) const MAX_ENCODED_BYTES: usize = 34 + crate::MAX_INDEX_KEY_BYTES;
#[must_use]
pub fn to_bytes(&self) -> Vec<u8> {
let mut bytes = vec![1, u8::from(self.inclusive)];
bytes.extend(self.binding);
bytes.extend(&self.position);
bytes
}
pub fn from_bytes(bytes: &[u8]) -> Result<Self, Error> {
if !(35..=Self::MAX_ENCODED_BYTES).contains(&bytes.len()) || bytes[0] != 1 || bytes[1] > 1 {
return Err(Error::InvalidCursor);
}
Ok(Self {
binding: bytes[2..34].try_into().map_err(|_| Error::InvalidCursor)?,
position: bytes[34..].to_vec(),
inclusive: bytes[1] == 1,
})
}
}
#[derive(Debug)]
pub struct QueryPage<T> {
pub rows: Vec<T>,
pub next: Option<QueryCursor>,
pub examined: usize,
pub fetched: usize,
pub output_bytes: usize,
}
impl QueryPage<Vec<u8>> {
#[inline(never)]
pub(super) fn decode_entities<E: Entity>(self) -> Result<QueryPage<E>, Error> {
Ok(QueryPage {
rows: self
.rows
.iter()
.map(|bytes| E::decode(bytes))
.collect::<Result<_, _>>()?,
next: self.next,
examined: self.examined,
fetched: self.fetched,
output_bytes: self.output_bytes,
})
}
#[inline(never)]
fn decode_projection<R: Value>(self) -> Result<QueryPage<R>, Error> {
Ok(QueryPage {
rows: self
.rows
.iter()
.map(|bytes| {
let mut reader = Decoder::new(bytes)?;
let row = R::decode_from(&mut reader)?;
reader.finish()?;
Ok(row)
})
.collect::<Result<_, Error>>()?,
next: self.next,
examined: self.examined,
fetched: self.fetched,
output_bytes: self.output_bytes,
})
}
}
struct Predicate<'a> {
field: &'a str,
comparison: Comparison,
value: IndexValue<'a>,
or_next: bool,
}
struct Request<'a> {
groups: aggregate::GroupRequest<'a>,
predicates: Vec<Predicate<'a>>,
index: Option<(&'a str, Vec<IndexValue<'a>>)>,
order: Option<Vec<&'a str>>,
order_descending: u8,
descending: bool,
distinct: bool,
rows: usize,
work: usize,
bytes: usize,
cursor: Option<&'a QueryCursor>,
over_limit: bool,
}
impl Default for Request<'_> {
fn default() -> Self {
Self {
groups: aggregate::GroupRequest::default(),
predicates: Vec::new(),
index: None,
order: None,
order_descending: 0,
descending: false,
distinct: false,
rows: 32,
work: 128,
bytes: MAX_OUTPUT,
cursor: None,
over_limit: false,
}
}
}
impl<'a> Request<'a> {
#[inline(never)]
fn filter(&mut self, field: &'a str, comparison: Comparison, value: impl Into<IndexValue<'a>>) {
if self.predicates.len() == MAX_TERMS {
self.over_limit = true;
} else {
self.predicates.push(Predicate {
field,
comparison,
value: value.into(),
or_next: false,
});
}
}
#[inline(never)]
fn or_clause(
&mut self,
alternatives: impl ExactSizeIterator<Item = (&'a str, Comparison, IndexValue<'a>)>,
) {
let count = alternatives.len();
if count == 0 || count > MAX_TERMS - self.predicates.len() {
self.over_limit = true;
} else {
self.predicates.extend(alternatives.enumerate().map(
|(i, (field, comparison, value))| Predicate {
field,
comparison,
value,
or_next: i + 1 < count,
},
));
}
}
#[inline(never)]
fn filter_not_in(&mut self, field: &'a str, values: &[IndexValue<'a>]) {
if values.is_empty() || values.len() > MAX_TERMS - self.predicates.len() {
self.over_limit = true;
return;
}
for &value in values {
self.filter(field, Comparison::Ne, value);
}
}
#[inline(never)]
fn using_index(&mut self, name: &'a str, values: &[IndexValue<'a>]) {
if values.len() > 4 {
self.over_limit = true;
} else {
self.index = Some((name, values.to_vec()));
}
}
#[inline(never)]
fn order_by(&mut self, fields: &[&'a str]) {
self.order_descending = 0;
if fields.len() > 4 {
self.over_limit = true;
} else {
self.order = Some(fields.to_vec());
}
}
#[inline(never)]
fn order_by_each(&mut self, fields: &[(&'a str, SortDirection)]) {
if fields.len() > 4 {
self.over_limit = true;
return;
}
self.order = Some(fields.iter().map(|(name, _)| *name).collect());
self.order_descending = fields
.iter()
.enumerate()
.fold(0, |mask, (i, (_, direction))| {
mask | (u8::from(*direction == SortDirection::Descending) << i)
});
}
fn primary_descending(&self, entity: &EntitySchema) -> bool {
self.order_descending != 0
&& self.order.as_ref().is_some_and(|fields| {
fields.last() == Some(&entity.primary_key)
&& self.order_descending & (1 << (fields.len() - 1)) != 0
})
}
}
pub(super) fn source_page<M: Memory>(
map: &Map<M>,
entity: &EntitySchema,
binding: [u8; 32],
incarnation: [u8; 16],
cursor: Option<&QueryCursor>,
rows: usize,
bytes: usize,
) -> Result<QueryPage<Vec<u8>>, Error> {
let request = Request {
rows,
work: rows,
bytes,
cursor,
..Request::default()
};
let plan = Plan::admit(entity, &request, binding, incarnation, None, false)?;
execute(map, entity, &request, &plan, None)
}
pub struct Query<'a, E, M: Memory = ic_storage::DefaultMemoryImpl> {
db: &'a Database<M>,
request: Request<'a>,
entity: PhantomData<E>,
}
impl<M: Memory> Database<M> {
#[must_use]
pub fn query<E: Entity>(&self) -> Query<'_, E, M> {
Query {
db: self,
entity: PhantomData,
request: Request::default(),
}
}
}
impl<'a, E: Entity, M: Memory> Query<'a, E, M> {
#[must_use]
pub fn distinct(mut self) -> Self {
self.request.distinct = true;
self
}
#[must_use]
pub fn filter(
mut self,
field: &'a str,
comparison: Comparison,
value: impl Into<IndexValue<'a>>,
) -> Self {
self.request.filter(field, comparison, value);
self
}
#[must_use]
pub fn filter_between(
self,
field: &'a str,
lower: impl Into<IndexValue<'a>>,
upper: impl Into<IndexValue<'a>>,
) -> Self {
self.filter(field, Comparison::Ge, lower)
.filter(field, Comparison::Le, upper)
}
#[must_use]
pub fn filter_not_between(
self,
field: &'a str,
lower: impl Into<IndexValue<'a>>,
upper: impl Into<IndexValue<'a>>,
) -> Self {
self.filter_any(&[
(field, Comparison::Lt, lower.into()),
(field, Comparison::Gt, upper.into()),
])
}
#[must_use]
pub fn filter_any(mut self, alternatives: &[(&'a str, Comparison, IndexValue<'a>)]) -> Self {
self.request.or_clause(alternatives.iter().copied());
self
}
#[must_use]
pub fn filter_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
self.request.or_clause(
values
.iter()
.copied()
.map(|value| (field, Comparison::Eq, value)),
);
self
}
#[must_use]
pub fn filter_not_in(mut self, field: &'a str, values: &[IndexValue<'a>]) -> Self {
self.request.filter_not_in(field, values);
self
}
#[must_use]
pub fn using_index(mut self, name: &'a str, values: &[IndexValue<'a>]) -> Self {
self.request.using_index(name, values);
self
}
#[must_use]
pub fn order_by(mut self, fields: &[&'a str]) -> Self {
self.request.order_by(fields);
self
}
#[must_use]
pub fn order_by_each(mut self, fields: &[(&'a str, SortDirection)]) -> Self {
self.request.order_by_each(fields);
self
}
#[must_use]
pub fn descending(mut self) -> Self {
self.request.descending = true;
self
}
#[must_use]
pub fn limit(mut self, rows: usize) -> Self {
self.request.rows = rows;
self
}
#[must_use]
pub fn work_limit(mut self, candidates: usize) -> Self {
self.request.work = candidates;
self
}
#[must_use]
pub fn byte_limit(mut self, bytes: usize) -> Self {
self.request.bytes = bytes;
self
}
#[must_use]
pub fn after(mut self, cursor: &'a QueryCursor) -> Self {
self.request.cursor = Some(cursor);
self
}
pub fn fetch(self) -> Result<QueryPage<E>, Error> {
fetch_rows(self.db, E::SCHEMA, self.request, None)?.decode_entities()
}
pub fn fetch_as<R: Value>(self) -> Result<QueryPage<R>, Error> {
let raw = fetch_rows(self.db, E::SCHEMA, self.request, Some(R::definition()))?;
raw.decode_projection()
}
}
fn admit_projection(entity: &EntitySchema, output: &TypeSchema) -> Result<u16, Error> {
let TypeBody::Record(fields) = &output.body else {
return Err(Error::InvalidQuery);
};
if fields.is_empty()
|| fields.len() > crate::schema::MAX_FIELDS
|| fields.windows(2).any(|w| w[0].name >= w[1].name)
{
return Err(Error::InvalidQuery);
}
let mut source = TypeGraph::default();
let mut target = TypeGraph::default();
let mut mask = 0;
for field in *fields {
let position = entity
.fields
.iter()
.position(|f| f.name == field.name)
.ok_or(Error::InvalidQuery)?;
let stored = &entity.fields[position];
if stored.value != field.value || stored.optional != field.optional {
return Err(Error::InvalidQuery);
}
source
.include(stored.value)
.map_err(|_| Error::InvalidQuery)?;
target
.include(field.value)
.map_err(|_| Error::InvalidQuery)?;
mask |= 1 << position;
}
if !source.contains(&target) {
return Err(Error::InvalidQuery);
}
Ok(mask)
}
struct Term {
position: usize,
comparison: Comparison,
operand: Vec<u8>,
absent: bool,
or_next: bool,
}
fn admit_ordered_fields(entity: &EntitySchema, mask: u16) -> Result<(), Error> {
for (i, field) in entity.fields.iter().enumerate() {
if mask & (1 << i) != 0 && !key::supports(field.value) {
return Err(Error::InvalidQuery);
}
}
Ok(())
}
fn comparison_key(
entity: &EntitySchema,
mask: u16,
values: &[IndexValue<'_>],
) -> Result<Vec<u8>, Error> {
let mut key = Vec::new();
for (i, field) in entity.fields.iter().enumerate() {
if mask & (1 << i) != 0 {
values[i].append_component(field.optional, &mut key);
if key.len() > MAX_COMPARISON_KEY {
return Err(Error::Limit);
}
}
}
Ok(key)
}
fn admit_output(size: usize, limit: usize, used: &mut usize) -> Result<(), Error> {
if size > limit {
return Err(Error::RowTooLarge);
}
if size > limit - *used {
return Err(Error::Limit);
}
*used += size;
Ok(())
}
fn projection_size(spans: &[(u16, u16)], mask: u16) -> usize {
spans
.iter()
.enumerate()
.filter(|(i, _)| mask & (1 << i) != 0)
.map(|(_, (start, end))| usize::from(end - start))
.sum()
}
fn copy_projection(bytes: &[u8], spans: &[(u16, u16)], mask: u16, size: usize) -> Vec<u8> {
let mut output = Vec::with_capacity(size);
for (i, &(start, end)) in spans.iter().enumerate() {
if mask & (1 << i) != 0 {
output.extend_from_slice(&bytes[usize::from(start)..usize::from(end)]);
}
}
output
}
struct Plan<'a> {
index: Option<&'a IndexSchema>,
prefix: Vec<u8>,
fixed_components: usize,
terms: Vec<Term>,
selected: u16,
presence: u16,
binding: [u8; 32],
projection: Option<u16>,
distinct: distinct::Strategy,
sort: Option<Vec<(usize, bool)>>,
descending: bool,
}
impl<'a> Plan<'a> {
fn admit(
entity: &'a EntitySchema,
request: &Request<'_>,
schema: [u8; 32],
incarnation: [u8; 16],
projection: Option<&TypeSchema>,
group_output: bool,
) -> Result<Self, Error> {
if request.over_limit
|| !(1..=32).contains(&request.rows)
|| !(1..=MAX_WORK).contains(&request.work)
|| !(1..=MAX_OUTPUT).contains(&request.bytes)
{
return Err(Error::Limit);
}
if !group_output && !request.groups.is_empty() {
return Err(Error::InvalidQuery);
}
for value in request
.predicates
.iter()
.map(|p| &p.value)
.chain(request.index.iter().flat_map(|(_, values)| values.iter()))
{
if match value {
IndexValue::Text(text) => text.len() > crate::codec::MAX_ROW_BYTES,
IndexValue::Blob(bytes) => bytes.len() > crate::codec::MAX_ROW_BYTES,
_ => false,
} {
return Err(Error::Limit);
}
}
let primary = entity
.fields
.iter()
.position(|f| f.name == entity.primary_key)
.ok_or(Error::InvalidQuery)?;
let mut plan = Self {
index: None,
prefix: prefix(2, entity.id),
fixed_components: 0,
terms: Vec::new(),
selected: 1 << primary,
presence: 0,
binding: [0; 32],
projection: projection
.map(|output| admit_projection(entity, output))
.transpose()?,
distinct: distinct::Strategy::Identity,
sort: None,
descending: request.descending ^ request.primary_descending(entity),
};
for predicate in &request.predicates {
let position = entity
.fields
.iter()
.position(|f| f.name == predicate.field)
.ok_or(Error::InvalidQuery)?;
let field = &entity.fields[position];
let ordered = key::supports(field.value);
if !ordered
&& !(predicate.value == IndexValue::Absent
&& matches!(predicate.comparison, Comparison::Eq | Comparison::Ne))
{
return Err(Error::InvalidQuery);
}
predicate
.comparison
.admit(field.value, field.optional, predicate.value)?;
let absent = predicate.value == IndexValue::Absent;
let mut operand = Vec::new();
predicate
.value
.append_component(field.optional, &mut operand);
plan.terms.push(Term {
position,
comparison: predicate.comparison,
operand,
absent,
or_next: predicate.or_next,
});
if ordered {
plan.selected |= 1 << position;
} else {
plan.presence |= 1 << position;
}
}
match order::select(entity, request)? {
order::Path::Primary => {}
order::Path::Index(path) => {
plan.index = Some(path.index);
plan.prefix = path.prefix;
plan.selected |= entity.key_fields();
plan.fixed_components = path.fixed;
}
order::Path::Sort(fields) => {
for &(position, _) in &fields {
plan.selected |= 1 << position;
}
plan.sort = Some(fields);
}
}
if request.distinct {
plan.distinct = distinct::admit(
entity,
request,
plan.projection,
plan.index,
plan.fixed_components,
plan.sort.is_some(),
)?;
if plan.distinct == distinct::Strategy::Complete {
plan.selected |= plan.projection.ok_or(Error::InvalidQuery)?;
}
}
let mut hash = Sha256::new();
hash.update(b"ic-db:query:v1\0");
hash.update(schema);
hash.update(incarnation);
hash.update([u8::from(request.descending)]);
hash.update((plan.prefix.len() as u32).to_le_bytes());
hash.update(&plan.prefix);
for term in &plan.terms {
hash.update([term.position as u8, term.comparison as u8]);
hash.update((term.operand.len() as u32).to_le_bytes());
hash.update(&term.operand);
}
let clauses = plan
.terms
.iter()
.enumerate()
.fold(0_u8, |mask, (i, term)| mask | (u8::from(term.or_next) << i));
if clauses != 0 {
hash.update(b"or-clauses\0");
hash.update([clauses]);
}
if let Some(order) = &request.order {
hash.update(b"order\0");
hash.update([order.len() as u8]);
for name in order {
hash.update([entity
.fields
.iter()
.position(|f| f.name == *name)
.ok_or(Error::InvalidQuery)? as u8]);
}
}
if request.order_descending != 0 {
hash.update(b"order-directions\0");
hash.update([request.order_descending]);
}
if let Some(mask) = plan.projection {
hash.update(b"projection\0");
hash.update(mask.to_le_bytes());
}
if request.distinct {
hash.update(b"distinct\0");
}
plan.binding = hash.finalize().into();
if let Some(cursor) = request.cursor {
if cursor.binding != plan.binding {
return Err(Error::InvalidCursor);
}
plan.validate_position(entity, &cursor.position)
.map_err(|_| Error::InvalidCursor)?;
}
Ok(plan)
}
fn validate_position(&self, entity: &EntitySchema, bytes: &[u8]) -> Result<(), Error> {
if bytes.len() > crate::MAX_INDEX_KEY_BYTES || !bytes.starts_with(&self.prefix) {
return Err(Error::InvalidCursor);
}
if let Some(index) = self.index {
let mut remaining = bytes.get(9..).ok_or(Error::InvalidCursor)?;
for name in index.fields {
consume_index_component(entity, index, name, &mut remaining)?;
}
if !index.unique {
key::consume(&mut remaining, entity.key_type()?)?;
}
if !remaining.is_empty() {
return Err(Error::InvalidCursor);
}
} else {
RowKey::decode(
bytes.get(5..).ok_or(Error::InvalidCursor)?,
entity.key_type()?,
)?;
}
Ok(())
}
fn cursor(&self, position: &[u8], inclusive: bool) -> QueryCursor {
QueryCursor {
binding: self.binding,
position: position.to_vec(),
inclusive,
}
}
}
fn consume_index_component(
entity: &EntitySchema,
index: &IndexSchema,
name: &str,
remaining: &mut &[u8],
) -> Result<(), Error> {
let field = entity
.fields
.iter()
.find(|f| f.name == name)
.ok_or(Error::InvalidQuery)?;
if field.optional {
let (&presence, rest) = remaining.split_first().ok_or(Error::InvalidCursor)?;
*remaining = rest;
match presence {
0 if !index.present_only => return Ok(()),
1 => {}
_ => return Err(Error::InvalidCursor),
}
}
key::consume(remaining, field.value)
}
#[inline(never)]
#[expect(
clippy::needless_pass_by_value,
reason = "own the request so predicate cleanup stays outside entity-specialized terminals"
)]
fn fetch_rows<M: Memory>(
db: &Database<M>,
entity: &EntitySchema,
request: Request<'_>,
projection: Option<&TypeSchema>,
) -> Result<QueryPage<Vec<u8>>, Error> {
db.schema.admits(entity)?;
let plan = Plan::admit(
entity,
&request,
db.schema.fingerprint(),
db.incarnation,
projection,
false,
)?;
execute(&db.map, entity, &request, &plan, None)
}
fn execute<M: Memory>(
map: &Map<M>,
entity: &EntitySchema,
request: &Request<'_>,
plan: &Plan<'_>,
mut aggregate: Option<aggregate::Accumulator<'_>>,
) -> Result<QueryPage<Vec<u8>>, Error> {
execute_inner(map, entity, request, plan, aggregate.as_mut(), None)
}
const STEP_INPUT_BYTES: usize = 64 * 1024;
const CANDIDATE_BYTES: usize = crate::codec::MAX_ROW_BYTES + 2 * crate::MAX_INDEX_KEY_BYTES;
fn execute_inner<M: Memory>(
map: &Map<M>,
entity: &EntitySchema,
request: &Request<'_>,
plan: &Plan<'_>,
mut aggregate: Option<&mut aggregate::Accumulator<'_>>,
mut input_bytes: Option<&mut usize>,
) -> Result<QueryPage<Vec<u8>>, Error> {
let mut page = QueryPage {
rows: Vec::new(),
next: None,
examined: 0,
fetched: 0,
output_bytes: 0,
};
let Some(bounds) = range::bounds(entity, request, plan)? else {
return Ok(page);
};
let mut entries = map.range(bounds);
let mut collected = if plan.distinct == distinct::Strategy::Complete {
Some(distinct::Collection::new(
plan.projection.ok_or(Error::InvalidQuery)?,
))
} else {
None
};
let mut sorted = plan
.sort
.as_ref()
.map(|_| sort::Collection::new(request, plan.distinct == distinct::Strategy::Sorted));
let mut component = Vec::new();
let mut previous = if let Some(cursor) = request.cursor.filter(|c| !c.inclusive) {
distinct::boundary(entity, plan.index, plan.distinct, &cursor.position)?.map(<[u8]>::to_vec)
} else {
None
};
while let Some(entry) = if plan.descending {
entries.next_back()
} else {
entries.next()
} {
if request.work == 0 {
return Err(Error::Limit);
}
page.examined += 1;
let stored_key = entry.key();
let mut read_bytes = stored_key.len();
let (owner, bytes) = if plan.index.is_some() {
let owner_bytes = entry.value();
read_bytes += owner_bytes.len();
let owner = RowKey::decode(&owner_bytes, entity.key_type()?)?;
let bytes = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
(owner, bytes)
} else {
(
RowKey::decode(&stored_key[5..], entity.key_type()?)?,
entry.value(),
)
};
if let Some(used) = input_bytes.as_deref_mut() {
read_bytes += bytes.len();
if read_bytes > CANDIDATE_BYTES {
return Err(Error::Corrupt);
}
*used += read_bytes;
}
page.fetched += 1;
let mut values = [IndexValue::Absent; crate::schema::MAX_FIELDS];
let mut spans = [(0_u16, 0_u16); crate::schema::MAX_FIELDS];
entity.inspect_fields(
&bytes,
plan.selected,
&mut values,
(plan.presence != 0
|| plan.projection.is_some()
|| aggregate.as_ref().is_some_and(|a| a.needs_spans()))
.then_some(&mut spans),
)?;
let primary = entity
.fields
.iter()
.position(|f| f.name == entity.primary_key)
.ok_or(Error::Corrupt)?;
if RowKey::from_index(values[primary])? != owner {
return Err(Error::Corrupt);
}
if plan.index.is_some() {
validate_index_entry(entity, &entity.row_info(&values)?, owner, stored_key)?;
}
let matches = plan
.terms
.split_inclusive(|term| !term.or_next)
.all(|clause| {
clause.iter().any(|term| {
if plan.presence & (1 << term.position) != 0 {
let absent = bytes[usize::from(spans[term.position].0)] == 0;
return term.comparison.accepts_absent(absent);
}
let value = values[term.position];
component.clear();
value.append_component(entity.fields[term.position].optional, &mut component);
term.comparison.accepts(
(value != IndexValue::Absent).then_some(component.as_slice()),
(!term.absent).then_some(term.operand.as_slice()),
entity.fields[term.position].optional,
)
})
});
let boundary = distinct::boundary(entity, plan.index, plan.distinct, stored_key)?;
let duplicate = boundary.is_some_and(|key| previous.as_deref() == Some(key));
if matches && let Some(accumulator) = aggregate.as_mut() {
accumulator.push(entity, &values, &bytes, &spans)?;
if matches!(accumulator, aggregate::Accumulator::Exists(_)) {
return Ok(page);
}
} else if matches && let Some(collection) = collected.as_mut() {
collection.push(entity, request, &values, &bytes, &spans)?;
} else if matches && let Some(collection) = sorted.as_mut() {
collection.push(entity, plan, &values, &bytes, &spans)?;
} else if matches && !duplicate {
let size = plan
.projection
.map_or(bytes.len(), |mask| projection_size(&spans, mask));
if size > request.bytes {
return Err(Error::RowTooLarge);
}
if size > request.bytes - page.output_bytes {
page.next = Some(plan.cursor(stored_key, true));
return Ok(page);
}
page.output_bytes += size;
if let Some(mask) = plan.projection {
page.rows.push(copy_projection(&bytes, &spans, mask, size));
} else {
page.rows.push(bytes);
}
if let Some(boundary) = boundary {
previous = Some(boundary.to_vec());
}
}
if page.rows.len() == request.rows
|| page.examined == request.work
|| input_bytes
.as_deref()
.is_some_and(|used| *used > STEP_INPUT_BYTES - CANDIDATE_BYTES)
{
if (aggregate.is_some() && input_bytes.is_none())
|| collected.is_some()
|| sorted.is_some()
{
return Err(Error::Limit);
}
page.next = Some(plan.cursor(stored_key, false));
return Ok(page);
}
}
if let Some(collection) = collected {
page.output_bytes = collection.output_bytes;
page.rows = collection.rows;
}
if let Some(collection) = sorted {
collection.finish(request.bytes, &mut page)?;
}
Ok(page)
}