Source-linked AI summary
Bounded, Indeterminate, or a Bug: A Condition-Aware Oracle for Differential Testing of SQL Aggregates
Madhulatha Mandarapu, Sandeep Kunkunuru
TL;DR
Floating-point aggregates undermine differential testing because legitimate rounding differences can resemble bugs, and fixed epsilons misclassify errors. The paper uses exact rational ground truth with algorithm-specific forward-error bounds, finding that variance can become untestable far earlier than sum, especially in ClickHouse, while a 360-test hunt found no anomalies.
Problem
Floating-point aggregates lack a sound differential-testing oracle because non-associative arithmetic allows correct engines to disagree, while fixed epsilons can misclassify discrepancies.
Method
The paper treats the exact rational value of stored doubles as ground truth and classifies discrepancies using forward-error bounds parameterized by the aggregate’s condition number and engine algorithm.
Results
ClickHouse is the lone one-pass engine with p=2.05; on ordinary data its variance is wrong by up to 2100%, while stable engines remain exact to eleven digits.
Takeaways & Limitations
Testability is an algorithm property: one-pass variance becomes untestable at a condition number about 10^6 below sum’s, including ordinary timestamp data.
Takeaways & Limitations
The oracle assumes normalized arithmetic and finite exact intermediate sums, and the study’s 360-test hunt found zero anomalies rather than proving engine correctness.
Abstract
from arXiv · showhide
Differential database testing compares results across engines and calls a discrepancy a bug. For floating-point aggregates this is unsound: engines legitimately disagree because floating-point arithmetic is not associative. Practice patches this with an epsilon; the leading oracles avoid floating point entirely. We give the oracle this practice lacks, and show its decisive quantity is not the query but the engine's algorithm. Ground truth is the exact rational value of the stored doubles -- arithmetic, not another engine -- and each discrepancy is classified exact, bounded, or indeterminate. The relative error of an aggregate f under an algorithm A obeys rel_err <= C_A(n,u) * kappa_f^p, so the testability boundary, beyond which no oracle can separate a bug from rounding, is kappa*_{f,A} = (1/C_A)^{1/p}. SUM and AVG are the linear case p=1; variance is p=2 for the one-pass algorithm and p=1 for Welford. Across eight engines in four classes the measured exponent recovers each algorithm, and ClickHouse is the lone one-pass engine (p=2.05); engine-wide, it returns zero standard deviation, NaN correlation and wrong-sign regression, while every other engine stays exact and the vendor ships the Welford fix. Its variance is untestable at a condition number 10^6 below SUM's, which ordinary storage conventions (epoch-nanosecond timestamps, tight sensors) cross -- there ClickHouse errs by 2100%. A randomised hunt of 360 tests finds zero anomalies, evidence the oracle is sound. Code and data are public.
1 Introduction
Floating-point aggregates make differential testing unsound because non-associative arithmetic permits legitimate cross-engine differences. The paper introduces an algorithm-aware oracle and shows that variance exposes a much narrower testability boundary than sum.
- Floating-point arithmetic is not associative, so engines may return different but correct aggregate results when they combine values in different orders.
- A fixed epsilon misclassifies both cancellation-heavy computations and accurate computations, whereas the relevant discriminator is the condition number.
- The oracle uses the exact rational value of stored doubles and classifies discrepancies as exact, bounded, or indeterminate using an algorithm-specific bound.
- For sum and avg, the testability boundary is 1/γn; textbook one-pass variance has a boundary of (1/γn)1/2, roughly 10^6 times smaller.
- Across eight engines, ClickHouse is the lone one-pass engine with p=2.05, while every other engine is stable with p ≤1.06.
- On ordinary timestamp, coordinate, and sensor data, ClickHouse variance can be wrong by up to 2100%, while stable engines remain exact to eleven digits.
- A randomized hunt of 360 in-domain tests found zero anomalies, supporting oracle soundness rather than engine correctness.
2 The condition number and the testability boundary
The paper defines exact rational ground truth and analyzes aggregate error through condition number, unit roundoff, and algorithm-dependent stability parameters. The resulting boundary differs sharply between linear aggregates, one-pass variance, and Welford variance.
- Every stored binary64 value is rational, enabling exact aggregate ground truth in arbitrary precision; the unit roundoff is u = 2^-53.
- Sum, avg, and Welford variance remain decidable to κ∼10^12, while textbook one-pass variance becomes indeterminate above κ∼10^6.
- The variance condition number is 1 + x̄^2/V, becoming large when a column is nearly constant and its variance is tiny relative to its raw second moment.
- Textbook one-pass variance forms a cancelling subtraction and has exponent p=2, whereas Welford accumulates deviations from a running mean and has p=1.
- At n = 10^4, the one-pass boundary is 9.5 × 10^5 versus 9.0 × 10^11 for the linear case, making its decidable window about 10^6 times narrower.
3 The oracle: verdicts and two boundaries
The oracle compares an engine answer with exact ground truth under the measured algorithm’s error bound. It distinguishes explainable rounding from anomalies and marks discrepancies beyond the boundary as undecidable.
- Given an engine answer, exact value, condition number, and measured algorithm, the oracle evaluates the algorithm-specific relative-error bound.
- When κf ≥1, the bound admits any discrepancy, so no oracle can distinguish a bug from rounding for that aggregate–algorithm pair.
- A discrepancy is bounded when it lies within the algorithm’s bound, meaning the difference is explained by that algorithm.
- A discrepancy is anomalous when it exceeds what the algorithm can produce, indicating a candidate bug or modelling error that requires triage.
- Beyond κ∗f,A = (1/CA)1/p, testing cannot conclude anything from a discrepancy; one-pass algorithms reach this wall quadratically sooner.
- A fixed epsilon has a crossover κε where it produces false negatives below the crossover and false positives above it.
4 Experimental setup
The evaluation uses five local database engines, measures native or explicitly identified aggregate implementations, and verifies bit-exact data transport before error analysis.
- The local setup includes PostgreSQL 17, MySQL 8.4, ClickHouse 25.3, DuckDB 1.5.4, and SQLite 3.45.1.
- The harness measures compensated sums where available and uses each engine’s native population variance, with a Welford user-defined aggregate as SQLite’s stable reference.
- All engines receive bit-exact values, except SQLite and PostgreSQL normalize −0.0 to +0.0; signed zero does not change sum or variance.
5 Results I: SUM is the linear baseline
SUM instantiates the oracle in the linear p=1 case and provides the baseline against which variance results depart.
- Zero anomalies were found across the SUM grid, with plain sums staying within γ_nκ and compensated sums within tighter bounds.
- At n=10^4, the SUM testability boundary is κ*=9.0 × 10^11.
- Real TPC-H sums sit at κ≈1, far inside the decidable zone, making shipped epsilons too permissive.
- Only fuzzer-generated exactly cancelling ±MAX data reaches SUM’s indeterminate regime.
6 Results II: variance recovers the algorithm
Measured error slopes recover the variance algorithm used by each engine, distinguishing ClickHouse’s one-pass computation from stable alternatives. The resulting per-algorithm oracle bounds large disagreements without falsely labeling rounding as bugs.
- Algorithm recovery: p=2.05 identifies ClickHouse’s varPop as the textbook one-pass algorithm, while other engines exhibit approximately linear error growth.Measured slopes are 0.90 for DuckDB, MySQL, and SQLite’s Welford reference, and 1.05 for PostgreSQL.
- Algorithm recovery: The reference exponents recover the known Welford and one-pass behaviors, serving as a leak check for the algorithm-identification harness.The harness must recover reference implementations before its measurements on database engines can be trusted.
- Oracle verdicts: Zero anomalies across 70 variance cells and 70 sum cells shows that the per-algorithm bound correctly classifies discrepancies, including ClickHouse’s indeterminate cases.The one-pass bound turns indeterminate when its predicted error reaches one rather than falsely accusing the engine.
- Oracle verdicts: Above κV ≈ 10^6, ClickHouse becomes indeterminate while four stable engines remain bounded to eleven digits.A large ClickHouse–DuckDB disagreement in this regime is compatible with ClickHouse rounding and cannot be interpreted using an overly tight fixed epsilon.
7 Results III: real data versus its representation
Variance is well-conditioned on raw analytic columns but becomes difficult to test when ordinary storage conventions introduce large offsets. Epoch-scale representations cross the one-pass boundary, producing severe ClickHouse errors while stable engines remain accurate.
- Raw analytic data: κV ∈ [1.9, 13.4] for TPC-H numeric columns stays far inside both algorithms’ decidable zones.This includes dates stored as epoch days and seconds, so raw analytic columns pose no conditioning hazard.
- Representation effects: κV grows with additive offsets, so absolute representations such as epoch timestamps, kelvin temperatures, coordinates, and prices can make ordinary spreads ill-conditioned.Variance conditioning differs from summation conditioning because κV is offset-sensitive.
- Representation effects: Five of six storage conventions cross the one-pass boundary κ∗_one-pass = 9.5 × 10^5, making ClickHouse’s varPop indeterminate or grossly wrong.The coarse daily price series is the negative control and remains decidable everywhere.
- Representation effects: 21 relative error, or 2100%, occurs for one-minute event timestamps stored as Unix seconds, while stable engines remain accurate to 10^-10.The p=2 bound admits the ClickHouse error, so the verdict is indeterminate rather than an anomaly.
- Representation effects: Everyday representation choices reach the indeterminate regime for variance, unlike sum’s need for fuzzer-generated ±MAX values.The exposure is attributed to the interaction between storage representation and engine algorithm.
8 Results IV: the taxonomy across engine classes and the moment family
Measurements across engine classes show that one-pass moment computation is concentrated in ClickHouse rather than widespread, and its algorithmic choice extends across the moment family with qualitatively broken results on ill-conditioned data.
- Taxonomy across engine classes: ClickHouse is the only one-pass engine across the surveyed classes, while PostgreSQL, MySQL, DuckDB, SQLite, DataFusion and QuestDB are stable.The time-series engine is stable, so the timestamp hazard is attributed to ClickHouse’s algorithm rather than time-series systems generally.
- Moment family: The one-pass choice spans ClickHouse’s moment family, including variance, covariance, correlation, regression and standard deviation.Its covariance exponent is p = 2.02, matching its variance measurement, while every other tested engine is stable again.
- Moment family: ClickHouse documents the instability and ships slower Stable variants that implement the prescribed Welford fix.On the same column, varPopStable and covarPopStable have relative errors 1.5 × 10−8 and 8.6 × 10−9, versus 100% and 6200% for the defaults.
- Taxonomy across engine classes: Figure 5 compares measured exponents for variance and covariance across eight engines and four classes, isolating ClickHouse as an engine-level outlier.The other engines remain in the stable region across all classes.
9 Soundness: a bug hunt and the domain of validity
A randomized hunt found no bound violations in 360 in-domain engine-tests, supporting oracle soundness while also identifying explicit validity limits for subnormal and overflowing inputs.
- Soundness: 360 randomized in-domain engine-tests produced zero anomalies across seven generators, three table sizes, four seeds and six engines.The result is evidence that the bounds are sound, not evidence that the engines are bug-free.
- Domain of validity: The oracle applies to normalized columns whose exact intermediate sums are finite, excluding cases that violate its arithmetic assumptions.Higham’s bound assumes normalized arithmetic and no overflow.
- Domain of validity: Under gradual underflow, deviations round to zero and every engine returns variance 0, making the normalized-float bound inapplicable rather than revealing a bug.These subnormal inputs are treated as a modeling limit because all engines agree.
- Domain of validity: Near overflow, the exact sum of squares can exceed binary64 range and produce genuine ±∞, so the oracle’s bound is undefined.Such cases are excluded from the oracle’s domain.
10 Related work
Prior differential-testing work largely avoids floating-point discrepancies or uses fixed tolerances, while this paper carries condition-aware forward-error bounds into DBMS testing. Its scope and claims are bounded by measured algorithms, configurations, workloads, and binary64 aggregate cases.
- Prior differential testing: Prior work either restricts multi-row aggregates, partitions queries so rounding errors cancel, avoids floating-point cases, or uses a 1% epsilon.None of these approaches classifies a numeric discrepancy against a forward-error bound.
- Contribution: The paper extends condition-number-aware oracle design from standalone numerical programs to DBMS differential testing.It instantiates the bound for p=1 and p=2 aggregate families and measures real engines and workloads.
- Data boundary: Real analytic columns are safe, while the variance hazard arises from storage representations such as epoch-nanosecond timestamps and tight sensors.The limitation is attributed to representation rather than analytic data itself.
- Interpretation: ClickHouse’s high-exponent one-pass moment family is treated as a documented speed/accuracy trade-off, with Stable variants shipped by the engine.The paper therefore judges the default against the p=2 bound rather than labeling every resulting verdict an anomaly.
- Limitations: The exponent is measured through controlled log–log fits, and differential power remains qualified by thread and plan settings.Stable-engine slopes of 0.90–1.05 do not establish unconditional variance safety.
- Scope: The evaluation covers binary64 sum, population variance/stddev, and covariance-family aggregates, while decimal semantics, windowed aggregates, and group-by partitioning remain untouched.Average is not measured separately but follows analytically from sum’s conditioning.
12 Conclusion
The paper replaces fixed epsilon testing for floating-point aggregates with exact rational ground truth and an algorithm-specific forward-error decision rule. This yields a testability boundary that can classify discrepancies as exact, bounded, or indeterminate, with variance especially vulnerable under one-pass algorithms.
- 12 Conclusion: The oracle uses the exact rational value of stored doubles as ground truth and classifies discrepancies as exact, bounded, or indeterminate.The resulting boundary is κ*_{f,A} = (1/C_A)^(1/p), determined by the engine’s algorithm.
- 12 Conclusion: Variance under the shipped one-pass algorithm becomes untestable 10^6 times sooner than sum, including on ordinary timestamp data.The conclusion ties this boundary to the algorithm rather than merely to the query.
- 12 Conclusion: Code, exact workloads, and a one-command reproduction are publicly available, and the experiments used one machine with free software and no cloud resources.The repository URL is provided in the paper.