use crate::fold::Fold;
use crate::part::Part;
use crate::types::Record;
use anyhow::Result;
use std::collections::{BTreeMap, HashSet};
use std::sync::Arc;
pub(crate) struct Visibility {
pub rows: Vec<Vec<usize>>,
pub superseded: usize,
pub tombstones: usize,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum RowOrigin {
Part { part: usize, row: usize },
Memtable,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct RowRef {
pub id: String,
pub origin: RowOrigin,
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct RowBatch {
pub rows: Vec<RowRef>,
pub physical_rows: usize,
pub superseded_rows: usize,
pub tombstones: usize,
pub memtable_entries: usize,
pub resolved_through: Option<String>,
pub has_more: bool,
pub budget_exhausted: bool,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct RowScan<'a> {
pub from: Option<&'a str>,
pub to: Option<&'a str>,
pub limit: usize,
pub reverse: bool,
pub max_resolution_entries: usize,
pub allow_oversized_group: bool,
}
pub(crate) fn scan_physical_scope(
parts: &[Arc<Part>],
from: Option<&str>,
to: Option<&str>,
) -> Result<crate::scan::ScanPhysicalScope> {
let mut scope = crate::scan::ScanPhysicalScope {
immutable_parts_considered: parts.len(),
..Default::default()
};
for part in parts {
let rows = part.rows_in_range(from, to)?;
if !rows.is_empty() {
scope.immutable_parts_with_rows += 1;
}
scope.immutable_rows_in_bounds = scope
.immutable_rows_in_bounds
.checked_add(rows.len())
.ok_or_else(|| anyhow::anyhow!("scan explanation physical-row count overflow"))?;
}
Ok(scope)
}
pub(crate) fn visibility(parts: &[Arc<Part>]) -> Result<Visibility> {
let mut rows: Vec<Vec<usize>> = vec![Vec::new(); parts.len()];
let mut seen: HashSet<String> = HashSet::new();
let (mut superseded, mut tombstones) = (0usize, 0usize);
for (pi, p) in parts.iter().enumerate().rev() {
let ids = p.ids()?;
let tombs = p.tombstones()?;
for (row, id) in ids.iter().enumerate() {
if !seen.insert(id.clone()) {
superseded += 1;
} else if tombs.binary_search(&(row as u64)).is_ok() {
tombstones += 1;
} else {
rows[pi].push(row);
}
}
}
Ok(Visibility { rows, superseded, tombstones })
}
pub fn get(parts: &[Arc<Part>], id: &str) -> Result<Option<Record>> {
match locate(parts, id)? {
Some((p, row)) => Ok(Some(p.record(row)?)),
None => Ok(None),
}
}
pub(crate) fn project_rows(
parts: &[Arc<Part>],
resolved: &[&RowRef],
attrs: &HashSet<&str>,
contents: &HashSet<&str>,
) -> Result<Vec<Record>> {
let mut grouped: BTreeMap<usize, Vec<(usize, usize, &RowRef)>> = BTreeMap::new();
for (output, resolved) in resolved.iter().enumerate() {
let RowOrigin::Part { part, row } = resolved.origin else {
anyhow::bail!("committed projection received a memtable row")
};
grouped.entry(part).or_default().push((output, row, resolved));
}
let mut out: Vec<Option<Record>> = vec![None; resolved.len()];
for (part_index, group) in grouped {
let part = parts.get(part_index).ok_or_else(|| {
anyhow::anyhow!("resolved part {part_index} is outside the immutable snapshot")
})?;
let rows: Vec<usize> = group.iter().map(|(_, row, _)| *row).collect();
for &row in &rows {
if row >= part.len() {
anyhow::bail!(
"resolved row {row} is outside part {part_index} with {} rows",
part.len()
);
}
}
let projected_attrs = part.attrs_selected_many(&rows, attrs)?;
let projected_contents = part.contents_selected_many(&rows, contents)?;
for (((output, _, resolved), attrs), contents) in
group.into_iter().zip(projected_attrs).zip(projected_contents)
{
out[output] = Some(Record { id: resolved.id.clone(), contents, attrs });
}
}
out.into_iter()
.map(|record| record.ok_or_else(|| anyhow::anyhow!("projected row was not produced")))
.collect()
}
pub fn reconstruct(parts: &[Arc<Part>], fold: &Fold, id: &str) -> Result<Option<Vec<u8>>> {
reconstruct_content(parts, fold, id, crate::types::BODY_CONTENT)
}
pub fn reconstruct_content(
parts: &[Arc<Part>],
fold: &Fold,
id: &str,
name: &str,
) -> Result<Option<Vec<u8>>> {
match locate(parts, id)? {
Some((p, row)) => p.reconstruct_content(row, name, fold),
None => Ok(None),
}
}
pub(crate) fn reconstruct_projected_content(
parts: &[Arc<Part>],
fold: &Fold,
resolved: &RowRef,
content: &crate::types::Content,
) -> Result<Vec<u8>> {
let RowOrigin::Part { part: part_index, row } = resolved.origin else {
anyhow::bail!("committed reconstruction received a memtable row")
};
let part = parts.get(part_index).ok_or_else(|| {
anyhow::anyhow!("resolved part {part_index} is outside the immutable snapshot")
})?;
if row >= part.len() {
anyhow::bail!(
"resolved row {} is outside part {} with {} rows",
row,
part_index,
part.len()
);
}
part.reconstruct_projected_content(content, fold)
}
pub fn exists(parts: &[Arc<Part>], id: &str) -> Result<bool> {
Ok(locate(parts, id)?.is_some())
}
fn locate<'a>(parts: &'a [Arc<Part>], id: &str) -> Result<Option<(&'a Arc<Part>, usize)>> {
for p in parts.iter().rev() {
if let Some(row) = p.find(id)? {
if p.is_tombstone(row)? {
return Ok(None);
}
return Ok(Some((p, row)));
}
}
Ok(None)
}
pub(crate) fn scan_rows<'a, I>(
parts: &[Arc<Part>],
mut overlay: I,
request: RowScan<'_>,
) -> Result<RowBatch>
where
I: Iterator<Item = (&'a str, bool)>,
{
if request.limit == 0 {
return Ok(RowBatch::default());
}
struct Walk {
range: std::ops::Range<usize>,
row: usize,
current: Option<String>,
}
let mut walks = Vec::with_capacity(parts.len());
for part in parts {
let range = part.rows_in_range(request.from, request.to)?;
let row = if request.reverse { range.end.saturating_sub(1) } else { range.start };
let current = if range.is_empty() { None } else { Some(part.id(row)?) };
walks.push(Walk { range, row, current });
}
let mut overlay_current = overlay.next();
let mut batch = RowBatch { rows: Vec::with_capacity(request.limit), ..RowBatch::default() };
while batch.rows.len() < request.limit {
let part_best = walks
.iter()
.filter_map(|walk| walk.current.as_ref())
.min_by(|a, b| if request.reverse { b.cmp(a) } else { a.cmp(b) })
.cloned();
let best = match (part_best, overlay_current.as_ref().map(|(id, _)| *id)) {
(Some(part), Some(overlay)) => {
let overlay_wins =
if request.reverse { overlay > part.as_str() } else { overlay < part.as_str() };
if overlay_wins {
overlay.to_owned()
} else {
part
}
}
(Some(part), None) => part,
(None, Some(overlay)) => overlay.to_owned(),
(None, None) => break,
};
let matching: Vec<usize> = walks
.iter()
.enumerate()
.filter_map(|(pi, walk)| (walk.current.as_deref() == Some(best.as_str())).then_some(pi))
.collect();
let overlay_matches = overlay_current.is_some_and(|(id, _)| id == best);
let group_entries = matching.len() + usize::from(overlay_matches);
let used = batch
.physical_rows
.checked_add(batch.memtable_entries)
.ok_or_else(|| anyhow::anyhow!("total row-resolution counter overflow"))?;
if group_entries > request.max_resolution_entries.saturating_sub(used)
&& (used > 0 || !request.allow_oversized_group)
{
batch.has_more = true;
batch.budget_exhausted = true;
break;
}
batch.physical_rows = batch
.physical_rows
.checked_add(matching.len())
.ok_or_else(|| anyhow::anyhow!("physical row-resolution counter overflow"))?;
if overlay_matches {
batch.memtable_entries = batch
.memtable_entries
.checked_add(1)
.ok_or_else(|| anyhow::anyhow!("memtable row-resolution counter overflow"))?;
batch.superseded_rows = batch
.superseded_rows
.checked_add(matching.len())
.ok_or_else(|| anyhow::anyhow!("superseded row-resolution counter overflow"))?;
if overlay_current.expect("the overlay id matched").1 {
batch.rows.push(RowRef { id: best.clone(), origin: RowOrigin::Memtable });
}
} else {
batch.superseded_rows = batch
.superseded_rows
.checked_add(matching.len().saturating_sub(1))
.ok_or_else(|| anyhow::anyhow!("superseded row-resolution counter overflow"))?;
let newest = *matching.last().expect("the selected id has at least one source part");
if !parts[newest].is_tombstone(walks[newest].row)? {
batch.rows.push(RowRef {
id: best.clone(),
origin: RowOrigin::Part { part: newest, row: walks[newest].row },
});
} else {
batch.tombstones = batch
.tombstones
.checked_add(1)
.ok_or_else(|| anyhow::anyhow!("tombstone row-resolution counter overflow"))?;
}
}
for pi in matching {
let walk = &mut walks[pi];
if request.reverse {
if walk.row == walk.range.start {
walk.current = None;
} else {
walk.row -= 1;
walk.current = Some(parts[pi].id(walk.row)?);
}
} else {
walk.row += 1;
if walk.row >= walk.range.end {
walk.current = None;
} else {
walk.current = Some(parts[pi].id(walk.row)?);
}
}
}
if overlay_matches {
overlay_current = overlay.next();
}
batch.resolved_through = Some(best);
let sources_remain =
overlay_current.is_some() || walks.iter().any(|walk| walk.current.is_some());
let used = batch
.physical_rows
.checked_add(batch.memtable_entries)
.ok_or_else(|| anyhow::anyhow!("total row-resolution counter overflow"))?;
if sources_remain && used >= request.max_resolution_entries {
batch.has_more = true;
batch.budget_exhausted = true;
break;
}
}
if !batch.has_more {
batch.has_more =
overlay_current.is_some() || walks.iter().any(|walk| walk.current.is_some());
}
Ok(batch)
}
pub fn scan_ids(
parts: &[Arc<Part>],
from: Option<&str>,
to: Option<&str>,
limit: usize,
reverse: bool,
) -> Result<Vec<String>> {
Ok(scan_rows(
parts,
std::iter::empty::<(&str, bool)>(),
RowScan {
from,
to,
limit,
reverse,
max_resolution_entries: usize::MAX,
allow_oversized_group: true,
},
)?
.rows
.into_iter()
.map(|row| row.id)
.collect())
}
pub fn ids(parts: &[Arc<Part>]) -> Result<Vec<String>> {
let visible = visibility(parts)?;
let mut out = Vec::new();
for (p, rows) in parts.iter().zip(&visible.rows) {
let listed = p.ids()?;
for &row in rows {
out.push(
listed
.get(row)
.ok_or_else(|| anyhow::anyhow!("visible row {row} is outside its part"))?
.clone(),
);
}
}
out.sort();
Ok(out)
}