use std::collections::{HashMap, HashSet};
use std::path::{Path, PathBuf};
use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant, SystemTime};
use anyhow::{Context, Result};
use tracing::{debug, info, warn};
use crate::embedding::EmbeddingProvider;
use crate::retrieval::bm25::search_bm25_with_stores_and_filters;
use crate::retrieval::graph_augmentation::augment_pool;
use crate::retrieval::query_classifier::{QueryType, classify_query, params_for_query_type};
use crate::retrieval::query_utils::result_key;
use crate::retrieval::ranking::is_path_weighted_query;
use crate::retrieval::reranker::{Reranker, rerank_results};
use crate::retrieval::vector::{
VectorSearchError, search_vector_with_cached_stores_timed, search_vector_with_stores_timed,
};
use crate::storage::bm25::Bm25Index;
use crate::storage::metadata::MetadataStore;
use crate::storage::vector::VectorStore;
use crate::types::{SearchFilters, SearchResult};
pub(crate) struct SearchStores {
pub(crate) bm25: Bm25Index,
pub(crate) bm25_metadata: Mutex<MetadataStore>,
pub(crate) vector_metadata: Mutex<MetadataStore>,
vector_path: PathBuf,
vector: Mutex<Option<CachedVectorStore>>,
metadata_path: PathBuf,
indexed_files: Mutex<Option<CachedIndexedFiles>>,
}
struct CachedIndexedFiles {
stamp: MetadataDbStamp,
files: Arc<Vec<String>>,
}
#[derive(Clone, Copy, PartialEq, Eq)]
struct MetadataDbStamp {
db_len: Option<u64>,
db_mtime: Option<SystemTime>,
wal_len: Option<u64>,
wal_mtime: Option<SystemTime>,
}
fn metadata_db_stamp(db_path: &Path) -> MetadataDbStamp {
let wal_path = db_path.with_file_name(format!(
"{}-wal",
db_path
.file_name()
.map(|name| name.to_string_lossy().into_owned())
.unwrap_or_default()
));
let stats = |path: &Path| {
std::fs::metadata(path)
.ok()
.map(|metadata| (metadata.len(), metadata.modified().ok()))
};
let (db_len, db_mtime) = stats(db_path).map_or((None, None), |(len, mtime)| (Some(len), mtime));
let (wal_len, wal_mtime) =
stats(&wal_path).map_or((None, None), |(len, mtime)| (Some(len), mtime));
MetadataDbStamp {
db_len,
db_mtime,
wal_len,
wal_mtime,
}
}
struct CachedVectorStore {
dim: usize,
stamp: VectorStoreStamp,
store: Arc<Mutex<VectorStore>>,
}
#[derive(Clone, Copy, PartialEq, Eq)]
struct VectorStoreStamp {
db_len: Option<u64>,
db_mtime: Option<SystemTime>,
manifest_mtime: Option<SystemTime>,
manifest_generation: Option<u64>,
}
fn vector_store_stamp(vector_path: &Path) -> VectorStoreStamp {
let db_metadata = std::fs::metadata(vector_path).ok();
let manifest_path = vector_path.with_file_name("vectors.manifest");
let manifest_mtime = std::fs::metadata(&manifest_path)
.and_then(|metadata| metadata.modified())
.ok();
let manifest_generation = std::fs::read(&manifest_path)
.ok()
.and_then(|bytes| serde_json::from_slice::<serde_json::Value>(&bytes).ok())
.and_then(|manifest| {
manifest
.get("generation")
.and_then(serde_json::Value::as_u64)
});
VectorStoreStamp {
db_len: db_metadata.as_ref().map(std::fs::Metadata::len),
db_mtime: db_metadata.and_then(|metadata| metadata.modified().ok()),
manifest_mtime,
manifest_generation,
}
}
impl SearchStores {
pub(crate) fn open(index_dir: &Path) -> Result<Self> {
let bm25 = Bm25Index::open(&index_dir.join("bm25"))
.context("failed to open BM25 index for search")?;
let metadata_path = index_dir.join("metadata.db");
let bm25_metadata = MetadataStore::open(&metadata_path)
.context("failed to open metadata store for search")?;
let vector_metadata = MetadataStore::open(&metadata_path)
.context("failed to open vector metadata store for search")?;
Ok(Self {
bm25,
bm25_metadata: Mutex::new(bm25_metadata),
vector_metadata: Mutex::new(vector_metadata),
vector_path: index_dir.join("vectors.db"),
vector: Mutex::new(None),
metadata_path,
indexed_files: Mutex::new(None),
})
}
pub(crate) fn indexed_files(&self) -> Result<Arc<Vec<String>>> {
let stamp = metadata_db_stamp(&self.metadata_path);
{
let cached = self
.indexed_files
.lock()
.map_err(|_| anyhow::anyhow!("indexed files cache lock poisoned"))?;
if let Some(cached) = cached.as_ref()
&& cached.stamp == stamp
{
return Ok(Arc::clone(&cached.files));
}
}
let files = Arc::new(
MetadataStore::open(&self.metadata_path)
.context("failed to open metadata store for file list")?
.indexed_files()?,
);
let mut cached = self
.indexed_files
.lock()
.map_err(|_| anyhow::anyhow!("indexed files cache lock poisoned"))?;
*cached = Some(CachedIndexedFiles {
stamp,
files: Arc::clone(&files),
});
Ok(files)
}
pub(crate) fn vector_store(&self, dim: usize) -> Result<Arc<Mutex<VectorStore>>> {
let mut cached = self
.vector
.lock()
.map_err(|_| anyhow::anyhow!("vector store cache lock poisoned"))?;
let stamp = vector_store_stamp(&self.vector_path);
if let Some(cached_store) = cached.as_ref()
&& cached_store.dim == dim
&& cached_store.stamp == stamp
{
return Ok(Arc::clone(&cached_store.store));
}
let store = Arc::new(Mutex::new(
VectorStore::open(&self.vector_path, dim).context("failed to open vector store")?,
));
let stamp = vector_store_stamp(&self.vector_path);
*cached = Some(CachedVectorStore {
dim,
stamp,
store: Arc::clone(&store),
});
Ok(store)
}
}
#[derive(Debug, thiserror::Error)]
pub enum HybridSearchError {
#[error("both BM25 and vector search failed: bm25={bm25_error}, vector={vector_error}")]
BothFailed {
bm25_error: String,
vector_error: String,
},
#[error("{0}")]
PipelineError(#[from] anyhow::Error),
}
pub fn compute_vector_candidates(limit: usize, multiplier: usize) -> usize {
limit.saturating_mul(multiplier).max(50)
}
fn compute_bm25_candidates(query: &str, limit: usize) -> usize {
let query_type = classify_query(query);
let token_count = query.split_whitespace().count();
if is_path_weighted_query(query) {
return limit.saturating_mul(5).max(100);
}
if query_type == QueryType::NaturalLanguage {
return limit.saturating_mul(4).max(limit + 40);
}
if token_count <= 2 {
return limit.saturating_mul(4).max(80);
}
limit.saturating_mul(3).max(limit + 20)
}
#[derive(Debug, Default)]
pub struct HybridTimings {
pub embedding: Option<Duration>,
pub bm25: Option<Duration>,
pub vector: Option<Duration>,
pub fusion: Option<Duration>,
pub reranking: Option<Duration>,
}
#[allow(clippy::too_many_arguments)]
pub async fn search_hybrid(
index_dir: &Path,
provider: &impl EmbeddingProvider,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
limit: usize,
rrf_k: f64,
stored_dim: usize,
vector_candidates: usize,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
search_hybrid_inner(
index_dir,
provider,
bm25_query,
vector_query,
filters,
limit,
rrf_k,
stored_dim,
vector_candidates,
None,
)
.await
}
#[allow(clippy::too_many_arguments)]
pub(crate) async fn search_hybrid_with_stores(
index_dir: &Path,
provider: &impl EmbeddingProvider,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
limit: usize,
rrf_k: f64,
stored_dim: usize,
vector_candidates: usize,
stores: Arc<SearchStores>,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
search_hybrid_inner(
index_dir,
provider,
bm25_query,
vector_query,
filters,
limit,
rrf_k,
stored_dim,
vector_candidates,
Some(stores),
)
.await
}
#[allow(clippy::too_many_arguments)]
async fn search_hybrid_inner(
index_dir: &Path,
provider: &impl EmbeddingProvider,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
limit: usize,
rrf_k: f64,
stored_dim: usize,
vector_candidates: usize,
stores: Option<Arc<SearchStores>>,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
let query_type = classify_query(bm25_query);
let query_params = params_for_query_type(query_type);
let bm25_candidates = compute_bm25_candidates(bm25_query, limit);
let mut timings = HybridTimings::default();
let bm25_dir = index_dir.join("bm25");
let metadata_path = index_dir.join("metadata.db");
let bm25_query = bm25_query.to_string();
let bm25_filters = filters.clone();
let stores_for_bm25 = stores.clone();
let bm25_handle = tokio::task::spawn_blocking(move || {
let start = Instant::now();
let result = match stores_for_bm25 {
Some(stores) => stores
.bm25_metadata
.lock()
.map_err(|_| anyhow::anyhow!("metadata store lock poisoned"))
.and_then(|store| {
search_bm25_with_stores_and_filters(
&stores.bm25,
&store,
&bm25_query,
&bm25_filters,
bm25_candidates,
)
}),
None => Bm25Index::open(&bm25_dir)
.context("failed to open BM25 index for search")
.and_then(|index| {
let store = MetadataStore::open(&metadata_path)
.context("failed to open metadata store for BM25 search")?;
search_bm25_with_stores_and_filters(
&index,
&store,
&bm25_query,
&bm25_filters,
bm25_candidates,
)
}),
};
(result, start.elapsed())
});
let vector_fetch = if filters.is_empty() {
vector_candidates
} else {
vector_candidates.saturating_mul(4).max(200)
};
let vector_start = Instant::now();
let vector_outcome = match stores {
Some(stores) => match stores.vector_store(stored_dim) {
Ok(vector_store) => {
match search_vector_with_cached_stores_timed(
vector_store.as_ref(),
&stores.vector_metadata,
provider,
vector_query,
vector_fetch,
)
.await
{
Ok((mut results, embed_elapsed)) => {
if !filters.is_empty() {
results.retain(|result| filters.matches(result));
}
Ok((results, embed_elapsed))
}
Err(err) => Err(err),
}
}
Err(err) => Err(VectorSearchError::StorageError(err)),
},
None => match VectorStore::open(&index_dir.join("vectors.db"), stored_dim) {
Ok(vector_store) => {
let vector_metadata_result = MetadataStore::open(&index_dir.join("metadata.db"))
.context("failed to open metadata store");
match vector_metadata_result {
Ok(vector_metadata) => {
match search_vector_with_stores_timed(
&vector_store,
&vector_metadata,
provider,
vector_query,
vector_fetch,
)
.await
{
Ok((mut results, embed_elapsed)) => {
if !filters.is_empty() {
results.retain(|result| filters.matches(result));
}
Ok((results, embed_elapsed))
}
Err(err) => Err(err),
}
}
Err(err) => Err(VectorSearchError::StorageError(err)),
}
}
Err(err) => Err(VectorSearchError::StorageError(
err.context("failed to open vector store"),
)),
},
};
let embed_elapsed = vector_outcome
.as_ref()
.ok()
.map(|(_, embed_elapsed)| *embed_elapsed);
charge_vector_span(&mut timings, vector_start.elapsed(), embed_elapsed);
let vector_results = vector_outcome.map(|(results, _)| results);
let (bm25_results, bm25_elapsed) = bm25_handle.await.map_err(|e| {
HybridSearchError::PipelineError(anyhow::anyhow!("BM25 task panicked: {e}"))
})?;
timings.bm25 = Some(bm25_elapsed);
match (bm25_results, vector_results) {
(Ok(bm25), Ok(vector)) => {
debug!(
bm25_count = bm25.len(),
vector_count = vector.len(),
query_type = ?query_type,
bm25_weight = query_params.bm25_weight,
vector_weight = query_params.vector_weight,
"merging BM25 and vector results via weighted RRF"
);
let fusion_start = Instant::now();
let fused = fuse_rrf_weighted(
&bm25,
&vector,
rrf_k,
limit,
query_params.bm25_weight,
query_params.vector_weight,
);
timings.fusion = Some(fusion_start.elapsed());
Ok((fused, timings))
}
(Ok(bm25), Err(vec_err)) => {
warn!(
error = %vec_err,
"vector search failed, falling back to BM25-only results"
);
let mut results = bm25;
results.truncate(limit);
Ok((results, timings))
}
(Err(bm25_err), Ok(vector)) => {
warn!(
error = %bm25_err,
"BM25 search failed, falling back to vector-only results"
);
let mut results = vector;
results.truncate(limit);
Ok((results, timings))
}
(Err(bm25_err), Err(vec_err)) => Err(HybridSearchError::BothFailed {
bm25_error: format!("{bm25_err:#}"),
vector_error: format!("{vec_err:#}"),
}),
}
}
#[allow(clippy::too_many_arguments)]
pub async fn search_hybrid_reranked(
index_dir: &Path,
provider: &impl EmbeddingProvider,
reranker: &impl Reranker,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
fetch_limit: usize,
result_limit: usize,
rrf_k: f64,
stored_dim: usize,
rerank_candidates: usize,
vector_candidates: usize,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
search_hybrid_reranked_with_augmentation(
index_dir,
provider,
reranker,
bm25_query,
vector_query,
filters,
fetch_limit,
result_limit,
rrf_k,
stored_dim,
rerank_candidates,
vector_candidates,
false,
)
.await
}
#[allow(clippy::too_many_arguments)]
pub(crate) async fn search_hybrid_reranked_with_stores(
index_dir: &Path,
provider: &impl EmbeddingProvider,
reranker: &impl Reranker,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
fetch_limit: usize,
result_limit: usize,
rrf_k: f64,
stored_dim: usize,
rerank_candidates: usize,
vector_candidates: usize,
graph_augmentation_enabled: bool,
stores: Arc<SearchStores>,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
search_hybrid_reranked_inner(
index_dir,
provider,
reranker,
bm25_query,
vector_query,
filters,
fetch_limit,
result_limit,
rrf_k,
stored_dim,
rerank_candidates,
vector_candidates,
graph_augmentation_enabled,
Some(stores),
)
.await
}
#[allow(clippy::too_many_arguments)]
pub(crate) async fn search_hybrid_reranked_with_augmentation(
index_dir: &Path,
provider: &impl EmbeddingProvider,
reranker: &impl Reranker,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
fetch_limit: usize,
result_limit: usize,
rrf_k: f64,
stored_dim: usize,
rerank_candidates: usize,
vector_candidates: usize,
graph_augmentation_enabled: bool,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
search_hybrid_reranked_inner(
index_dir,
provider,
reranker,
bm25_query,
vector_query,
filters,
fetch_limit,
result_limit,
rrf_k,
stored_dim,
rerank_candidates,
vector_candidates,
graph_augmentation_enabled,
None,
)
.await
}
#[allow(clippy::too_many_arguments)]
async fn search_hybrid_reranked_inner(
index_dir: &Path,
provider: &impl EmbeddingProvider,
reranker: &impl Reranker,
bm25_query: &str,
vector_query: &str,
filters: &SearchFilters,
fetch_limit: usize,
result_limit: usize,
rrf_k: f64,
stored_dim: usize,
rerank_candidates: usize,
vector_candidates: usize,
graph_augmentation_enabled: bool,
stores: Option<Arc<SearchStores>>,
) -> Result<(Vec<SearchResult>, HybridTimings), HybridSearchError> {
let fusion_limit = rerank_candidates.max(fetch_limit);
let (mut hybrid_results, mut timings) = match stores {
Some(stores) => {
search_hybrid_with_stores(
index_dir,
provider,
bm25_query,
vector_query,
filters,
fusion_limit,
rrf_k,
stored_dim,
vector_candidates,
stores,
)
.await?
}
None => {
search_hybrid(
index_dir,
provider,
bm25_query,
vector_query,
filters,
fusion_limit,
rrf_k,
stored_dim,
vector_candidates,
)
.await?
}
};
let augmented_count = if graph_augmentation_enabled {
augment_pool(index_dir, &mut hybrid_results, filters)
} else {
0
};
if hybrid_results.is_empty() {
return Ok((hybrid_results, timings));
}
if hybrid_results.len() <= result_limit && augmented_count == 0 {
return Ok((hybrid_results, timings));
}
let rerank_start = Instant::now();
let rerank_limit = if augmented_count > 0 {
hybrid_results.len()
} else {
rerank_candidates
};
match rerank_results(reranker, vector_query, &hybrid_results, rerank_limit).await {
Ok(mut reranked) => {
timings.reranking = Some(rerank_start.elapsed());
info!(
query = vector_query,
candidates = hybrid_results.len(),
reranked = reranked.len(),
"reranking complete"
);
reranked = merge_reranked_results(reranked, hybrid_results, rerank_limit, fetch_limit);
Ok((reranked, timings))
}
Err(rerank_err) => {
timings.reranking = Some(rerank_start.elapsed());
warn!(
error = %rerank_err,
"reranker unavailable, returning unreranked results"
);
eprintln!(
"Warning: reranker unavailable ({rerank_err}), returning unreranked results."
);
let mut results = hybrid_results;
results.truncate(fetch_limit);
Ok((results, timings))
}
}
}
fn merge_reranked_results(
mut reranked: Vec<SearchResult>,
hybrid_results: Vec<SearchResult>,
rerank_limit: usize,
fetch_limit: usize,
) -> Vec<SearchResult> {
let rerank_prefix_len = rerank_limit.min(hybrid_results.len());
let mut present = reranked.iter().map(result_key).collect::<HashSet<_>>();
let mut score_ceiling = reranked.last().map(|result| result.score);
let mut append_unscored = |mut result: SearchResult| {
if !present.insert(result_key(&result)) {
return;
}
if let Some(ceiling) = score_ceiling {
result.score = result.score.min(ceiling);
}
score_ceiling = Some(result.score);
reranked.push(result);
};
for result in hybrid_results.iter().take(rerank_prefix_len) {
append_unscored(result.clone());
}
for result in hybrid_results.into_iter().skip(rerank_prefix_len) {
append_unscored(result);
}
reranked.truncate(fetch_limit);
reranked
}
pub fn fuse_rrf(
bm25_results: &[SearchResult],
vector_results: &[SearchResult],
rrf_k: f64,
limit: usize,
) -> Vec<SearchResult> {
fuse_rrf_multi_weighted(&[bm25_results, vector_results], &[1.0, 1.0], rrf_k, limit)
}
pub fn fuse_rrf_weighted(
bm25_results: &[SearchResult],
vector_results: &[SearchResult],
rrf_k: f64,
limit: usize,
bm25_weight: f64,
vector_weight: f64,
) -> Vec<SearchResult> {
fuse_rrf_multi_weighted(
&[bm25_results, vector_results],
&[bm25_weight, vector_weight],
rrf_k,
limit,
)
}
pub fn fuse_rrf_multi_weighted(
result_sets: &[&[SearchResult]],
weights: &[f64],
rrf_k: f64,
limit: usize,
) -> Vec<SearchResult> {
let mut fused: HashMap<String, (f64, SearchResult)> = HashMap::new();
for (set_idx, result_set) in result_sets.iter().enumerate() {
let weight = weights.get(set_idx).copied().unwrap_or(1.0);
for (rank_0, result) in result_set.iter().enumerate() {
let key = result_key(result);
let rrf_score = weight / (rrf_k + (rank_0 + 1) as f64);
fused
.entry(key)
.and_modify(|(score, _)| *score += rrf_score)
.or_insert_with(|| (rrf_score, result.clone()));
}
}
let mut ranked: Vec<(f64, SearchResult)> = fused.into_values().collect();
ranked.sort_by(|a, b| {
b.0.partial_cmp(&a.0)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| {
(&a.1.file_path, a.1.line_start, a.1.line_end).cmp(&(
&b.1.file_path,
b.1.line_start,
b.1.line_end,
))
})
});
ranked
.into_iter()
.take(limit)
.map(|(rrf_score, mut result)| {
result.score = rrf_score;
result
})
.collect()
}
fn charge_vector_span(
timings: &mut HybridTimings,
vector_span: Duration,
embed_elapsed: Option<Duration>,
) {
timings.embedding = embed_elapsed;
timings.vector = Some(vector_span.saturating_sub(embed_elapsed.unwrap_or_default()));
}
#[cfg(test)]
#[path = "hybrid_tests.rs"]
mod tests;
#[cfg(test)]
mod shortfall_tests {
use super::*;
use crate::types::Language;
fn result(index: usize) -> SearchResult {
SearchResult {
file_path: format!("candidate-{index}.rs"),
line_start: 1,
line_end: 1,
content: format!("candidate {index}"),
language: Language::Rust,
score: 1.0 - index as f64 / 100.0,
symbol_name: None,
symbol_type: None,
}
}
#[test]
fn reranker_shortfall_appends_missing_candidates_in_hybrid_order() {
let hybrid_results: Vec<_> = (0..20).map(result).collect();
let scored_indices = (0..7).chain(13..20);
let reranked = scored_indices
.enumerate()
.map(|(rank, index)| {
let mut result = hybrid_results[index].clone();
result.score = 100.0 - rank as f64;
result
})
.collect();
let merged = merge_reranked_results(reranked, hybrid_results, 20, 20);
assert_eq!(merged.len(), 20);
let missing_tail: Vec<_> = merged[14..]
.iter()
.map(|result| result.content.as_str())
.collect();
assert_eq!(
missing_tail,
vec![
"candidate 7",
"candidate 8",
"candidate 9",
"candidate 10",
"candidate 11",
"candidate 12",
]
);
}
}