dataprof_core/sampling/sampler.rs
1//! The runtime that applies a [`SamplingStrategy`] to a stream of rows.
2//!
3//! Strategies fall into two families, and the difference is not cosmetic:
4//!
5//! * `Systematic` decides each row on the spot, so a row can be folded into
6//! the running statistics immediately and memory stays bounded.
7//! * `Reservoir` and `Random` cannot. Whether row 5 belongs in a uniform sample
8//! of 10 is not known until the stream ends: row 5 may be evicted at row 900.
9//! Streaming statistics are not retractable, so a row that was folded in and
10//! later evicted would silently corrupt the profile. These strategies
11//! therefore buffer the candidate rows and hand the final sample back at end
12//! of stream, costing `size` rows of memory.
13//!
14//! [`RowSampler`] hides that split behind one interface so every engine treats
15//! sampling identically. Consult [`RowSampler::is_buffered`] to know which of
16//! [`RowSampler::accept`] or [`RowSampler::offer`] to call.
17
18use crate::errors::DataProfilerError;
19
20use super::reservoir::ReservoirSampler;
21use super::strategies::SamplingStrategy;
22
23/// A fixed-size uniform sample held in memory until the stream ends.
24#[derive(Debug)]
25struct SampleBuffer<R> {
26 capacity: usize,
27 rows: Vec<R>,
28 sampler: ReservoirSampler,
29 seen: usize,
30}
31
32impl<R> SampleBuffer<R> {
33 fn new(capacity: usize) -> Self {
34 Self {
35 capacity,
36 rows: Vec::new(),
37 sampler: ReservoirSampler::new(capacity),
38 seen: 0,
39 }
40 }
41
42 /// Offer a row to the sample, replacing an existing member if selected.
43 ///
44 /// Algorithm R: the first `capacity` rows fill the reservoir, after which
45 /// row `n` replaces a uniformly chosen member with probability
46 /// `capacity / n`. Every row of the stream ends up equally likely to be in
47 /// the final sample.
48 fn offer(&mut self, values: R) {
49 self.seen += 1;
50 if self.capacity == 0 {
51 return;
52 }
53 if self.rows.len() < self.capacity {
54 self.rows.push(values);
55 return;
56 }
57 if let Some(position) = self.sampler.replacement_slot(self.seen) {
58 self.rows[position] = values;
59 }
60 }
61
62 fn take(&mut self) -> Vec<R> {
63 std::mem::take(&mut self.rows)
64 }
65}
66
67/// Applies a [`SamplingStrategy`] to a stream of rows, holding the state the
68/// strategy needs across rows.
69///
70/// Engines create one sampler per scan and keep it for the whole scan.
71///
72/// `R` is what the fixed-size stage holds for each row until the stream ends.
73/// It is the row's field values unless an engine has to keep something about
74/// the row that its values cannot say, and must then get it back with exactly
75/// the rows that were sampled.
76#[derive(Debug)]
77pub struct RowSampler<R = Vec<String>> {
78 /// Keep every `interval`-th row (systematic sampling).
79 interval: Option<usize>,
80 /// Fixed-size stage, for random and reservoir sampling.
81 buffer: Option<SampleBuffer<R>>,
82 /// Rows offered to the sampler, whether or not they were kept.
83 iterated: usize,
84 /// Rows the sampler accepted for immediate folding (streaming path only).
85 accepted: usize,
86}
87
88impl RowSampler {
89 /// Build a sampler for `strategy`.
90 pub fn new(strategy: &SamplingStrategy) -> Result<Self, DataProfilerError> {
91 Self::for_rows(strategy)
92 }
93}
94
95impl<R> RowSampler<R> {
96 /// As [`RowSampler::new`], for a sampler whose fixed-size stage holds `R`
97 /// for each row rather than its field values alone.
98 pub fn for_rows(strategy: &SamplingStrategy) -> Result<Self, DataProfilerError> {
99 let (interval, buffer) = match strategy {
100 SamplingStrategy::None => (None, None),
101 SamplingStrategy::Random { size } | SamplingStrategy::Reservoir { size } => {
102 (None, Some(SampleBuffer::new(*size)))
103 }
104 // An interval of 0 or 1 keeps every row.
105 SamplingStrategy::Systematic { interval } => {
106 ((*interval > 1).then_some(*interval), None)
107 }
108 };
109 Ok(Self {
110 interval,
111 buffer,
112 iterated: 0,
113 accepted: 0,
114 })
115 }
116
117 /// Whether rows must be handed to [`offer`](Self::offer) instead of being
118 /// folded in as [`accept`](Self::accept) approves them.
119 pub fn is_buffered(&self) -> bool {
120 self.buffer.is_some()
121 }
122
123 /// Whether this sampler can ever exclude a row.
124 pub fn is_noop(&self) -> bool {
125 self.interval.is_none() && self.buffer.is_none()
126 }
127
128 /// Decide whether the next row passes the systematic filter.
129 ///
130 /// Call this for every row, including on the buffered path, so the row
131 /// count stays exact.
132 pub fn accept(&mut self) -> bool {
133 let index = self.iterated;
134 self.iterated += 1;
135 if self
136 .interval
137 .is_some_and(|interval| !index.is_multiple_of(interval))
138 {
139 return false;
140 }
141 if self.buffer.is_none() {
142 self.accepted += 1;
143 }
144 true
145 }
146
147 /// Hand a row that passed [`accept`](Self::accept) to the fixed-size stage.
148 ///
149 /// Only meaningful when [`is_buffered`](Self::is_buffered) is true.
150 pub fn offer(&mut self, values: R) {
151 if let Some(buffer) = self.buffer.as_mut() {
152 buffer.offer(values);
153 }
154 }
155
156 /// The final sample from the fixed-size stage, ready to fold into the
157 /// statistics. Empty for a purely streaming strategy.
158 pub fn take_sample(&mut self) -> Vec<R> {
159 match self.buffer.as_mut() {
160 Some(buffer) => {
161 let rows = buffer.take();
162 self.accepted += rows.len();
163 rows
164 }
165 None => Vec::new(),
166 }
167 }
168
169 /// Rows the sampler has seen, sampled or not.
170 pub fn iterated_rows(&self) -> usize {
171 self.iterated
172 }
173
174 /// Rows that ended up in the sample.
175 pub fn sampled_rows(&self) -> usize {
176 self.accepted
177 }
178
179 /// Rows a `max_rows` cap counts so far.
180 ///
181 /// A streaming strategy folds rows in as it keeps them, so the cap bounds
182 /// the rows kept: a systematic interval under `max_rows(n)` reads until it
183 /// has kept `n`. A fixed-size strategy has kept nothing until the stream
184 /// ends, so the cap bounds the rows read and the sample is drawn from
185 /// those; counting kept rows would let `reservoir(100)` under
186 /// `max_rows(20)` return 100 rows. Engines check the cap per row and per
187 /// chunk, and both checks use this count, so the rows analyzed do not
188 /// depend on where a chunk ends.
189 pub fn rows_against_cap(&self) -> usize {
190 if self.is_buffered() {
191 self.iterated
192 } else {
193 self.accepted
194 }
195 }
196}
197
198#[cfg(test)]
199mod tests {
200 use super::*;
201
202 fn run(strategy: SamplingStrategy, rows: usize) -> (usize, usize) {
203 let mut sampler = RowSampler::new(&strategy).expect("valid strategy");
204 for i in 0..rows {
205 if sampler.accept() && sampler.is_buffered() {
206 sampler.offer(vec![i.to_string()]);
207 }
208 }
209 let final_rows = sampler.take_sample().len();
210 (sampler.sampled_rows(), final_rows)
211 }
212
213 #[test]
214 fn reservoir_yields_exactly_its_size() {
215 let (sampled, buffered) = run(SamplingStrategy::Reservoir { size: 10 }, 100);
216 assert_eq!(buffered, 10);
217 assert_eq!(sampled, 10);
218 }
219
220 #[test]
221 fn reservoir_smaller_than_its_size_keeps_every_row() {
222 let (sampled, buffered) = run(SamplingStrategy::Reservoir { size: 50 }, 20);
223 assert_eq!(buffered, 20, "a short stream cannot fill the reservoir");
224 assert_eq!(sampled, 20);
225 }
226
227 #[test]
228 fn random_matches_reservoir_semantics() {
229 let (_, buffered) = run(SamplingStrategy::Random { size: 25 }, 500);
230 assert_eq!(buffered, 25);
231 }
232
233 #[test]
234 fn systematic_takes_every_nth_row() {
235 let (sampled, _) = run(SamplingStrategy::Systematic { interval: 10 }, 100);
236 assert_eq!(sampled, 10);
237 }
238
239 #[test]
240 fn systematic_with_interval_zero_or_one_keeps_every_row() {
241 for interval in [0, 1] {
242 let (sampled, _) = run(SamplingStrategy::Systematic { interval }, 37);
243 assert_eq!(sampled, 37, "interval {interval}");
244 }
245 }
246
247 #[test]
248 fn none_is_a_noop() {
249 let sampler = RowSampler::new(&SamplingStrategy::None).unwrap();
250 assert!(sampler.is_noop());
251 assert!(!sampler.is_buffered());
252 }
253}