DuckDB fsum returns the wrong sum when small values are summed before the large values cancel
In DuckDB 2.0.0, fsum returns the wrong sum when small values are summed before the large values cancel.
Reproduce it
SELECT fsum(v) FROM (VALUES (1e16::DOUBLE), (1.0), (-1e16)) t(v);
DuckDB 2.0.0 returns:
0.0
The correct answer
The correct answer is 1.0. 1e16 + 1 − 1e16 = 1. The Python code determines the exact sum with fractions and rounds it once to a double:
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([1e16, 1.0, -1e16])) # 1.0
Why DuckDB gets it wrong
DuckDB's fsum applies its Kahan correction by folding it into the next value it adds. When that next value is large, the correction is rounded away.
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 |
| 1e16 | 1e16 | 1e16 | 0 | First value into the sum |
| 1 | 1 | 1e16 | −1 | The 1 is lost in the sum but caught as a −1 correction |
| −1e16 | −1e16 | 0 | 0 | −1e16 − (−1) rounds to −1e16, so the correction is lost |
| merge: 0 | 0 | 0 | 0 | The partial state is merged into an empty one: the sum |
| merge: −0 | −0 | 0 | 0 | Then minus the correction |
Result: fsum returns the sum, 0.0.
How to fix it
A fixed-point sum keeps the sum exact 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 |
| 1e16 | 1e16 × 2^1074 | 1e16 × 2^1074 | First value into the sum, exactly |
| 1 | 1 × 2^1074 | (1e16 + 1) × 2^1074 | The 1 is kept: whole numbers add exactly |
| −1e16 | −1e16 × 2^1074 | 1 × 2^1074 | 1e16 cancels exactly |
Result: 1 × 2^1074 × 2^−1074 = 1.0.
Vendor issue
Reported to DuckDB as duckdb/duckdb#28161.
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.