zeppelin_embed/planner/
mod.rs

1//! Typed filter planning, exact execution branches, and truthful plan reports.
2
3mod choose;
4mod exec;
5mod lexical;
6mod prune;
7#[cfg(any(test, feature = "test-seams"))]
8mod receipt;
9
10pub use choose::{ALLOW_LIST_ROWS_THRESHOLD, choose_scan_branch};
11pub use exec::{FilteredSearchError, FilteredSearchOutcome};
12pub(crate) use lexical::search_lexical_filtered_refs_controlled;
13pub use lexical::{
14    LEXICAL_ALLOW_LIST_DIVISOR, LexicalBranch, LexicalFilterError, LexicalSearchOutcome,
15    search_lexical_filtered,
16};
17pub use prune::{PlanError, segment_may_match, validate_predicate};
18#[cfg(any(test, feature = "test-seams"))]
19pub(crate) use receipt::MetadataQueryContext;
20#[cfg(any(test, feature = "test-seams"))]
21#[doc(hidden)]
22pub use receipt::{
23    MetadataControllerError, MetadataExecutionReceipt, MetadataFeatureDetail,
24    MetadataFeatureReceipt, MetadataTestArm, MetadataTestController,
25};
26
27use crate::ingest::RowSource;
28use crate::meta::Predicate;
29
30/// One exact vector-filter execution branch.
31#[derive(Clone, Copy, Debug, Eq, PartialEq)]
32pub enum SegmentBranch {
33    /// The clustering range proved that the segment cannot match.
34    Pruned,
35    /// Iterate the exact allow-list and score only its rows.
36    ExactAllowList,
37    /// Sweep the segment and mask every row through the exact allow-list.
38    MaskedScan,
39    /// Graph traversal navigates every row and retains only effective-mask rows.
40    FilteredGraph,
41    /// Filtered traversal abandoned to an exact allow-list answer.
42    GraphExactFallback,
43    /// Unfiltered graph traversal.
44    Graph,
45}
46
47/// The physical tier represented by one segment plan.
48#[derive(Clone, Copy, Debug, Eq, PartialEq)]
49pub enum SegmentTier {
50    /// The in-RAM active segment.
51    ActiveScan,
52    /// An immutable segment without graph traversal selected.
53    SealedScan,
54    /// An immutable segment with a published graph artifact.
55    SealedGraph,
56}
57
58/// Where the exact filter is enforced relative to candidate scoring.
59#[derive(Clone, Copy, Debug, Eq, PartialEq)]
60pub enum FilterMode {
61    /// No filter was requested.
62    None,
63    /// The bitmap restricts rows before scoring.
64    Pre,
65    /// Traversal enforces the filter while visiting nodes.
66    InTraversal,
67    /// Candidate scoring precedes an exact membership check.
68    Post,
69}
70
71/// A named fallback recorded by the planner.
72#[derive(Clone, Copy, Debug, Eq, PartialEq)]
73pub enum PlanFallback {
74    /// No fallback was required.
75    None,
76    /// Filtered traversal crossed its independent selectivity budget.
77    VisitedBudget,
78    /// A caller-supplied `ef` was raised to compensate for selectivity.
79    EfWidened,
80    /// Corrective ef widening exhausted before retaining the requested rows.
81    CandidateShortfall,
82}
83
84/// The only explicit caller tiers that deliberately select scan execution.
85#[derive(Clone, Copy, Debug, Eq, PartialEq)]
86pub enum ExplicitScanTier {
87    /// Exhaustively score full-precision rows.
88    Exact,
89    /// Exhaustively score the segment's persisted scan representation.
90    Scan,
91}
92
93/// Why one segment was served without graph traversal.
94///
95/// These are capacity and caller-choice reasons only. Graph integrity and
96/// validation failures remain typed query errors and never become reasons for
97/// a quiet scan.
98#[derive(Clone, Copy, Debug, Eq, PartialEq)]
99pub enum ScanReason {
100    /// The immutable segment has not reached the measured graph crossover.
101    BelowGraphThreshold {
102        /// Dense rows in the segment.
103        rows: u32,
104        /// Minimum rows required by the segment's policy bucket.
105        min_rows: u32,
106    },
107    /// The segment is eligible, but its graph has not been published yet.
108    GraphPending,
109    /// The mutable unsealed tail cannot carry a graph.
110    ActiveSegment,
111    /// Hybrid widening requested the complete corpus.
112    FullMaterialization,
113    /// Hybrid widening made graph traversal more expensive than exact scan.
114    WideningCap {
115        /// Candidate pool the graph would have visited.
116        ef: usize,
117        /// Rows used to evaluate the widening cap.
118        rows: usize,
119    },
120    /// The caller explicitly selected a scan tier.
121    ExplicitTier(ExplicitScanTier),
122}
123
124/// Stable slots in [`crate::lifecycle::Stats::scans_by_reason`].
125#[derive(Clone, Copy, Debug, Eq, PartialEq)]
126#[repr(usize)]
127pub enum ScanReasonCounter {
128    /// [`ScanReason::BelowGraphThreshold`].
129    BelowGraphThreshold = 0,
130    /// [`ScanReason::GraphPending`].
131    GraphPending = 1,
132    /// [`ScanReason::ActiveSegment`].
133    ActiveSegment = 2,
134    /// [`ScanReason::FullMaterialization`].
135    FullMaterialization = 3,
136    /// [`ScanReason::WideningCap`].
137    WideningCap = 4,
138    /// [`ScanReason::ExplicitTier`] with [`ExplicitScanTier::Exact`].
139    ExplicitExact = 5,
140    /// [`ScanReason::ExplicitTier`] with [`ExplicitScanTier::Scan`].
141    ExplicitScan = 6,
142}
143
144impl ScanReasonCounter {
145    /// Array index for this stable counter slot.
146    #[must_use]
147    pub const fn index(self) -> usize {
148        self as usize
149    }
150}
151
152/// Number of stable scan-reason counter slots.
153pub const SCAN_REASON_COUNTER_COUNT: usize = 7;
154
155impl ScanReason {
156    pub(crate) const fn counter(self) -> ScanReasonCounter {
157        match self {
158            Self::BelowGraphThreshold { .. } => ScanReasonCounter::BelowGraphThreshold,
159            Self::GraphPending => ScanReasonCounter::GraphPending,
160            Self::ActiveSegment => ScanReasonCounter::ActiveSegment,
161            Self::FullMaterialization => ScanReasonCounter::FullMaterialization,
162            Self::WideningCap { .. } => ScanReasonCounter::WideningCap,
163            Self::ExplicitTier(ExplicitScanTier::Exact) => ScanReasonCounter::ExplicitExact,
164            Self::ExplicitTier(ExplicitScanTier::Scan) => ScanReasonCounter::ExplicitScan,
165        }
166    }
167}
168
169/// Closed recursive plan IR. New execution families require a new enum variant.
170#[derive(Clone, Debug, PartialEq)]
171pub enum PlanNode {
172    /// One exact vector scan.
173    Scan {
174        /// Store-global segment address.
175        source: RowSource,
176        /// Exact scan branch selected for the segment.
177        branch: SegmentBranch,
178    },
179    /// One future lexical execution leg.
180    Lexical {
181        /// Whether the allow-list drives iteration.
182        allow_list_driven: bool,
183    },
184    /// One graph leg with an optional exact fallback child.
185    Graph {
186        /// Store-global segment address.
187        source: RowSource,
188        /// Exact child used when traversal reports a fallback disposition.
189        fallback: Option<Box<PlanNode>>,
190    },
191    /// Exact bitmap intersection wrapped around another typed node.
192    BitmapIntersect {
193        /// The validated closed predicate AST.
194        predicate: Predicate,
195        /// The execution node constrained by the bitmap.
196        input: Box<PlanNode>,
197    },
198    /// Reserved typed fusion node for task 17.
199    Fusion {
200        /// Independently typed child legs.
201        inputs: Vec<PlanNode>,
202    },
203}
204
205/// Truthful per-segment plan report returned with filtered results.
206#[derive(Clone, Debug, PartialEq)]
207pub struct SegmentPlan {
208    /// Collision-free segment address.
209    pub source: RowSource,
210    /// Physical tier observed from published state.
211    pub tier: SegmentTier,
212    /// Exact branch that actually executed.
213    pub branch: SegmentBranch,
214    /// Filter enforcement position.
215    pub filter_mode: FilterMode,
216    /// Exact alive-bounded allow-list cardinality.
217    pub filter_cardinality: u64,
218    /// Whether result quality is approximate.
219    pub approximate: bool,
220    /// Named fallback, if any.
221    pub fallback: PlanFallback,
222    /// Capacity or caller-choice reason when this plan executed a scan.
223    pub scan_reason: Option<ScanReason>,
224    /// Caller-supplied graph width, or `None` for adaptive or scan work.
225    pub ef_requested: Option<usize>,
226    /// Actual filter-aware graph width, or `None` when no traversal ran.
227    pub ef_effective: Option<usize>,
228    /// Graph profile actually used, or `None` when no traversal ran.
229    pub graph_profile: Option<crate::graph::search::GraphSearchProfile>,
230    /// Recursive typed node for this segment.
231    pub node: PlanNode,
232}
233
234impl SegmentPlan {
235    pub(crate) fn unfiltered_scan(
236        source: RowSource,
237        tier: SegmentTier,
238        cardinality: u64,
239        scan_reason: ScanReason,
240    ) -> Self {
241        let branch = SegmentBranch::MaskedScan;
242        Self {
243            source,
244            tier,
245            branch,
246            filter_mode: FilterMode::None,
247            filter_cardinality: cardinality,
248            approximate: false,
249            fallback: PlanFallback::None,
250            scan_reason: Some(scan_reason),
251            ef_requested: None,
252            ef_effective: None,
253            graph_profile: None,
254            node: PlanNode::Scan { source, branch },
255        }
256    }
257
258    pub(crate) fn unfiltered_graph(
259        source: RowSource,
260        cardinality: u64,
261        ef_requested: Option<usize>,
262        ef_effective: usize,
263        graph_profile: crate::graph::search::GraphSearchProfile,
264    ) -> Self {
265        Self {
266            source,
267            tier: SegmentTier::SealedGraph,
268            branch: SegmentBranch::Graph,
269            filter_mode: FilterMode::None,
270            filter_cardinality: cardinality,
271            approximate: true,
272            fallback: PlanFallback::None,
273            scan_reason: None,
274            ef_requested,
275            ef_effective: Some(ef_effective),
276            graph_profile: Some(graph_profile),
277            node: PlanNode::Graph {
278                source,
279                fallback: None,
280            },
281        }
282    }
283
284    pub(crate) fn unfiltered_pruned(source: RowSource, cardinality: u64) -> Self {
285        Self {
286            source,
287            tier: SegmentTier::SealedGraph,
288            branch: SegmentBranch::Pruned,
289            filter_mode: FilterMode::None,
290            filter_cardinality: cardinality,
291            approximate: false,
292            fallback: PlanFallback::None,
293            scan_reason: None,
294            ef_requested: None,
295            ef_effective: None,
296            graph_profile: None,
297            node: PlanNode::Scan {
298                source,
299                branch: SegmentBranch::Pruned,
300            },
301        }
302    }
303
304    pub(crate) fn exact(
305        source: RowSource,
306        tier: SegmentTier,
307        branch: SegmentBranch,
308        cardinality: u64,
309        scan_reason: Option<ScanReason>,
310    ) -> Self {
311        Self {
312            source,
313            tier,
314            branch,
315            filter_mode: FilterMode::Pre,
316            filter_cardinality: cardinality,
317            approximate: false,
318            fallback: PlanFallback::None,
319            scan_reason,
320            ef_requested: None,
321            ef_effective: None,
322            graph_profile: None,
323            node: PlanNode::Scan { source, branch },
324        }
325    }
326
327    pub(crate) fn filtered_graph(
328        source: RowSource,
329        cardinality: u64,
330        ef_requested: Option<usize>,
331        ef_effective: usize,
332        branch: SegmentBranch,
333        fallback: PlanFallback,
334        graph_profile: crate::graph::search::GraphSearchProfile,
335    ) -> Self {
336        let (node, filter_mode, approximate) = match branch {
337            SegmentBranch::FilteredGraph => (
338                PlanNode::Graph {
339                    source,
340                    fallback: None,
341                },
342                FilterMode::InTraversal,
343                true,
344            ),
345            SegmentBranch::GraphExactFallback => (
346                PlanNode::Graph {
347                    source,
348                    fallback: Some(Box::new(PlanNode::Scan {
349                        source,
350                        branch: SegmentBranch::ExactAllowList,
351                    })),
352                },
353                FilterMode::Pre,
354                false,
355            ),
356            _ => (PlanNode::Scan { source, branch }, FilterMode::Pre, false),
357        };
358        Self {
359            source,
360            tier: SegmentTier::SealedGraph,
361            branch,
362            filter_mode,
363            filter_cardinality: cardinality,
364            approximate,
365            fallback,
366            scan_reason: None,
367            ef_requested,
368            ef_effective: Some(ef_effective),
369            graph_profile: Some(graph_profile),
370            node,
371        }
372    }
373
374    pub(crate) fn with_predicate(mut self, predicate: &Predicate) -> Self {
375        self.node = PlanNode::BitmapIntersect {
376            predicate: predicate.clone(),
377            input: Box::new(self.node),
378        };
379        self
380    }
381}
zeppelin_embed/planner/mod.rs

zeppelin_embed/planner/
mod.rs
