nx_sketch_ams.nx source
↩ module page · 203 lines · 6159 B
1// sketch_ams.nx -- AMS sketch (Alon-Matias-Szegedy 1996).
2//
3// Estimates F_2 = Σ f_i² (second frequency moment) of a stream over
4// implicit-keyed items. Used for:
5// - self-join size estimation in databases
6// - query-plan cardinality estimation
7// - skew detection (high F_2 = skewed distribution)
8// - L2 norm of frequency vector
9//
10// ALGORITHM:
11// For each of d * s estimators, a random ±1 sign function ξ_jk.
12// On (item x, count c): counter[j][k] += ξ_jk(x) * c for all (j,k).
13// F_2 estimate per estimator: counter[j][k]²
14// Within-group AVERAGE: F_2_j = mean of counter[j][k]² over k.
15// Across-group MEDIAN: F_2 ≈ median(F_2_j) across j.
16//
17// Variance: average reduces variance by 1/s. Median over d
18// independent estimates boosts confidence to 1 - 2^(-d/2).
19//
20// MEMORY: d * s * 8 bytes. d=5, s=64 -> 2560 bytes for F_2 with
21// 12.5% relative error at 87.5% confidence.
22//
23// LOSSLESS-LANGUAGE DISCIPLINE: nx_ams_query returns ApproxI64 with
24// NX_ENV_REL_STDDEV = 1/sqrt(s) per estimator (further tightened by
25// median-of-d boost in practice). conf_ppb tracks (1 - 2^(-d/2)).
26
27// nx_safety_envelope:
28// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
29// sil_target: SIL1
30// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
31// verdict: NOT_YET_EVALUATED
32
33import "nx_syscalls.nx"
34import "nx_sketch_types.nx"
35import "nx_vecmath.nx"
36
37const NX_AMS_MIN_D: i64 = 3
38const NX_AMS_MAX_D: i64 = 32
39const NX_AMS_MIN_S: i64 = 4
40const NX_AMS_MAX_S: i64 = 1024
41
42struct AMS {
43 counters: *i64, // d * s
44 d: i64,
45 s: i64,
46 seed: i64,
47 total: i64,
48}
49
50// === construction =================================================
51
52func nx_ams_alloc(d: i64, s: i64, seed: i64) -> *AMS {
53 if d < NX_AMS_MIN_D { return 0 as *AMS }
54 if d > NX_AMS_MAX_D { return 0 as *AMS }
55 if s < NX_AMS_MIN_S { return 0 as *AMS }
56 if s > NX_AMS_MAX_S { return 0 as *AMS }
57 let raw: *u8 = sys_mmap(48)
58 let a: *AMS = raw as *AMS
59 let cells: i64 = d * s
60 a.counters = sys_mmap(cells * 8) as *i64
61 var i: i64 = 0
62 while i < cells {
63 a.counters[i] = 0
64 i = i + 1
65 }
66 a.d = d
67 a.s = s
68 a.seed = seed
69 a.total = 0
70 return a
71}
72
73// === sign hash function ===========================================
74//
75// For estimator (j, k) and item key, derive a deterministic ±1 sign.
76// Mix item key with row/col indices and seed; top bit -> sign.
77
78func nx_ams_sign(a: *AMS, key: i64, j: i64, k: i64) -> i64 {
79 let mixed: i64 = ((key + j * 0x9E3779B9 + k * 0xBF58476D1CE4E5B9) *
80 0xC2B2AE3D27D4EB4F + a.seed) & 0xFFFFFFFFFFFFFFFF
81 if (mixed & (1 << 63)) == 0 { return 1 }
82 return -1
83}
84
85func nx_ams_cell_idx(a: *AMS, j: i64, k: i64) -> i64 {
86 return j * a.s + k
87}
88
89// === add ==========================================================
90
91func nx_ams_add(a: *AMS, key: i64, count: i64) -> i64 {
92 if count == 0 { return 0 }
93 a.total = a.total + count
94 var j: i64 = 0
95 while j < a.d {
96 var k: i64 = 0
97 while k < a.s {
98 let sign: i64 = nx_ams_sign(a, key, j, k)
99 let idx: i64 = nx_ams_cell_idx(a, j, k)
100 a.counters[idx] = a.counters[idx] + sign * count
101 k = k + 1
102 }
103 j = j + 1
104 }
105 return 0
106}
107
108// === F_2 estimate =================================================
109//
110// Per estimator: F_2_jk = counter[j][k]²
111// Group average: F_2_j = (1/s) Σ_k counter[j][k]²
112// Median across j: F_2 = median(F_2_j)
113
114func nx_ams_isqrt(x: i64) -> i64 { return vm_isqrt(x) }
115
116func nx_ams_f2(a: *AMS) -> i64 {
117 // Compute group averages into scratch[d].
118 let scratch_raw: *u8 = sys_mmap(a.d * 8)
119 let scratch: *i64 = scratch_raw as *i64
120 var j: i64 = 0
121 while j < a.d {
122 var sum_sq: i64 = 0
123 var k: i64 = 0
124 while k < a.s {
125 let idx: i64 = nx_ams_cell_idx(a, j, k)
126 let c: i64 = a.counters[idx]
127 sum_sq = sum_sq + c * c
128 k = k + 1
129 }
130 scratch[j] = sum_sq / a.s
131 j = j + 1
132 }
133 // Insertion sort scratch[0..d).
134 var i: i64 = 1
135 while i < a.d {
136 let cur: i64 = scratch[i]
137 var p: i64 = i - 1
138 var done: i64 = 0
139 while done == 0 {
140 if p < 0 { done = 1 }
141 if done == 0 {
142 if scratch[p] <= cur { done = 1 }
143 if done == 0 {
144 scratch[p + 1] = scratch[p]
145 p = p - 1
146 }
147 }
148 }
149 scratch[p + 1] = cur
150 i = i + 1
151 }
152 // Median.
153 return scratch[a.d / 2]
154}
155
156// === typed envelope ===============================================
157
158func nx_ams_stderr_ppb(s: i64) -> i64 {
159 // Per-estimator relative stddev ~ 1/sqrt(s).
160 let isq: i64 = nx_ams_isqrt(s)
161 if isq == 0 { return 1000000000 }
162 return 1000000000 / isq
163}
164
165func nx_ams_conf_ppb(d: i64) -> i64 {
166 // (1 - 2^(-d/2)) confidence. d=5 -> 1 - 0.177 ~ 0.823.
167 if d <= 3 { return 500000000 }
168 if d <= 5 { return 823000000 }
169 if d <= 7 { return 875000000 }
170 if d <= 11 { return 968000000 }
171 return 992000000
172}
173
174func nx_ams_query_f2(a: *AMS) -> *ApproxI64 {
175 let f2: i64 = nx_ams_f2(a)
176 return nx_approx_new(f2, NX_ENV_REL_STDDEV, nx_ams_stderr_ppb(a.s),
177 nx_ams_conf_ppb(a.d),
178 NX_MATURITY_REFERENCE_IMPL,
179 NX_ADV_HONEST)
180}
181
182// === merge ========================================================
183//
184// Counters add element-wise. Matching d, s, seed required.
185
186func nx_ams_merge(a: *AMS, b: *AMS) -> *AMS {
187 if a.d != b.d { return 0 as *AMS }
188 if a.s != b.s { return 0 as *AMS }
189 if a.seed != b.seed { return 0 as *AMS }
190 let out: *AMS = nx_ams_alloc(a.d, a.s, a.seed)
191 let cells: i64 = a.d * a.s
192 var i: i64 = 0
193 while i < cells {
194 out.counters[i] = a.counters[i] + b.counters[i]
195 i = i + 1
196 }
197 out.total = a.total + b.total
198 return out
199}
200
201func nx_ams_memory_bytes(a: *AMS) -> i64 {
202 return 48 + a.d * a.s * 8
203}