nx_search_onsite_engine.nx source
↩ module page · 469 lines · 19616 B
1// nx_search_onsite_engine.nx -- V1 onsite search engine
2// (composes NxSearchQuery + NxInvIndex -> NxSearchResults).
3//
4// COMPOSES (per NISHI_SMALL_SHARP_COMPOSABLE_STANDARD §4.1 M7):
5// hub/nx_search_query_parser (NxSearchQuery struct + accessors)
6// nx_search_inverted (nx_inv_query_term + NxInvIndex)
7// nx_hygiene_prims (caller-allocated buffer pattern)
8//
9// COMPOSED BY:
10// wiki/nx_wiki_search_handler (next commit; closes /wiki/search 501)
11// (future) sprinkler-config-site search handler
12// any site using the inverted-index layer
13//
14// Status: V1. 2026-05-27.
15//
16// WINNER-TIER: BASELINE-C provisional
17// INCUMBENTS: Lucene IndexSearcher (Elasticsearch core),
18// Tantivy Searcher, Bleve IndexAlias, Whoosh
19// Searcher, MeiliSearch query executor
20// NUMBERS: V1 implements AND-only filter + count-of-matched-
21// terms scoring; paired latency bench vs Lucene
22// IndexSearcher pending real workload
23// GAP: Lucene ships BM25 (default since 6.0), boolean
24// queries with NOT/SHOULD, phrase queries, span
25// queries, field-boosted multi-match -- V1 ships
26// JUST implicit-AND + position-stable ranking
27// PLAN: M-next: V2 BM25F via nx_search_bm25f using
28// nx_search_inverted_persist's positional postings
29// (charter §5.2)
30// EXEMPTION REASON: n/a; provisional pending measurement
31//
32// V1 SCOPE per NISHI_SEARCH_CHARTER.md §5.1:
33// - Implicit AND: doc must contain ALL query terms (sealed
34// no-half-state behavior; V2 adds explicit boolean)
35// - Score = count of distinct query terms matched per doc
36// (per V1 charter §3.5; V2 BM25F + LTR)
37// - Top-N sort descending (max_results from NxSearchQuery)
38// - Sealed NxSearchResults emit; caller owns rowids+scores arrays
39// - elapsed_us QoS observable for monitoring pillar
40//
41// V1 ALGORITHM (honest design):
42// 1. Allocate a counter byte-array sized to max_rowid+1 (caller-
43// owned via nx_search_onsite_init). Each rowid's counter is
44// incremented once per query-term that hits it.
45// 2. For each query term, call nx_inv_query_term, walk the
46// returned rowids, increment counter[rowid].
47// 3. Final pass: emit rowids where counter[rowid] == n_query_terms
48// (= matched ALL terms = AND-intersection).
49// 4. Score is counter value (== n_query_terms for survivors;
50// preserved for V2 scoring hooks).
51// 5. Stable insertion-order tiebreak via single forward walk
52// gives reproducible ranking.
53//
54// COMPLEXITY: O(sum of postings-list lengths + N_docs) per query.
55// At 1000 docs + 5 query terms = ~5000 ops + 1000 scan = sub-ms.
56// SPACE: O(N_docs) bytes for counter array; caller-allocated cap.
57
58import "nx_syscalls.nx"
59import "nx_search_inverted.nx"
60import "nx_search_query_parser.nx"
61
62// ===== Sealed verdict surface (codes 1600-1609) =================================================
63const NX_SOE_OK: i64 = 0
64const NX_SOE_BAD_INPUT: i64 = 1600
65const NX_SOE_INDEX_BAD: i64 = 1601
66const NX_SOE_QUERY_EMPTY: i64 = 1602
67const NX_SOE_RESULTS_CAP_TOO_SMALL: i64 = 1603
68const NX_SOE_COUNTER_CAP_OVERFLOW: i64 = 1604
69const NX_SOE_TERM_BUF_OVERFLOW: i64 = 1605
70const NX_SOE_LOOP_BUDGET: i64 = 1606
71const NX_SOE_NOT_IMPLEMENTED: i64 = 1607
72
73// ===== Named sizing constants (M7 no magic numbers) =================================================
74const NX_SOE_DEFAULT_RESULTS_CAP: i64 = 100
75const NX_SOE_HARD_RESULTS_CAP: i64 = 10000
76const NX_SOE_MAX_TERM_POSTINGS: i64 = 100000 // per-term posting list cap
77const NX_SOE_DEFAULT_COUNTER_CAP: i64 = 4000000 // 4M docs * 1 byte = 4MB
78const NX_SOE_LOOP_BUDGET_PER_QUERY: i64 = 10000000 // hard cap; bail on runaway
79const NX_SOE_MAX_TERMS_USED: i64 = 255 // counter byte saturates here
80const NX_SOE_SCRATCH_TERM_BUF: i64 = 128 // 64-char max term + len byte + room
81
82// ===== NxSearchResults struct (caller-allocated per M4) =================================================
83
84struct NxSearchResults {
85 rowids: *i64 // caller-allocated; cap NX_SOE_HARD_RESULTS_CAP+
86 rowids_cap: i64
87 scores: *i64 // parallel array; same cap as rowids
88 scores_cap: i64
89 count: i64 // # of filled entries
90 elapsed_us: i64 // QoS observable (per Cardinal 18)
91 n_terms: i64 // input query term count (for caller diagnostics)
92 valid: i64
93}
94
95// Sealed-init.
96func nx_search_results_init(r: *NxSearchResults,
97 rowids_buf: *i64, rowids_cap: i64,
98 scores_buf: *i64, scores_cap: i64) -> i64 {
99 if (r as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
100 if (rowids_buf as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
101 if (scores_buf as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
102 if rowids_cap < 1 { return 0 - NX_SOE_RESULTS_CAP_TOO_SMALL }
103 if scores_cap < rowids_cap { return 0 - NX_SOE_BAD_INPUT }
104 if rowids_cap > NX_SOE_HARD_RESULTS_CAP { return 0 - NX_SOE_RESULTS_CAP_TOO_SMALL }
105 r.rowids = rowids_buf
106 r.rowids_cap = rowids_cap
107 r.scores = scores_buf
108 r.scores_cap = scores_cap
109 r.count = 0
110 r.elapsed_us = 0
111 r.n_terms = 0
112 r.valid = 1
113 return NX_SOE_OK
114}
115
116// ===== Engine context (caller owns counter buffer) =================================================
117//
118// Holding the counter buffer outside the per-query run lets the
119// caller amortize the 4MB allocation across many queries.
120
121struct NxSearchOnsiteCtx {
122 counter: *u8 // caller-allocated; len counter_cap bytes
123 counter_cap: i64 // = max_rowid + 1
124 term_buf: *u8 // caller-allocated NX_SOE_SCRATCH_TERM_BUF
125 term_buf_cap: i64
126 postings_buf: *i64 // caller-allocated for nx_inv_query_term output
127 postings_cap: i64
128 valid: i64
129 // V2: per-rowid MUST_NOT hit counter (sys_mmap allocated in _init).
130 // Doc is excluded if must_not_counter[rowid] > 0.
131 must_not_counter: *u8
132}
133
134func nx_search_onsite_init(ctx: *NxSearchOnsiteCtx,
135 counter_buf: *u8, counter_cap: i64,
136 term_buf: *u8, term_buf_cap: i64,
137 postings_buf: *i64, postings_cap: i64) -> i64 {
138 if (ctx as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
139 if (counter_buf as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
140 if (term_buf as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
141 if (postings_buf as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
142 if counter_cap < 1 { return 0 - NX_SOE_COUNTER_CAP_OVERFLOW }
143 if counter_cap > NX_SOE_DEFAULT_COUNTER_CAP { return 0 - NX_SOE_COUNTER_CAP_OVERFLOW }
144 if term_buf_cap < NX_SOE_SCRATCH_TERM_BUF { return 0 - NX_SOE_TERM_BUF_OVERFLOW }
145 if postings_cap < 1 { return 0 - NX_SOE_BAD_INPUT }
146 if postings_cap > NX_SOE_MAX_TERM_POSTINGS { return 0 - NX_SOE_BAD_INPUT }
147 ctx.counter = counter_buf
148 ctx.counter_cap = counter_cap
149 ctx.term_buf = term_buf
150 ctx.term_buf_cap = term_buf_cap
151 ctx.postings_buf = postings_buf
152 ctx.postings_cap = postings_cap
153 // V2: must_not_counter sized parallel to counter; internally allocated.
154 ctx.must_not_counter = sys_mmap(counter_cap)
155 ctx.valid = 1
156 return NX_SOE_OK
157}
158
159// ===== Counter array reset (bounded) =================================================
160
161func nx_soe_counter_reset(ctx: *NxSearchOnsiteCtx) -> i64 {
162 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
163 var i: i64 = 0
164 var iter: i64 = 0
165 while i < ctx.counter_cap {
166 if iter >= NX_SOE_LOOP_BUDGET_PER_QUERY { return 0 - NX_SOE_LOOP_BUDGET }
167 ctx.counter[i] = 0 as u8
168 ctx.must_not_counter[i] = 0 as u8 // V2 reset
169 i = i + 1
170 iter = iter + 1
171 }
172 return NX_SOE_OK
173}
174
175// ===== Per-term posting walk: increment counters =================================================
176
177// V2: kind-aware posting walker. Routes increments to the appropriate
178// counter based on term kind (MUST/SHOULD -> match counter; MUST_NOT
179// -> must_not counter). Called by run loop with the parsed term kind.
180func nx_soe_apply_term_postings_kind(ctx: *NxSearchOnsiteCtx,
181 idx: *NxInvIndex,
182 term_ptr: *u8, term_n: i64,
183 term_kind: i64) -> i64 {
184 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
185 if (idx as i64) == 0 { return 0 - NX_SOE_INDEX_BAD }
186
187 let result: *NxInvQueryResult = (sys_mmap(64)) as *NxInvQueryResult
188 let rc: i64 = nx_inv_query_term(idx, term_ptr, term_n,
189 ctx.postings_buf, ctx.postings_cap, result)
190 if rc == NX_INV_NO_MATCHES { return NX_SOE_OK }
191 if rc != NX_INV_OK { return 0 - NX_SOE_INDEX_BAD }
192
193 var i: i64 = 0
194 var iter: i64 = 0
195 while i < result.n_rowids_filled {
196 if iter >= NX_SOE_LOOP_BUDGET_PER_QUERY { return 0 - NX_SOE_LOOP_BUDGET }
197 let rowid: i64 = ctx.postings_buf[i]
198 if rowid < 0 { i = i + 1; iter = iter + 1 }
199 if rowid >= 0 {
200 if rowid >= ctx.counter_cap { return 0 - NX_SOE_COUNTER_CAP_OVERFLOW }
201 // V2 dispatch by kind.
202 if term_kind == 2 { // MUST_NOT (NX_SQP_TERM_KIND_MUST_NOT)
203 let cur_mn: i64 = ctx.must_not_counter[rowid] as i64
204 if cur_mn < 255 {
205 ctx.must_not_counter[rowid] = ((cur_mn + 1) & 0xff) as u8
206 }
207 }
208 if term_kind != 2 { // MUST or SHOULD -> match counter
209 let cur: i64 = ctx.counter[rowid] as i64
210 if cur < NX_SOE_MAX_TERMS_USED {
211 ctx.counter[rowid] = ((cur + 1) & 0xff) as u8
212 }
213 }
214 i = i + 1; iter = iter + 1
215 }
216 }
217 return NX_SOE_OK
218}
219
220// V1 backward-compat: defaults to MUST kind (preserves implicit-AND).
221func nx_soe_apply_term_postings(ctx: *NxSearchOnsiteCtx,
222 idx: *NxInvIndex,
223 term_ptr: *u8, term_n: i64) -> i64 {
224 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
225 if (idx as i64) == 0 { return 0 - NX_SOE_INDEX_BAD }
226
227 // Query the inverted index.
228 let result: *NxInvQueryResult = (sys_mmap(64)) as *NxInvQueryResult
229 let rc: i64 = nx_inv_query_term(idx, term_ptr, term_n,
230 ctx.postings_buf, ctx.postings_cap, result)
231 if rc == NX_INV_NO_MATCHES { return NX_SOE_OK } // term not in vocab; AND will eliminate
232 if rc != NX_INV_OK { return 0 - NX_SOE_INDEX_BAD }
233
234 // Walk filled rowids; increment counters.
235 var i: i64 = 0
236 var iter: i64 = 0
237 while i < result.n_rowids_filled {
238 if iter >= NX_SOE_LOOP_BUDGET_PER_QUERY { return 0 - NX_SOE_LOOP_BUDGET }
239 let rowid: i64 = ctx.postings_buf[i]
240 if rowid < 0 {
241 // Defensive: bad posting; skip.
242 i = i + 1
243 iter = iter + 1
244 }
245 if rowid >= 0 {
246 if rowid >= ctx.counter_cap {
247 // Doc beyond counter cap; can't score this query.
248 return 0 - NX_SOE_COUNTER_CAP_OVERFLOW
249 }
250 // Saturating increment: stop at 255 (u8 ceiling).
251 let cur: i64 = ctx.counter[rowid] as i64
252 if cur < NX_SOE_MAX_TERMS_USED {
253 ctx.counter[rowid] = ((cur + 1) & 0xff) as u8
254 }
255 i = i + 1
256 iter = iter + 1
257 }
258 }
259 return NX_SOE_OK
260}
261
262// ===== Copy parsed term out of NxSearchQuery into scratch buffer =================================================
263//
264// NxSearchQuery stores terms packed; we want a stable buffer the
265// inverted index can hash safely. Bounded copy.
266
267func nx_soe_copy_term(ctx: *NxSearchOnsiteCtx,
268 q: *NxSearchQuery, term_idx: i64,
269 out_n: *i64) -> i64 {
270 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
271 if (out_n as i64) == 0 { return 0 - NX_SOE_BAD_INPUT }
272
273 let term_ptr_out: *i64 = (sys_mmap(8)) as *i64
274 let term_len_out: *i64 = (sys_mmap(8)) as *i64
275 term_ptr_out[0] = 0
276 term_len_out[0] = 0
277 let rc: i64 = nx_search_query_term_at(q, term_idx, term_ptr_out, term_len_out)
278 if rc != NX_SQP_OK { return 0 - NX_SOE_BAD_INPUT }
279 let src: *u8 = term_ptr_out[0] as *u8
280 let len: i64 = term_len_out[0]
281 if len < 1 { return 0 - NX_SOE_BAD_INPUT }
282 if len + 1 > ctx.term_buf_cap { return 0 - NX_SOE_TERM_BUF_OVERFLOW }
283
284 var i: i64 = 0
285 while i < len {
286 if i >= NX_SOE_SCRATCH_TERM_BUF { return 0 - NX_SOE_TERM_BUF_OVERFLOW }
287 ctx.term_buf[i] = src[i]
288 i = i + 1
289 }
290 out_n[0] = len
291 return NX_SOE_OK
292}
293
294// ===== Top-N collection: walk counter array, emit qualifying rowids =================================================
295//
296// V1 ranking: score = counter[rowid] == n_terms (all matched).
297// Tiebreak = ascending rowid (stable insertion-order from index
298// construction). Walks counter array once; bounded by counter_cap.
299
300func nx_soe_collect_results(ctx: *NxSearchOnsiteCtx,
301 n_terms: i64,
302 r: *NxSearchResults,
303 max_results: i64) -> i64 {
304 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
305 if r.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
306 if n_terms < 1 { return 0 - NX_SOE_QUERY_EMPTY }
307 if max_results < 1 { return 0 - NX_SOE_BAD_INPUT }
308
309 var cap: i64 = max_results
310 if cap > r.rowids_cap { cap = r.rowids_cap }
311
312 var emitted: i64 = 0
313 var i: i64 = 0
314 var iter: i64 = 0
315 while i < ctx.counter_cap {
316 if emitted >= cap { i = ctx.counter_cap + 1 } // sentinel: stop
317 if iter >= NX_SOE_LOOP_BUDGET_PER_QUERY { return 0 - NX_SOE_LOOP_BUDGET }
318 iter = iter + 1
319 if i < ctx.counter_cap {
320 let c: i64 = ctx.counter[i] as i64
321 if c == n_terms {
322 if emitted < r.rowids_cap {
323 r.rowids[emitted] = i
324 r.scores[emitted] = c
325 emitted = emitted + 1
326 }
327 }
328 i = i + 1
329 }
330 }
331 r.count = emitted
332 return NX_SOE_OK
333}
334
335// V2: kind-aware collect. Emit rowid when match_counter >= must_count
336// AND must_not_counter == 0. Score = match_counter value (count of
337// matched MUST + SHOULD terms; higher = more relevant).
338func nx_soe_collect_results_v2(ctx: *NxSearchOnsiteCtx,
339 must_count: i64,
340 r: *NxSearchResults,
341 max_results: i64) -> i64 {
342 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
343 if r.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
344 if must_count < 0 { return 0 - NX_SOE_BAD_INPUT }
345 if max_results < 1 { return 0 - NX_SOE_BAD_INPUT }
346
347 var cap: i64 = max_results
348 if cap > r.rowids_cap { cap = r.rowids_cap }
349
350 var emitted: i64 = 0
351 var i: i64 = 0
352 var iter: i64 = 0
353 while i < ctx.counter_cap {
354 if emitted >= cap { i = ctx.counter_cap + 1 }
355 if iter >= NX_SOE_LOOP_BUDGET_PER_QUERY { return 0 - NX_SOE_LOOP_BUDGET }
356 iter = iter + 1
357 if i < ctx.counter_cap {
358 let mn: i64 = ctx.must_not_counter[i] as i64
359 let c: i64 = ctx.counter[i] as i64
360 // MUST satisfied AND no MUST_NOT hit?
361 if mn == 0 {
362 if c >= must_count {
363 if c > 0 { // exclude truly-zero matches (must_count==0 + nothing matched)
364 if emitted < r.rowids_cap {
365 r.rowids[emitted] = i
366 r.scores[emitted] = c
367 emitted = emitted + 1
368 }
369 }
370 }
371 }
372 i = i + 1
373 }
374 }
375 r.count = emitted
376 return NX_SOE_OK
377}
378
379// ===== Top-level entry: run a query end-to-end =================================================
380
381func nx_search_onsite_run(ctx: *NxSearchOnsiteCtx,
382 idx: *NxInvIndex,
383 q: *NxSearchQuery,
384 r: *NxSearchResults) -> i64 {
385 if ctx.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
386 if r.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
387 if (idx as i64) == 0 { return 0 - NX_SOE_INDEX_BAD }
388 if q.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
389
390 let t_start: i64 = sys_clock_now_us()
391
392 let n_terms: i64 = nx_search_query_count(q)
393 r.n_terms = n_terms
394 if n_terms < 1 {
395 // Empty query is well-defined: zero results, no error
396 // (so /wiki/search?n=20 with no q still renders empty page).
397 r.count = 0
398 r.elapsed_us = sys_clock_now_us() - t_start
399 return NX_SOE_OK
400 }
401 if n_terms > NX_SOE_MAX_TERMS_USED { return 0 - NX_SOE_BAD_INPUT }
402
403 // Reset counter array.
404 let rc_reset: i64 = nx_soe_counter_reset(ctx)
405 if rc_reset != NX_SOE_OK { return rc_reset }
406
407 // For each term: copy into scratch + apply postings -> counters
408 // (V2: kind-aware dispatch to match/must_not counters).
409 // Also count MUSTs to compute the required-match threshold.
410 var ti: i64 = 0
411 var iter: i64 = 0
412 var must_count: i64 = 0
413 while ti < n_terms {
414 if iter >= NX_SOE_LOOP_BUDGET_PER_QUERY { return 0 - NX_SOE_LOOP_BUDGET }
415 iter = iter + 1
416
417 let term_len_out: *i64 = (sys_mmap(8)) as *i64
418 term_len_out[0] = 0
419 let rc_copy: i64 = nx_soe_copy_term(ctx, q, ti, term_len_out)
420 if rc_copy != NX_SOE_OK { return rc_copy }
421
422 let term_kind: i64 = nx_search_query_term_kind_at(q, ti)
423 if term_kind == 1 { must_count = must_count + 1 } // NX_SQP_TERM_KIND_MUST
424
425 let rc_apply: i64 = nx_soe_apply_term_postings_kind(ctx, idx,
426 ctx.term_buf, term_len_out[0],
427 term_kind)
428 if rc_apply != NX_SOE_OK { return rc_apply }
429
430 ti = ti + 1
431 }
432
433 // Collect top-N. V2 filter: emit rowid if match_count >= must_count
434 // AND must_not_counter[rowid] == 0. V1 backward compat: when all
435 // terms are MUST (default), must_count == n_terms, so emission
436 // matches V1 exactly (only docs with all terms hit are emitted).
437 let max_results: i64 = nx_search_query_max_results(q)
438 let rc_collect: i64 = nx_soe_collect_results_v2(ctx, must_count, r, max_results)
439 if rc_collect != NX_SOE_OK { return rc_collect }
440
441 r.elapsed_us = sys_clock_now_us() - t_start
442 return NX_SOE_OK
443}
444
445// ===== Result accessors (M1 no NULL; bounded) =================================================
446
447func nx_search_results_count(r: *NxSearchResults) -> i64 {
448 if r.valid != 1 { return 0 }
449 return r.count
450}
451
452func nx_search_results_rowid_at(r: *NxSearchResults, i: i64) -> i64 {
453 if r.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
454 if i < 0 { return 0 - NX_SOE_BAD_INPUT }
455 if i >= r.count { return 0 - NX_SOE_BAD_INPUT }
456 return r.rowids[i]
457}
458
459func nx_search_results_score_at(r: *NxSearchResults, i: i64) -> i64 {
460 if r.valid != 1 { return 0 - NX_SOE_BAD_INPUT }
461 if i < 0 { return 0 - NX_SOE_BAD_INPUT }
462 if i >= r.count { return 0 - NX_SOE_BAD_INPUT }
463 return r.scores[i]
464}
465
466func nx_search_results_elapsed_us(r: *NxSearchResults) -> i64 {
467 if r.valid != 1 { return 0 }
468 return r.elapsed_us
469}