use std::any::Any;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use arrow_array::RecordBatch;
use datafusion::common::ScalarValue;
use datafusion::physical_plan::SendableRecordBatchStream;
use datafusion::physical_plan::stream::RecordBatchStreamAdapter;
use lance_core::datatypes::Schema as LanceSchema;
use lance_core::{Error, Result};
use lance_file::version::ConcreteFileVersion;
use lance_index::IndexType;
use lance_index::scalar::ScalarIndexParams;
use lance_index::scalar::expression::ScalarQueryParser;
use lance_index::scalar::registry::TrainingCriteria;
use lance_io::object_store::ObjectStore;
use lance_table::format::IndexMetadata;
use object_store::path::Path;
use uuid::Uuid;
use super::RowPosition;
use super::query::{MemMatches, MemQuery, SearchContext};
use crate::Dataset;
use crate::dataset::INDICES_DIR;
use crate::dataset::mem_wal::memtable::batch_store::StoredBatch;
pub trait MemIndexParams: Any + Send + Sync + std::fmt::Debug {
fn same_as(&self, other: &dyn MemIndexParams) -> bool;
}
impl<T: Any + Send + Sync + std::fmt::Debug + PartialEq> MemIndexParams for T {
fn same_as(&self, other: &dyn MemIndexParams) -> bool {
(other as &dyn Any).downcast_ref::<T>() == Some(self)
}
}
pub struct MemIndexBuildContext<'a> {
pub name: &'a str,
pub schema: &'a LanceSchema,
pub field_ids: &'a [i32],
pub columns: &'a [String],
pub capacity_rows: usize,
pub capacity_batches: usize,
pub params: &'a dyn MemIndexParams,
}
impl MemIndexBuildContext<'_> {
pub fn single_column(&self) -> Result<(&str, i32)> {
match (self.columns, self.field_ids) {
([column], [field_id]) => Ok((column.as_str(), *field_id)),
_ => Err(Error::invalid_input(format!(
"index '{}' covers {} columns, but this kind covers exactly one",
self.name,
self.columns.len()
))),
}
}
pub fn check_columns_resolve(&self) -> Result<()> {
check_column_count(self.name, self.columns, self.field_ids)?;
for (column, field_id) in self.columns.iter().zip(self.field_ids) {
let field = self.schema.field(column).ok_or_else(|| {
Error::invalid_input(format!(
"index '{}' is configured on column '{}', which is not in the shard schema; \
available columns: [{}]",
self.name,
column,
self.schema
.fields
.iter()
.map(|f| f.name.as_str())
.collect::<Vec<_>>()
.join(", ")
))
})?;
if field.id != *field_id {
return Err(Error::invalid_input(format!(
"index '{}' is configured with field_id {field_id} but its column '{column}' \
has field_id {} in the shard schema",
self.name, field.id,
)));
}
}
Ok(())
}
pub fn check_top_level_columns(&self) -> Result<()> {
self.check_columns_resolve()?;
for column in self.columns {
if !self.schema.fields.iter().any(|field| &field.name == column) {
return Err(Error::invalid_input(format!(
"index '{}' covers the nested column '{column}'; this kind maintains only \
top-level columns",
self.name
)));
}
}
Ok(())
}
pub fn params<P: Any>(&self) -> Result<&P> {
downcast_params(self.name, self.params)
}
}
fn downcast_params<'a, P: Any>(name: &str, params: &'a dyn MemIndexParams) -> Result<&'a P> {
(params as &dyn Any).downcast_ref::<P>().ok_or_else(|| {
Error::internal(format!(
"index '{name}' was built with params of an unexpected type"
))
})
}
pub struct ResolveContext<'a> {
pub name: &'a str,
pub dataset: &'a Dataset,
pub index_meta: &'a IndexMetadata,
pub schema: &'a LanceSchema,
pub columns: &'a [String],
overrides: Option<&'a (dyn Any + Send + Sync)>,
overrides_read: AtomicBool,
}
impl<'a> ResolveContext<'a> {
pub(crate) fn new(
name: &'a str,
dataset: &'a Dataset,
index_meta: &'a IndexMetadata,
schema: &'a LanceSchema,
columns: &'a [String],
overrides: Option<&'a (dyn Any + Send + Sync)>,
) -> Self {
Self {
name,
dataset,
index_meta,
schema,
columns,
overrides,
overrides_read: AtomicBool::new(false),
}
}
pub fn overrides<P: Any>(&self) -> Result<Option<&P>> {
self.overrides_read.store(true, Ordering::Relaxed);
let Some(overrides) = self.overrides else {
return Ok(None);
};
overrides.downcast_ref::<P>().map(Some).ok_or_else(|| {
Error::invalid_input(format!(
"index '{}' was given writer settings of a type its plugin does not read; \
it reads {}",
self.name,
std::any::type_name::<P>()
))
})
}
pub(crate) fn overrides_ignored(&self) -> bool {
self.overrides.is_some() && !self.overrides_read.load(Ordering::Relaxed)
}
}
#[derive(Debug)]
pub struct ResolvedIndex {
pub columns: Vec<String>,
pub field_ids: Option<Vec<i32>>,
pub params: Arc<dyn MemIndexParams>,
}
impl ResolvedIndex {
pub fn plain(columns: Vec<String>) -> Self {
Self::with_params(columns, ())
}
pub fn with_params<P: MemIndexParams>(columns: Vec<String>, params: P) -> Self {
Self {
columns,
field_ids: None,
params: Arc::new(params),
}
}
pub fn with_field_ids(mut self, field_ids: Vec<i32>) -> Self {
self.field_ids = Some(field_ids);
self
}
}
pub struct GenerationWrite<'a> {
pub path: &'a Path,
pub object_store: &'a Arc<ObjectStore>,
pub dataset: &'a Dataset,
pub total_rows: usize,
pub name: &'a str,
pub storage_version: ConcreteFileVersion,
}
impl GenerationWrite<'_> {
pub fn new_index_dir(&self) -> (Uuid, Path) {
let uuid = Uuid::new_v4();
let dir = self.path.clone().join(INDICES_DIR).join(uuid.to_string());
(uuid, dir)
}
pub fn index_metadata(
&self,
uuid: Uuid,
field_ids: Vec<i32>,
index_details: prost_types::Any,
index_version: i32,
) -> IndexMetadata {
IndexMetadata {
uuid,
name: self.name.to_string(),
fields: field_ids,
covering_fields: vec![],
dataset_version: self.dataset.version().version,
fragment_bitmap: Some(self.dataset.fragment_bitmap.as_ref().clone()),
index_details: Some(Arc::new(index_details)),
index_version,
created_at: Some(chrono::Utc::now()),
base_id: None,
files: None,
}
}
}
pub struct FlushContext<'a> {
pub batch_size: usize,
pub generation: Option<&'a GenerationWrite<'a>>,
}
impl<'a> FlushContext<'a> {
pub fn training_only(batch_size: usize) -> Self {
Self {
batch_size,
generation: None,
}
}
pub fn generation(&self) -> Result<&'a GenerationWrite<'a>> {
self.generation.ok_or_else(|| {
Error::internal("an index that writes its own file was flushed with no generation")
})
}
}
pub enum FlushOutcome {
Skip,
BuildFromGeneration,
TrainingData(SendableRecordBatchStream),
Wrote(Box<IndexMetadata>),
}
impl FlushOutcome {
pub fn from_batches(batches: Vec<RecordBatch>) -> Self {
let Some(first) = batches.first() else {
return Self::BuildFromGeneration;
};
let schema = first.schema();
Self::TrainingData(Box::pin(RecordBatchStreamAdapter::new(
schema,
futures::stream::iter(batches.into_iter().map(Ok)),
)))
}
}
#[async_trait::async_trait]
pub trait MemIndex: Send + Sync + std::fmt::Debug + Any {
fn columns(&self) -> &[String];
fn can_answer(&self, query: &dyn MemQuery) -> bool;
fn insert(&self, batch: &RecordBatch, row_offset: RowPosition) -> Result<()>;
fn insert_batches(&self, batches: &[StoredBatch]) -> Result<()> {
batches
.iter()
.try_for_each(|stored| self.insert(&stored.data, stored.row_offset))
}
fn resident_bytes(&self) -> usize;
fn search(&self, query: &dyn MemQuery, ctx: &SearchContext) -> Result<Option<MemMatches>>;
async fn flush(&self, ctx: &FlushContext<'_>) -> Result<FlushOutcome>;
fn as_primary_key(self: Arc<Self>) -> Option<Arc<dyn PrimaryKeyIndex>> {
None
}
}
pub trait PrimaryKeyIndex: Send + Sync {
fn insert_and_report_existing(
&self,
batch: &RecordBatch,
row_offset: RowPosition,
) -> Result<bool>;
fn newest_visible(&self, key: &ScalarValue, max_visible: RowPosition) -> Option<RowPosition>;
fn training_batches(&self, batch_size: usize) -> Result<Vec<RecordBatch>>;
fn is_empty(&self) -> bool;
}
#[async_trait::async_trait]
pub trait MemIndexPlugin: Send + Sync + std::fmt::Debug + Any {
fn name(&self) -> &str;
fn details_message(&self) -> &str;
fn version(&self) -> u32 {
1
}
fn flush_index_type(&self) -> IndexType;
fn training_criteria(&self) -> TrainingCriteria;
fn flush_params(&self, _spec: &MemIndexSpec) -> Result<ScalarIndexParams> {
Ok(ScalarIndexParams::default())
}
fn query_parser(
&self,
_index_name: String,
_params: &dyn MemIndexParams,
) -> Option<Box<dyn ScalarQueryParser>> {
None
}
async fn resolve(&self, ctx: &ResolveContext<'_>) -> Result<ResolvedIndex> {
Ok(ResolvedIndex::plain(ctx.columns.to_vec()))
}
fn validate(&self, ctx: &MemIndexBuildContext<'_>) -> Result<()>;
fn create(&self, ctx: &MemIndexBuildContext<'_>) -> Result<Arc<dyn MemIndex>>;
}
#[derive(Debug, Clone)]
pub struct MemIndexRegistry {
plugins: Vec<Arc<dyn MemIndexPlugin>>,
}
impl MemIndexRegistry {
pub fn empty() -> Self {
Self {
plugins: Vec::new(),
}
}
pub fn add_plugin(&mut self, plugin: Arc<dyn MemIndexPlugin>) -> Result<()> {
check_details_message(plugin.as_ref())?;
let message = plugin.details_message();
if let Some(existing) = self
.plugins
.iter()
.find(|other| other.details_message() == message)
{
return Err(Error::invalid_input(format!(
"plugin '{}' claims details message '{message}', which '{}' already claims",
plugin.name(),
existing.name(),
)));
}
self.plugins.push(plugin);
Ok(())
}
pub fn with_plugin(mut self, plugin: Arc<dyn MemIndexPlugin>) -> Result<Self> {
self.add_plugin(plugin)?;
Ok(self)
}
pub fn replace_plugin(&mut self, plugin: Arc<dyn MemIndexPlugin>) -> Result<()> {
check_details_message(plugin.as_ref())?;
self.plugins
.retain(|other| other.details_message() != plugin.details_message());
self.plugins.push(plugin);
Ok(())
}
pub fn plugin_for_details_url(&self, type_url: &str) -> Option<&Arc<dyn MemIndexPlugin>> {
let message = type_url.rsplit(['/', '.']).next().unwrap_or(type_url);
self.plugins
.iter()
.find(|plugin| plugin.details_message() == message)
}
pub fn plugins(&self) -> &[Arc<dyn MemIndexPlugin>] {
&self.plugins
}
}
fn check_details_message(plugin: &dyn MemIndexPlugin) -> Result<()> {
let message = plugin.details_message();
if message.is_empty() || message.contains(['.', '/']) {
return Err(Error::invalid_input(format!(
"plugin '{}' claims details message '{message}', which is not a bare message name",
plugin.name()
)));
}
Ok(())
}
#[derive(Clone)]
pub struct MemIndexSpec {
pub name: String,
pub field_ids: Vec<i32>,
pub columns: Vec<String>,
pub plugin: Arc<dyn MemIndexPlugin>,
pub params: Arc<dyn MemIndexParams>,
}
impl MemIndexSpec {
pub fn for_plugin(
name: impl Into<String>,
field_id: i32,
column: impl Into<String>,
plugin: Arc<dyn MemIndexPlugin>,
) -> Self {
Self::single_column(name, field_id, column, plugin, Arc::new(()))
}
pub fn single_column(
name: impl Into<String>,
field_id: i32,
column: impl Into<String>,
plugin: Arc<dyn MemIndexPlugin>,
params: Arc<dyn MemIndexParams>,
) -> Self {
Self {
name: name.into(),
field_ids: vec![field_id],
columns: vec![column.into()],
plugin,
params,
}
}
pub fn same_index(&self, other: &Self) -> bool {
self.name == other.name
&& self.columns == other.columns
&& self.field_ids == other.field_ids
&& (self.plugin.as_ref() as &dyn Any).type_id()
== (other.plugin.as_ref() as &dyn Any).type_id()
&& self.plugin.details_message() == other.plugin.details_message()
&& self.plugin.version() == other.plugin.version()
&& self.params.same_as(other.params.as_ref())
}
pub fn params<P: Any>(&self) -> Result<&P> {
downcast_params(&self.name, self.params.as_ref())
}
fn build_context<'a>(
&'a self,
schema: &'a LanceSchema,
capacity_rows: usize,
capacity_batches: usize,
) -> MemIndexBuildContext<'a> {
MemIndexBuildContext {
name: &self.name,
schema,
field_ids: &self.field_ids,
columns: &self.columns,
capacity_rows,
capacity_batches,
params: self.params.as_ref(),
}
}
pub fn validate(&self, schema: &LanceSchema) -> Result<()> {
check_column_count(&self.name, &self.columns, &self.field_ids)?;
self.plugin.validate(&self.build_context(schema, 0, 0))?;
if self.plugin.flush_index_type().is_scalar() {
self.plugin.flush_params(self)?;
}
Ok(())
}
pub fn build(
&self,
schema: &LanceSchema,
capacity_rows: usize,
capacity_batches: usize,
) -> Result<Arc<dyn MemIndex>> {
check_column_count(&self.name, &self.columns, &self.field_ids)?;
self.plugin
.create(&self.build_context(schema, capacity_rows, capacity_batches))
}
}
fn check_column_count(name: &str, columns: &[String], field_ids: &[i32]) -> Result<()> {
if columns.len() != field_ids.len() {
return Err(Error::invalid_input(format!(
"index '{name}' names {} columns but {} field ids",
columns.len(),
field_ids.len()
)));
}
Ok(())
}
impl std::fmt::Debug for MemIndexSpec {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("MemIndexSpec")
.field("name", &self.name)
.field("columns", &self.columns)
.field("field_ids", &self.field_ids)
.field("plugin", &self.plugin.name())
.field("version", &self.plugin.version())
.field("params", &self.params)
.finish()
}
}