code wiki / _hdl_build / nx_dataframe_approx.nx
`nx_dataframe_approx.nx` source

1// nx_dataframe_approx.nx -- LIB: wire the DORMANT sketch primitives behind the aggregation front door
2// (nx_dataframe). The 07-10 audit found nx_sketch_hll (HLL++) and nx_sketch_tdigest (Dunning) genuinely
3// real but ORPHANED -- and their accuracy claims UNMEASURED (headers: ReferenceImpl / NOT_YET_EVALUATED).
4// This lib gives the store-facing calls (approx distinct + approx quantile AT SCALE) and its gate MEASURES
5// estimate error against exact ground truth computed independently -- killing the unmeasured-claim debt.
6// license_tier: ORIGINAL
7import "nx_syscalls.nx"
8import "_hdl_build/nx_dataframe.nx"
9import "nx_sketch_hll.nx"
10import "nx_sketch_tdigest.nx"
11
12// approx COUNT DISTINCT of an i64 column via HLL++ (lg_k=12 -> ~1.6 percent rel stddev, 4KB registers).
13func dfa_distinct(col: *i64, n: i64, lg_k: i64) -> i64 {
14    let h: *Hll = nx_hll_alloc(lg_k, 2654435769)
15    if (h as i64) == 0 { return 0 - 1 }
16    let kb: *u8 = sys_mmap(8)
17    var i: i64 = 0
18    while i < n {
19        let v: i64 = col[i]
20        kb[0] = (v & 0xff) as u8
21        kb[1] = ((v >> 8) & 0xff) as u8
22        kb[2] = ((v >> 16) & 0xff) as u8
23        kb[3] = ((v >> 24) & 0xff) as u8
24        kb[4] = ((v >> 32) & 0xff) as u8
25        kb[5] = ((v >> 40) & 0xff) as u8
26        kb[6] = ((v >> 48) & 0xff) as u8
27        kb[7] = ((v >> 56) & 0xff) as u8
28        nx_hll_add(h, kb, 8)
29        i = i + 1
30    }
31    return nx_hll_estimate(h)
32}
33
34// EXACT distinct (first-seen scan) -- the independent ground truth the gate measures the sketch against.
35// O(n * d); fine at gate scale, and honest: no assumed cardinality, it is COUNTED.
36func dfa_distinct_exact(col: *i64, n: i64, scratch: *i64, max_d: i64) -> i64 {
37    var d: i64 = 0
38    var i: i64 = 0
39    while i < n {
40        let v: i64 = col[i]
41        var seen: i64 = 0
42        var j: i64 = 0
43        while j < d { if scratch[j] == v { seen = 1; j = d } else { j = j + 1 } }
44        if seen == 0 { if d < max_d { scratch[d] = v; d = d + 1 } }
45        i = i + 1
46    }
47    return d
48}
49
50// approx QUANTILE via t-digest (q_permil 0..1000, same scale as df_quantile). delta = compression (100 typical).
51func dfa_quantile(col: *i64, n: i64, q_permil: i64, delta: i64) -> i64 {
52    let td: *TDigest = nx_tdigest_alloc(delta)
53    if (td as i64) == 0 { return 0 - 1 }
54    var i: i64 = 0
55    while i < n { nx_tdigest_add(td, col[i]); i = i + 1 }
56    return nx_tdigest_quantile(td, q_permil)
57}
58
59// relative error in PERMIL between estimate and exact (|est-exact|*1000/exact); exact<=0 -> -1.
60func dfa_err_permil(est: i64, exact: i64) -> i64 {
61    if exact <= 0 { return 0 - 1 }
62    var d: i64 = est - exact
63    if d < 0 { d = 0 - d }
64    return (d * 1000) / exact
65}
nx_dataframe_approx.nx source

`nx_dataframe_approx.nx` source
