DuckDB favg returns the wrong average when values differ greatly in magnitude
In DuckDB 1.5.5 and 2.0.0, favg returns the wrong average when values differ greatly in magnitude. Over the four doubles 1, 1e100, 1, and −1e100, it returns 0.0. It should return 0.5.
Reproduce it
SELECT favg(v) FROM (VALUES (1.0::DOUBLE), (1e100), (1.0), (-1e100)) t(v);
DuckDB 2.0.0 returns:
0.0
The correct answer
The correct answer is 0.5. 1e100 − 1e100 + 1 + 1 = 2. The mean of the four values is 2 / 4 = 0.5. The Python code determines the exact mean with fractions and rounds it once to a double:
from fractions import Fraction as F
def favg(values):
# the exact mean, rounded once to a double
return float(sum(F(v) for v in values) / len(values))
print(favg([1.0, 1e100, 1.0, -1e100])) # 0.5
Why DuckDB gets it wrong
A double can only hold the equivalent of around 16 decimal digits of precision. Adding 1 to 1e100 requires more precision.
DuckDB's favg uses Kahan summation in an attempt to prevent this precision loss. However, it only catches the loss when the running sum is the larger number in the summation step. If the running sum is the smaller number, it is unable to catch the precision loss.
Kahan Algorithm
- adjusted value = value − correction
- new sum = adjusted value + old sum
- correction = (new sum − old sum) − adjusted value
| Value | Adj Val | Sum | Correction | Explanation |
|---|---|---|---|---|
| — | — | 0 | 0 | init |
| 1 | 1 | 1 | 0 | First number into accumulator |
| 1e100 | 1e100 | 1e100 | 0 | We lost the 1 here due to precision |
| 1 | 1 | 1e100 | −1 | We caught the −1 since 1e100 cancel out |
| −1e100 | −1e100 | 0 | 0 | The −1 correction is lost during addition due to precision |
Therefore the average is 0/4 = 0.
How to fix it
Shewchuk summation keeps the sum exact by storing it as a short list of doubles called partials.
Shewchuk Algorithm
- Start with an empty partial list
- If a new value can't be added to an existing partial without loss of precision → then keep it as its own partial → else add it to an existing partial
- If adding to an existing partial results in zero, remove it
Final Step: result = sum of the partials, rounded once
| Value | Partials | Explanation |
|---|---|---|
| — | [ ] | init |
| 1 | [1] | First number into accumulator |
| 1e100 | [1, 1e100] | The 1 can't add to 1e100 partial without losing precision, so it stays a partial |
| 1 | [2, 1e100] | The 1 is added to the 1 partial |
| −1e100 | [2] | 1e100 cancels and its partial is removed |
Result: 2, and the average is 2/4 = 0.5.
Vendor issue
Reported to DuckDB as duckdb/duckdb#27961.
writePath
FAVG function
writePath's FAVG uses Shewchuk summation. No precision is lost due to the way partials are handled. The sum is rounded only once at the end, so the result is the most precise double. The function ensures results are always the same regardless of 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.