DuckDB fsum returns NaN instead of the sum when the running sum overflows
In DuckDB 2.0.0, fsum returns NaN instead of the sum when the running sum overflows.
Reproduce it
SELECT fsum(v) FROM (VALUES (1e308::DOUBLE), (1e308), (-1e308)) t(v);
DuckDB 2.0.0 returns:
-nan
The correct answer
The correct answer is 1e+308. 1e308 + 1e308 − 1e308 = 1e308.
from fractions import Fraction as F
def fsum(values):
# the exact sum, rounded once to a double
return float(sum(F(v) for v in values))
print(fsum([1e308, 1e308, -1e308])) # 1e+308
Why DuckDB gets it wrong
DuckDB's fsum keeps its Kahan running sum in a double. The sum overflows to infinity even though the true sum fits in a double.
Kahan Algorithm
- adjusted value = value − correction
- new sum = old sum + adjusted value
- correction = (new sum − old sum) − adjusted value
- merge: add the sum, then minus the correction, into an empty sum with steps 1–3
- result = sum
| Value | Adjusted | Sum | Correction | Explanation |
|---|---|---|---|---|
| — | — | 0 | 0 | init |
| 1e308 | 1e308 | 1e308 | 0 | First value into the sum |
| 1e308 | 1e308 | inf | inf | The sum passes the largest double, so the sum and the correction become inf |
| −1e308 | −inf | nan | nan | −1e308 − inf = −inf, and inf + −inf = nan |
| merge: nan | nan | nan | nan | Merging the sum into an empty one carries the nan |
| merge: nan | nan | nan | nan | Merging minus the correction keeps the nan |
Result: fsum returns the sum, nan, which DuckDB prints as -nan.
How to fix it
A fixed-point sum keeps the sum exact with room for sums far beyond the largest double. It does this by adding every value as a whole number of units of the smallest double.
Fixed-Point Algorithm
- Start with a sum of 0
- Turn each value into a whole number of units of the smallest double (value × 2^1074)
- Add that whole number to the sum exactly
Final Step: result = sum × 2^−1074, rounded once
| Value | Units | Sum (units) | Explanation |
|---|---|---|---|
| — | — | 0 | init |
| 1e308 | 1e308 × 2^1074 | 1e308 × 2^1074 | First value into the sum, exactly |
| 1e308 | 1e308 × 2^1074 | 2 × 1e308 × 2^1074 | Added exactly, with no overflow |
| −1e308 | −1e308 × 2^1074 | 1e308 × 2^1074 | Added exactly |
Result: 1e308 × 2^1074 × 2^−1074 = 1e+308.
Vendor issue
Reported to DuckDB as duckdb/duckdb#28164.
writePath
FSUM function
writePath's FSUM uses an exact fixed-point sum. No precision is lost because every value is added as a whole number. The sum is rounded once at the end, so the result is the most precise double. The result does not depend on row order.
About us
writePath is an AWS Marketplace SaaS for sub-millisecond aggregations over the first or last N rows of your data with no pre-computation. It offers 65 high-precision aggregation functions tested against reference implementations.