Skip to main content

qualia_core_db/inference/runtime/graph_assist/
query.rs

1use crate::indexing::QuinIndex;
2use crate::NQuin;
3
4use super::identity::{derive_prefix_identity, PrefixIdentity};
5
6#[repr(C)]
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub struct GraphQuery {
9    /// Zero is a wildcard.
10    pub context: u64,
11    /// Zero is a wildcard.
12    pub subject: u64,
13    /// Zero is a wildcard.
14    pub predicate: u64,
15    /// Zero is a wildcard.
16    pub object: u64,
17}
18
19#[repr(C)]
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub struct GraphAssistPolicy {
22    pub max_facts: u32,
23    pub sensitivity_ceiling: u8,
24    pub require_valid_parity: bool,
25    pub _pad: [u8; 2],
26}
27
28impl Default for GraphAssistPolicy {
29    fn default() -> Self {
30        Self {
31            max_facts: 64,
32            sensitivity_ceiling: 0,
33            require_valid_parity: true,
34            _pad: [0; 2],
35        }
36    }
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
40pub enum GraphQueryError {
41    InvalidPolicy,
42    OutputBufferFull,
43}
44
45#[repr(C)]
46#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
47pub struct GraphSelectionReceipt {
48    pub scanned: u32,
49    pub matched: u32,
50    pub written: u32,
51    pub rejected_sensitivity: u32,
52    pub rejected_parity: u32,
53    pub prefix_identity: PrefixIdentity,
54}
55
56#[inline]
57fn matches(query: &GraphQuery, quin: &NQuin) -> bool {
58    (query.context == 0 || query.context == quin.context)
59        && (query.subject == 0 || query.subject == quin.subject)
60        && (query.predicate == 0 || query.predicate == quin.predicate)
61        && (query.object == 0 || query.object == quin.object)
62}
63
64/// Select graph facts directly from the flat Quin store into caller-owned storage.
65///
66/// This is the native inference query interface: hashed fields avoid SPARQL parsing and strings in
67/// the request path, while callers that need full SPARQL can resolve a graph slice before calling.
68pub fn query_graph_into(
69    graph: &[NQuin],
70    query: &GraphQuery,
71    policy: GraphAssistPolicy,
72    model_instance: u64,
73    tokenizer_revision: u64,
74    graph_revision: u64,
75    out: &mut [NQuin],
76) -> Result<GraphSelectionReceipt, GraphQueryError> {
77    if policy.max_facts == 0 {
78        return Err(GraphQueryError::InvalidPolicy);
79    }
80    let capacity = out.len().min(policy.max_facts as usize);
81    let mut receipt = GraphSelectionReceipt::default();
82    for quin in graph {
83        receipt.scanned = receipt.scanned.saturating_add(1);
84        if !matches(query, quin) {
85            continue;
86        }
87        let sensitivity = (quin.context >> 56) as u8;
88        if sensitivity > policy.sensitivity_ceiling {
89            receipt.rejected_sensitivity = receipt.rejected_sensitivity.saturating_add(1);
90            continue;
91        }
92        if policy.require_valid_parity
93            && quin.parity != (quin.subject ^ quin.predicate ^ quin.object ^ quin.context)
94        {
95            receipt.rejected_parity = receipt.rejected_parity.saturating_add(1);
96            continue;
97        }
98        receipt.matched = receipt.matched.saturating_add(1);
99        if receipt.written as usize >= capacity {
100            return Err(GraphQueryError::OutputBufferFull);
101        }
102        out[receipt.written as usize] = *quin;
103        receipt.written += 1;
104    }
105    receipt.prefix_identity = derive_prefix_identity(
106        model_instance,
107        tokenizer_revision,
108        query.context,
109        graph_revision,
110        &out[..receipt.written as usize],
111    );
112    Ok(receipt)
113}
114
115/// Select graph facts using a pre-built [`QuinIndex`] to scan only the narrowest non-wildcard
116/// posting list in ascending graph order ($O(k)$ candidate inspection instead of $O(N)$ full scan).
117///
118/// Produces bit-identical `out` facts, `matched`, `written`, `rejected_sensitivity`,
119/// `rejected_parity`, and `prefix_identity` to [`query_graph_into`] without heap allocation.
120pub fn query_graph_indexed_into(
121    graph: &[NQuin],
122    index: &QuinIndex,
123    query: &GraphQuery,
124    policy: GraphAssistPolicy,
125    model_instance: u64,
126    tokenizer_revision: u64,
127    graph_revision: u64,
128    out: &mut [NQuin],
129) -> Result<GraphSelectionReceipt, GraphQueryError> {
130    if policy.max_facts == 0 {
131        return Err(GraphQueryError::InvalidPolicy);
132    }
133    // Fall back to linear scan when all query fields are wildcards or index length differs.
134    if (query.context == 0 && query.subject == 0 && query.predicate == 0 && query.object == 0)
135        || index.len() != graph.len()
136    {
137        return query_graph_into(
138            graph,
139            query,
140            policy,
141            model_instance,
142            tokenizer_revision,
143            graph_revision,
144            out,
145        );
146    }
147
148    let mut slices: [&[usize]; 4] = [&[]; 4];
149    let mut slice_count = 0usize;
150    if query.subject != 0 {
151        slices[slice_count] = index.rows_by_subject(query.subject);
152        slice_count += 1;
153    }
154    if query.predicate != 0 {
155        slices[slice_count] = index.rows_by_predicate(query.predicate);
156        slice_count += 1;
157    }
158    if query.object != 0 {
159        slices[slice_count] = index.rows_by_object(query.object);
160        slice_count += 1;
161    }
162    if query.context != 0 {
163        slices[slice_count] = index.rows_by_context(query.context);
164        slice_count += 1;
165    }
166
167    let mut best_idx = 0usize;
168    for i in 1..slice_count {
169        if slices[i].len() < slices[best_idx].len() {
170            best_idx = i;
171        }
172    }
173    let candidates = slices[best_idx];
174
175    let capacity = out.len().min(policy.max_facts as usize);
176    let mut receipt = GraphSelectionReceipt::default();
177    for &row_idx in candidates {
178        let Some(quin) = graph.get(row_idx) else {
179            continue;
180        };
181        receipt.scanned = receipt.scanned.saturating_add(1);
182        if !matches(query, quin) {
183            continue;
184        }
185        let sensitivity = (quin.context >> 56) as u8;
186        if sensitivity > policy.sensitivity_ceiling {
187            receipt.rejected_sensitivity = receipt.rejected_sensitivity.saturating_add(1);
188            continue;
189        }
190        if policy.require_valid_parity
191            && quin.parity != (quin.subject ^ quin.predicate ^ quin.object ^ quin.context)
192        {
193            receipt.rejected_parity = receipt.rejected_parity.saturating_add(1);
194            continue;
195        }
196        receipt.matched = receipt.matched.saturating_add(1);
197        if receipt.written as usize >= capacity {
198            return Err(GraphQueryError::OutputBufferFull);
199        }
200        out[receipt.written as usize] = *quin;
201        receipt.written += 1;
202    }
203    receipt.prefix_identity = derive_prefix_identity(
204        model_instance,
205        tokenizer_revision,
206        query.context,
207        graph_revision,
208        &out[..receipt.written as usize],
209    );
210    Ok(receipt)
211}
212
213#[cfg(test)]
214mod unit_tests {
215    use super::*;
216
217    fn make_quin(subject: u64, predicate: u64, object: u64, context: u64) -> NQuin {
218        NQuin {
219            subject,
220            predicate,
221            object,
222            context,
223            metadata: 0,
224            parity: subject ^ predicate ^ object ^ context,
225        }
226    }
227
228    #[test]
229    fn indexed_query_is_bit_exact_with_linear_scan_and_reduces_scanned_rows() {
230        let mut bad_parity = make_quin(1, 10, 999, 7);
231        bad_parity.parity ^= 1;
232        let restricted_ctx = (1u64 << 56) | 7;
233        let restricted = make_quin(1, 10, 888, restricted_ctx);
234
235        let graph = [
236            make_quin(1, 10, 100, 7),
237            make_quin(2, 20, 200, 7),
238            bad_parity,
239            make_quin(1, 10, 300, 7),
240            restricted,
241            make_quin(3, 10, 400, 8),
242            make_quin(4, 30, 500, 7),
243            make_quin(1, 10, 600, 7),
244        ];
245        let index = QuinIndex::from_slice(&graph);
246
247        let queries = [
248            // Narrowest on subject=1 (4 rows in subject=1 vs 5 rows in predicate=10 vs 5 rows in context=7)
249            GraphQuery {
250                context: 7,
251                subject: 1,
252                predicate: 10,
253                object: 0,
254            },
255            // Single predicate filter
256            GraphQuery {
257                context: 0,
258                subject: 0,
259                predicate: 10,
260                object: 0,
261            },
262            // Narrowest on object=300 (1 row)
263            GraphQuery {
264                context: 7,
265                subject: 0,
266                predicate: 10,
267                object: 300,
268            },
269            // Restricted context query
270            GraphQuery {
271                context: restricted_ctx,
272                subject: 1,
273                predicate: 10,
274                object: 0,
275            },
276            // Non-existent key (0 candidate rows)
277            GraphQuery {
278                context: 7,
279                subject: 9999,
280                predicate: 10,
281                object: 0,
282            },
283            // Wildcard all fields
284            GraphQuery {
285                context: 0,
286                subject: 0,
287                predicate: 0,
288                object: 0,
289            },
290        ];
291
292        for query in &queries {
293            let mut out_linear = [NQuin::default(); 8];
294            let mut out_indexed = [NQuin::default(); 8];
295            let r_linear = query_graph_into(
296                &graph,
297                query,
298                GraphAssistPolicy::default(),
299                41,
300                42,
301                43,
302                &mut out_linear,
303            )
304            .unwrap();
305            let r_indexed = query_graph_indexed_into(
306                &graph,
307                &index,
308                query,
309                GraphAssistPolicy::default(),
310                41,
311                42,
312                43,
313                &mut out_indexed,
314            )
315            .unwrap();
316
317            assert_eq!(r_indexed.matched, r_linear.matched);
318            assert_eq!(r_indexed.written, r_linear.written);
319            assert_eq!(r_indexed.rejected_sensitivity, r_linear.rejected_sensitivity);
320            assert_eq!(r_indexed.rejected_parity, r_linear.rejected_parity);
321            assert_eq!(r_indexed.prefix_identity, r_linear.prefix_identity);
322            assert_eq!(out_indexed, out_linear);
323            assert!(r_indexed.scanned <= r_linear.scanned);
324        }
325
326        // Verify narrowest candidate selection on (context=7, subject=0, predicate=10, object=300):
327        // object=300 has exactly 1 row in the index vs 8 total graph rows.
328        let mut out_narrow = [NQuin::default(); 4];
329        let r_narrow = query_graph_indexed_into(
330            &graph,
331            &index,
332            &queries[2],
333            GraphAssistPolicy::default(),
334            41,
335            42,
336            43,
337            &mut out_narrow,
338        )
339        .unwrap();
340        assert_eq!(r_narrow.scanned, 1);
341        assert_eq!(r_narrow.written, 1);
342    }
343
344    #[test]
345    fn indexed_query_matches_error_contracts() {
346        let graph = [make_quin(1, 10, 100, 7), make_quin(1, 10, 200, 7)];
347        let index = QuinIndex::from_slice(&graph);
348        let query = GraphQuery {
349            context: 7,
350            subject: 1,
351            predicate: 10,
352            object: 0,
353        };
354
355        let mut out = [NQuin::default(); 1];
356        let bad_policy = GraphAssistPolicy {
357            max_facts: 0,
358            ..GraphAssistPolicy::default()
359        };
360        assert_eq!(
361            query_graph_indexed_into(&graph, &index, &query, bad_policy, 1, 1, 1, &mut out),
362            Err(GraphQueryError::InvalidPolicy)
363        );
364        assert_eq!(
365            query_graph_indexed_into(
366                &graph,
367                &index,
368                &query,
369                GraphAssistPolicy::default(),
370                1,
371                1,
372                1,
373                &mut out
374            ),
375            Err(GraphQueryError::OutputBufferFull)
376        );
377    }
378}