uqa-storage-sqlite 0.5.0

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

use rusqlite::{params, Connection};
use uqa_core::memory::{MemoryError, MemoryReservation};
use uqa_storage::mvcc::{
    resolve_prepared_receipt, CommitFailure, CommitReceipt, CommitResult, CommitSequence,
    CommitStatus, DatabaseId, PreparedRecordCommit, StorageTransactionId, VersionError,
    VersionResult,
};
use uqa_storage::read_control::StorageReadControl;

use super::{admission, codec, native, Error, PhysicalResult};

pub(super) fn reserve_bindings(
    prepared: &PreparedRecordCommit,
    control: &StorageReadControl,
) -> VersionResult<MemoryReservation> {
    let binding = |key: usize, value: u64| {
        usize::try_from(value)
            .ok()
            .and_then(|value| key.checked_mul(2)?.checked_add(value))
            .and_then(|length| length.checked_add(96))
            .ok_or(MemoryError::SizeOverflow)
    };
    let mut peak = 96;
    let mut writes = prepared.writes();
    while let Some(write) = writes.next_metadata(control)? {
        peak = peak.max(binding(write.key().len(), write.value_len().unwrap_or(0))?);
    }
    for key in prepared.required_keys() {
        control.cancellation().check()?;
        peak = peak.max(binding(key.len(), 0)?);
    }
    Ok(control.memory().reserve(peak)?)
}

pub(super) fn allocate(
    connection: &Connection,
    identity: DatabaseId,
    native: Option<native::NativeRecordNamespace>,
    control: &StorageReadControl,
) -> PhysicalResult<StorageTransactionId> {
    allocate_with_owner(connection, identity, native, false, control, |_| Ok(()))
}

pub(super) fn allocate_with_owner(
    connection: &Connection,
    identity: DatabaseId,
    native: Option<native::NativeRecordNamespace>,
    managed: bool,
    control: &StorageReadControl,
    retain: impl FnOnce(StorageTransactionId) -> VersionResult<()>,
) -> PhysicalResult<StorageTransactionId> {
    let _permit = admission::permit(connection, control)?;
    let transaction = admission::begin(connection, control)?;
    native::check_mapping(&transaction, native)?;
    let current = codec::header(&transaction, identity)?;
    if receipts_reach_limit(&transaction, &current)? {
        return Err(VersionError::ReceiptRetentionExhausted {
            limit: current.receipt_limit,
        }
        .into());
    }
    let id = StorageTransactionId::new(
        identity,
        current
            .allocated
            .checked_add(1)
            .ok_or(VersionError::TransactionIdsExhausted)?,
    )?;
    let bytes = id.allocation().to_be_bytes();
    retain(id)?;
    transaction
        .prepare_cached("UPDATE _uqa_mvcc_metadata SET allocated = ?1 WHERE singleton = 1")?
        .execute(params![bytes.as_slice()])?;
    transaction.prepare_cached("INSERT INTO _uqa_mvcc_transactions (allocation, status, sequence, fingerprint, managed) VALUES (?1, 0, NULL, NULL, ?2)")?.execute(params![bytes.as_slice(), i64::from(managed)])?;
    control.cancellation().check().map_err(VersionError::from)?;
    admission::commit(transaction, control)?;
    Ok(id)
}

/// Whether the retained receipts have reached the retention limit. Every retained receipt lies between the oldest one and the last allocation, so their distance bounds the count without visiting a row. Counting is linear in the receipts kept, which are deleted only when the limit is reached, so they are counted only when the bound does not settle the answer.
fn receipts_reach_limit(connection: &Connection, current: &codec::Header) -> PhysicalResult<bool> {
    let oldest = {
        let mut statement = connection.prepare_cached(
            "SELECT allocation FROM _uqa_mvcc_transactions ORDER BY allocation LIMIT 1",
        )?;
        let mut rows = statement.query([])?;
        let Some(row) = rows.next()? else {
            return Ok(current.receipt_limit == 0);
        };
        codec::integer(codec::bytes(row, 0)?)?
    };
    if current
        .allocated
        .checked_sub(oldest)
        .is_some_and(|span| span.saturating_add(1) < current.receipt_limit)
    {
        return Ok(false);
    }
    let retained: i64 = connection
        .prepare_cached("SELECT count(*) FROM _uqa_mvcc_transactions")?
        .query_row([], |row| row.get(0))?;
    let retained = u64::try_from(retained)
        .map_err(|_| VersionError::InvalidEncoding("negative transaction receipt count"))?;
    Ok(retained >= current.receipt_limit)
}

pub(super) fn commit(
    connection: &Connection,
    id: StorageTransactionId,
    prepared: &PreparedRecordCommit,
    native: Option<native::NativeRecordNamespace>,
    control: &StorageReadControl,
) -> CommitResult {
    let rejected = |error: Error| CommitFailure::Rejected(error.into_version());
    let _permit = admission::permit(connection, control).map_err(rejected)?;
    let transaction = admission::begin(connection, control).map_err(rejected)?;
    native::check_mapping(&transaction, native).map_err(rejected)?;
    let current = codec::header(&transaction, id.database()).map_err(rejected)?;
    let status = codec::status(&transaction, id).map_err(rejected)?;
    if let Some(receipt) = resolve_prepared_receipt(status, id, prepared.fingerprint())? {
        return Ok(receipt);
    }
    prepared.validate_snapshot(current.sequence)?;
    super::tombstones::validate(&transaction, prepared, control).map_err(rejected)?;
    prepared.validate(control, |key| {
        codec::head(&transaction, key).map_err(Error::into_version)
    })?;
    let sequence = if prepared.is_empty() {
        current.sequence
    } else {
        current.sequence.successor()?
    };
    let receipt = CommitReceipt {
        transaction: id,
        sequence,
        fingerprint: prepared.fingerprint(),
    };
    if let Some(namespace) = native {
        native::materialize(&transaction, namespace.0, prepared, sequence, control)
            .map_err(rejected)?;
    }
    stage(&transaction, prepared, receipt, control).map_err(rejected)?;
    admission::commit(transaction, control).map_err(|error| match error {
        Error::Version(error @ VersionError::Cancelled(_)) => CommitFailure::Rejected(error),
        error => CommitFailure::Indeterminate {
            transaction: id,
            source: error.into_version().into_storage_error(),
        },
    })?;
    Ok(receipt)
}

