Duckdb: R: Incorrect results from rolling window summation

[DavisVaughan]

I would imagine that this affects duckdb as a whole, but here is an example in R of computing a size 2 rolling summation of the current row + 1 row before it. I've compared with SQLite for the correct results:

library(duckdb)
library(RSQLite)
library(DBI)

con_sqlite <- dbConnect(SQLite())
con_duck <- dbConnect(duckdb())

dbWriteTable(con_sqlite, "cars", mtcars)
dbWriteTable(con_duck, "cars", mtcars)

query <- "
  SELECT 
    mpg, 
    SUM(mpg) OVER (ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS mpg_roll
  FROM
    cars
"

head(dbGetQuery(con_sqlite, query), n = 10)
#>     mpg mpg_roll
#> 1  21.0     21.0
#> 2  21.0     42.0
#> 3  22.8     43.8
#> 4  21.4     44.2
#> 5  18.7     40.1
#> 6  18.1     36.8
#> 7  14.3     32.4
#> 8  24.4     38.7
#> 9  22.8     47.2
#> 10 19.2     42.0

head(dbGetQuery(con_duck, query), n = 10)
#>     mpg mpg_roll
#> 1  21.0    642.9
#> 2  21.0    642.9
#> 3  22.8    621.9
#> 4  21.4    600.9
#> 5  18.7    578.1
#> 6  18.1    556.7
#> 7  14.3    538.0
#> 8  24.4    519.9
#> 9  22.8    505.6
#> 10 19.2    481.2

^{Created on 2020-09-28 by the reprex package (v0.3.0.9001)}

[jtommaney-alibaba]

Possibly related to missing order by clause? Without order by, correct interpretation may be that multiple preceding rows are tied/included. TBH, not sure if there is constant handling here, with at least some dbms issuing a syntax error.

Behavior appears correct with order by clause:

query="""
SELECT
mpg,
SUM(mpg) OVER (order by model ROWS BETWEEN 1 PRECEDING AND CURRENT ROW ) AS mpg_roll
FROM
cars order by model
"""
print(cur.execute(query).fetchall())

(15.2, 15.2),
(10.4, 25.6),
(13.3, 23.7),
(14.7, 28.0),
(22.8, 37.5),
(15.5, 38.3),
(14.3, 29.8),
(19.7, 34.0),
(32.4, 52.1),
(27.3, 59.7),
(15.8, 43.1),
(30.4, 46.2),
(21.4, 51.8),
(18.7, 40.1),
(10.4, 29.1),
(30.4, 40.8),
(15.0, 45.4),
(21.0, 36.0),
(21.0, 42.0),
(22.8, 43.8),
(24.4, 47.2),
(19.2, 43.6),
(17.8, 37.0),
(16.4, 34.2),
(17.3, 33.7),
(15.2, 32.5),
(19.2, 34.4),
(26.0, 45.2),
(33.9, 59.9),
(21.5, 55.4),
(18.1, 39.6),
(21.4, 39.5)

[DavisVaughan]

Oh interesting. I probably would have expected the implicit row number to be used when order-by isn't specified here.

Nevertheless, I think there might still be some issues? Here is a similar example with a row number specified, again we just compute the rolling sum of the current value + 1 value before. Results seem to be incorrect at seemingly random locations

library(duckdb)
#> Warning: package 'duckdb' was built under R version 4.0.2
#> Loading required package: DBI
library(DBI)
library(data.table)

con_duck <- dbConnect(duckdb())

n_row <- 1e5L

df <- data.frame(
  x = seq_len(n_row) + 0, 
  row_number = seq_len(n_row)
)

query <- "
  SELECT 
    SUM(x) OVER (ORDER BY row_number ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS x_roll
  FROM
    temp
"

duckdb_register(con_duck, "temp", df)

roll_duck <- dbGetQuery(con_duck, query)$x_roll
roll_dt <- frollsum(df$x, 2)

# frollsum() doesn't compute on partial windows so hack this to mimic duckdb behavior
roll_dt[[1]] <- df$x[[1]]

issues <- roll_duck != roll_dt

# quite a few differences
sum(issues)
#> [1] 6305

first_diff <- which(issues)[1]

df$roll_duck <- roll_duck
df$roll_dt <- roll_dt

# check out the rows around the first issue
df[first_diff + -5:5,]
#>       x row_number roll_duck roll_dt
#> 892 892        892      1783    1783
#> 893 893        893      1785    1785
#> 894 894        894      1787    1787
#> 895 895        895      1789    1789
#> 896 896        896      1791    1791
#> 897 897        897      1857    1793
#> 898 898        898      1923    1795
#> 899 899        899      1925    1797
#> 900 900        900      1927    1799
#> 901 901        901      1929    1801
#> 902 902        902      1931    1803

^{Created on 2020-09-28 by the reprex package (v0.3.0.9001)}

[Mytherin]

Thanks for the report! I can confirm this is a bug, even with the ordering specified. The following SQL statements reproduces your results:

create table temp as select * from range(0, 10000) temp(x);
SELECT *,
       expected=x_roll
FROM
  (SELECT x,
          rowid,
          CASE WHEN x=0 THEN 0
          ELSE x*2-1
          END AS expected,
          SUM(x) OVER (ORDER BY rowid ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS x_roll
   FROM temp) t1(x)
WHERE x BETWEEN 892 AND 902
ORDER BY x;

This gives the following results:

x           rowid       expected    x_roll      expected=x_roll
----------  ----------  ----------  ----------  ---------------
892         892         1783        1783        true           
893         893         1785        1785        true           
894         894         1787        1787        true           
895         895         1789        1789        true           
896         896         1791        1855        false          
897         897         1793        1921        false          
898         898         1795        1923        false          
899         899         1797        1925        false          
900         900         1799        1927        false          
901         901         1801        1929        false          
902         902         1803        1931        false    

The case where no ORDER BY is specified is a bit more fuzzy indeed. This case is not as important as the results are not well defined (and many systems throw an error here). I do think the results you are seeing are a result of a bug as well (likely the same bug). Likely when we fix this bug the results will match the ones by SQLite.

[Mytherin]

Both issues should be fixed in #970. These were actually two separate problems. The first was caused by the transformer not correctly handling the ROWS BETWEEN... case, and instead parsing it as RANGE BETWEEN.... Because there was no ORDER BY supplied, the range is the entire result (everything is tied in order). This caused the first two rows to be the sum of all values, the third result to be the sum of all values minus the first, etc.

The second problem was caused by an intermediate chunk not being properly reset, which lead to a read-only part being written to in an edge case, which caused incorrect results.

Thanks again for the report!