nx_blockmax_wand.nx source

1// nx_blockmax_wand.nx -- LIB: block-max top-k pruning (block-max-WAND / MaxScore family) = the QUERY-SPEED lever for a 2// billion-posting index. Instead of scoring every doc in every query term's postings, keep a top-k threshold and PRUNE 3// any doc whose UPPER BOUND (sum of the per-BLOCK max impacts of the terms that contain it) can't beat the threshold. 4// Composes the 256-doc blocks from nx_posting_compress -- each block carries a max-impact, so whole blocks skip. The 5// invariant that makes it EXACT: upper_bound >= true score, so a pruned doc could never have entered the top-k. 6// Built + gated NOW on a fixture (exactness vs exhaustive + measured skips); the pivot/skip-pointer scaling runs on the 7// NAS index later. No float. license_tier: ORIGINAL 8import "nx_syscalls.nx" 9 10const BMW_B: i64 = 2 // demo block size (fine, so block-max < term-max); production block = 256 (nx_posting_compress) 11 12// per-block max impact for a term's impact array -> bm[]; returns block count. 13func bmw_block_max(imp: *i64, cnt: i64, bm: *i64) -> i64 { 14 var b: i64 = 0; var i: i64 = 0 15 while i < cnt { 16 var mx: i64 = 0; var j: i64 = 0 17 while j < BMW_B { if i+j < cnt { if imp[i+j] > mx { mx = imp[i+j] } } j = j + 1 } 18 bm[b] = mx; b = b + 1; i = i + BMW_B 19 } 20 return b 21} 22// impact of a term (docs,imp,cnt) for doc d; sets blk[0]=block index; returns -1 if absent. 23func bmw_find(docs: *i64, imp: *i64, cnt: i64, d: i64, blk: *i64) -> i64 { 24 var i: i64 = 0 25 while i < cnt { if docs[i] == d { blk[0] = i / BMW_B; return imp[i] } i = i + 1 } 26 return 0 - 1 27} 28// full score of doc d = sum of impacts of query terms containing d. 29func bmw_score(td: *i64, ti: *i64, tc: *i64, nt: i64, d: i64) -> i64 { 30 var s: i64 = 0; var t: i64 = 0 31 let blk: *i64 = sys_mmap(8) as *i64 32 while t < nt { let im: i64 = bmw_find(td[t] as *i64, ti[t] as *i64, tc[t], d, blk); if im >= 0 { s = s + im } t = t + 1 } 33 return s 34} 35// block-max upper bound for d = sum of per-block max impacts of the terms containing d (>= true score). 36func bmw_ub(td: *i64, ti: *i64, tc: *i64, tbm: *i64, nt: i64, d: i64) -> i64 { 37 var ub: i64 = 0; var t: i64 = 0 38 let blk: *i64 = sys_mmap(8) as *i64 39 while t < nt { let im: i64 = bmw_find(td[t] as *i64, ti[t] as *i64, tc[t], d, blk); if im >= 0 { let bm: *i64 = tbm[t] as *i64; ub = ub + bm[blk[0]] } t = t + 1 } 40 return ub 41} 42// insert (d,s) into the top-k arrays; maintain theta[0] = current kth-best (min of the k). returns 1 if inserted. 43func bmw_insert(tkd: *i64, tks: *i64, k: i64, filled: *i64, theta: *i64, d: i64, s: i64) -> i64 { 44 if filled[0] < k { 45 tkd[filled[0]] = d; tks[filled[0]] = s; filled[0] = filled[0] + 1 46 if filled[0] == k { var mn: i64 = tks[0]; var i: i64 = 1; while i < k { if tks[i] < mn { mn = tks[i] } i = i + 1 } theta[0] = mn } 47 return 1 48 } 49 if s > theta[0] { 50 var mi: i64 = 0; var i: i64 = 1; while i < k { if tks[i] < tks[mi] { mi = i } i = i + 1 } 51 tkd[mi] = d; tks[mi] = s 52 var mn: i64 = tks[0]; i = 1; while i < k { if tks[i] < mn { mn = tks[i] } i = i + 1 } theta[0] = mn 53 return 1 54 } 55 return 0 56} 57// EXHAUSTIVE top-k: score every union doc. fills tkd/tks[k]; returns docs scored (= nu). 58func bmw_exhaustive(td: *i64, ti: *i64, tc: *i64, nt: i64, udocs: *i64, nu: i64, k: i64, tkd: *i64, tks: *i64) -> i64 { 59 let filled: *i64 = sys_mmap(8) as *i64; filled[0] = 0 60 let theta: *i64 = sys_mmap(8) as *i64; theta[0] = 0 61 var i: i64 = 0 62 while i < nu { let s: i64 = bmw_score(td, ti, tc, nt, udocs[i]); bmw_insert(tkd, tks, k, filled, theta, udocs[i], s); i = i + 1 } 63 return nu 64} 65// BLOCK-MAX PRUNED top-k: skip any doc whose block-max upper bound <= threshold. fills tkd/tks[k]; returns docs FULLY SCORED. 66func bmw_blockmax(td: *i64, ti: *i64, tc: *i64, tbm: *i64, nt: i64, udocs: *i64, nu: i64, k: i64, tkd: *i64, tks: *i64) -> i64 { 67 let filled: *i64 = sys_mmap(8) as *i64; filled[0] = 0 68 let theta: *i64 = sys_mmap(8) as *i64; theta[0] = 0 69 var scored: i64 = 0 70 var i: i64 = 0 71 while i < nu { 72 let d: i64 = udocs[i] 73 var doit: i64 = 0 74 if filled[0] < k { doit = 1 } else { if bmw_ub(td, ti, tc, tbm, nt, d) > theta[0] { doit = 1 } } 75 if doit == 1 { let s: i64 = bmw_score(td, ti, tc, nt, d); scored = scored + 1; bmw_insert(tkd, tks, k, filled, theta, d, s) } 76 i = i + 1 77 } 78 return scored 79}