Skip to main content

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;