use std::collections::{BTreeSet, HashMap};
use std::fmt::Write as _;
use happenstance_core::{Query, QueryItem};
use rusqlite::Connection;
use rusqlite::types::Value;
#[derive(Debug, Default)]
pub(crate) struct Selectivity(HashMap<String, i64>);
impl Selectivity {
pub(crate) fn read_for(
connection: &Connection,
query: &Query,
max_parameters: usize,
) -> rusqlite::Result<Self> {
let mut wanted: BTreeSet<&str> = BTreeSet::new();
for item in query.items().unwrap_or_default() {
let tags = item.tags();
if tags.len() > 1 {
for tag in tags {
wanted.insert(tag.as_str());
}
}
}
if wanted.is_empty() {
return Ok(Self::default());
}
let wanted: Vec<&str> = wanted.into_iter().collect();
let mut counts = HashMap::with_capacity(wanted.len());
for batch in wanted.chunks(max_parameters.max(1)) {
let sql = format!(
"SELECT tag, events FROM tag_cardinality WHERE tag IN ({})",
placeholders(batch.len())
);
let mut statement = connection.prepare(&sql)?;
let mut rows = statement.query(rusqlite::params_from_iter(batch.iter()))?;
while let Some(row) = rows.next()? {
counts.insert(row.get::<_, String>(0)?, row.get::<_, i64>(1)?);
}
}
Ok(Self(counts))
}
fn most_selective_first(&self, mut tags: Vec<String>) -> Vec<String> {
tags.sort_by_key(|tag| self.0.get(tag).copied().unwrap_or(0));
tags
}
}
pub(crate) fn chunks(
query: &Query,
selectivity: &Selectivity,
max_arms: usize,
max_parameters: usize,
bound: Option<i64>,
) -> Vec<(String, Vec<Value>)> {
match query.items() {
None => match bound {
None => vec![("SELECT position FROM event".to_owned(), Vec::new())],
Some(boundary) => vec![(
"SELECT position FROM event WHERE position > ?".to_owned(),
vec![Value::Integer(boundary)],
)],
},
Some(items) => partition(
items,
max_arms.max(1),
max_parameters.max(1),
usize::from(bound.is_some()),
)
.into_iter()
.map(|chunk| {
let mut params = Vec::new();
let sql = arms_sql(chunk, selectivity, bound, &mut params);
(sql, params)
})
.collect(),
}
}
fn partition(
items: &[QueryItem],
max_arms: usize,
max_parameters: usize,
per_arm_extra: usize,
) -> Vec<&[QueryItem]> {
let mut out = Vec::new();
let mut start = 0;
let mut arms = 0;
let mut parameters = 0;
for (index, item) in items.iter().enumerate() {
let cost = item_parameters(item) + per_arm_extra;
if arms > 0 && (arms == max_arms || parameters + cost > max_parameters) {
out.push(&items[start..index]);
start = index;
arms = 0;
parameters = 0;
}
arms += 1;
parameters += cost;
}
out.push(&items[start..]);
out
}
fn item_parameters(item: &QueryItem) -> usize {
item.tags().len() + item.types().len()
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Window {
pub(crate) lo: i64,
pub(crate) hi: i64,
pub(crate) budget: i64,
pub(crate) backwards: bool,
}
pub(crate) fn page_statements(
query: &Query,
selectivity: &Selectivity,
max_arms: usize,
max_parameters: usize,
window: Window,
columns: &str,
) -> Vec<(String, Vec<Value>)> {
let max_arms = max_arms.max(1);
let direction = if window.backwards { "DESC" } else { "ASC" };
let Some(items) = query.items() else {
return vec![(
format!(
"SELECT {columns} FROM event WHERE position >= ? AND position <= ? \
ORDER BY position {direction} LIMIT ?"
),
vec![
Value::Integer(window.lo),
Value::Integer(window.hi),
Value::Integer(window.budget),
],
)];
};
partition(items, max_arms, max_parameters.saturating_sub(1).max(1), 2)
.into_iter()
.map(|chunk| {
let mut params = Vec::new();
let compound = windowed_arms_sql(chunk, selectivity, window, &mut params);
let sql = format!(
"SELECT {} FROM event JOIN ({compound}) AS m \
ON m.position = event.position ORDER BY event.position {direction}",
qualified(columns)
);
(sql, params)
})
.collect()
}
fn windowed_arms_sql(
items: &[QueryItem],
selectivity: &Selectivity,
window: Window,
params: &mut Vec<Value>,
) -> String {
let direction = if window.backwards { "DESC" } else { "ASC" };
let arms = if items.is_empty() {
"SELECT position FROM event WHERE 0".to_owned()
} else {
items
.iter()
.map(|item| windowed_item_sql(item, selectivity, window, params))
.collect::<Vec<_>>()
.join(" UNION ")
};
params.push(Value::Integer(window.budget));
format!("{arms} ORDER BY position {direction} LIMIT ?")
}
fn windowed_item_sql(
item: &QueryItem,
selectivity: &Selectivity,
window: Window,
params: &mut Vec<Value>,
) -> String {
let tags = selectivity.most_selective_first(owned_tags(item));
let types = item.types();
if tags.is_empty() {
let mut sql =
String::from("SELECT position FROM event WHERE position >= ? AND position <= ?");
params.push(Value::Integer(window.lo));
params.push(Value::Integer(window.hi));
if !types.is_empty() {
for event_type in types {
params.push(Value::Text(event_type.as_str().to_owned()));
}
write!(sql, " AND event_type IN ({})", placeholders(types.len()))
.expect("writing to a String cannot fail");
}
return sql;
}
let mut sql =
String::from("SELECT seed.position AS position FROM event_tag AS seed WHERE seed.tag = ?");
params.push(Value::Text(tags[0].clone()));
if !types.is_empty() {
for event_type in types {
params.push(Value::Text(event_type.as_str().to_owned()));
}
write!(
sql,
" AND seed.event_type IN ({})",
placeholders(types.len())
)
.expect("writing to a String cannot fail");
}
params.push(Value::Integer(window.lo));
params.push(Value::Integer(window.hi));
sql.push_str(" AND seed.position >= ? AND seed.position <= ?");
for (index, tag) in tags[1..].iter().enumerate() {
params.push(Value::Text(tag.clone()));
write!(
sql,
" AND EXISTS (SELECT 1 FROM event_tag AS m{index} WHERE m{index}.tag = ? \
AND m{index}.position = seed.position)"
)
.expect("writing to a String cannot fail");
}
sql
}
fn qualified(columns: &str) -> String {
columns
.split(',')
.map(|column| format!("event.{}", column.trim()))
.collect::<Vec<_>>()
.join(", ")
}
pub(crate) fn arms_sql(
items: &[QueryItem],
selectivity: &Selectivity,
bound: Option<i64>,
params: &mut Vec<Value>,
) -> String {
if items.is_empty() {
return "SELECT position FROM event WHERE 0".to_owned();
}
items
.iter()
.map(|item| item_sql(item, selectivity, bound, params))
.collect::<Vec<_>>()
.join(" UNION ")
}
fn item_sql(
item: &QueryItem,
selectivity: &Selectivity,
bound: Option<i64>,
params: &mut Vec<Value>,
) -> String {
let tags = selectivity.most_selective_first(owned_tags(item));
let types = item.types();
if tags.is_empty() {
if types.is_empty() {
return match bound {
None => "SELECT position FROM event".to_owned(),
Some(boundary) => {
params.push(Value::Integer(boundary));
"SELECT position FROM event WHERE position > ?".to_owned()
}
};
}
for event_type in types {
params.push(Value::Text(event_type.as_str().to_owned()));
}
let mut sql = format!(
"SELECT position FROM event WHERE event_type IN ({})",
placeholders(types.len())
);
if let Some(boundary) = bound {
params.push(Value::Integer(boundary));
sql.push_str(" AND position > ?");
}
return sql;
}
let mut sql =
String::from("SELECT seed.position AS position FROM event_tag AS seed WHERE seed.tag = ?");
params.push(Value::Text(tags[0].clone()));
if !types.is_empty() {
for event_type in types {
params.push(Value::Text(event_type.as_str().to_owned()));
}
sql.push_str(" AND seed.event_type IN (");
sql.push_str(&placeholders(types.len()));
sql.push(')');
}
if let Some(boundary) = bound {
params.push(Value::Integer(boundary));
sql.push_str(" AND seed.position > ?");
}
for (index, tag) in tags[1..].iter().enumerate() {
params.push(Value::Text(tag.clone()));
write!(
sql,
" AND EXISTS (SELECT 1 FROM event_tag AS m{index} \
WHERE m{index}.tag = ? AND m{index}.position = seed.position)"
)
.expect("writing to a String cannot fail");
}
sql
}
fn owned_tags(item: &QueryItem) -> Vec<String> {
item.tags()
.iter()
.map(|tag| tag.as_str().to_owned())
.collect()
}
pub(crate) fn placeholders(n: usize) -> String {
let mut out = String::with_capacity(n * 2);
for i in 0..n {
if i > 0 {
out.push(',');
}
out.push('?');
}
out
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used)]
use std::time::Instant;
use happenstance_core::Tags;
use super::*;
const ITEMS: usize = 128;
const TAGS_PER_ITEM: usize = 128;
const MINIMUM_SPEEDUP: u32 = 5;
fn floor_query() -> Query {
let items = (0..ITEMS).map(|item| {
let pairs: Vec<(String, String)> = (0..TAGS_PER_ITEM)
.map(|tag| (format!("k{item:03}"), format!("v{tag:03}")))
.collect();
let tags = Tags::from_pairs(
pairs
.iter()
.map(|(key, value)| (key.as_str(), value.as_str())),
)
.unwrap();
QueryItem::new(Vec::<String>::new(), tags).unwrap()
});
Query::from_items(items).unwrap()
}
fn planning_connection() -> Connection {
let connection = Connection::open_in_memory().unwrap();
connection
.execute_batch(
"CREATE TABLE tag_cardinality (tag TEXT PRIMARY KEY, events INTEGER NOT NULL) \
WITHOUT ROWID;",
)
.unwrap();
connection
}
fn read_for_quadratic(
connection: &Connection,
query: &Query,
max_parameters: usize,
) -> rusqlite::Result<Selectivity> {
fn distinct_tags_quadratic(item: &QueryItem) -> Vec<String> {
let mut out: Vec<String> = Vec::with_capacity(item.tags().len());
for tag in item.tags() {
let value = tag.as_str().to_owned();
if !out.contains(&value) {
out.push(value);
}
}
out
}
let mut wanted: Vec<String> = Vec::new();
for item in query.items().unwrap_or_default() {
let tags = distinct_tags_quadratic(item);
if tags.len() > 1 {
for tag in tags {
if !wanted.contains(&tag) {
wanted.push(tag);
}
}
}
}
if wanted.is_empty() {
return Ok(Selectivity::default());
}
let mut counts = HashMap::with_capacity(wanted.len());
for batch in wanted.chunks(max_parameters.max(1)) {
let sql = format!(
"SELECT tag, events FROM tag_cardinality WHERE tag IN ({})",
placeholders(batch.len())
);
let mut statement = connection.prepare(&sql)?;
let mut rows = statement.query(rusqlite::params_from_iter(batch.iter()))?;
while let Some(row) = rows.next()? {
counts.insert(row.get::<_, String>(0)?, row.get::<_, i64>(1)?);
}
}
Ok(Selectivity(counts))
}
#[test]
fn the_selectivity_lookup_agrees_with_the_quadratic_and_is_faster_than_it() {
let connection = planning_connection();
let query = floor_query();
let expected = read_for_quadratic(
&connection,
&query,
crate::event_store::SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)
.unwrap();
let actual = Selectivity::read_for(
&connection,
&query,
crate::event_store::SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)
.unwrap();
assert_eq!(
actual.0, expected.0,
"the shipped lookup answers a different question from the one it replaced"
);
let started = Instant::now();
read_for_quadratic(
&connection,
&query,
crate::event_store::SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)
.unwrap();
let quadratic = started.elapsed();
let shipped = (0..3)
.map(|_| {
let started = Instant::now();
Selectivity::read_for(
&connection,
&query,
crate::event_store::SqliteEventStore::MAX_QUERY_PARAMETERS_PER_STATEMENT,
)
.unwrap();
started.elapsed()
})
.min()
.unwrap();
assert!(
quadratic >= shipped * MINIMUM_SPEEDUP,
"at VT-23's floor ({ITEMS} items x {TAGS_PER_ITEM} tags) the shipped selectivity \
lookup took {shipped:?} against the quadratic's {quadratic:?}, which is under the \
{MINIMUM_SPEEDUP}x this asserts; the accumulation is quadratic in the query's \
distinct tags again"
);
}
#[test]
fn a_query_items_tags_are_already_canonical() {
fn distinct_tags_quadratic(item: &QueryItem) -> Vec<String> {
let mut out: Vec<String> = Vec::with_capacity(item.tags().len());
for tag in item.tags() {
let value = tag.as_str().to_owned();
if !out.contains(&value) {
out.push(value);
}
}
out
}
for pairs in [
vec![("course", "c1"), ("course", "c1")],
vec![("course", "c1"), ("course", "c10")],
vec![("course", "c1"), ("student", "s1"), ("course", "c1")],
vec![("a", "b"), ("a", "bc"), ("ab", "c")],
] {
let tags = Tags::from_pairs(pairs.iter().copied()).unwrap();
let item = QueryItem::new(Vec::<String>::new(), tags).unwrap();
assert_eq!(
owned_tags(&item),
distinct_tags_quadratic(&item),
"the dedup removed something, so it was not dead work: {pairs:?}"
);
assert_eq!(
item_parameters(&item),
distinct_tags_quadratic(&item).len() + item.types().len(),
"the parameter count parted company with what `item_sql` will bind: {pairs:?}"
);
}
}
const COLUMNS: &str = "position, event_type";
const WIDE: usize = usize::MAX;
fn tagged_query() -> Query {
let tags = Tags::from_pairs([("subject", "s1")]).expect("two non-empty strings");
Query::from_items(vec![QueryItem::tagged(tags).expect("a non-empty tag set")])
.expect("a non-empty item list")
}
fn window() -> Window {
Window {
lo: 7,
hi: 900,
budget: 512,
backwards: false,
}
}
#[test]
fn an_all_query_pages_without_a_join() {
let plan = page_statements(
&Query::all(),
&Selectivity::default(),
8,
WIDE,
window(),
COLUMNS,
);
assert_eq!(plan.len(), 1);
assert_eq!(
plan[0].0,
"SELECT position, event_type FROM event \
WHERE position >= ? AND position <= ? ORDER BY position ASC LIMIT ?"
);
assert_eq!(plan[0].1.len(), 3);
}
#[test]
fn a_tagged_page_carries_the_window_per_arm_and_the_budget_on_the_compound() {
let plan = page_statements(
&tagged_query(),
&Selectivity::default(),
8,
WIDE,
window(),
COLUMNS,
);
assert_eq!(plan.len(), 1);
let sql = &plan[0].0;
assert!(
sql.contains("seed.position >= ? AND seed.position <= ?"),
"the arm lost its window: {sql}"
);
assert_eq!(sql.matches(" LIMIT ?").count(), 1, "{sql}");
assert!(sql.contains("ORDER BY position ASC LIMIT ?"), "{sql}");
assert!(
sql.contains(") AS m ON m.position = event.position"),
"{sql}"
);
assert!(!sql.contains("position IN ("), "{sql}");
assert!(sql.starts_with("SELECT event.position, event.event_type FROM event JOIN ("));
}
#[test]
fn backwards_orders_the_compound_and_the_page_alike() {
let mut window = window();
window.backwards = true;
let plan = page_statements(
&tagged_query(),
&Selectivity::default(),
8,
WIDE,
window,
COLUMNS,
);
let sql = &plan[0].0;
assert!(sql.contains("ORDER BY position DESC LIMIT ?"), "{sql}");
assert!(sql.ends_with("ORDER BY event.position DESC"), "{sql}");
assert_eq!(sql.matches("ASC").count(), 0, "{sql}");
}
#[test]
fn a_wide_query_chunks_and_every_chunk_keeps_the_full_budget() {
let items = (0..5)
.map(|index| {
let value = format!("s{index}");
let tags =
Tags::from_pairs([("subject", value.as_str())]).expect("non-empty strings");
QueryItem::tagged(tags).expect("a non-empty tag set")
})
.collect::<Vec<_>>();
let query = Query::from_items(items).expect("a non-empty item list");
let plan = page_statements(&query, &Selectivity::default(), 2, WIDE, window(), COLUMNS);
assert_eq!(plan.len(), 3);
for (sql, params) in &plan {
assert_eq!(sql.matches(" LIMIT ?").count(), 1, "{sql}");
assert_eq!(params.last(), Some(&Value::Integer(512)), "{sql}");
}
}
#[test]
fn the_guard_still_binds_its_boundary() {
let unbounded = chunks(&Query::all(), &Selectivity::default(), 8, WIDE, None);
assert_eq!(unbounded[0].0, "SELECT position FROM event");
assert!(unbounded[0].1.is_empty());
let bounded = chunks(&Query::all(), &Selectivity::default(), 8, WIDE, Some(41));
assert_eq!(
bounded[0].0,
"SELECT position FROM event WHERE position > ?"
);
assert_eq!(bounded[0].1.len(), 1);
}
}