use std::future::Future;
use std::path::Path;
use std::pin::Pin;
use std::sync::{Arc, Mutex};
use std::task::{Context, Poll};
use std::vec;
use futures_core::Stream;
use happenstance_core::{
AppendCondition, AppendError, ConditionViolated, Event, EventId, InvalidEventType, InvalidTag,
Query, ReadOptions, RecordedAt, SendEventStore, SequencePosition, SequencedEvent, StoreId,
};
use rusqlite::Connection;
use rusqlite::types::Value;
use tokio::runtime::{Handle, TryCurrentError};
use tokio::task::{JoinError, JoinHandle};
use crate::connection::ConnectionSettings;
use crate::query_sql::Selectivity;
const PAGE_SIZE: usize = 512;
#[derive(Debug, Clone)]
pub struct SqliteEventStore {
connection: Arc<Mutex<Connection>>,
store_id: StoreId,
runtime: Option<Handle>,
}
pub const SCHEMA_VERSION: u32 = 1;
const MIGRATION_1: &str = "\
CREATE TABLE IF NOT EXISTS event (
position INTEGER PRIMARY KEY AUTOINCREMENT,
event_type TEXT NOT NULL,
data BLOB NOT NULL,
metadata BLOB,
tags BLOB NOT NULL,
origin_store BLOB,
origin_position INTEGER,
recorded_at INTEGER NOT NULL,
UNIQUE (origin_store, origin_position)
);
CREATE INDEX IF NOT EXISTS event_type_idx ON event(event_type, position);
CREATE TABLE IF NOT EXISTS event_tag (
tag TEXT NOT NULL,
position INTEGER NOT NULL REFERENCES event(position),
event_type TEXT NOT NULL,
PRIMARY KEY (tag, position)
) WITHOUT ROWID;
CREATE TABLE IF NOT EXISTS tag_cardinality (
tag TEXT PRIMARY KEY,
events INTEGER NOT NULL
) WITHOUT ROWID;
CREATE TABLE IF NOT EXISTS store_meta (
k TEXT PRIMARY KEY,
v BLOB NOT NULL
) WITHOUT ROWID;";
const STORE_ID_KEY: &str = "store_id";
const SCHEMA_VERSION_KEY: &str = "schema_version";
impl SqliteEventStore {
pub const MAX_EVENT_DATA_LEN: usize = 1_048_576;
pub const MAX_TAGS_PER_EVENT: usize = 128;
pub const MAX_EVENTS_PER_BATCH: usize = 256;
pub const MAX_PAGE_BYTES_PER_STATEMENT: usize = 8 * Self::MAX_EVENT_DATA_LEN;
pub const MAX_QUERY_ARMS_PER_STATEMENT: usize = 400;
pub const MAX_QUERY_PARAMETERS_PER_STATEMENT: usize = PARAMETER_BUDGET;
#[must_use]
pub fn planned_statement_count(query: &Query) -> usize {
let window = crate::query_sql::Window {
lo: 0,
hi: i64::MAX,
budget: i64::try_from(PAGE_SIZE).unwrap_or(i64::MAX),
backwards: false,
};
crate::query_sql::page_statements(
query,
&Selectivity::default(),
Self::MAX_QUERY_ARMS_PER_STATEMENT,
Self::MAX_QUERY_PARAMETERS_PER_STATEMENT,
window,
crate::row::COLUMNS,
)
.len()
}
pub fn new(connection: Connection) -> Result<Self, SqliteEventStoreError> {
let store_id = read_identity(&connection)?;
Ok(Self::with_store_id(connection, store_id))
}
fn with_store_id(connection: Connection, store_id: StoreId) -> Self {
Self {
connection: Arc::new(Mutex::new(connection)),
store_id,
runtime: Handle::try_current().ok(),
}
}
pub fn open(path: impl AsRef<Path>) -> Result<Self, SqliteEventStoreError> {
let mut connection = crate::connection::open_configured(path)?;
let store_id = Self::migrate(&mut connection)?;
Ok(Self::with_store_id(connection, store_id))
}
pub fn open_in_memory() -> Result<Self, SqliteEventStoreError> {
let mut connection = Connection::open_in_memory()?;
crate::connection::configure(&connection)?;
let store_id = Self::migrate(&mut connection)?;
Ok(Self::with_store_id(connection, store_id))
}
#[must_use]
pub const fn store_id(&self) -> StoreId {
self.store_id
}
pub fn settings(&self) -> Result<ConnectionSettings, SqliteEventStoreError> {
let connection = self
.connection
.lock()
.map_err(|_| SqliteEventStoreError::ConnectionPoisoned)?;
Ok(ConnectionSettings::read_back(&connection)?)
}
pub fn remint_identity(path: impl AsRef<Path>) -> Result<StoreId, SqliteEventStoreError> {
let mut connection = crate::connection::open_configured(path)?;
Self::migrate(&mut connection)?;
let transaction =
connection.transaction_with_behavior(rusqlite::TransactionBehavior::Immediate)?;
transaction.execute(
"UPDATE store_meta SET v = randomblob(16) WHERE k = ?",
[STORE_ID_KEY],
)?;
let minted = read_identity(&transaction)?;
transaction.commit()?;
Ok(minted)
}
fn check_ceilings(events: &[Event]) -> Result<(), AppendError<SqliteEventStoreError>> {
if events.len() > Self::MAX_EVENTS_PER_BATCH {
return Err(AppendError::ExceedsStoreLimit {
limit: happenstance_core::StoreLimit::EventsPerBatch,
len: events.len(),
});
}
for event in events {
if event.data().len() > Self::MAX_EVENT_DATA_LEN {
return Err(AppendError::ExceedsStoreLimit {
limit: happenstance_core::StoreLimit::EventDataLen,
len: event.data().len(),
});
}
if event.tags().len() > Self::MAX_TAGS_PER_EVENT {
return Err(AppendError::ExceedsStoreLimit {
limit: happenstance_core::StoreLimit::TagsPerEvent,
len: event.tags().len(),
});
}
}
Ok(())
}
fn append_locked(
connection: &mut Connection,
store_id: StoreId,
events: &[Event],
condition: Option<&AppendCondition>,
recorded_at: RecordedAt,
) -> Result<SequencePosition, AppendError<SqliteEventStoreError>> {
let transaction = connection
.transaction_with_behavior(rusqlite::TransactionBehavior::Immediate)
.map_err(store_error)?;
let persisted = read_identity(&transaction).map_err(AppendError::Store)?;
if persisted != store_id {
drop(transaction);
return Err(AppendError::Store(SqliteEventStoreError::IdentityMoved {
handle: store_id,
persisted,
}));
}
if let Some(condition) = condition
&& let Some(conflict) = evaluate(&transaction, condition).map_err(store_error)?
{
drop(transaction);
return Err(AppendError::ConditionViolated(ConditionViolated::at(
conflict,
)));
}
let last = write_batch(&transaction, store_id, events, recorded_at).map_err(store_error)?;
transaction.commit().map_err(store_error)?;
Ok(last)
}
fn migrate(connection: &mut Connection) -> Result<StoreId, SqliteEventStoreError> {
let transaction =
connection.transaction_with_behavior(rusqlite::TransactionBehavior::Immediate)?;
transaction.execute_batch(MIGRATION_1)?;
transaction.execute(
"INSERT OR IGNORE INTO store_meta (k, v) VALUES (?, ?)",
rusqlite::params![SCHEMA_VERSION_KEY, SCHEMA_VERSION],
)?;
transaction.execute(
"INSERT OR IGNORE INTO store_meta (k, v) VALUES (?, randomblob(16))",
[STORE_ID_KEY],
)?;
let store_id = read_identity(&transaction)?;
transaction.commit()?;
Ok(store_id)
}
}
const PARAMETER_BUDGET: usize = 30_000;
const TAG_ROW_PARAMETERS: usize = 3;
fn now() -> RecordedAt {
use std::time::{SystemTime, UNIX_EPOCH};
let millis = SystemTime::now()
.duration_since(UNIX_EPOCH)
.ok()
.and_then(|since| i64::try_from(since.as_millis()).ok())
.unwrap_or(0);
RecordedAt::from_millis(millis)
}
fn payload_bytes(event: &SequencedEvent) -> usize {
event.event.data().len()
+ event
.event
.metadata()
.map_or(0, happenstance_core::bytes::Bytes::len)
}
fn as_i64(position: SequencePosition) -> i64 {
i64::try_from(position.get()).unwrap_or(i64::MAX)
}
pub(crate) fn position_from_row(stored: i64) -> Result<SequencePosition, SqliteEventStoreError> {
u64::try_from(stored)
.ok()
.and_then(SequencePosition::new)
.ok_or(SqliteEventStoreError::InvalidPosition(stored))
}
fn store_error(error: impl Into<SqliteEventStoreError>) -> AppendError<SqliteEventStoreError> {
AppendError::Store(error.into())
}
fn evaluate(
connection: &Connection,
condition: &AppendCondition,
) -> Result<Option<SequencePosition>, SqliteEventStoreError> {
let lowest: Option<i64> =
connection.query_row("SELECT min(position) FROM event", [], |row| row.get(0))?;
if let Some(stored) = lowest {
position_from_row(stored)?;
}
for guard in condition.guards() {
let selectivity = Selectivity::read_for(
connection,
&guard.query,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)?;
let boundary = guard.after.map_or(0, as_i64);
let plan = crate::query_sql::chunks(
&guard.query,
&selectivity,
SqliteEventStore::MAX_QUERY_ARMS_PER_STATEMENT,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
Some(boundary),
);
let mut highest: Option<i64> = None;
for (matched, params) in plan {
let chunk: Option<i64> = connection.query_row(
&format!("SELECT max(position) FROM ({matched})"),
rusqlite::params_from_iter(params.iter()),
|row| row.get(0),
)?;
highest = highest.max(chunk);
}
if let Some(stored) = highest {
let conflict = position_from_row(stored)?;
if stored > boundary {
return Ok(Some(conflict));
}
}
}
Ok(None)
}
fn write_batch(
connection: &Connection,
store_id: StoreId,
events: &[Event],
recorded_at: RecordedAt,
) -> Result<SequencePosition, SqliteEventStoreError> {
let mut positions = Vec::with_capacity(events.len());
{
let mut insert = connection.prepare(
"INSERT INTO event (event_type, data, metadata, tags, recorded_at) \
VALUES (?, ?, ?, ?, ?)",
)?;
for event in events {
insert.execute(rusqlite::params![
event.event_type().as_str(),
&event.data()[..],
event.metadata().map(|metadata| &metadata[..]),
crate::row::encode_tags(event.tags()),
recorded_at.as_millis(),
])?;
positions.push(connection.last_insert_rowid());
}
}
write_tag_rows(connection, events, &positions)?;
bump_cardinality(connection, events)?;
if let Some(&first) = positions.first() {
connection.execute(
"UPDATE event SET origin_store = ?, origin_position = position \
WHERE position >= ? AND origin_position IS NULL",
rusqlite::params![&store_id.to_bytes()[..], first],
)?;
}
let last = positions.last().copied().unwrap_or_default();
position_from_row(last)
}
fn write_tag_rows(
connection: &Connection,
events: &[Event],
positions: &[i64],
) -> rusqlite::Result<()> {
let rows_per_statement = (PARAMETER_BUDGET / TAG_ROW_PARAMETERS).max(1);
let mut buffer: Vec<Value> = Vec::with_capacity(rows_per_statement * TAG_ROW_PARAMETERS);
let mut buffered = 0usize;
for (event, position) in events.iter().zip(positions) {
for tag in event.tags() {
buffer.push(Value::Text(tag.as_str().to_owned()));
buffer.push(Value::Integer(*position));
buffer.push(Value::Text(event.event_type().as_str().to_owned()));
buffered += 1;
if buffered == rows_per_statement {
flush_tag_rows(connection, &buffer, buffered)?;
buffer.clear();
buffered = 0;
}
}
}
if buffered > 0 {
flush_tag_rows(connection, &buffer, buffered)?;
}
Ok(())
}
fn flush_tag_rows(connection: &Connection, buffer: &[Value], rows: usize) -> rusqlite::Result<()> {
let tuples = (0..rows).map(|_| "(?,?,?)").collect::<Vec<_>>().join(",");
connection.execute(
&format!("INSERT INTO event_tag (tag, position, event_type) VALUES {tuples}"),
rusqlite::params_from_iter(buffer.iter()),
)?;
Ok(())
}
fn bump_cardinality(connection: &Connection, events: &[Event]) -> rusqlite::Result<()> {
let mut statement = connection.prepare(
"INSERT INTO tag_cardinality (tag, events) VALUES (?, 1) \
ON CONFLICT(tag) DO UPDATE SET events = events + 1",
)?;
for event in events {
for tag in event.tags() {
statement.execute([tag.as_str()])?;
}
}
Ok(())
}
fn read_identity(connection: &Connection) -> Result<StoreId, SqliteEventStoreError> {
let version: u32 = connection.query_row(
"SELECT CAST(v AS INTEGER) FROM store_meta WHERE k = ?",
[SCHEMA_VERSION_KEY],
|row| row.get(0),
)?;
if version > SCHEMA_VERSION {
return Err(SqliteEventStoreError::UnsupportedSchemaVersion {
found: version,
supported: SCHEMA_VERSION,
});
}
let raw: Vec<u8> = connection
.query_row(
"SELECT CAST(v AS BLOB) FROM store_meta WHERE k = ?",
[STORE_ID_KEY],
|row| row.get(0),
)
.map_err(|err| match err {
rusqlite::Error::QueryReturnedNoRows => SqliteEventStoreError::MissingIdentity,
other => SqliteEventStoreError::Sqlite(other),
})?;
let bytes: [u8; 16] = raw
.as_slice()
.try_into()
.map_err(|_| SqliteEventStoreError::MalformedIdentity { len: raw.len() })?;
Ok(StoreId::from_bytes(bytes))
}
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum SqliteEventStoreError {
#[error("SQLite failed: {0}")]
Sqlite(#[from] rusqlite::Error),
#[error("the SQLite connection mutex was poisoned by a panicking thread")]
ConnectionPoisoned,
#[error("the blocking SQLite task did not complete: {0}")]
Worker(#[from] JoinError),
#[error("no tokio runtime is available to run the blocking SQLite query: {0}")]
NoRuntime(#[from] TryCurrentError),
#[error("stored position {0} is not a valid sequence position")]
InvalidPosition(i64),
#[error("stored event type is invalid: {0}")]
StoredEventType(#[from] InvalidEventType),
#[error("stored tag is invalid: {0}")]
StoredTag(#[from] InvalidTag),
#[error(
"this build understands schema version {supported}, and the database is \
at version {found}"
)]
UnsupportedSchemaVersion {
found: u32,
supported: u32,
},
#[error(
"the database has been migrated but carries no store identity; minting \
a replacement would re-issue event identities for events that already \
exist"
)]
MissingIdentity,
#[error("the stored store identity is {len} bytes, and a StoreId is sixteen")]
MalformedIdentity {
len: usize,
},
#[error(
"this handle mints identities under store {handle}, and the database now \
carries {persisted}: it was re-minted while this handle was open, so the \
handle must be dropped and the store reopened"
)]
IdentityMoved {
handle: StoreId,
persisted: StoreId,
},
#[error("the event at position {position} carries no origin identity")]
UnstampedEvent {
position: SequencePosition,
},
#[error("a stored tag column is not valid UTF-8")]
CorruptTags,
}
impl SendEventStore for SqliteEventStore {
type Error = SqliteEventStoreError;
fn read(
&self,
query: &Query,
options: ReadOptions,
) -> impl Stream<Item = Result<SequencedEvent, Self::Error>> + Send {
SqliteReadStream {
state: ReadState::Idle(Box::new(ReadCursor {
connection: Arc::clone(&self.connection),
runtime: self.runtime.clone(),
query: query.clone(),
options,
resume_from: options.from,
remaining: options.limit,
ceiling: Ceiling::Unsampled,
finished: false,
})),
}
}
async fn append(
&self,
events: &[Event],
condition: Option<&AppendCondition>,
) -> Result<SequencePosition, AppendError<Self::Error>> {
if events.is_empty() {
return Err(AppendError::NoEvents);
}
Self::check_ceilings(events)?;
let recorded_at = now();
let mut connection = self
.connection
.lock()
.map_err(|_| AppendError::Store(SqliteEventStoreError::ConnectionPoisoned))?;
Self::append_locked(
&mut connection,
self.store_id,
events,
condition,
recorded_at,
)
}
async fn head(&self) -> Result<Option<SequencePosition>, Self::Error> {
let connection = self
.connection
.lock()
.map_err(|_| SqliteEventStoreError::ConnectionPoisoned)?;
let highest: Option<i64> =
connection.query_row("SELECT max(position) FROM event", [], |row| row.get(0))?;
highest.map(position_from_row).transpose()
}
async fn contains_event_id(&self, id: EventId) -> Result<bool, Self::Error> {
let connection = self
.connection
.lock()
.map_err(|_| SqliteEventStoreError::ConnectionPoisoned)?;
let found: Option<i64> = connection
.query_row(
"SELECT 1 FROM event WHERE origin_store = ? AND origin_position = ? LIMIT 1",
rusqlite::params![&id.store().to_bytes()[..], as_i64(id.position())],
|row| row.get(0),
)
.or_else(|err| match err {
rusqlite::Error::QueryReturnedNoRows => Ok(None),
other => Err(other),
})?;
Ok(found.is_some())
}
}
#[derive(Debug)]
pub struct SqliteReadStream {
state: ReadState,
}
#[derive(Debug)]
enum ReadState {
Idle(Box<ReadCursor>),
Fetching(JoinHandle<FetchOutcome>),
Draining {
cursor: Box<ReadCursor>,
rows: vec::IntoIter<SequencedEvent>,
},
Done,
}
type FetchOutcome = (Box<ReadCursor>, Result<Page, SqliteEventStoreError>);
#[derive(Debug)]
struct Page {
rows: Vec<SequencedEvent>,
exhausted: bool,
}
#[derive(Debug, Clone, Copy)]
enum Ceiling {
Unsampled,
Empty,
At(SequencePosition),
}
#[derive(Debug)]
struct ReadCursor {
connection: Arc<Mutex<Connection>>,
runtime: Option<Handle>,
query: Query,
options: ReadOptions,
resume_from: Option<SequencePosition>,
remaining: Option<usize>,
ceiling: Ceiling,
finished: bool,
}
#[cfg(test)]
thread_local! {
static PAGE_CONNECTION_ACQUISITIONS: std::cell::Cell<usize> =
const { std::cell::Cell::new(0) };
}
impl ReadCursor {
fn lock_connection(
&self,
) -> Result<std::sync::MutexGuard<'_, Connection>, SqliteEventStoreError> {
#[cfg(test)]
PAGE_CONNECTION_ACQUISITIONS.with(|taken| taken.set(taken.get() + 1));
self.connection
.lock()
.map_err(|_| SqliteEventStoreError::ConnectionPoisoned)
}
fn sample_ceiling(&mut self) -> Result<(), SqliteEventStoreError> {
if !matches!(self.ceiling, Ceiling::Unsampled) {
return Ok(());
}
let (lowest, highest): (Option<i64>, Option<i64>) = {
let connection = self.lock_connection()?;
connection.query_row(
"SELECT min(position), max(position) FROM event",
[],
|row| Ok((row.get(0)?, row.get(1)?)),
)?
};
if let Some(stored) = lowest {
position_from_row(stored)?;
}
self.ceiling = match highest {
Some(stored) => Ceiling::At(position_from_row(stored)?),
None => Ceiling::Empty,
};
Ok(())
}
fn page_window(&self, ceiling: SequencePosition, budget: usize) -> crate::query_sql::Window {
let ceiling = as_i64(ceiling);
let resume_from = self.resume_from.map(as_i64);
let to = self.options.to.map(as_i64);
let (lower, upper) = if self.options.backwards {
(to, resume_from)
} else {
(resume_from, to)
};
crate::query_sql::Window {
lo: lower.unwrap_or(0),
hi: upper.map_or(ceiling, |bound| bound.min(ceiling)),
budget: i64::try_from(budget).unwrap_or(i64::MAX),
backwards: self.options.backwards,
}
}
fn fetch_page(&mut self) -> Result<Page, SqliteEventStoreError> {
self.sample_ceiling()?;
let Ceiling::At(ceiling) = self.ceiling else {
return Ok(Page {
rows: Vec::new(),
exhausted: true,
});
};
let budget = self.remaining.map_or(PAGE_SIZE, |left| left.min(PAGE_SIZE));
if budget == 0 {
return Ok(Page {
rows: Vec::new(),
exhausted: true,
});
}
let selectivity = {
let connection = self.lock_connection()?;
Selectivity::read_for(
&connection,
&self.query,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)?
};
let plan = crate::query_sql::page_statements(
&self.query,
&selectivity,
SqliteEventStore::MAX_QUERY_ARMS_PER_STATEMENT,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
self.page_window(ceiling, budget),
crate::row::COLUMNS,
);
let mut merged: Vec<SequencedEvent> = Vec::with_capacity(budget);
let mut effective = budget;
for (sql, params) in plan {
let (taken, cut) = {
let connection = self.lock_connection()?;
let mut statement = connection.prepare(&sql)?;
let mut rows = statement.query(rusqlite::params_from_iter(params.iter()))?;
let mut resident = 0usize;
let mut taken = 0usize;
let mut cut = false;
while let Some(row) = rows.next()? {
let event = crate::row::to_event(row)?;
resident += payload_bytes(&event);
merged.push(event);
taken += 1;
if resident >= SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT {
cut = true;
break;
}
}
(taken, cut)
};
if cut {
effective = effective.min(taken);
}
}
if self.options.backwards {
merged.sort_by_key(|event| core::cmp::Reverse(event.position));
} else {
merged.sort_by_key(|event| event.position);
}
merged.dedup_by_key(|event| event.position);
let exhausted = effective == budget && merged.len() < budget;
merged.truncate(effective);
Ok(Page {
rows: merged,
exhausted,
})
}
fn advance(&mut self, page: &Page) {
let mut exhausted_by_position = false;
if let Some(last) = page.rows.last() {
let next = if self.options.backwards {
SequencePosition::new(last.position.get().saturating_sub(1))
} else {
last.position.next()
};
exhausted_by_position = next.is_none();
self.resume_from = next;
}
if let Some(remaining) = self.remaining.as_mut() {
*remaining = remaining.saturating_sub(page.rows.len());
}
self.finished = page.exhausted || exhausted_by_position || self.remaining == Some(0);
}
}
impl Stream for SqliteReadStream {
type Item = Result<SequencedEvent, SqliteEventStoreError>;
fn poll_next(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>> {
let this = Pin::into_inner(self);
loop {
match std::mem::replace(&mut this.state, ReadState::Done) {
ReadState::Idle(mut cursor) => {
if cursor.finished {
return Poll::Ready(None);
}
if let Err(err) = cursor.sample_ceiling() {
return Poll::Ready(Some(Err(err)));
}
let runtime = match cursor.runtime.clone() {
Some(runtime) => runtime,
None => match Handle::try_current() {
Ok(runtime) => runtime,
Err(err) => return Poll::Ready(Some(Err(err.into()))),
},
};
this.state = ReadState::Fetching(runtime.spawn_blocking(move || {
let mut cursor = cursor;
let page = cursor.fetch_page();
(cursor, page)
}));
}
ReadState::Fetching(mut handle) => match Pin::new(&mut handle).poll(cx) {
Poll::Pending => {
this.state = ReadState::Fetching(handle);
return Poll::Pending;
}
Poll::Ready(Err(join)) => return Poll::Ready(Some(Err(join.into()))),
Poll::Ready(Ok((_cursor, Err(err)))) => return Poll::Ready(Some(Err(err))),
Poll::Ready(Ok((mut cursor, Ok(page)))) => {
cursor.advance(&page);
this.state = ReadState::Draining {
cursor,
rows: page.rows.into_iter(),
};
}
},
ReadState::Draining { cursor, mut rows } => match rows.next() {
Some(event) => {
this.state = ReadState::Draining { cursor, rows };
return Poll::Ready(Some(Ok(event)));
}
None => this.state = ReadState::Idle(cursor),
},
ReadState::Done => return Poll::Ready(None),
}
}
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used)]
use happenstance_core::{QueryItem, Tags};
use super::*;
fn seeded(count: usize, data: usize, metadata: usize) -> Vec<Event> {
(0..count)
.map(|n| {
let mut event = Event::new("Sized", vec![b'd'; data])
.unwrap()
.with_tags(Tags::from_pairs([("page", "p1")]).unwrap());
if metadata > 0 {
event = event.with_metadata(vec![b'm'; metadata]);
}
let _ = n;
event
})
.collect()
}
fn cursor(store: &SqliteEventStore, query: &Query) -> ReadCursor {
let options = ReadOptions::default();
ReadCursor {
connection: Arc::clone(&store.connection),
runtime: store.runtime.clone(),
query: query.clone(),
options,
resume_from: options.from,
remaining: options.limit,
ceiling: Ceiling::Unsampled,
finished: false,
}
}
fn resident(page: &Page) -> usize {
page.rows
.iter()
.map(|event| {
event.event.data().len()
+ event
.event
.metadata()
.map_or(0, happenstance_core::bytes::Bytes::len)
})
.sum()
}
#[tokio::test]
async fn a_page_stops_at_the_byte_budget_rather_than_at_the_row_budget() {
let per_row = SqliteEventStore::MAX_EVENT_DATA_LEN;
let fits = SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT / per_row;
let query = Query::all();
for (seed, expected_first_page, expected_exhausted) in [
(fits - 1, fits - 1, true),
(fits, fits, false),
(fits + 1, fits, false),
] {
let store = SqliteEventStore::open_in_memory().unwrap();
store.append(&seeded(seed, per_row, 0), None).await.unwrap();
let page = cursor(&store, &query).fetch_page().unwrap();
assert_eq!(
page.rows.len(),
expected_first_page,
"a log of {seed} rows of {per_row} B produced a first page of {} rows",
page.rows.len()
);
assert!(
resident(&page) <= SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT,
"a log of {seed} rows produced a page of {} B, over the {} B budget",
resident(&page),
SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT
);
assert_eq!(
page.exhausted, expected_exhausted,
"a log of {seed} rows reported exhausted = {}",
page.exhausted
);
}
}
#[tokio::test]
async fn one_row_over_the_whole_budget_still_makes_progress() {
let oversized = SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT + 1;
let store = SqliteEventStore::open_in_memory().unwrap();
store.append(&seeded(2, 1, oversized), None).await.unwrap();
let mut cursor = cursor(&store, &Query::all());
let first = cursor.fetch_page().unwrap();
assert_eq!(
first.rows.len(),
1,
"a row bigger than the budget must still be yielded, one at a time"
);
assert!(!first.exhausted, "there is a second row to come");
cursor.advance(&first);
let second = cursor.fetch_page().unwrap();
assert_eq!(second.rows.len(), 1, "the second row followed the first");
}
#[tokio::test]
async fn a_page_takes_the_connection_once_per_statement() {
let store = SqliteEventStore::open_in_memory().unwrap();
let items = SqliteEventStore::MAX_QUERY_ARMS_PER_STATEMENT * 2 + 1;
let query = Query::from_items((0..items).map(|n| {
QueryItem::new(
Vec::<String>::new(),
Tags::from_pairs([("item", &format!("i{n}")[..])]).unwrap(),
)
.unwrap()
}))
.unwrap();
let statements = SqliteEventStore::planned_statement_count(&query);
assert!(statements > 1, "the fixture must cross the arm width");
store.append(&seeded(1, 1, 0), None).await.unwrap();
PAGE_CONNECTION_ACQUISITIONS.with(|taken| taken.set(0));
let _ = cursor(&store, &query).fetch_page().unwrap();
let taken = PAGE_CONNECTION_ACQUISITIONS.with(std::cell::Cell::get);
assert_eq!(
taken,
2 + statements,
"one page of a {statements}-statement plan took the connection {taken} times; \
the ceiling sample and the selectivity lookup are one each, and every statement \
of the plan is one more"
);
}
#[tokio::test]
async fn a_byte_cut_page_drops_no_event_across_statements() {
let per_row = SqliteEventStore::MAX_EVENT_DATA_LEN;
let fits = SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT / per_row;
let store = SqliteEventStore::open_in_memory().unwrap();
let seeded: Vec<Event> = (0..fits * 3)
.map(|n| {
let side = if n % 2 == 0 { "a" } else { "b" };
Event::new("Sized", vec![b'd'; per_row])
.unwrap()
.with_tags(Tags::from_pairs([("side", side)]).unwrap())
})
.collect();
let expected: Vec<SequencePosition> = {
store.append(&seeded, None).await.unwrap();
let head = store.head().await.unwrap().unwrap();
(1..=head.get()).filter_map(SequencePosition::new).collect()
};
let arms = SqliteEventStore::MAX_QUERY_ARMS_PER_STATEMENT;
let items = (0..=arms).map(|n| {
let tag = match n {
0 => "a".to_owned(),
n if n == arms => "b".to_owned(),
other => format!("absent{other}"),
};
QueryItem::new(
Vec::<String>::new(),
Tags::from_pairs([("side", &tag[..])]).unwrap(),
)
.unwrap()
});
let query = Query::from_items(items).unwrap();
assert!(
SqliteEventStore::planned_statement_count(&query) > 1,
"the fixture must span more than one statement"
);
let mut cursor = cursor(&store, &query);
let mut observed = Vec::new();
let mut pages = 0;
while !cursor.finished {
let page = cursor.fetch_page().unwrap();
assert!(
resident(&page) <= SqliteEventStore::MAX_PAGE_BYTES_PER_STATEMENT,
"page {pages} held {} B, over the budget",
resident(&page)
);
observed.extend(page.rows.iter().map(|event| event.position));
cursor.advance(&page);
pages += 1;
assert!(pages < 100, "the read stopped making progress");
}
assert_eq!(
observed, expected,
"a page cut by the byte budget dropped events the other statement would have supplied"
);
assert!(pages > 1, "the fixture must take more than one page");
}
}
#[cfg(test)]
mod plan_tests {
use happenstance_core::{Query, QueryItem, Tags};
use rusqlite::Connection;
use super::SqliteEventStore;
use crate::query_sql::{Selectivity, Window, page_statements};
fn seeded() -> Connection {
let mut connection = Connection::open_in_memory().expect("an in-memory database");
SqliteEventStore::migrate(&mut connection).expect("migrating must succeed");
let transaction = connection.transaction().expect("a transaction");
for position in 1..=5_000i64 {
transaction
.execute(
"INSERT INTO event (position, event_type, data, metadata, tags, \
origin_store, origin_position, recorded_at) \
VALUES (?, 'Seeded', X'00', NULL, X'1f', X'00000000000000000000000000000000', ?, 0)",
rusqlite::params![position, position],
)
.expect("an event row");
for tag in [
format!("subject:s{}", position % 100),
"shard:cold".to_owned(),
] {
transaction
.execute(
"INSERT INTO event_tag (tag, position, event_type) VALUES (?, ?, 'Seeded')",
rusqlite::params![tag, position],
)
.expect("a tag row");
}
}
transaction.commit().expect("the seed must commit");
connection
}
fn plan_rows(
connection: &Connection,
sql: &str,
params: &[rusqlite::types::Value],
) -> Vec<(i64, i64, String)> {
let mut statement = connection
.prepare(&format!("EXPLAIN QUERY PLAN {sql}"))
.expect("the plan must prepare");
statement
.query_map(rusqlite::params_from_iter(params.iter()), |row| {
Ok((row.get(0)?, row.get(1)?, row.get(3)?))
})
.expect("the plan must run")
.map(|row| row.expect("a plan row"))
.collect()
}
fn descends_from(rows: &[(i64, i64, String)], node: i64, ancestor: i64) -> bool {
let mut current = node;
for _ in 0..=rows.len() {
if current == ancestor {
return true;
}
match rows.iter().find(|(id, _, _)| *id == current) {
Some((_, parent, _)) if *parent != current => current = *parent,
_ => return false,
}
}
false
}
#[test]
fn the_page_plan_is_a_merge_and_not_a_sort() {
let connection = seeded();
let items = ["s1", "s2"]
.into_iter()
.map(|subject| {
let tags = Tags::from_pairs([("subject", subject), ("shard", "cold")])
.expect("two non-empty pairs");
QueryItem::tagged(tags).expect("a non-empty tag set")
})
.collect::<Vec<_>>();
let query = Query::from_items(items).expect("a non-empty item list");
let selectivity = Selectivity::read_for(
&connection,
&query,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)
.expect("the lookup must succeed");
let plan = page_statements(
&query,
&selectivity,
SqliteEventStore::MAX_QUERY_ARMS_PER_STATEMENT,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
Window {
lo: 1,
hi: 5_000,
budget: 512,
backwards: false,
},
crate::row::COLUMNS,
);
assert_eq!(plan.len(), 1);
let rows = plan_rows(&connection, &plan[0].0, &plan[0].1);
let rendered = rows
.iter()
.map(|(id, parent, detail)| format!("id={id} parent={parent} {detail}"))
.collect::<Vec<_>>()
.join("\n");
assert!(
rows.iter().any(|(_, _, detail)| detail.contains("MERGE")),
"the compound was not merged — the arms are being collected before \
the page is taken:\n{rendered}"
);
let Some(&(coroutine, _, _)) = rows
.iter()
.find(|(_, _, detail)| detail.contains("CO-ROUTINE"))
else {
panic!("no co-routine in the plan:\n{rendered}")
};
for (id, _, detail) in &rows {
assert!(
!(detail.contains("TEMP B-TREE") && descends_from(&rows, *id, coroutine)),
"a sorter sits inside the co-routine, so the whole matched set is \
being ordered before the page is taken:\n{rendered}"
);
}
}
#[test]
fn every_arm_seeks_into_its_tag_range_rather_than_rewinding() {
let connection = seeded();
let tags = Tags::from_pairs([("subject", "s1")]).expect("one non-empty pair");
let query = Query::from_item(QueryItem::tagged(tags).expect("a non-empty tag set"));
let selectivity = Selectivity::read_for(
&connection,
&query,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)
.expect("the lookup must succeed");
let plan = page_statements(
&query,
&selectivity,
SqliteEventStore::MAX_QUERY_ARMS_PER_STATEMENT,
SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
Window {
lo: 2_500,
hi: 5_000,
budget: 512,
backwards: false,
},
crate::row::COLUMNS,
);
let rows = plan_rows(&connection, &plan[0].0, &plan[0].1);
let rendered = rows
.iter()
.map(|(_, _, detail)| detail.clone())
.collect::<Vec<_>>()
.join("\n");
assert!(
rows.iter().any(|(_, _, detail)| {
detail.contains("SEARCH seed")
&& detail.contains("tag=?")
&& detail.contains("position>")
}),
"the arm's window did not reach the index:\n{rendered}"
);
}
}