nx_sketch_ams.nx source
↩ module page · 217 lines · 6453 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"
35
36const NX_AMS_MIN_D: i64 = 3
37const NX_AMS_MAX_D: i64 = 32
38const NX_AMS_MIN_S: i64 = 4
39const NX_AMS_MAX_S: i64 = 1024
40
41struct AMS {
42 counters: *i64, // d * s
43 d: i64,
44 s: i64,
45 seed: i64,
46 total: i64,
47}
48
49// === construction =================================================
50
51func nx_ams_alloc(d: i64, s: i64, seed: i64) -> *AMS {
52 if d < NX_AMS_MIN_D { return 0 as *AMS }
53 if d > NX_AMS_MAX_D { return 0 as *AMS }
54 if s < NX_AMS_MIN_S { return 0 as *AMS }
55 if s > NX_AMS_MAX_S { return 0 as *AMS }
56 let raw: *u8 = sys_mmap(48)
57 let a: *AMS = raw as *AMS
58 let cells: i64 = d * s
59 a.counters = sys_mmap(cells * 8) as *i64
60 var i: i64 = 0
61 while i < cells {
62 a.counters[i] = 0
63 i = i + 1
64 }
65 a.d = d
66 a.s = s
67 a.seed = seed
68 a.total = 0
69 return a
70}
71
72// === sign hash function ===========================================
73//
74// For estimator (j, k) and item key, derive a deterministic ±1 sign.
75// Mix item key with row/col indices and seed; top bit -> sign.
76
77func nx_ams_sign(a: *AMS, key: i64, j: i64, k: i64) -> i64 {
78 let mixed: i64 = ((key + j * 0x9E3779B9 + k * 0xBF58476D1CE4E5B9) *
79 0xC2B2AE3D27D4EB4F + a.seed) & 0xFFFFFFFFFFFFFFFF
80 if (mixed & (1 << 63)) == 0 { return 1 }
81 return -1
82}
83
84func nx_ams_cell_idx(a: *AMS, j: i64, k: i64) -> i64 {
85 return j * a.s + k
86}
87
88// === add ==========================================================
89
90func nx_ams_add(a: *AMS, key: i64, count: i64) -> i64 {
91 if count == 0 { return 0 }
92 a.total = a.total + count
93 var j: i64 = 0
94 while j < a.d {
95 var k: i64 = 0
96 while k < a.s {
97 let sign: i64 = nx_ams_sign(a, key, j, k)
98 let idx: i64 = nx_ams_cell_idx(a, j, k)
99 a.counters[idx] = a.counters[idx] + sign * count
100 k = k + 1
101 }
102 j = j + 1
103 }
104 return 0
105}
106
107// === F_2 estimate =================================================
108//
109// Per estimator: F_2_jk = counter[j][k]²
110// Group average: F_2_j = (1/s) Σ_k counter[j][k]²
111// Median across j: F_2 = median(F_2_j)
112
113func nx_ams_isqrt(x: i64) -> i64 {
114 if x < 0 { return 0 }
115 if x == 0 { return 0 }
116 if x < 4 { return 1 }
117 var g: i64 = (x >> 1) + 1
118 var iter: i64 = 0
119 while iter < 64 {
120 let next_g: i64 = (g + x / g) / 2
121 if next_g >= g { iter = 64 }
122 if next_g < g {
123 g = next_g
124 iter = iter + 1
125 }
126 }
127 return g
128}
129
130func nx_ams_f2(a: *AMS) -> i64 {
131 // Compute group averages into scratch[d].
132 let scratch_raw: *u8 = sys_mmap(a.d * 8)
133 let scratch: *i64 = scratch_raw as *i64
134 var j: i64 = 0
135 while j < a.d {
136 var sum_sq: i64 = 0
137 var k: i64 = 0
138 while k < a.s {
139 let idx: i64 = nx_ams_cell_idx(a, j, k)
140 let c: i64 = a.counters[idx]
141 sum_sq = sum_sq + c * c
142 k = k + 1
143 }
144 scratch[j] = sum_sq / a.s
145 j = j + 1
146 }
147 // Insertion sort scratch[0..d).
148 var i: i64 = 1
149 while i < a.d {
150 let cur: i64 = scratch[i]
151 var p: i64 = i - 1
152 var done: i64 = 0
153 while done == 0 {
154 if p < 0 { done = 1 }
155 if done == 0 {
156 if scratch[p] <= cur { done = 1 }
157 if done == 0 {
158 scratch[p + 1] = scratch[p]
159 p = p - 1
160 }
161 }
162 }
163 scratch[p + 1] = cur
164 i = i + 1
165 }
166 // Median.
167 return scratch[a.d / 2]
168}
169
170// === typed envelope ===============================================
171
172func nx_ams_stderr_ppb(s: i64) -> i64 {
173 // Per-estimator relative stddev ~ 1/sqrt(s).
174 let isq: i64 = nx_ams_isqrt(s)
175 if isq == 0 { return 1000000000 }
176 return 1000000000 / isq
177}
178
179func nx_ams_conf_ppb(d: i64) -> i64 {
180 // (1 - 2^(-d/2)) confidence. d=5 -> 1 - 0.177 ~ 0.823.
181 if d <= 3 { return 500000000 }
182 if d <= 5 { return 823000000 }
183 if d <= 7 { return 875000000 }
184 if d <= 11 { return 968000000 }
185 return 992000000
186}
187
188func nx_ams_query_f2(a: *AMS) -> *ApproxI64 {
189 let f2: i64 = nx_ams_f2(a)
190 return nx_approx_new(f2, NX_ENV_REL_STDDEV, nx_ams_stderr_ppb(a.s),
191 nx_ams_conf_ppb(a.d),
192 NX_MATURITY_REFERENCE_IMPL,
193 NX_ADV_HONEST)
194}
195
196// === merge ========================================================
197//
198// Counters add element-wise. Matching d, s, seed required.
199
200func nx_ams_merge(a: *AMS, b: *AMS) -> *AMS {
201 if a.d != b.d { return 0 as *AMS }
202 if a.s != b.s { return 0 as *AMS }
203 if a.seed != b.seed { return 0 as *AMS }
204 let out: *AMS = nx_ams_alloc(a.d, a.s, a.seed)
205 let cells: i64 = a.d * a.s
206 var i: i64 = 0
207 while i < cells {
208 out.counters[i] = a.counters[i] + b.counters[i]
209 i = i + 1
210 }
211 out.total = a.total + b.total
212 return out
213}
214
215func nx_ams_memory_bytes(a: *AMS) -> i64 {
216 return 48 + a.d * a.s * 8
217}