fn stage(
    connection: &Connection,
    prepared: &PreparedRecordCommit,
    receipt: CommitReceipt,
    control: &StorageReadControl,
) -> PhysicalResult<()> {
    let sequence = receipt.sequence.as_u64().to_be_bytes();
    let has_runs: bool = connection
        .prepare_cached("SELECT EXISTS(SELECT 1 FROM _uqa_mvcc_runs)")?
        .query_row([], |row| row.get(0))?;
    {
        let mut versions = connection.prepare_cached(
            "INSERT INTO _uqa_mvcc_versions (key, sequence, value) VALUES (?1, ?2, ?3)",
        )?;
        let mut previous = connection.prepare_cached("INSERT INTO _uqa_mvcc_versions (key, sequence, value) SELECT key, sequence, NULL FROM _uqa_mvcc_heads WHERE key = ?1 AND compacted = 1")?;
        let mut heads = connection.prepare_cached("INSERT INTO _uqa_mvcc_heads (key, sequence, compacted) VALUES (?1, ?2, 0) ON CONFLICT(key) DO UPDATE SET sequence = excluded.sequence, compacted = 0")?;
        let mut writes = prepared.writes();
        while let Some(write) = writes.next(control)? {
            // Validation found the head each write expects. A key that expects none has no head, so it is in no run and has no compacted tombstone to restore before its first version.
            if write.expected().is_some() {
                if has_runs {
                    super::runs::extract(connection, write.key(), control)?;
                }
                previous.execute([write.key()])?;
                previous.clear_bindings();
            } else {
                debug_assert!(
                    codec::head(connection, write.key())?.is_none(),
                    "a write that expects no revision was staged over a head"
                );
            }
            versions.execute(params![write.key(), sequence.as_slice(), write.value()])?;
            versions.clear_bindings();
            heads.execute(params![write.key(), sequence.as_slice()])?;
            heads.clear_bindings();
        }
    }
    connection
        .prepare_cached("UPDATE _uqa_mvcc_metadata SET sequence = ?1 WHERE singleton = 1")?
        .execute(params![sequence.as_slice()])?;
    connection.prepare_cached("UPDATE _uqa_mvcc_transactions SET status = 2, sequence = ?1, fingerprint = ?2 WHERE allocation = ?3")?.execute(params![sequence.as_slice(), receipt.fingerprint.as_slice(), receipt.transaction.allocation().to_be_bytes().as_slice()])?;
    control.cancellation().check().map_err(VersionError::from)?;
    Ok(())
}

pub(super) fn stage_record(
    connection: &Connection,
    key: &[u8],
    value: Option<&[u8]>,
    sequence: CommitSequence,
    control: &StorageReadControl,
) -> PhysicalResult<()> {
    control.cancellation().check().map_err(VersionError::from)?;
    let _bindings =
        crate::read_control::reserve_bindings(control, &[key, value.unwrap_or_default()])?;
    let sequence = sequence.as_u64().to_be_bytes();
    super::runs::extract(connection, key, control)?;
    connection.prepare_cached("INSERT INTO _uqa_mvcc_versions (key, sequence, value) SELECT key, sequence, NULL FROM _uqa_mvcc_heads WHERE key = ?1 AND compacted = 1")?.execute([key])?;
    connection
        .prepare_cached("INSERT INTO _uqa_mvcc_versions(key, sequence, value) VALUES (?1, ?2, ?3)")?
        .execute(params![key, sequence.as_slice(), value])?;
    connection.prepare_cached("INSERT INTO _uqa_mvcc_heads(key, sequence, compacted) VALUES (?1, ?2, 0) ON CONFLICT(key) DO UPDATE SET sequence = excluded.sequence, compacted = 0")?.execute(params![key, sequence.as_slice()])?;
    Ok(())
}

pub(super) fn abort(
    connection: &Connection,
    id: StorageTransactionId,
    native: Option<native::NativeRecordNamespace>,
    control: &StorageReadControl,
) -> PhysicalResult<CommitStatus> {
    // Recording an abort waits for writer admission like any other write instead of failing once SQLite's busy timeout expires, which would leave the rollback to surface later as a cleanup failure.
    let _permit = admission::permit(connection, control)?;
    let transaction = admission::begin(connection, control)?;
    native::check_mapping(&transaction, native)?;
    codec::header(&transaction, id.database())?;
    let status = codec::status(&transaction, id)?;
    if status != CommitStatus::Pending {
        return Ok(status);
    }
    transaction
        .prepare_cached("UPDATE _uqa_mvcc_transactions SET status = 1 WHERE allocation = ?1")?
        .execute(params![id.allocation().to_be_bytes().as_slice()])?;
    control.cancellation().check().map_err(VersionError::from)?;
    admission::commit(transaction, control)?;
    Ok(CommitStatus::Aborted)
}