DuckDB fsum returns the wrong sum when small values are added to a large value that later cancels
In DuckDB 2.0.0, fsum returns the wrong sum when small values are added to a large value that later cancels.
Reproduce it
SELECT fsum(v) FROM (SELECT 3.6686354453820154e17::DOUBLE AS v UNION ALL SELECT 37.0::DOUBLE FROM range(14) UNION ALL SELECT -3.6686354453820154e17::DOUBLE);
DuckDB 2.0.0 returns:
512.0
The correct answer
The correct answer is 518.0.
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([3.6686354453820154e17] + [37.0] * 14 + [-3.6686354453820154e17])) # 518.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
- each part of the UNION ALL is summed in its own partial state with steps 1–3
- merge: each partial state, in order, adds its sum, then minus its correction, into one result state that starts empty, with steps 1–3
- result = sum
| Value | Adjusted | Sum | Correction | Explanation |
|---|---|---|---|---|
| — | — | 0 | 0 | init: first partial state |
| 3.6686354453820154e17 | 3.6686354453820154e17 | 3.6686354453820154e17 | 0 | First value into the sum |
| merge: 3.6686354453820154e17 | 3.6686354453820154e17 | 3.6686354453820154e17 | 0 | The partial state is merged into the empty result state: the sum |
| merge: −0 | −0 | 3.6686354453820154e17 | 0 | Then minus the correction |
| — | — | 0 | 0 | init: second partial state, for the 37s |
| 37 | 37 | 37 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 74 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 111 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 148 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 185 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 222 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 259 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 296 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 333 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 370 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 407 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 444 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 481 | 0 | Whole numbers this small add exactly |
| 37 | 37 | 518 | 0 | Whole numbers this small add exactly |
| merge: 518 | 518 | 3.6686354453820205e17 | −6 | 3.6686354453820154e17 + 518 rounds to 3.6686354453820154e17 + 512, and the correction catches the −6 |
| merge: −0 | 6 | 3.6686354453820205e17 | −6 | Then minus the correction: 0 − (−6) = 6 rounds away again, so the correction stays −6 |
| — | — | 0 | 0 | init: third partial state |
| −3.6686354453820154e17 | −3.6686354453820154e17 | −3.6686354453820154e17 | 0 | First value into the sum |
| merge: −3.6686354453820154e17 | −3.6686354453820154e17 | 512 | 0 | −3.6686354453820154e17 − (−6) rounds to −3.6686354453820154e17, so the correction is lost |
| merge: −0 | −0 | 512 | 0 | Then minus the correction |
Result: fsum returns the sum, 512.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 |
| 3.6686354453820154e17 | 3.6686354453820154e17 × 2^1074 | 3.6686354453820154e17 × 2^1074 | First value into the sum, exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 37) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 74) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 111) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 148) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 185) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 222) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 259) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 296) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 333) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 370) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 407) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 444) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 481) × 2^1074 | Added exactly |
| 37 | 37 × 2^1074 | (3.6686354453820154e17 + 518) × 2^1074 | Added exactly |
| −3.6686354453820154e17 | −3.6686354453820154e17 × 2^1074 | 518 × 2^1074 | 3.6686354453820154e17 cancels exactly |
Result: 518 × 2^1074 × 2^−1074 = 518.0.
Vendor issue
Reported to DuckDB as duckdb/duckdb#28162.
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.