Skip to main content

dataprof_runtime/
streaming_stats.rs

1use rand::rngs::SmallRng;
2use rand::{Rng, SeedableRng};
3use std::collections::{HashMap, HashSet};
4use std::fmt::Write as _;
5
6use crate::{ValueHintBindingAccumulator, profile_builder::infer_data_type_streaming};
7use dataprof_core::{SemanticHintBinding, SemanticHintKind, SemanticHints, char_len};
8use dataprof_metrics::analysis::inference::is_null_like_token;
9use dataprof_metrics::{
10    CardinalityEstimator, DateTimeAccumulator, EXACT_CARDINALITY_THRESHOLD, NumericAccumulator,
11    ParsedNumber, RowCompletenessSummary, RowDuplicateSummary, value_matches_hint,
12};
13
14/// Incremental statistics computation for streaming data processing.
15///
16/// This module provides bounded-memory statistical computation using:
17/// - **[`NumericAccumulator`]** for numerically stable mean/variance/stddev
18///   (O(1) memory), shared with the batch paths so every engine reports the
19///   same numbers
20/// - **CardinalityEstimator** for distinct counts: exact up to
21///   `EXACT_CARDINALITY_THRESHOLD` distinct values, then a HyperLogLog
22///   estimate (~16 KB fixed registers)
23/// - **Reservoir sampling** for unbiased samples (fixed capacity; total memory
24///   depends on the capacity and the length of sampled strings)
25/// - **Streaming text-length tracking** with min/max/mean/histogram (O(1) memory)
26
27#[derive(Debug, Clone)]
28pub struct StreamReservoirSampler {
29    reservoir: Vec<String>,
30    capacity: usize,
31    count: u64,
32    rng: SmallRng,
33}
34
35impl StreamReservoirSampler {
36    const DEFAULT_SEED: u64 = 0xDA7A_900D_F00D_5EED;
37
38    pub fn new(capacity: usize) -> Self {
39        let capacity = capacity.max(1);
40        Self {
41            reservoir: Vec::with_capacity(capacity.min(1024)),
42            capacity,
43            count: 0,
44            // Profiling the same ordered source must produce the same report.
45            // Callers that need randomized admission have an explicit sampling
46            // strategy; this internal bounded-memory sample is deterministic.
47            rng: SmallRng::seed_from_u64(Self::DEFAULT_SEED),
48        }
49    }
50
51    #[cfg(test)]
52    pub fn seed(capacity: usize, seed: u64) -> Self {
53        Self {
54            reservoir: Vec::with_capacity(capacity.min(1024)),
55            capacity,
56            count: 0,
57            rng: SmallRng::seed_from_u64(seed),
58        }
59    }
60
61    #[inline]
62    pub fn offer(&mut self, value: &str) {
63        self.count += 1;
64        if self.reservoir.len() < self.capacity {
65            self.reservoir.push(value.to_owned());
66        } else {
67            let index = self.rng.random_range(0..self.count as usize);
68            if index < self.capacity {
69                self.reservoir[index] = value.to_owned();
70            }
71        }
72    }
73
74    /// Keep a uniformly chosen `new_capacity` of the retained values.
75    ///
76    /// A reservoir is a uniform sample as a set, not slot by slot: the values
77    /// that filled it first keep their slots until replaced, so truncating
78    /// kept the head of the stream. Under early memory pressure that made the
79    /// quality sample the first rows of the source. A uniform subset of a
80    /// uniform sample is a uniform sample, and later offers keep it one.
81    pub fn shrink_to(&mut self, new_capacity: usize) {
82        let new_capacity = new_capacity.max(1);
83        let retained = self.reservoir.len();
84        if retained > new_capacity {
85            for slot in 0..new_capacity {
86                let pick = self.rng.random_range(slot..retained);
87                self.reservoir.swap(slot, pick);
88            }
89            self.reservoir.truncate(new_capacity);
90        }
91        self.capacity = new_capacity;
92        self.reservoir.shrink_to_fit();
93    }
94
95    pub fn samples(&self) -> &[String] {
96        &self.reservoir
97    }
98
99    pub fn memory_usage_bytes(&self) -> usize {
100        self.reservoir
101            .iter()
102            .map(|value| std::mem::size_of::<String>() + value.capacity())
103            .sum()
104    }
105
106    /// Fold another sampler in, leaving every value of the combined population
107    /// equally likely to have survived.
108    ///
109    /// The two reservoirs stand for populations of very different sizes: a
110    /// partition of a million rows and one of a hundred each hand over at most
111    /// `capacity` values. Pooling the reservoirs and subsampling uniformly
112    /// would let the small partition supply half the merged sample, so sample
113    /// values, and the patterns inferred from them, would depend on how the
114    /// input happened to be split. The number of survivors drawn from each
115    /// side follows the hypergeometric distribution over the two population
116    /// counts instead, which is the split a single pass would have produced.
117    ///
118    /// A sampler shrunk under memory pressure holds fewer values than its
119    /// population earns it. Nothing can be conjured in their place, so the
120    /// shortfall is filled from the other side rather than returning a sample
121    /// shorter than the capacity allows.
122    pub fn merge(&mut self, other: &StreamReservoirSampler) {
123        if other.count == 0 {
124            return;
125        }
126
127        let available_self = self.reservoir.len();
128        let available_other = other.reservoir.len();
129        let target = self.capacity.min(available_self + available_other);
130
131        let mut take_self = 0usize;
132        let mut take_other = 0usize;
133        let mut population_self = self.count;
134        let mut population_other = other.count;
135
136        for _ in 0..target {
137            // Fewer draws remain than the two sides hold, so at most one of
138            // them is exhausted here. Each side also keeps at least one
139            // unconsumed population row per unconsumed sample slot, so the
140            // range below is never empty.
141            let from_self = if take_self == available_self {
142                false
143            } else if take_other == available_other {
144                true
145            } else {
146                self.rng.random_range(0..population_self + population_other) < population_self
147            };
148
149            if from_self {
150                take_self += 1;
151                population_self -= 1;
152            } else {
153                take_other += 1;
154                population_other -= 1;
155            }
156        }
157
158        // Partial Fisher-Yates over each side: the first `take_*` slots become
159        // a uniform draw without replacement from that side's sample.
160        let mut merged: Vec<String> = std::mem::take(&mut self.reservoir);
161        for index in 0..take_self {
162            let swap_with = self.rng.random_range(index..available_self);
163            merged.swap(index, swap_with);
164        }
165        merged.truncate(take_self);
166
167        let mut indices: Vec<usize> = (0..available_other).collect();
168        for index in 0..take_other {
169            let swap_with = self.rng.random_range(index..available_other);
170            indices.swap(index, swap_with);
171        }
172        merged.extend(
173            indices[..take_other]
174                .iter()
175                .map(|&index| other.reservoir[index].clone()),
176        );
177
178        self.reservoir = merged;
179        self.count += other.count;
180    }
181}
182
183#[derive(Debug, Clone)]
184pub struct TextLengthStats {
185    pub min_length: usize,
186    pub max_length: usize,
187    pub avg_length: f64,
188    welford: NumericAccumulator,
189    histogram: [u64; 32],
190}
191
192impl TextLengthStats {
193    pub fn new() -> Self {
194        Self {
195            min_length: usize::MAX,
196            max_length: 0,
197            avg_length: 0.0,
198            welford: NumericAccumulator::new(),
199            histogram: [0u64; 32],
200        }
201    }
202
203    pub fn update(&mut self, length: usize) {
204        self.min_length = self.min_length.min(length);
205        self.max_length = self.max_length.max(length);
206        self.welford.update(length as f64);
207        self.avg_length = self.welford.mean();
208
209        let bucket = if length == 0 {
210            0
211        } else {
212            (usize::BITS - length.leading_zeros()).min(31) as usize
213        };
214        self.histogram[bucket] += 1;
215    }
216
217    pub fn merge(&mut self, other: &TextLengthStats) {
218        if other.welford.count() == 0 {
219            return;
220        }
221        if self.welford.count() == 0 {
222            *self = other.clone();
223            return;
224        }
225
226        self.min_length = self.min_length.min(other.min_length);
227        self.max_length = self.max_length.max(other.max_length);
228        self.welford.merge(&other.welford);
229        self.avg_length = self.welford.mean();
230
231        for (left, right) in self.histogram.iter_mut().zip(other.histogram.iter()) {
232            *left += *right;
233        }
234    }
235
236    pub fn empty() -> Self {
237        Self {
238            min_length: 0,
239            max_length: 0,
240            avg_length: 0.0,
241            welford: NumericAccumulator::new(),
242            histogram: [0u64; 32],
243        }
244    }
245}
246
247impl Default for TextLengthStats {
248    fn default() -> Self {
249        Self::new()
250    }
251}
252
253#[derive(Debug, Clone)]
254pub struct StreamingStatistics {
255    pub count: usize,
256    pub null_count: usize,
257    pub min: f64,
258    pub max: f64,
259    welford: NumericAccumulator,
260    /// Distinct values over every non-null value, independent of the
261    /// reservoir: exact past the reservoir's capacity, the same estimator the
262    /// columnar and in-memory paths use.
263    distinct: CardinalityEstimator,
264    sampler: StreamReservoirSampler,
265    text_length_tracker: TextLengthStats,
266    date_match_count: usize,
267    /// Date statistics over every non-null value, independent of the
268    /// reservoir (#1297).
269    dates: DateTimeAccumulator,
270}
271
272impl StreamingStatistics {
273    pub fn new() -> Self {
274        Self {
275            count: 0,
276            null_count: 0,
277            min: f64::INFINITY,
278            max: f64::NEG_INFINITY,
279            welford: NumericAccumulator::new(),
280            distinct: CardinalityEstimator::new(),
281            sampler: StreamReservoirSampler::new(10_000),
282            text_length_tracker: TextLengthStats::new(),
283            date_match_count: 0,
284            dates: DateTimeAccumulator::new(),
285        }
286    }
287
288    pub fn with_sample_capacity(max_sample: usize) -> Self {
289        Self {
290            sampler: StreamReservoirSampler::new(max_sample),
291            ..Self::new()
292        }
293    }
294
295    pub fn update(&mut self, value: &str) {
296        self.count += 1;
297
298        if is_null_like_token(value) {
299            self.null_count += 1;
300            return;
301        }
302
303        self.distinct.insert(value);
304        self.sampler.offer(value);
305        // Unicode scalar values, not UTF-8 bytes: see `dataprof_core::text_units`.
306        self.text_length_tracker.update(char_len(value));
307        if value_matches_hint(value, SemanticHintKind::Temporal) {
308            self.date_match_count += 1;
309        }
310        self.dates.update(value);
311
312        if let Some(number) = ParsedNumber::parse(value) {
313            self.welford.update_number(number);
314            self.min = self.min.min(number.to_f64());
315            self.max = self.max.max(number.to_f64());
316        }
317    }
318
319    pub fn merge(&mut self, other: &StreamingStatistics) {
320        self.count += other.count;
321        self.null_count += other.null_count;
322
323        if other.min < self.min {
324            self.min = other.min;
325        }
326        if other.max > self.max {
327            self.max = other.max;
328        }
329
330        self.welford.merge(&other.welford);
331        self.distinct.merge(&other.distinct);
332        self.sampler.merge(&other.sampler);
333        self.text_length_tracker.merge(&other.text_length_tracker);
334        self.date_match_count += other.date_match_count;
335        self.dates.merge(&other.dates);
336    }
337
338    pub fn mean(&self) -> f64 {
339        self.welford.mean()
340    }
341
342    pub fn variance(&self) -> f64 {
343        self.welford.population_variance()
344    }
345
346    pub fn std_dev(&self) -> f64 {
347        self.welford.population_std_dev()
348    }
349
350    /// Distinct non-null values, exact until the estimator spills.
351    ///
352    /// This used to count the reservoir when it held every value and fall
353    /// back to a sketch otherwise, so any column longer than the reservoir,
354    /// even one with a single value, reported an approximate count, and a
355    /// different one from the engines that use the shared estimator.
356    pub fn unique_count(&self) -> usize {
357        self.distinct.estimate()
358    }
359
360    pub fn unique_count_is_approximate(&self) -> bool {
361        self.distinct.is_approximate()
362    }
363
364    /// See [`CardinalityEstimator::distinct_lower_bound`].
365    pub fn unique_count_lower_bound(&self) -> usize {
366        self.distinct.distinct_lower_bound()
367    }
368
369    /// Answer distinct counts from the sketch from here on, freeing the exact
370    /// set. For memory pressure; the count is then reported approximate.
371    pub fn spill_distinct(&mut self) {
372        self.distinct.spill();
373    }
374
375    /// Heap held by the exact distinct set: zero once it has spilled, and zero
376    /// for a column that has seen no value, so spilling it would free nothing.
377    pub fn exact_distinct_bytes(&self) -> usize {
378        self.distinct.exact_bytes()
379    }
380
381    pub fn sample_values(&self) -> &[String] {
382        self.sampler.samples()
383    }
384
385    /// Values over the full stream accepted by the temporal calculator.
386    pub fn date_match_count(&self) -> usize {
387        self.date_match_count
388    }
389
390    /// Date statistics over every non-null value this column has streamed.
391    pub fn date_statistics(&self) -> &DateTimeAccumulator {
392        &self.dates
393    }
394
395    /// Exact aggregates over every numeric value this column has streamed,
396    /// or `None` when no value parsed as a finite number.
397    ///
398    /// These come from the O(1)-memory min/max fields and the Welford
399    /// accumulator, so they cover the full stream even when the reservoir
400    /// sample no longer does.
401    pub fn exact_numeric_aggregates(
402        &self,
403    ) -> Option<crate::profile_builder::ExactNumericAggregates> {
404        let count = self.welford.count();
405        if count == 0 {
406            return None;
407        }
408        Some(crate::profile_builder::ExactNumericAggregates {
409            min: self.min,
410            max: self.max,
411            mean: self.welford.mean(),
412            std_dev: self.welford.sample_std_dev(),
413            variance: self.welford.sample_variance(),
414            count: count as usize,
415            min_value: self.welford.min_value(),
416            max_value: self.welford.max_value(),
417        })
418    }
419
420    pub fn text_length_stats(&self) -> TextLengthStats {
421        if self.text_length_tracker.welford.count() == 0 {
422            return TextLengthStats::empty();
423        }
424        self.text_length_tracker.clone()
425    }
426
427    pub fn reduce_sample_capacity(&mut self) {
428        self.sampler.shrink_to(self.sampler.capacity / 2);
429    }
430
431    pub fn memory_usage_bytes(&self) -> usize {
432        let struct_size = std::mem::size_of::<Self>();
433        let distinct_size = self.distinct.memory_usage_bytes();
434        let reservoir_size = self.sampler.memory_usage_bytes();
435        // The year maps behind the date statistics (#1297): one entry per
436        // distinct year, so small on real dates but counted all the same.
437        let dates_size = self.dates.heap_bytes();
438
439        struct_size + distinct_size + reservoir_size + dates_size
440    }
441}
442
443impl Default for StreamingStatistics {
444    fn default() -> Self {
445        Self::new()
446    }
447}
448
449/// Canonical encoding of one row, for duplicate detection.
450///
451/// Fields are length-prefixed so their boundaries are unambiguous:
452/// `["ab", "c"]` and `["a", "bc"]` must not sign alike. Trailing absent
453/// fields are then dropped, which makes the signature independent of how wide
454/// the schema had grown when the row was read. A JSON key discovered
455/// mid-stream appends a column, and without the trim every row that predates
456/// it signs one field shorter than an identical row read afterwards, so the
457/// two count as distinct and the duplicate total comes up silently short.
458///
459/// The trim is safe because an absent field and an explicitly empty one are
460/// the same null to this profiler: it collapses only rows that already hold
461/// equal values in every column they share. On a fixed schema it applies
462/// uniformly to every row, so it changes no count there.
463#[derive(Debug, Default)]
464pub struct RowSignature {
465    buffer: String,
466    /// Length of `buffer` through the last field that held a value.
467    len_through_last_present: usize,
468}
469
470impl RowSignature {
471    /// Append one field. An absent field is the empty string, the same
472    /// representation [`StreamingColumnCollection::process_record`] gives a
473    /// missing trailing value and an Arrow null.
474    ///
475    /// Only an exactly empty value counts as absent here, deliberately: the
476    /// broader `is_null_like_token` rule that decides `null_count` also matches
477    /// `null`, `nan` and whitespace, and trimming on it would collapse a row
478    /// ending in one of those against a row that ends in no field at all,
479    /// inventing a duplicate.
480    pub fn push_field(&mut self, value: &str) {
481        self.push_tagged(value, ':');
482    }
483
484    /// Append one field holding a JSON object or array, given as its text.
485    ///
486    /// A container crosses as its compact JSON, which a string can spell, so
487    /// it is tagged apart from a scalar: `"{\"x\":1}"` and `{"x": 1}` are two
488    /// values and must not sign alike (#945).
489    pub fn push_container_field(&mut self, text: &str) {
490        self.push_tagged(text, '#');
491    }
492
493    /// Append one field as its length, `tag`, then the text.
494    fn push_tagged(&mut self, value: &str, tag: char) {
495        let _ = write!(self.buffer, "{}{tag}", value.len());
496        self.buffer.push_str(value);
497        if !value.is_empty() {
498            self.len_through_last_present = self.buffer.len();
499        }
500    }
501
502    /// The signature, with trailing absent fields dropped.
503    pub fn finish(mut self) -> String {
504        self.buffer.truncate(self.len_through_last_present);
505        self.buffer
506    }
507}
508
509/// Full-stream row-duplicate tracking with bounded memory.
510///
511/// Every record's fields are folded into a [`RowSignature`] and fed to a
512/// [`CardinalityEstimator`]: duplicates are counted exactly while the
513/// distinct-row signatures fit the estimator's exact set, and estimated
514/// (flagged approximate) once it spills to its HLL sketch. Unlike the
515/// per-column reservoirs, this sees whole rows — including null-like values —
516/// so the count is row-aligned by construction.
517///
518/// The exact set holds 64-bit fingerprints of the signatures. Two different
519/// rows share one with probability about `n^2 / 2^65` over `n` distinct rows:
520/// 3e-8 at the default limit of one million, 2e-5 at 27 million, 2e-3 at 300
521/// million. A shared fingerprint counts one duplicate that is not there, so
522/// on a large raised limit a `max_duplicate_rows 0` failure on a count of one
523/// carries that chance of being wrong (#1292).
524#[derive(Debug, Clone)]
525pub struct RowUniquenessTracker {
526    rows_seen: usize,
527    distinct: CardinalityEstimator,
528    /// Distinct rows counted exactly before the count becomes an estimate.
529    exact_limit: usize,
530    /// Set when the caller chose `exact_limit`: memory pressure then leaves
531    /// the exact set alone, so the verdict does not depend on the machine.
532    limit_requested: bool,
533    /// Set once signatures made under different schemas have been folded in.
534    ///
535    /// A signature encodes length-prefixed values and nothing else, so a row
536    /// `{a: "x"}` and a row `{b: "x"}` both sign as `1:x` while the union
537    /// schema makes them different rows; a differing field *order* collides
538    /// the same way. The signatures are already folded into the estimator and
539    /// cannot be rebuilt against the union schema, so the count is withheld
540    /// rather than reported as a plausible number. Defaults to false, which is
541    /// what a tracker fed from a single schema is.
542    incomparable_signatures: bool,
543}
544
545impl Default for RowUniquenessTracker {
546    fn default() -> Self {
547        Self::with_exact_limit(None)
548    }
549}
550
551impl RowUniquenessTracker {
552    /// A tracker that counts exactly up to `limit` distinct rows, or up to
553    /// [`EXACT_CARDINALITY_THRESHOLD`] when `None`. A limit given here is
554    /// kept under memory pressure; see [`Self::spill`].
555    pub fn with_exact_limit(limit: Option<usize>) -> Self {
556        let exact_limit = limit.unwrap_or(EXACT_CARDINALITY_THRESHOLD);
557        Self {
558            rows_seen: 0,
559            distinct: CardinalityEstimator::with_threshold(exact_limit),
560            exact_limit,
561            limit_requested: limit.is_some(),
562            incomparable_signatures: false,
563        }
564    }
565
566    /// Distinct rows this tracker counts exactly before estimating.
567    pub fn exact_limit(&self) -> usize {
568        self.exact_limit
569    }
570
571    pub fn observe(&mut self, signature: String) {
572        self.rows_seen += 1;
573        self.distinct.insert_owned(signature);
574    }
575
576    pub fn rows_seen(&self) -> usize {
577        self.rows_seen
578    }
579
580    /// Rows minus distinct rows; exact until the estimator spills.
581    pub fn duplicate_rows(&self) -> usize {
582        self.rows_seen.saturating_sub(self.distinct.estimate())
583    }
584
585    pub fn is_approximate(&self) -> bool {
586        self.distinct.is_approximate()
587    }
588
589    /// Record that the signatures folded in so far were not all made against
590    /// the same schema, so they cannot be compared with each other.
591    pub fn mark_incomparable(&mut self) {
592        self.incomparable_signatures = true;
593    }
594
595    pub fn merge(&mut self, other: &RowUniquenessTracker) {
596        self.rows_seen += other.rows_seen;
597        self.distinct.merge(&other.distinct);
598        self.incomparable_signatures |= other.incomparable_signatures;
599    }
600
601    pub fn memory_usage_bytes(&self) -> usize {
602        self.distinct.memory_usage_bytes()
603    }
604
605    /// Heap held by the exact set of row signatures: what [`Self::spill`] frees.
606    pub fn exact_bytes(&self) -> usize {
607        self.distinct.exact_bytes()
608    }
609
610    /// The part of [`Self::exact_bytes`] a memory budget answers for: all of
611    /// it, unless the caller set the limit. That set is the caller's choice
612    /// of memory and stays outside the budget, so it neither spills the
613    /// column sets nor shrinks the reservoirs on every chunk (#1292).
614    pub fn budgeted_exact_bytes(&self) -> usize {
615        if self.limit_requested {
616            0
617        } else {
618            self.exact_bytes()
619        }
620    }
621
622    /// Answer the duplicate count from the sketch from here on, freeing the
623    /// exact set. For memory pressure; the count is then reported approximate.
624    /// Returns the bytes freed.
625    ///
626    /// A tracker whose limit the caller set keeps its exact set and frees
627    /// nothing: the limit is the caller's choice of memory for an exact
628    /// count, and a count that ended where the machine's budget did would
629    /// make the verdict depend on the machine (#1292).
630    pub fn spill(&mut self) -> usize {
631        if self.limit_requested {
632            return 0;
633        }
634        let freed = self.distinct.exact_bytes();
635        self.distinct.spill();
636        freed
637    }
638
639    /// Summary for quality metrics, or `None` when no rows were observed
640    /// (e.g. an engine that never fed whole records through this tracker) or
641    /// when the signatures seen are not comparable with one another.
642    pub fn summary(&self) -> Option<RowDuplicateSummary> {
643        if self.rows_seen == 0 || self.incomparable_signatures {
644            return None;
645        }
646        Some(RowDuplicateSummary {
647            duplicate_rows: self.duplicate_rows(),
648            rows_checked: self.rows_seen,
649            approximate: self.is_approximate(),
650            exact_limit: self.exact_limit,
651            max_duplicate_rows: self
652                .rows_seen
653                .saturating_sub(self.distinct.distinct_lower_bound()),
654        })
655    }
656}
657
658/// Full-stream count of records in which every field is present.
659///
660/// Completeness of a *record* is not recoverable from per-column null
661/// totals: those say how many nulls exist, not whether two of them shared a
662/// row. One counter fed whole rows answers it exactly, at any scale and
663/// regardless of sampling.
664#[derive(Debug, Clone, Default)]
665pub struct RowCompletenessTracker {
666    rows_seen: usize,
667    complete_rows: usize,
668}
669
670impl RowCompletenessTracker {
671    /// Record one row. `had_null` is true when any of its fields was absent.
672    pub fn observe(&mut self, had_null: bool) {
673        self.rows_seen += 1;
674        if !had_null {
675            self.complete_rows += 1;
676        }
677    }
678
679    /// A column appeared after rows had already been counted, so every row
680    /// counted so far is missing it and none of them was complete after all.
681    pub fn invalidate_completed_rows(&mut self) {
682        self.complete_rows = 0;
683    }
684
685    /// Count complete records across columns that are already row-aligned
686    /// and hold every value, as the database and ad-hoc input paths do.
687    ///
688    /// A row shorter than `total_rows` in some column is missing that field,
689    /// which is the same as holding a null there — the reading
690    /// [`StreamingColumnCollection::process_record`] gives ragged records.
691    pub fn observe_aligned_columns(&mut self, columns: &[&[String]], total_rows: usize) {
692        if columns.is_empty() {
693            return;
694        }
695        for row_index in 0..total_rows {
696            let had_null = columns.iter().any(|cells| {
697                cells
698                    .get(row_index)
699                    .is_none_or(|value| is_null_like_token(value))
700            });
701            self.observe(had_null);
702        }
703    }
704
705    pub fn merge(&mut self, other: &RowCompletenessTracker) {
706        self.rows_seen += other.rows_seen;
707        self.complete_rows += other.complete_rows;
708    }
709
710    /// Exact complete-record counts, or `None` when no rows were observed.
711    pub fn summary(&self) -> Option<RowCompletenessSummary> {
712        if self.rows_seen == 0 {
713            return None;
714        }
715        Some(RowCompletenessSummary {
716            complete_rows: self.complete_rows,
717            rows_checked: self.rows_seen,
718        })
719    }
720}
721
722pub struct StreamingColumnCollection {
723    columns: HashMap<String, StreamingStatistics>,
724    ordered_names: Vec<String>,
725    memory_limit_bytes: usize,
726    row_tracker: RowUniquenessTracker,
727    completeness_tracker: RowCompletenessTracker,
728    hint_bindings: ValueHintBindingAccumulator,
729}
730
731impl StreamingColumnCollection {
732    pub fn new() -> Self {
733        Self {
734            columns: HashMap::new(),
735            ordered_names: Vec::new(),
736            memory_limit_bytes: 100 * 1024 * 1024,
737            row_tracker: RowUniquenessTracker::default(),
738            completeness_tracker: RowCompletenessTracker::default(),
739            hint_bindings: ValueHintBindingAccumulator::default(),
740        }
741    }
742
743    pub fn memory_limit(limit_mb: usize) -> Self {
744        Self {
745            columns: HashMap::new(),
746            ordered_names: Vec::new(),
747            memory_limit_bytes: limit_mb * 1024 * 1024,
748            row_tracker: RowUniquenessTracker::default(),
749            completeness_tracker: RowCompletenessTracker::default(),
750            hint_bindings: ValueHintBindingAccumulator::default(),
751        }
752    }
753
754    /// Configure value-driven semantic hints before records are processed.
755    pub fn with_semantic_hints(mut self, hints: &SemanticHints) -> Self {
756        self.hint_bindings = ValueHintBindingAccumulator::new(hints);
757        self
758    }
759
760    /// Count duplicate rows exactly up to `limit` distinct rows, before any
761    /// record is processed. See [`RowUniquenessTracker::with_exact_limit`].
762    pub fn with_duplicate_rows_exact_limit(mut self, limit: Option<usize>) -> Self {
763        self.row_tracker = RowUniquenessTracker::with_exact_limit(limit);
764        self
765    }
766
767    pub fn init_columns(&mut self, headers: &[String]) {
768        for header in headers {
769            if !self.columns.contains_key(header) {
770                self.columns
771                    .insert(header.clone(), StreamingStatistics::default());
772                self.ordered_names.push(header.clone());
773            }
774        }
775    }
776
777    /// Add a column discovered after `prior_rows` records have already passed.
778    ///
779    /// JSON objects may introduce keys at any point in a stream. Those earlier
780    /// objects are missing the new key, so the column must start with matching
781    /// total/null counters rather than looking shorter and more complete than
782    /// the dataset.
783    pub fn init_column_with_missing(&mut self, header: &str, prior_rows: usize) {
784        if self.columns.contains_key(header) {
785            return;
786        }
787
788        let stats = StreamingStatistics {
789            count: prior_rows,
790            null_count: prior_rows,
791            ..Default::default()
792        };
793        self.columns.insert(header.to_string(), stats);
794        self.ordered_names.push(header.to_string());
795        if prior_rows > 0 {
796            self.completeness_tracker.invalidate_completed_rows();
797        }
798    }
799
800    pub fn process_record<I>(&mut self, headers: &[String], values: I)
801    where
802        I: IntoIterator<Item = String>,
803    {
804        self.process_record_with_containers(headers, values, &[]);
805    }
806
807    /// [`process_record`](Self::process_record) for a record whose fields at
808    /// `containers` (positions in `headers`) were JSON objects or arrays,
809    /// given as their text. Their statistics read the text like any other
810    /// value; only the row signature tells them apart from a string that
811    /// spells the same text (#945).
812    pub fn process_record_with_containers<I>(
813        &mut self,
814        headers: &[String],
815        values: I,
816        containers: &[usize],
817    ) where
818        I: IntoIterator<Item = String>,
819    {
820        let mut row_signature = RowSignature::default();
821        let mut row_has_null = false;
822        let mut values = values.into_iter();
823
824        // Headers define the row schema. Normalize a missing trailing field to
825        // the profiler's empty/null representation so ragged flexible records
826        // update every column and hash identically to an explicit empty field.
827        for (position, header) in headers.iter().enumerate() {
828            let value = values.next().unwrap_or_default();
829            if containers.contains(&position) {
830                row_signature.push_container_field(&value);
831            } else {
832                row_signature.push_field(&value);
833            }
834
835            if let Some(stats) = self.columns.get_mut(header) {
836                stats.update(&value);
837            } else {
838                self.ordered_names.push(header.clone());
839                self.columns
840                    .entry(header.clone())
841                    .or_default()
842                    .update(&value);
843            }
844            // Same null definition the column counters use, so the record
845            // count and the cell counts always describe the same nulls.
846            row_has_null |= is_null_like_token(&value);
847            self.hint_bindings.observe(header, &value);
848        }
849
850        // A fieldless JSON object is still a record. If a column appears
851        // later, init_column_with_missing marks these earlier rows incomplete;
852        // their empty signatures already match rows of trailing absent fields.
853        self.row_tracker.observe(row_signature.finish());
854        self.completeness_tracker.observe(row_has_null);
855    }
856
857    /// Full-stream row-duplicate counts, or `None` when no rows were seen.
858    pub fn row_duplicate_summary(&self) -> Option<RowDuplicateSummary> {
859        self.row_tracker.summary()
860    }
861
862    /// Full-stream complete-record counts, or `None` when no rows were seen.
863    pub fn row_completeness_summary(&self) -> Option<RowCompletenessSummary> {
864        self.completeness_tracker.summary()
865    }
866
867    /// Exact value-driven semantic-hint evidence over every processed record.
868    pub fn semantic_hint_bindings(&self) -> Vec<SemanticHintBinding> {
869        self.hint_bindings
870            .bindings(self.ordered_names.iter().map(String::as_str))
871    }
872
873    pub fn get_column_stats(&self, column_name: &str) -> Option<&StreamingStatistics> {
874        self.columns.get(column_name)
875    }
876
877    pub fn column_names(&self) -> Vec<String> {
878        self.ordered_names.clone()
879    }
880
881    /// Retain only the selected columns, preserving their source order.
882    ///
883    /// Parsers call this after validating the selection against the complete
884    /// source schema. Row-level trackers intentionally remain unchanged; a
885    /// projected report withholds the row-level quality dimensions because
886    /// their meaning changes when columns are removed.
887    pub fn retain_columns(&mut self, names: &[String]) {
888        let selected = names.iter().map(String::as_str).collect::<HashSet<_>>();
889        self.columns
890            .retain(|name, _| selected.contains(name.as_str()));
891        self.ordered_names
892            .retain(|name| selected.contains(name.as_str()));
893    }
894
895    pub fn memory_usage_bytes(&self) -> usize {
896        self.columns
897            .values()
898            .map(|stats| stats.memory_usage_bytes())
899            .sum::<usize>()
900            + self.row_tracker.memory_usage_bytes()
901    }
902
903    pub fn is_memory_pressure(&self) -> bool {
904        self.budgeted_usage_bytes() > (self.memory_limit_bytes * 80 / 100)
905    }
906
907    /// [`Self::memory_usage_bytes`] less a row-tracker exact set the caller's
908    /// limit keeps outside the budget. See
909    /// [`RowUniquenessTracker::budgeted_exact_bytes`].
910    fn budgeted_usage_bytes(&self) -> usize {
911        self.memory_usage_bytes() - self.row_tracker.exact_bytes()
912            + self.row_tracker.budgeted_exact_bytes()
913    }
914
915    pub fn reduce_memory_usage(&mut self) {
916        // Exact distinct sets grow with the data and are spilled first: the
917        // largest first, and only while still over the line, so the columns
918        // that stay exact are the ones that cost least to keep. Ties go by
919        // column order, so the choice does not depend on hash order. The row
920        // tracker goes last of the exact sets: its duplicate count feeds the
921        // score, and once spilled it is reported approximate.
922        //
923        // The reservoirs are shrunk only if spilling was not enough. They are
924        // small by comparison, and halving them on every chunk under pressure
925        // degrades every sampled statistic, which is too high a price to pay
926        // for memory the distinct sets can give back.
927        //
928        // Usage is measured once and each spill subtracts what it frees:
929        // measuring walks every reservoir, too slow to repeat per column.
930        let limit = self.memory_limit_bytes * 80 / 100;
931        let mut usage = self.budgeted_usage_bytes();
932        if usage <= limit {
933            return;
934        }
935        usage -= self.spill_distinct_sets(usage - limit);
936        if usage > limit {
937            usage -= self.row_tracker.spill();
938        }
939        if usage > limit {
940            for stats in self.columns.values_mut() {
941                stats.reduce_sample_capacity();
942            }
943        }
944    }
945
946    /// Spill column exact sets, largest first, until at least `excess` bytes
947    /// are freed or none is left. Returns the bytes freed.
948    fn spill_distinct_sets(&mut self, excess: usize) -> usize {
949        let mut by_size: Vec<(usize, usize)> = self
950            .ordered_names
951            .iter()
952            .enumerate()
953            .filter_map(|(position, name)| {
954                let bytes = self.columns.get(name)?.exact_distinct_bytes();
955                (bytes > 0).then_some((position, bytes))
956            })
957            .collect();
958        by_size.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));
959        let mut freed = 0;
960        for (position, bytes) in by_size {
961            if freed >= excess {
962                break;
963            }
964            let name = &self.ordered_names[position];
965            if let Some(stats) = self.columns.get_mut(name) {
966                stats.spill_distinct();
967                freed += bytes;
968            }
969        }
970        freed
971    }
972
973    /// Fingerprint of each column's currently inferred data type.
974    ///
975    /// Returns a `u64` hash suitable for cheap comparison in a schema
976    /// stability tracker.
977    pub fn column_type_fingerprint(&self) -> u64 {
978        use std::collections::hash_map::DefaultHasher;
979        use std::hash::{Hash, Hasher};
980
981        let mut hasher = DefaultHasher::new();
982        let mut names: Vec<&String> = self.columns.keys().collect();
983        names.sort();
984        for name in names {
985            let stats = &self.columns[name];
986            let data_type = infer_data_type_streaming(stats);
987            name.hash(&mut hasher);
988            std::mem::discriminant(&data_type).hash(&mut hasher);
989        }
990        hasher.finish()
991    }
992
993    /// Fold another collection into this one, as if a single pass had read
994    /// both sides.
995    ///
996    /// The merged profile describes the union of the two schemas, and three
997    /// consequences of that are each a silently wrong number when skipped:
998    ///
999    /// - A column only one side saw has to join `ordered_names`, or
1000    ///   [`Self::column_names`] omits it and the column vanishes from the
1001    ///   report while its statistics sit unreachable in the map.
1002    /// - That column is absent from every record the *other* side read, so it
1003    ///   is padded with those rows as missing values, the way
1004    ///   [`Self::init_column_with_missing`] pads a key that appears mid-stream.
1005    ///   Skipping the padding leaves the column looking shorter and more
1006    ///   complete than the dataset.
1007    /// - Rows counted complete against the narrower schema are not complete
1008    ///   against the union, so that side's complete-row count is invalidated
1009    ///   for the same reason.
1010    ///
1011    /// Row signatures are built per record from that record's own headers, and
1012    /// encode values only. Two sides that read different columns, or the same
1013    /// columns in a different order, therefore sign different rows identically.
1014    /// Those signatures cannot be rebuilt against the union schema once folded
1015    /// into the estimator, so the merged duplicate count is withheld rather
1016    /// than reported wrong.
1017    pub fn merge(&mut self, other: StreamingColumnCollection) {
1018        let self_rows = self.row_tracker.rows_seen();
1019        let other_rows = other.row_tracker.rows_seen();
1020
1021        let StreamingColumnCollection {
1022            columns,
1023            ordered_names,
1024            memory_limit_bytes: _,
1025            row_tracker,
1026            mut completeness_tracker,
1027            hint_bindings,
1028        } = other;
1029
1030        // Signatures are positional over the record's own headers, so they
1031        // only mean the same thing on both sides when both read the same
1032        // columns in the same order. Captured before the orders are joined.
1033        let schemas_match = self.ordered_names == ordered_names;
1034
1035        // A column this side saw and the other did not is absent from every
1036        // record the other side read.
1037        let mut other_lacks_columns = false;
1038        for (column_name, stats) in self.columns.iter_mut() {
1039            if columns.contains_key(column_name) {
1040                continue;
1041            }
1042            other_lacks_columns = true;
1043            stats.count += other_rows;
1044            stats.null_count += other_rows;
1045        }
1046
1047        // Columns the other side introduces keep its discovery order, appended
1048        // after the ones already known here. Names carry the order; the map
1049        // carries the statistics, and the two always hold the same keys.
1050        let mut self_lacks_columns = false;
1051        for column_name in &ordered_names {
1052            if !self.columns.contains_key(column_name) {
1053                self.ordered_names.push(column_name.clone());
1054                self_lacks_columns = true;
1055            }
1056        }
1057
1058        for (column_name, other_stats) in columns {
1059            match self.columns.get_mut(&column_name) {
1060                Some(existing_stats) => existing_stats.merge(&other_stats),
1061                None => {
1062                    let mut stats = other_stats;
1063                    // Records this side already read had no such field.
1064                    stats.count += self_rows;
1065                    stats.null_count += self_rows;
1066                    self.columns.insert(column_name, stats);
1067                }
1068            }
1069        }
1070
1071        if self_lacks_columns && self_rows > 0 {
1072            self.completeness_tracker.invalidate_completed_rows();
1073        }
1074        if other_lacks_columns && other_rows > 0 {
1075            completeness_tracker.invalidate_completed_rows();
1076        }
1077
1078        self.completeness_tracker.merge(&completeness_tracker);
1079        self.row_tracker.merge(&row_tracker);
1080        // Only a side that signed rows can make them incomparable, so folding
1081        // a partition into a fresh accumulator stays a plain accumulation.
1082        if self_rows > 0 && other_rows > 0 && !schemas_match {
1083            self.row_tracker.mark_incomparable();
1084        }
1085        self.hint_bindings.merge(&hint_bindings);
1086    }
1087}
1088
1089impl Default for StreamingColumnCollection {
1090    fn default() -> Self {
1091        Self::new()
1092    }
1093}
1094
1095#[cfg(test)]
1096mod row_tracker_tests {
1097    use super::*;
1098
1099    fn record(collection: &mut StreamingColumnCollection, headers: &[String], values: &[&str]) {
1100        collection.process_record(headers, values.iter().map(|v| v.to_string()));
1101    }
1102
1103    fn completeness(collection: &StreamingColumnCollection) -> (usize, usize) {
1104        let summary = collection
1105            .row_completeness_summary()
1106            .expect("rows were observed");
1107        (summary.complete_rows, summary.rows_checked)
1108    }
1109
1110    /// The date statistics' year maps count toward the memory the incremental
1111    /// and async engines limit (Copilot review on #1301).
1112    #[test]
1113    fn memory_usage_counts_the_date_statistics() {
1114        let mut stats = StreamingStatistics::new();
1115        for year in 1000..3000 {
1116            stats.update(&format!("{year}-01-05"));
1117        }
1118        let dates = stats.date_statistics().heap_bytes();
1119        assert!(dates > 0);
1120        assert!(
1121            stats.memory_usage_bytes()
1122                >= std::mem::size_of::<StreamingStatistics>()
1123                    + stats.distinct.memory_usage_bytes()
1124                    + stats.sampler.memory_usage_bytes()
1125                    + dates
1126        );
1127    }
1128
1129    #[test]
1130    fn test_complete_rows_count_rows_not_null_cells() {
1131        let headers = vec!["a".to_string(), "b".to_string()];
1132        let mut collection = StreamingColumnCollection::new();
1133        // Both nulls land in the same row, so 3 of 4 rows are complete. Per
1134        // column the nulls total 2, which the cell-based lower bound would
1135        // read as only 2 complete rows.
1136        record(&mut collection, &headers, &["", ""]);
1137        record(&mut collection, &headers, &["x", "1"]);
1138        record(&mut collection, &headers, &["y", "2"]);
1139        record(&mut collection, &headers, &["z", "3"]);
1140
1141        assert_eq!(completeness(&collection), (3, 4));
1142    }
1143
1144    #[test]
1145    fn test_null_like_tokens_make_a_row_incomplete() {
1146        let headers = vec!["a".to_string(), "b".to_string()];
1147        let mut collection = StreamingColumnCollection::new();
1148        // The column counters treat these as nulls, so the record count must
1149        // too, or the two halves of the dimension describe different data.
1150        record(&mut collection, &headers, &["x", "NULL"]);
1151        record(&mut collection, &headers, &["y", "NaN"]);
1152        record(&mut collection, &headers, &["z", "  "]);
1153        record(&mut collection, &headers, &["w", "3"]);
1154
1155        assert_eq!(completeness(&collection), (1, 4));
1156    }
1157
1158    #[test]
1159    fn test_ragged_rows_are_incomplete() {
1160        let headers = vec!["a".to_string(), "b".to_string()];
1161        let mut collection = StreamingColumnCollection::new();
1162        record(&mut collection, &headers, &["x"]);
1163        record(&mut collection, &headers, &["y", "1"]);
1164
1165        assert_eq!(completeness(&collection), (1, 2));
1166    }
1167
1168    #[test]
1169    fn test_a_late_column_makes_earlier_rows_incomplete() {
1170        let mut collection = StreamingColumnCollection::new();
1171        let first = vec!["a".to_string()];
1172        record(&mut collection, &first, &["x"]);
1173        record(&mut collection, &first, &["y"]);
1174        assert_eq!(completeness(&collection), (2, 2));
1175
1176        // A JSON object introduces `b` on the third record. The first two
1177        // records never carried it, so neither of them was complete.
1178        collection.init_column_with_missing("b", 2);
1179        let both = vec!["a".to_string(), "b".to_string()];
1180        record(&mut collection, &both, &["z", "1"]);
1181
1182        assert_eq!(completeness(&collection), (1, 3));
1183    }
1184
1185    #[test]
1186    fn test_no_rows_means_no_completeness_summary() {
1187        let collection = StreamingColumnCollection::new();
1188        assert!(collection.row_completeness_summary().is_none());
1189    }
1190
1191    #[test]
1192    fn test_aligned_columns_count_the_same_complete_rows() {
1193        let a: Vec<String> = ["", "x", "y"].iter().map(|v| v.to_string()).collect();
1194        let b: Vec<String> = ["", "1", "2"].iter().map(|v| v.to_string()).collect();
1195        let mut tracker = RowCompletenessTracker::default();
1196        tracker.observe_aligned_columns(&[a.as_slice(), b.as_slice()], 3);
1197
1198        let summary = tracker.summary().expect("rows were observed");
1199        assert_eq!((summary.complete_rows, summary.rows_checked), (2, 3));
1200    }
1201
1202    #[test]
1203    fn test_aligned_columns_treat_a_short_column_as_missing() {
1204        let a: Vec<String> = ["x", "y"].iter().map(|v| v.to_string()).collect();
1205        let b: Vec<String> = ["1"].iter().map(|v| v.to_string()).collect();
1206        let mut tracker = RowCompletenessTracker::default();
1207        tracker.observe_aligned_columns(&[a.as_slice(), b.as_slice()], 2);
1208
1209        let summary = tracker.summary().expect("rows were observed");
1210        assert_eq!((summary.complete_rows, summary.rows_checked), (1, 2));
1211    }
1212
1213    #[test]
1214    fn test_exact_duplicates_including_null_rows() {
1215        let headers = vec!["a".to_string(), "b".to_string()];
1216        let mut collection = StreamingColumnCollection::new();
1217        record(&mut collection, &headers, &["x", ""]);
1218        record(&mut collection, &headers, &["x", ""]);
1219        record(&mut collection, &headers, &["x", "1"]);
1220        record(&mut collection, &headers, &["", ""]);
1221
1222        let summary = collection
1223            .row_duplicate_summary()
1224            .expect("rows were observed");
1225        assert_eq!(summary.rows_checked, 4);
1226        // Null-like values are part of the row identity: the per-column
1227        // reservoirs drop them, but the row tracker must not.
1228        assert_eq!(summary.duplicate_rows, 1);
1229        assert!(!summary.approximate);
1230    }
1231
1232    #[test]
1233    fn test_field_boundaries_are_unambiguous() {
1234        let headers = vec!["a".to_string(), "b".to_string()];
1235        let mut collection = StreamingColumnCollection::new();
1236        record(&mut collection, &headers, &["ab", "c"]);
1237        record(&mut collection, &headers, &["a", "bc"]);
1238
1239        let summary = collection
1240            .row_duplicate_summary()
1241            .expect("rows were observed");
1242        assert_eq!(
1243            summary.duplicate_rows, 0,
1244            "different field splits must not collide"
1245        );
1246    }
1247
1248    #[test]
1249    fn test_ragged_rows_normalize_missing_trailing_fields() {
1250        let headers = vec!["a".to_string(), "b".to_string()];
1251        let mut collection = StreamingColumnCollection::new();
1252        record(&mut collection, &headers, &["x"]);
1253        record(&mut collection, &headers, &["x", ""]);
1254
1255        let summary = collection
1256            .row_duplicate_summary()
1257            .expect("rows were observed");
1258        assert_eq!(summary.rows_checked, 2);
1259        assert_eq!(summary.duplicate_rows, 1);
1260        assert_eq!(
1261            collection
1262                .get_column_stats("b")
1263                .expect("column b")
1264                .null_count,
1265            2
1266        );
1267    }
1268
1269    #[test]
1270    fn test_trailing_null_like_token_is_not_trimmed() {
1271        // Only an exactly empty field is absent. A trailing "null" or " " is
1272        // a value the row holds, and `is_null_like_token` matches both;
1273        // trimming on that broader rule would collapse these rows against the
1274        // absent-field one and report duplicates that are not there.
1275        let headers = vec!["a".to_string(), "b".to_string()];
1276        let mut collection = StreamingColumnCollection::new();
1277        record(&mut collection, &headers, &["x", "null"]);
1278        record(&mut collection, &headers, &["x", " "]);
1279        record(&mut collection, &headers, &["x", ""]);
1280
1281        let summary = collection
1282            .row_duplicate_summary()
1283            .expect("rows were observed");
1284        assert_eq!(summary.duplicate_rows, 0);
1285    }
1286
1287    #[test]
1288    fn test_late_column_does_not_split_identical_rows() {
1289        // A JSON key discovered mid-stream appends a column. Rows read before
1290        // and after that point are signed against header lists of different
1291        // lengths, and two identical records must still count as duplicates.
1292        let mut collection = StreamingColumnCollection::new();
1293        let short = vec!["a".to_string()];
1294        let wide = vec!["a".to_string(), "b".to_string()];
1295
1296        record(&mut collection, &short, &["x"]);
1297        collection.init_column_with_missing("b", 1);
1298        record(&mut collection, &wide, &["x", "y"]);
1299        record(&mut collection, &wide, &["x", ""]);
1300
1301        let summary = collection
1302            .row_duplicate_summary()
1303            .expect("rows were observed");
1304        assert_eq!(summary.rows_checked, 3);
1305        assert_eq!(
1306            summary.duplicate_rows, 1,
1307            "rows 1 and 3 hold the same data; they differ only in how many \
1308             columns had been discovered when each was read"
1309        );
1310    }
1311
1312    #[test]
1313    fn test_late_column_in_the_middle_does_not_split_identical_rows() {
1314        // A second late key pushes the first one away from the end, so the
1315        // absent field sits in the middle of the later signatures.
1316        let mut collection = StreamingColumnCollection::new();
1317        let one = vec!["a".to_string()];
1318        let two = vec!["a".to_string(), "b".to_string()];
1319        let three = vec!["a".to_string(), "b".to_string(), "c".to_string()];
1320
1321        record(&mut collection, &one, &["1"]);
1322        collection.init_column_with_missing("b", 1);
1323        record(&mut collection, &two, &["1", "2"]);
1324        collection.init_column_with_missing("c", 2);
1325        record(&mut collection, &three, &["1", "", "3"]);
1326        record(&mut collection, &three, &["1", "", ""]);
1327
1328        let summary = collection
1329            .row_duplicate_summary()
1330            .expect("rows were observed");
1331        assert_eq!(summary.rows_checked, 4);
1332        assert_eq!(summary.duplicate_rows, 1, "row 4 repeats row 1");
1333    }
1334
1335    #[test]
1336    fn test_no_rows_means_no_summary() {
1337        let collection = StreamingColumnCollection::new();
1338        assert!(collection.row_duplicate_summary().is_none());
1339    }
1340
1341    #[test]
1342    fn a_column_longer_than_the_reservoir_keeps_an_exact_count() {
1343        // The engine used to go approximate as soon as a column outgrew its
1344        // 10,000-value reservoir: a one-value column over 20,000 rows was an
1345        // estimate, and 50,000 unique ids read 50,755.
1346        let mut constant = StreamingStatistics::new();
1347        let mut ids = StreamingStatistics::new();
1348        for id in 0..50_000 {
1349            constant.update("v1");
1350            ids.update(&id.to_string());
1351        }
1352        assert!(!constant.unique_count_is_approximate());
1353        assert_eq!(constant.unique_count(), 1);
1354        assert!(!ids.unique_count_is_approximate());
1355        assert_eq!(ids.unique_count(), 50_000);
1356    }
1357
1358    #[test]
1359    fn memory_pressure_spills_the_largest_exact_set_first() {
1360        let headers = vec!["id".to_string(), "flag".to_string()];
1361        // 300,000 fingerprints per exact set is ~4.7 MB; the row tracker
1362        // holds as much again. At 8 MB (pressure above 6.4 MB), spilling `id`
1363        // alone brings the collection back under the line.
1364        let mut collection = StreamingColumnCollection::memory_limit(8);
1365        for id in 0..300_000 {
1366            let flag = if id % 2 == 0 { "yes" } else { "no" };
1367            record(&mut collection, &headers, &[&id.to_string(), flag]);
1368        }
1369        assert!(
1370            collection.is_memory_pressure(),
1371            "300,000 exact fingerprints no longer exceed the limit; this test reaches nothing"
1372        );
1373        collection.reduce_memory_usage();
1374
1375        let id = collection.get_column_stats("id").unwrap();
1376        let flag = collection.get_column_stats("flag").unwrap();
1377        assert!(id.unique_count_is_approximate(), "the large set spills");
1378        assert!(!flag.unique_count_is_approximate(), "the small one is kept");
1379        assert_eq!(flag.unique_count(), 2);
1380        // Spilling was enough, so the sampled statistics keep their full
1381        // reservoirs rather than being halved on every chunk under pressure.
1382        assert_eq!(id.sample_values().len(), 10_000);
1383        assert_eq!(flag.sample_values().len(), 10_000);
1384    }
1385
1386    #[test]
1387    fn memory_pressure_spills_the_row_tracker_before_shrinking_reservoirs() {
1388        let headers = vec!["id".to_string(), "flag".to_string(), "blank".to_string()];
1389        // At 5 MB (pressure above 4 MB) spilling every column set still
1390        // leaves the row tracker's ~4.1 MB plus the reservoirs over the line.
1391        let mut collection = StreamingColumnCollection::memory_limit(5);
1392        for id in 0..300_000 {
1393            let flag = if id % 2 == 0 { "yes" } else { "no" };
1394            record(&mut collection, &headers, &[&id.to_string(), flag, ""]);
1395        }
1396        collection.reduce_memory_usage();
1397
1398        let rows = collection.row_duplicate_summary().unwrap();
1399        assert!(rows.approximate, "the row tracker spills");
1400        assert!(!collection.is_memory_pressure());
1401        // A column that has seen no value holds no exact set to give back,
1402        // so it keeps its exact count of zero.
1403        let blank = collection.get_column_stats("blank").unwrap();
1404        assert!(!blank.unique_count_is_approximate());
1405        assert_eq!(blank.unique_count(), 0);
1406        for name in ["id", "flag"] {
1407            let stats = collection.get_column_stats(name).unwrap();
1408            assert!(stats.unique_count_is_approximate(), "{name} spills first");
1409            assert_eq!(stats.sample_values().len(), 10_000, "{name} reservoir kept");
1410        }
1411    }
1412
1413    #[test]
1414    fn test_spills_to_approximate_beyond_distinct_threshold() {
1415        let headers = vec!["n".to_string()];
1416        let mut collection = StreamingColumnCollection::new();
1417        let distinct = dataprof_metrics::EXACT_CARDINALITY_THRESHOLD + 500;
1418        for i in 0..distinct {
1419            record(&mut collection, &headers, &[&i.to_string()]);
1420        }
1421        // Every row twice: duplicates == distinct.
1422        for i in 0..distinct {
1423            record(&mut collection, &headers, &[&i.to_string()]);
1424        }
1425
1426        let summary = collection
1427            .row_duplicate_summary()
1428            .expect("rows were observed");
1429        assert!(summary.approximate, "past the threshold the count is HLL");
1430        assert_eq!(summary.rows_checked, distinct * 2);
1431        let error = (summary.duplicate_rows as f64 - distinct as f64).abs() / distinct as f64;
1432        assert!(
1433            error < 0.05,
1434            "estimated {} duplicates for {distinct} true, off by {error:.4}",
1435            summary.duplicate_rows
1436        );
1437    }
1438
1439    #[test]
1440    fn test_merge_combines_row_trackers() {
1441        let headers = vec!["a".to_string()];
1442        let mut left = StreamingColumnCollection::new();
1443        let mut right = StreamingColumnCollection::new();
1444        record(&mut left, &headers, &["x"]);
1445        record(&mut left, &headers, &["y"]);
1446        record(&mut right, &headers, &["x"]);
1447
1448        left.merge(right);
1449        let summary = left.row_duplicate_summary().expect("rows were observed");
1450        assert_eq!(summary.rows_checked, 3);
1451        assert_eq!(summary.duplicate_rows, 1);
1452    }
1453
1454    #[test]
1455    fn test_merge_keeps_columns_only_the_other_side_saw() {
1456        let mut left = StreamingColumnCollection::new();
1457        let mut right = StreamingColumnCollection::new();
1458        record(&mut left, &["a".to_string()], &["1"]);
1459        record(&mut right, &["b".to_string()], &["2"]);
1460
1461        left.merge(right);
1462
1463        // A column reachable in the map but missing from the order is a column
1464        // the report never renders.
1465        assert_eq!(left.column_names(), vec!["a".to_string(), "b".to_string()]);
1466        assert!(left.get_column_stats("b").is_some());
1467    }
1468
1469    #[test]
1470    fn test_merge_pads_columns_the_other_side_never_saw() {
1471        let left_headers = vec!["a".to_string()];
1472        let right_headers = vec!["a".to_string(), "b".to_string()];
1473        let mut left = StreamingColumnCollection::new();
1474        let mut right = StreamingColumnCollection::new();
1475        record(&mut left, &left_headers, &["1"]);
1476        record(&mut left, &left_headers, &["2"]);
1477        record(&mut right, &right_headers, &["3", "x"]);
1478
1479        left.merge(right);
1480
1481        let b = left.get_column_stats("b").expect("column b survived");
1482        // Three records in the merged dataset, two of which had no `b` at all.
1483        assert_eq!(b.count, 3);
1484        assert_eq!(b.null_count, 2);
1485
1486        let a = left.get_column_stats("a").expect("column a");
1487        assert_eq!(a.count, 3);
1488        assert_eq!(a.null_count, 0);
1489    }
1490
1491    #[test]
1492    fn test_merge_combines_completeness() {
1493        let headers = vec!["a".to_string(), "b".to_string()];
1494        let mut left = StreamingColumnCollection::new();
1495        let mut right = StreamingColumnCollection::new();
1496        record(&mut left, &headers, &["1", "2"]);
1497        record(&mut left, &headers, &["3", ""]);
1498        record(&mut right, &headers, &["4", "5"]);
1499
1500        left.merge(right);
1501
1502        assert_eq!(completeness(&left), (2, 3));
1503    }
1504
1505    #[test]
1506    fn test_merge_invalidates_completeness_for_the_narrower_side() {
1507        let left_headers = vec!["a".to_string()];
1508        let right_headers = vec!["a".to_string(), "b".to_string()];
1509        let mut left = StreamingColumnCollection::new();
1510        let mut right = StreamingColumnCollection::new();
1511        record(&mut left, &left_headers, &["1"]);
1512        record(&mut right, &right_headers, &["2", "y"]);
1513
1514        left.merge(right);
1515
1516        // The left record has no `b`, so it is not complete against the union.
1517        assert_eq!(completeness(&left), (1, 2));
1518    }
1519
1520    #[test]
1521    fn test_merge_withholds_duplicates_when_schemas_differ() {
1522        let mut left = StreamingColumnCollection::new();
1523        let mut right = StreamingColumnCollection::new();
1524        record(&mut left, &["a".to_string()], &["x"]);
1525        record(&mut right, &["b".to_string()], &["x"]);
1526
1527        left.merge(right);
1528
1529        // Both rows sign as "1:x", so the count would claim one duplicate,
1530        // while under the union schema the rows differ in every field.
1531        assert!(left.row_duplicate_summary().is_none());
1532    }
1533
1534    #[test]
1535    fn test_merge_withholds_duplicates_when_column_order_differs() {
1536        let mut left = StreamingColumnCollection::new();
1537        let mut right = StreamingColumnCollection::new();
1538        record(&mut left, &["a".to_string(), "b".to_string()], &["x", "y"]);
1539        record(&mut right, &["b".to_string(), "a".to_string()], &["x", "y"]);
1540
1541        left.merge(right);
1542
1543        // Same columns, opposite order: the two signatures collide on rows
1544        // that hold the values the other way round.
1545        assert!(left.row_duplicate_summary().is_none());
1546    }
1547
1548    #[test]
1549    fn test_merge_keeps_duplicates_when_schemas_match() {
1550        let headers = vec!["a".to_string(), "b".to_string()];
1551        let mut left = StreamingColumnCollection::new();
1552        let mut right = StreamingColumnCollection::new();
1553        record(&mut left, &headers, &["x", "y"]);
1554        record(&mut right, &headers, &["x", "y"]);
1555
1556        left.merge(right);
1557
1558        let summary = left
1559            .row_duplicate_summary()
1560            .expect("one schema on both sides");
1561        assert_eq!(summary.rows_checked, 2);
1562        assert_eq!(summary.duplicate_rows, 1);
1563    }
1564
1565    #[test]
1566    fn test_merge_into_an_empty_accumulator_keeps_duplicates() {
1567        let headers = vec!["a".to_string()];
1568        let mut accumulator = StreamingColumnCollection::new();
1569        let mut partition = StreamingColumnCollection::new();
1570        record(&mut partition, &headers, &["x"]);
1571        record(&mut partition, &headers, &["x"]);
1572
1573        // A reduce starts from an empty accumulator. That is not a schema
1574        // mismatch: the empty side signed nothing to be confused with.
1575        accumulator.merge(partition);
1576
1577        let summary = accumulator
1578            .row_duplicate_summary()
1579            .expect("the empty side contributed no signatures");
1580        assert_eq!(summary.rows_checked, 2);
1581        assert_eq!(summary.duplicate_rows, 1);
1582    }
1583
1584    /// Merging partitions must produce the profile a single pass would.
1585    ///
1586    /// This is the acceptance criterion for any distributed profiling path:
1587    /// without it, the numbers silently depend on how the input was split.
1588    #[test]
1589    fn test_merged_partitions_match_a_single_pass() {
1590        let headers = vec!["id".to_string(), "city".to_string(), "score".to_string()];
1591        let rows: Vec<[String; 3]> = (0..300)
1592            .map(|index| {
1593                [
1594                    format!("{}", index % 10),
1595                    ["Rome", "Milan", "Turin", ""][index % 4].to_string(),
1596                    format!("{}.5", index % 5),
1597                ]
1598            })
1599            .collect();
1600
1601        let mut single = StreamingColumnCollection::new();
1602        for row in &rows {
1603            single.process_record(&headers, row.iter().cloned());
1604        }
1605
1606        // Seven partitions over 300 rows, so the split is uneven.
1607        let mut partitions: Vec<StreamingColumnCollection> =
1608            (0..7).map(|_| StreamingColumnCollection::new()).collect();
1609        for (index, row) in rows.iter().enumerate() {
1610            partitions[index % 7].process_record(&headers, row.iter().cloned());
1611        }
1612        let mut merged = partitions.remove(0);
1613        for partition in partitions {
1614            merged.merge(partition);
1615        }
1616
1617        assert_eq!(merged.column_names(), single.column_names());
1618        for name in single.column_names() {
1619            let expected = single.get_column_stats(&name).expect("single-pass column");
1620            let actual = merged.get_column_stats(&name).expect("merged column");
1621            assert_eq!(actual.count, expected.count, "count for {name}");
1622            assert_eq!(actual.null_count, expected.null_count, "nulls for {name}");
1623            assert_eq!(
1624                actual.unique_count(),
1625                expected.unique_count(),
1626                "distinct for {name}"
1627            );
1628            assert_eq!(actual.min, expected.min, "min for {name}");
1629            assert_eq!(actual.max, expected.max, "max for {name}");
1630            assert!(
1631                (actual.mean() - expected.mean()).abs() < 1e-9,
1632                "mean for {name}"
1633            );
1634            assert!(
1635                (actual.variance() - expected.variance()).abs() < 1e-9,
1636                "variance for {name}"
1637            );
1638        }
1639
1640        let merged_rows = merged.row_completeness_summary().expect("rows observed");
1641        let single_rows = single.row_completeness_summary().expect("rows observed");
1642        assert_eq!(merged_rows.rows_checked, single_rows.rows_checked);
1643        assert_eq!(merged_rows.complete_rows, single_rows.complete_rows);
1644
1645        let merged_dupes = merged.row_duplicate_summary().expect("rows observed");
1646        let single_dupes = single.row_duplicate_summary().expect("rows observed");
1647        assert_eq!(merged_dupes.rows_checked, single_dupes.rows_checked);
1648        assert_eq!(merged_dupes.duplicate_rows, single_dupes.duplicate_rows);
1649    }
1650}
1651
1652#[cfg(test)]
1653mod tests {
1654    use super::*;
1655    use dataprof_metrics::HyperLogLog;
1656
1657    #[test]
1658    fn test_streaming_statistics() {
1659        let mut stats = StreamingStatistics::new();
1660
1661        stats.update("10.5");
1662        stats.update("20.0");
1663        stats.update("15.5");
1664        stats.update("");
1665
1666        assert_eq!(stats.count, 4);
1667        assert_eq!(stats.null_count, 1);
1668        assert_eq!(stats.unique_count(), 3);
1669        assert!(!stats.unique_count_is_approximate());
1670        assert!((stats.mean() - 15.333333333333334).abs() < 1e-10);
1671        assert_eq!(stats.min, 10.5);
1672        assert_eq!(stats.max, 20.0);
1673    }
1674
1675    #[test]
1676    fn test_streaming_statistics_merge() {
1677        let mut stats1 = StreamingStatistics::new();
1678        stats1.update("10");
1679        stats1.update("20");
1680
1681        let mut stats2 = StreamingStatistics::new();
1682        stats2.update("30");
1683        stats2.update("40");
1684
1685        stats1.merge(&stats2);
1686
1687        assert_eq!(stats1.count, 4);
1688        assert_eq!(stats1.unique_count(), 4);
1689        assert!(!stats1.unique_count_is_approximate());
1690        assert!((stats1.mean() - 25.0).abs() < 1e-10);
1691        assert_eq!(stats1.min, 10.0);
1692        assert_eq!(stats1.max, 40.0);
1693    }
1694
1695    #[test]
1696    fn test_reservoir_merge_weights_sides_by_population() {
1697        let mut large = StreamReservoirSampler::new(100);
1698        for index in 0..10_000 {
1699            large.offer(&format!("large-{index}"));
1700        }
1701        let mut small = StreamReservoirSampler::new(100);
1702        for index in 0..100 {
1703            small.offer(&format!("small-{index}"));
1704        }
1705
1706        large.merge(&small);
1707
1708        assert_eq!(large.samples().len(), 100);
1709        let from_small = large
1710            .samples()
1711            .iter()
1712            .filter(|value| value.starts_with("small-"))
1713            .count();
1714        // The small side is 100 rows of 10,100, so it earns about one slot.
1715        // Pooling both reservoirs and subsampling uniformly would hand it
1716        // roughly half of them, making the sample depend on the partitioning.
1717        assert!(
1718            from_small <= 10,
1719            "small partition took {from_small} of 100 slots"
1720        );
1721    }
1722
1723    #[test]
1724    fn test_reservoir_merge_keeps_every_value_when_capacity_allows() {
1725        let mut left = StreamReservoirSampler::new(100);
1726        left.offer("a");
1727        left.offer("b");
1728        let mut right = StreamReservoirSampler::new(100);
1729        right.offer("c");
1730
1731        left.merge(&right);
1732
1733        let mut samples: Vec<String> = left.samples().to_vec();
1734        samples.sort();
1735        assert_eq!(samples, vec!["a", "b", "c"]);
1736        assert_eq!(left.count, 3);
1737    }
1738
1739    #[test]
1740    fn test_column_collection() {
1741        let mut collection = StreamingColumnCollection::new();
1742        let headers = vec!["name".to_string(), "age".to_string()];
1743
1744        collection.process_record(&headers, vec!["Alice".to_string(), "25".to_string()]);
1745        collection.process_record(&headers, vec!["Bob".to_string(), "30".to_string()]);
1746
1747        let age_stats = collection.get_column_stats("age").unwrap();
1748        assert_eq!(age_stats.count, 2);
1749        assert!((age_stats.mean() - 27.5).abs() < 1e-10);
1750    }
1751
1752    #[test]
1753    fn the_distinct_count_does_not_depend_on_the_reservoir() {
1754        // The reservoir bounds the sampled statistics, not the distinct count:
1755        // a column that outgrows it still counts its distinct values exactly
1756        // until the estimator itself spills.
1757        let mut stats = StreamingStatistics::with_sample_capacity(2);
1758        for value in ["a", "b", "c", "a"] {
1759            stats.update(value);
1760        }
1761        assert_eq!(stats.unique_count(), 3);
1762        assert!(!stats.unique_count_is_approximate());
1763
1764        stats.spill_distinct();
1765        assert!(stats.unique_count_is_approximate());
1766        assert_eq!(stats.unique_count(), 3);
1767    }
1768
1769    #[test]
1770    fn test_default_reservoir_sampling_is_deterministic() {
1771        let mut left = StreamReservoirSampler::new(10);
1772        let mut right = StreamReservoirSampler::new(10);
1773        for value in 0..1_000 {
1774            left.offer(&value.to_string());
1775            right.offer(&value.to_string());
1776        }
1777
1778        assert_eq!(left.samples(), right.samples());
1779    }
1780
1781    #[test]
1782    fn shrinking_a_reservoir_keeps_a_uniform_subset_not_its_head() {
1783        // A full reservoir that has not replaced anything yet holds the stream
1784        // in order, so truncating it kept exactly the first values.
1785        let mut sampler = StreamReservoirSampler::new(1_000);
1786        for value in 0..1_000 {
1787            sampler.offer(&value.to_string());
1788        }
1789        sampler.shrink_to(100);
1790
1791        let retained: Vec<usize> = sampler
1792            .samples()
1793            .iter()
1794            .map(|value| value.parse().unwrap())
1795            .collect();
1796        assert_eq!(retained.len(), 100);
1797        let mean = retained.iter().sum::<usize>() as f64 / retained.len() as f64;
1798        assert!(
1799            (350.0..650.0).contains(&mean),
1800            "mean {mean} of {retained:?}"
1801        );
1802        let mut distinct = retained.clone();
1803        distinct.sort_unstable();
1804        distinct.dedup();
1805        assert_eq!(distinct.len(), 100, "a value was kept twice");
1806    }
1807
1808    #[test]
1809    fn test_reservoir_zero_capacity_still_retains_a_sample() {
1810        let mut sampler = StreamReservoirSampler::new(0);
1811        sampler.offer("value");
1812
1813        assert_eq!(sampler.samples(), ["value"]);
1814    }
1815
1816    #[test]
1817    fn test_late_column_is_backfilled_as_missing() {
1818        let mut collection = StreamingColumnCollection::new();
1819        collection.init_column_with_missing("late", 3);
1820        collection.process_record(&["late".to_string()], ["value".to_string()]);
1821
1822        let stats = collection.get_column_stats("late").unwrap();
1823        assert_eq!(stats.count, 4);
1824        assert_eq!(stats.null_count, 3);
1825        assert_eq!(stats.unique_count(), 1);
1826    }
1827
1828    #[test]
1829    fn test_welford_accuracy() {
1830        let mut accumulator = NumericAccumulator::new();
1831        for value in 1..=1000 {
1832            accumulator.update(value as f64);
1833        }
1834        let expected_mean = 500.5;
1835        let expected_variance = (1000.0 * 1000.0 - 1.0) / 12.0;
1836        assert!((accumulator.mean() - expected_mean).abs() < 1e-6);
1837        assert!((accumulator.population_variance() - expected_variance).abs() < 1.0);
1838    }
1839
1840    #[test]
1841    fn test_welford_merge() {
1842        let mut left = NumericAccumulator::new();
1843        let mut right = NumericAccumulator::new();
1844        let mut full = NumericAccumulator::new();
1845
1846        for value in 1..=500 {
1847            left.update(value as f64);
1848            full.update(value as f64);
1849        }
1850        for value in 501..=1000 {
1851            right.update(value as f64);
1852            full.update(value as f64);
1853        }
1854
1855        left.merge(&right);
1856        assert!((left.mean() - full.mean()).abs() < 1e-10);
1857        assert!((left.population_variance() - full.population_variance()).abs() < 1e-6);
1858    }
1859
1860    #[test]
1861    fn test_hll_cardinality() {
1862        let mut counter = HyperLogLog::new();
1863        let total = 100_000;
1864        for index in 0..total {
1865            counter.insert(&format!("item_{index}"));
1866        }
1867        let estimate = counter.count();
1868        let error = (estimate as f64 - total as f64).abs() / total as f64;
1869        assert!(error < 0.05);
1870    }
1871
1872    #[test]
1873    fn test_reservoir_uniformity() {
1874        let mut sampler = StreamReservoirSampler::seed(1000, 42);
1875        let total = 100_000;
1876        for index in 0..total {
1877            sampler.offer(&index.to_string());
1878        }
1879
1880        assert_eq!(sampler.samples().len(), 1000);
1881        let values: Vec<usize> = sampler
1882            .samples()
1883            .iter()
1884            .map(|value| value.parse().unwrap())
1885            .collect();
1886        let max_value = *values.iter().max().unwrap();
1887        assert!(max_value > total / 2);
1888    }
1889
1890    #[test]
1891    fn test_text_length_stats_streaming() {
1892        let mut stats = TextLengthStats::new();
1893        for &length in &[3, 5, 10, 1, 7] {
1894            stats.update(length);
1895        }
1896        assert_eq!(stats.min_length, 1);
1897        assert_eq!(stats.max_length, 10);
1898        assert!((stats.avg_length - 5.2).abs() < 1e-10);
1899    }
1900
1901    #[test]
1902    fn test_memory_usage_bounded() {
1903        let mut stats = StreamingStatistics::new();
1904        for index in 0..50_000 {
1905            stats.update(&format!("value_{index}"));
1906        }
1907        let usage = stats.memory_usage_bytes();
1908        assert!(usage < 1_000_000);
1909    }
1910}