uqa-storage-sqlite 0.5.3

SQLite catalog, indexes, compressed storage, graph and key/value providers
Documentation
//
// Unified Query Algebra
//
// Copyright (c) 2023-2026 Cognica, Inc.
//

//! Probe disjoint intervals within each key length, then merge their ordered candidates.

use rusqlite::{params, Connection, OptionalExtension};
use uqa_core::memory::BudgetedVec;
use uqa_storage::{mvcc::VersionError, read_control::StorageReadControl};

use super::{suffix, Bounds, PhysicalResult, MAX_KEY};

/// A candidate stays in the existing bounded run-codec workspace until selected for a visitor; it never allocates a future key from the caller's allowance.
pub(in crate::mvcc) struct KeyCandidate {
    bytes: [u8; MAX_KEY],
    length: usize,
}

impl KeyCandidate {
    pub(in crate::mvcc) fn bytes(&self) -> &[u8] {
        &self.bytes[..self.length]
    }
}

pub(in crate::mvcc) fn next_key(
    connection: &Connection,
    lower: &[u8],
    exclusive: bool,
    upper: Option<&[u8]>,
    control: &StorageReadControl,
) -> PhysicalResult<Option<BudgetedVec<u8>>> {
    next_candidate(connection, lower, exclusive, upper, control)?
        .map(|key| crate::read_control::copy_bytes(key.bytes(), 0, control).map_err(Into::into))
        .transpose()
}

pub(in crate::mvcc) fn next_candidate(
    connection: &Connection,
    lower: &[u8],
    exclusive: bool,
    upper: Option<&[u8]>,
    control: &StorageReadControl,
) -> PhysicalResult<Option<KeyCandidate>> {
    let _bindings = crate::read_control::reserve_bindings(control, &[lower])?;
    let mut lengths = connection.prepare_cached(
        "SELECT key_length FROM _uqa_mvcc_runs WHERE key_length > ?1 ORDER BY key_length LIMIT 1",
    )?;
    let mut predecessor = connection.prepare_cached(super::LOOKUP)?;
    let mut successor = connection.prepare_cached("SELECT first_key, last_key, sequence, kind, CASE WHEN value IS NULL THEN NULL WHEN typeof(value) = 'blob' THEN length(value) ELSE -1 END, key_length FROM _uqa_mvcc_runs WHERE key_length = ?1 AND first_key > ?2 ORDER BY first_key LIMIT 1")?;
    let mut previous = 0;
    let mut selected: Option<KeyCandidate> = None;
    while let Some(length) = lengths
        .query_row([previous], |row| row.get::<_, i64>(0))
        .optional()?
    {
        control.cancellation().check().map_err(VersionError::from)?;
        if !(8..=1024).contains(&length) {
            return Err(VersionError::InvalidEncoding("invalid record run key length").into());
        }
        previous = length;
        let mut candidate = None;
        {
            let mut rows = predecessor.query(params![length, lower])?;
            if let Some(row) = rows.next()? {
                candidate = next_member(&Bounds::decode(row)?, lower, exclusive);
            }
        }
        if candidate.is_none() {
            let mut rows = successor.query(params![length, lower])?;
            if let Some(row) = rows.next()? {
                candidate = Some(Bounds::decode(row)?.first);
            }
        }
        if let Some(key) = candidate {
            let length = usize::try_from(length).expect("validated length");
            let bytes = &key[..length];
            if upper.is_none_or(|upper| bytes < upper)
                && selected
                    .as_ref()
                    .is_none_or(|selected| bytes < selected.bytes())
            {
                selected = Some(KeyCandidate { bytes: key, length });
            }
        }
    }
    Ok(selected)
}

fn next_member(bounds: &Bounds, lower: &[u8], exclusive: bool) -> Option<[u8; MAX_KEY]> {
    let start = suffix(bounds.first());
    let count = suffix(bounds.last()) - start + 1;
    let mut key = bounds.first;
    let offset = bounds.key_length - 8;
    let mut low = 0;
    let mut high = count;
    while low < high {
        let middle = low + (high - low) / 2;
        key[offset..bounds.key_length].copy_from_slice(&(start + middle).to_be_bytes());
        let candidate = &key[..bounds.key_length];
        if candidate < lower || (exclusive && candidate == lower) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    if low == count {
        return None;
    }
    key[offset..bounds.key_length].copy_from_slice(&(start + low).to_be_bytes());
    Some(key)
}