khive_retrieval/query_ir.rs
1//! Query Intermediate Representation for the retrieval pipeline.
2//!
3//! Composable IR tree representing how sub-queries are structured, filtered, and fused,
4//! separate from the Query struct which captures what to search.
5
6use khive_fusion::{FusionStrategy, FusionStrategyError};
7use khive_score::DeterministicScore;
8use serde::{Deserialize, Serialize};
9
10/// Candidates requested per hybrid search leaf before fusion.
11pub const HYBRID_CANDIDATE_MULTIPLIER: u32 = 4;
12
13// ---------------------------------------------------------------------------
14// Core IR node
15// ---------------------------------------------------------------------------
16
17/// A node in the Query IR tree.
18///
19/// Each variant represents a single retrieval operation or combinator.
20/// Nodes compose recursively -- a `Fuse` holds children, a `Filter` wraps
21/// a single child, and leaf nodes (`Vector`, `Keyword`, `Empty`) terminate
22/// the tree.
23#[derive(Debug, Clone, Serialize, Deserialize)]
24#[serde(rename_all = "snake_case")]
25pub enum QueryNode {
26 /// Vector similarity search (e.g. HNSW nearest-neighbor).
27 Vector {
28 /// Pre-computed query embedding.
29 embedding: Vec<f32>,
30 /// Logical requested limit; raw Collect adapters may retain existing provider overfetch.
31 /// Scalar executors enforce this as a strict returned-row bound.
32 top_k: usize,
33 /// Optional minimum similarity threshold.
34 min_score: Option<DeterministicScore>,
35 },
36
37 /// Keyword / BM25 text search.
38 Keyword {
39 /// Query text.
40 text: String,
41 /// Logical requested limit; raw Collect adapters may retain existing provider overfetch.
42 /// Scalar executors enforce this as a strict returned-row bound.
43 top_k: usize,
44 /// Optional minimum relevance threshold.
45 min_score: Option<DeterministicScore>,
46 },
47
48 /// Fuse multiple sub-queries into a single ranked list.
49 Fuse {
50 /// Sub-queries to fuse.
51 children: Vec<QueryNode>,
52 /// Strategy for combining ranked lists.
53 strategy: FuseStrategy,
54 /// Number of results after fusion.
55 top_k: usize,
56 },
57
58 /// Collect ordered raw child streams without fusion, ranking or deduplication.
59 ///
60 /// Only valid at the root of an executed collection plan.
61 Collect {
62 /// Independently executed children in declared slot order.
63 children: Vec<QueryNode>,
64 },
65
66 /// Filter the results of a sub-query.
67 Filter {
68 /// The sub-query whose results are filtered.
69 child: Box<QueryNode>,
70 /// Predicate to apply.
71 predicate: FilterPredicate,
72 },
73
74 /// Rerank the results of a sub-query.
75 Rerank {
76 /// The sub-query whose results are reranked.
77 child: Box<QueryNode>,
78 /// Reranking method.
79 method: RerankMethod,
80 /// Number of results after reranking.
81 top_k: usize,
82 },
83
84 /// An empty query that is guaranteed to produce no results.
85 ///
86 /// Useful as the result of constant-folding provably-empty sub-trees.
87 Empty,
88}
89
90// ---------------------------------------------------------------------------
91// Supporting enums
92// ---------------------------------------------------------------------------
93
94/// Fusion strategy for combining sub-query result lists.
95///
96/// Mirrors [`FusionStrategy`] at the IR level
97/// so that the query plan is self-contained and serialisable without depending
98/// on runtime fusion internals.
99#[derive(Debug, Clone, Serialize, Deserialize)]
100#[serde(rename_all = "snake_case")]
101pub enum FuseStrategy {
102 /// Reciprocal Rank Fusion with smoothing constant `k`.
103 ///
104 /// Standard default: k = 60 (Cormack et al., 2009).
105 Rrf {
106 /// Smoothing constant.
107 k: usize,
108 },
109
110 /// Weighted linear combination of scores.
111 ///
112 /// One weight per child; weights are normalised at execution time.
113 Weighted {
114 /// Per-child weights (will be normalised to sum to 1.0).
115 weights: Vec<f64>,
116 },
117
118 /// Weighted Reciprocal Rank Fusion over ordered children, without weight normalization.
119 WeightedRrf {
120 /// Smoothing constant (must be at least one at execution).
121 k: usize,
122 /// One finite, strictly positive weight per ordered child.
123 weights: Vec<f64>,
124 },
125
126 /// Union with max-score-per-document semantics.
127 Union,
128
129 /// Return only vector results.
130 VectorOnly,
131
132 /// Return only keyword results.
133 KeywordOnly,
134
135 /// A named custom strategy resolved by the executor.
136 Custom {
137 /// Strategy identifier.
138 name: String,
139 /// Opaque parameters preserved for the executor.
140 params: serde_json::Value,
141 },
142}
143
144impl From<FusionStrategy> for FuseStrategy {
145 fn from(strategy: FusionStrategy) -> Self {
146 match strategy {
147 FusionStrategy::Rrf { k } => Self::Rrf { k },
148 FusionStrategy::Weighted { weights } => Self::Weighted { weights },
149 FusionStrategy::WeightedRrf { k, weights } => Self::WeightedRrf { k, weights },
150 FusionStrategy::Union => Self::Union,
151 FusionStrategy::VectorOnly => Self::VectorOnly,
152 FusionStrategy::KeywordOnly => Self::KeywordOnly,
153 FusionStrategy::Custom { name, params } => Self::Custom { name, params },
154 }
155 }
156}
157
158impl TryFrom<FuseStrategy> for FusionStrategy {
159 type Error = FusionStrategyError;
160
161 fn try_from(strategy: FuseStrategy) -> Result<Self, Self::Error> {
162 match strategy {
163 FuseStrategy::Rrf { k } => Self::try_rrf(k),
164 FuseStrategy::Weighted { weights } => Self::try_weighted(weights),
165 FuseStrategy::WeightedRrf { k, weights } => Self::try_weighted_rrf(k, weights),
166 FuseStrategy::Union => Ok(Self::Union),
167 FuseStrategy::VectorOnly => Ok(Self::VectorOnly),
168 FuseStrategy::KeywordOnly => Ok(Self::KeywordOnly),
169 FuseStrategy::Custom { name, params } => Self::try_custom(name, params),
170 }
171 }
172}
173
174/// Predicate for post-retrieval filtering.
175#[derive(Debug, Clone, Serialize, Deserialize)]
176#[serde(rename_all = "snake_case")]
177pub enum FilterPredicate {
178 /// Keep only results whose score meets a minimum threshold.
179 MinScore(DeterministicScore),
180
181 /// Keep at most `k` results (top-k truncation).
182 TopK(usize),
183
184 /// Keep results where a metadata field equals a given value.
185 MetadataEquals {
186 /// Metadata field name.
187 field: String,
188 /// Expected value (JSON).
189 value: serde_json::Value,
190 },
191
192 /// All contained predicates must hold (conjunction).
193 And(Vec<FilterPredicate>),
194
195 /// At least one contained predicate must hold (disjunction).
196 Or(Vec<FilterPredicate>),
197}
198
199/// Method for reranking search results.
200#[derive(Debug, Clone, Serialize, Deserialize)]
201#[serde(rename_all = "snake_case")]
202pub enum RerankMethod {
203 /// Cross-encoder neural reranking (placeholder for future integration).
204 CrossEncoder {
205 /// Model identifier.
206 model: String,
207 },
208
209 /// Score-based reranking with custom per-signal weights.
210 ScoreWeighted {
211 /// Weights applied to each scoring signal.
212 weights: Vec<f64>,
213 },
214}
215
216// ---------------------------------------------------------------------------
217// Construction helpers
218// ---------------------------------------------------------------------------
219
220impl QueryNode {
221 /// Create a vector search leaf node.
222 pub fn vector(embedding: Vec<f32>, top_k: usize) -> Self {
223 QueryNode::Vector {
224 embedding,
225 top_k,
226 min_score: None,
227 }
228 }
229
230 /// Create a keyword search leaf node.
231 pub fn keyword(text: impl Into<String>, top_k: usize) -> Self {
232 QueryNode::Keyword {
233 text: text.into(),
234 top_k,
235 min_score: None,
236 }
237 }
238
239 /// Create a hybrid query (vector + keyword with RRF fusion, `top_k * 4` candidates each).
240 pub fn hybrid(embedding: Vec<f32>, text: impl Into<String>, top_k: usize) -> Self {
241 let candidate_k = top_k.saturating_mul(HYBRID_CANDIDATE_MULTIPLIER as usize);
242 QueryNode::Fuse {
243 children: vec![
244 QueryNode::vector(embedding, candidate_k),
245 QueryNode::keyword(text, candidate_k),
246 ],
247 strategy: FuseStrategy::Rrf { k: 60 },
248 top_k,
249 }
250 }
251
252 /// Wrap this node with a minimum-score filter.
253 #[must_use]
254 pub fn with_min_score(self, min_score: DeterministicScore) -> Self {
255 QueryNode::Filter {
256 child: Box::new(self),
257 predicate: FilterPredicate::MinScore(min_score),
258 }
259 }
260
261 /// Wrap this node with a top-k truncation filter.
262 #[must_use]
263 pub fn with_top_k(self, k: usize) -> Self {
264 QueryNode::Filter {
265 child: Box::new(self),
266 predicate: FilterPredicate::TopK(k),
267 }
268 }
269
270 // -----------------------------------------------------------------------
271 // Analysis helpers
272 // -----------------------------------------------------------------------
273
274 /// Returns `true` if this query is provably empty (no results possible).
275 ///
276 /// A query is provably empty when:
277 /// - It is the `Empty` variant.
278 /// - A leaf has `top_k == 0`.
279 /// - A keyword leaf has empty text.
280 /// - A fuse node has no children.
281 /// - A filter/rerank wraps a provably-empty child.
282 pub fn is_empty(&self) -> bool {
283 match self {
284 QueryNode::Empty => true,
285 QueryNode::Vector { top_k: 0, .. } => true,
286 QueryNode::Keyword { top_k: 0, .. } => true,
287 QueryNode::Keyword { text, .. } if text.is_empty() => true,
288 QueryNode::Fuse { children, .. } if children.is_empty() => true,
289 QueryNode::Collect { children } => children.iter().all(Self::is_empty),
290 QueryNode::Filter { child, .. } => child.is_empty(),
291 QueryNode::Rerank { child, .. } => child.is_empty(),
292 _ => false,
293 }
294 }
295
296 /// Count the total number of leaf search operations in the tree.
297 ///
298 /// `Vector` and `Keyword` nodes each count as 1. `Empty` counts as 0.
299 /// Combinators recurse into their children.
300 pub fn leaf_count(&self) -> usize {
301 match self {
302 QueryNode::Vector { .. } | QueryNode::Keyword { .. } => 1,
303 QueryNode::Fuse { children, .. } | QueryNode::Collect { children } => {
304 children.iter().map(|c| c.leaf_count()).sum()
305 }
306 QueryNode::Filter { child, .. } | QueryNode::Rerank { child, .. } => child.leaf_count(),
307 QueryNode::Empty => 0,
308 }
309 }
310
311 /// Return the effective `top_k` requested by this node.
312 ///
313 /// For `Filter` nodes with a `TopK` predicate, the predicate's value is
314 /// returned. Otherwise the child's `top_k` propagates upward.
315 pub fn top_k(&self) -> usize {
316 match self {
317 QueryNode::Vector { top_k, .. } => *top_k,
318 QueryNode::Keyword { top_k, .. } => *top_k,
319 QueryNode::Fuse { top_k, .. } => *top_k,
320 QueryNode::Collect { children } => children
321 .iter()
322 .fold(0usize, |total, child| total.saturating_add(child.top_k())),
323 QueryNode::Filter { child, predicate } => match predicate {
324 FilterPredicate::TopK(k) => *k,
325 _ => child.top_k(),
326 },
327 QueryNode::Rerank { top_k, .. } => *top_k,
328 QueryNode::Empty => 0,
329 }
330 }
331
332 /// Return the depth of the IR tree (longest root-to-leaf path).
333 ///
334 /// Leaf nodes have depth 1. `Empty` has depth 0.
335 pub fn depth(&self) -> usize {
336 match self {
337 QueryNode::Empty => 0,
338 QueryNode::Vector { .. } | QueryNode::Keyword { .. } => 1,
339 QueryNode::Fuse { children, .. } | QueryNode::Collect { children } => {
340 1 + children.iter().map(|c| c.depth()).max().unwrap_or(0)
341 }
342 QueryNode::Filter { child, .. } | QueryNode::Rerank { child, .. } => 1 + child.depth(),
343 }
344 }
345}
346
347// ---------------------------------------------------------------------------
348// Tests
349// ---------------------------------------------------------------------------
350
351#[cfg(test)]
352#[allow(clippy::uninlined_format_args)]
353#[path = "query_ir/tests.rs"]
354mod tests;