omgbase_surface/
planner.rs

1//! The tier-3 pushdown planner: reduces the row set a query scans by
2//! translating its pushable top-level `where` conjuncts into ONE SQL
3//! statement against the store, then handing the produced rows (plus the
4//! untranslatable residual) back to the in-memory engine to finish. Port of
5//! `packages/core/src/oqx-js/planner.ts` over the [`oqx`] seam
6//! ([`QueryPlanner`], [`Plan`], [`oqx::partition_pushable`],
7//! [`oqx::residual_query`], [`oqx::ROWS_ROOT`]).
8//!
9//! Correctness is guaranteed by the residual fallback — anything
10//! [`crate::translate`] declines stays in-memory — and verified by the
11//! differential gate (planned == in-memory over every corpus-backed query
12//! case and the conformance list). Deliberately conservative: only simple
13//! top-level target scans (no `follow`, no `from E` re-projection) whose
14//! source is a bare `docs|blocks|nodes|edges` or `$repo.<target>`, with at
15//! least one pushable scalar conjunct, are planned; everything else declines
16//! to a full in-memory run.
17//!
18//! One shape difference from the reference, forced by ownership: the
19//! reference attaches a store context to its plan (`makeStoreContext(…,
20//! rowsRoot)`), but a [`crate::StoreContext`] borrows the store's connection
21//! and `Plan::context` must be `'static`, so the plan carries no context and
22//! the runner ([`mod@crate::query`]) builds the rows-root context itself
23//! ([`crate::StoreContext::with_rows_root`]) — the same six lines
24//! `oqx::PlannedEngine::run` would execute.
25
26use oqx::ast::{Expr, Query};
27use oqx::{Plan, QueryPlanner, Value, partition_pushable, residual_query};
28use rusqlite::Connection;
29use rusqlite::types::Value as SqlValue;
30
31use crate::context::{Target, fetch_rows, tag_rows};
32use crate::translate::{TranslateCtx, translate_predicate};
33
34/// The SQL aliases of the scanned row (`self`) and its owning doc (`doc`).
35fn aliases(t: Target) -> (&'static str, &'static str) {
36    match t {
37        Target::Docs => ("d", "d"),
38        Target::Blocks => ("b", "d"),
39        Target::Nodes => ("n", "d"),
40        Target::Edges => ("e", "d"),
41    }
42}
43
44fn from_clause(t: Target) -> &'static str {
45    match t {
46        Target::Docs => "docs d",
47        Target::Blocks => "blocks b JOIN docs d ON d.doc_id = b.doc_id",
48        Target::Nodes => "nodes n JOIN docs d ON d.doc_id = n.doc_id",
49        Target::Edges => "edges e JOIN docs d ON d.doc_id = e.src_doc",
50    }
51}
52
53/// Row columns + the owning-doc path as `__path` (matches the context's
54/// roots so produced rows are indistinguishable from a full scan's).
55fn columns(t: Target) -> &'static str {
56    match t {
57        Target::Docs => "d.*",
58        Target::Blocks => "b.*, d.path AS __path",
59        Target::Nodes => "n.*, d.path AS __path",
60        Target::Edges => "e.*, d.path AS __path",
61    }
62}
63
64/// The root order (`spec/surface` §1.1).
65fn order_clause(t: Target) -> &'static str {
66    match t {
67        Target::Docs => "d.path, d.doc_id",
68        Target::Blocks => "d.path, b.block_id",
69        Target::Nodes => "d.path, n.node_id",
70        Target::Edges => "d.path, e.edge_id",
71    }
72}
73
74/// The liveness guards of the root scan, with the repo id bound.
75fn guards(t: Target) -> &'static str {
76    match t {
77        Target::Docs => "d.repo_id = ? AND d.deleted_commit IS NULL",
78        Target::Blocks => "b.repo_id = ? AND b.deleted_commit IS NULL AND d.deleted_commit IS NULL",
79        Target::Nodes => "n.repo_id = ? AND d.deleted_commit IS NULL",
80        Target::Edges => "e.repo_id = ? AND e.to_commit IS NULL AND d.deleted_commit IS NULL",
81    }
82}
83
84/// The root collection a query scans, if it is a bare `docs|blocks|nodes|edges`
85/// or `$repo.<target>` source (else `None` — not a pushable shape).
86fn root_target(source: &Expr) -> Option<Target> {
87    match source {
88        Expr::Ident { name } => Target::parse(name),
89        Expr::Member { recv, name } => match &**recv {
90            Expr::Ident { name: r } if r == "$repo" => Target::parse(name),
91            _ => None,
92        },
93        _ => None,
94    }
95}
96
97/// A compiled plan before execution: the statement, its params and the
98/// residual query. Pure — what the planner would run, for inspection.
99#[derive(Clone, Debug, PartialEq)]
100pub struct Compiled {
101    pub target: Target,
102    pub sql: String,
103    pub params: Vec<SqlValue>,
104    pub residual: Query,
105}
106
107/// Compile `query` against `repo_id`, or `None` when the shape declines: a
108/// `follow`, a `from E` re-projection, a source that is not a root scan, or
109/// no pushable conjunct at all (the engine then does everything).
110#[must_use]
111pub fn compile(query: &Query, params: &[Value], repo_id: &str) -> Option<Compiled> {
112    if query.follow.is_some() || !query.from.is_empty() {
113        return None;
114    }
115    let target = root_target(&query.source)?;
116    let (self_alias, doc_alias) = aliases(target);
117    let ctx = TranslateCtx {
118        target,
119        self_alias,
120        doc_alias,
121        params,
122    };
123    let (pushed, residual) = partition_pushable(query.r#where.as_ref(), |e| {
124        translate_predicate(e, &ctx).is_some()
125    });
126    if pushed.is_empty() {
127        return None;
128    }
129    let mut where_sql = guards(target).to_owned();
130    let mut sql_params = vec![SqlValue::Text(repo_id.to_owned())];
131    for e in &pushed {
132        let frag = translate_predicate(e, &ctx).expect("accepted by partition_pushable");
133        where_sql.push_str(" AND (");
134        where_sql.push_str(&frag.sql);
135        where_sql.push(')');
136        sql_params.extend(frag.params);
137    }
138    let sql = format!(
139        "SELECT {} FROM {} WHERE {where_sql} ORDER BY {}",
140        columns(target),
141        from_clause(target),
142        order_clause(target)
143    );
144    Some(Compiled {
145        target,
146        sql,
147        params: sql_params,
148        residual: residual_query(query, residual),
149    })
150}
151
152/// The SQLite planner over one repo of the store.
153pub struct SqlitePlanner<'a> {
154    conn: &'a Connection,
155    repo_id: String,
156}
157
158impl<'a> SqlitePlanner<'a> {
159    #[must_use]
160    pub fn new(conn: &'a Connection, repo_id: &str) -> Self {
161        Self {
162            conn,
163            repo_id: repo_id.to_owned(),
164        }
165    }
166
167    /// Plan `query`: `Ok(None)` when the shape declines, `Ok(Some(plan))`
168    /// with the produced rows (tagged like the context's root rows) and the
169    /// residual, `Err` when the statement itself failed (a store error, not
170    /// a decline — the runner reports it rather than silently rescanning).
171    pub fn try_plan(&self, query: &Query, params: &[Value]) -> rusqlite::Result<Option<Plan>> {
172        let Some(compiled) = compile(query, params, &self.repo_id) else {
173            return Ok(None);
174        };
175        let rows = fetch_rows(self.conn, &compiled.sql, &compiled.params)?;
176        Ok(Some(Plan::new(
177            tag_rows(rows, compiled.target),
178            compiled.residual,
179        )))
180    }
181}
182
183impl QueryPlanner for SqlitePlanner<'_> {
184    /// The seam's shape: a failed statement declines (the engine falls back
185    /// to a full scan). The runner uses [`Self::try_plan`] to surface it.
186    fn plan(&self, query: &Query, params: &[Value]) -> Option<Plan> {
187        self.try_plan(query, params).ok().flatten()
188    }
189}
190
191#[cfg(test)]
192mod tests {
193    use super::*;
194    use oqx::ROWS_ROOT;
195    use oqx::ast::Where;
196
197    fn parse(src: &str) -> Query {
198        oqx::parse_string(src).expect("parses")
199    }
200
201    fn text(s: &str) -> SqlValue {
202        SqlValue::Text(s.to_owned())
203    }
204
205    #[test]
206    fn a_pushable_scan_compiles_to_one_statement_in_root_order() {
207        let c =
208            compile(&parse("from docs where $path == \"index.md\""), &[], "r_1").expect("planned");
209        assert_eq!(c.target, Target::Docs);
210        assert_eq!(
211            c.sql,
212            "SELECT d.* FROM docs d WHERE d.repo_id = ? AND d.deleted_commit IS NULL AND ((d.path IS ?)) ORDER BY d.path, d.doc_id"
213        );
214        assert_eq!(c.params, vec![text("r_1"), text("index.md")]);
215        assert_eq!(
216            c.residual.source,
217            Expr::Ident {
218                name: ROWS_ROOT.to_owned()
219            }
220        );
221        assert_eq!(c.residual.r#where, None);
222    }
223
224    #[test]
225    fn every_target_has_its_join_columns_guards_and_order() {
226        let b = compile(
227            &parse("from blocks where $path.startsWith(\"lab/\")"),
228            &[],
229            "r",
230        )
231        .unwrap();
232        assert_eq!(
233            b.sql,
234            "SELECT b.*, d.path AS __path FROM blocks b JOIN docs d ON d.doc_id = b.doc_id \
235             WHERE b.repo_id = ? AND b.deleted_commit IS NULL AND d.deleted_commit IS NULL \
236             AND ((substr(d.path, 1, length(?)) = ?)) ORDER BY d.path, b.block_id"
237        );
238        assert_eq!(b.params, vec![text("r"), text("lab/"), text("lab/")]);
239        let n = compile(
240            &parse("$repo.nodes count { where kind == \"md:task\" }"),
241            &[],
242            "r",
243        )
244        .unwrap();
245        assert_eq!(n.target, Target::Nodes);
246        assert!(n.sql.starts_with(
247            "SELECT n.*, d.path AS __path FROM nodes n JOIN docs d ON d.doc_id = n.doc_id WHERE n.repo_id = ? AND d.deleted_commit IS NULL AND ((n.kind IS ?))"
248        ));
249        assert!(n.sql.ends_with("ORDER BY d.path, n.node_id"));
250        let e = compile(
251            &parse("from edges where predicate == \"references\""),
252            &[],
253            "r",
254        )
255        .unwrap();
256        assert!(e.sql.starts_with(
257            "SELECT e.*, d.path AS __path FROM edges e JOIN docs d ON d.doc_id = e.src_doc WHERE e.repo_id = ? AND e.to_commit IS NULL AND d.deleted_commit IS NULL AND ((e.predicate IS ?))"
258        ));
259        assert!(e.sql.ends_with("ORDER BY d.path, e.edge_id"));
260    }
261
262    #[test]
263    fn mixed_conjunctions_push_the_translatable_parts_and_keep_the_rest() {
264        let q = parse(
265            "from docs where $path.startsWith(\"processes/\") && nodes exists { where kind == \"md:task\" } && layer == \"canon\"",
266        );
267        let c = compile(&q, &[], "r").expect("planned");
268        assert!(
269            c.sql.contains("(substr(d.path, 1, length(?)) = ?)"),
270            "{}",
271            c.sql
272        );
273        assert!(c.sql.contains("p.key = 'layer'"), "{}", c.sql);
274        // Guards first, then the fragments' params in statement order.
275        assert_eq!(
276            c.params,
277            vec![
278                text("r"),
279                text("processes/"),
280                text("processes/"),
281                text("canon")
282            ]
283        );
284        // One conjunct left → it stands alone, not wrapped in an `and`.
285        assert!(
286            matches!(c.residual.r#where, Some(Where::Op(_))),
287            "{:?}",
288            c.residual.r#where
289        );
290        assert!(c.residual.from.is_empty());
291        assert_eq!(c.residual.select, q.select);
292        assert_eq!(c.residual.consumer, q.consumer);
293    }
294
295    #[test]
296    fn declined_shapes_return_none() {
297        // nothing pushable → let the engine do it all
298        assert!(compile(&parse("from docs"), &[], "r").is_none());
299        assert!(compile(&parse("from docs where era in 800..1680"), &[], "r").is_none());
300        assert!(compile(&parse("from docs where !verified"), &[], "r").is_none());
301        assert!(
302            compile(
303                &parse("from docs where $path == \"a\" || $path == \"b\""),
304                &[],
305                "r"
306            )
307            .is_none()
308        );
309        assert!(
310            compile(
311                &parse("from docs where nodes exists { where kind == \"md:task\" }"),
312                &[],
313                "r"
314            )
315            .is_none()
316        );
317        // follow
318        assert!(
319            compile(
320                &parse("from docs where $path == \"a.md\" follow distinct doc.out"),
321                &[],
322                "r"
323            )
324            .is_none()
325        );
326        // not a root scan
327        assert!(compile(&parse("from things where $path == \"a.md\""), &[], "r").is_none());
328        assert!(compile(&parse("from $repo where $path == \"a.md\""), &[], "r").is_none());
329        assert!(compile(&parse("from docs.nodes where kind == \"x\""), &[], "r").is_none());
330        // a `from E` re-projection (an AST-level shape)
331        let mut q = parse("from docs where $path == \"a.md\"");
332        q.from.push(Expr::Ident {
333            name: "nodes".to_owned(),
334        });
335        assert!(compile(&q, &[], "r").is_none());
336    }
337
338    #[test]
339    fn a_top_level_not_or_or_is_the_whole_residual_and_declines() {
340        // `!(…)` and `||` at the top are `Where::Not` / `Where::Or`, never scalar
341        // parts, so nothing is pushed even when their leaves would be.
342        assert!(compile(&parse("from docs where !($path == \"a\")"), &[], "r").is_none());
343        assert!(
344            compile(
345                &parse("from docs where ($path == \"a\" || $path == \"b\") && layer == \"canon\""),
346                &[],
347                "r"
348            )
349            .is_some()
350        );
351    }
352}
omgbase_surface/planner.rs

omgbase_surface/
planner.rs
