Duckdb: Add statistic functions

[willium]

For our use cases, it'd be great to have additional statistic functions like those provided in monetdb. I understand with UDFs it should be possible to approximate most of these, but it would be nice to have a pathway to first-class support or second-class by way of an extension (as with SQLite). Has there been any documented discussion around this? I imagine you've considered it given monetdb.

[Mytherin]

We have indeed discussed this, but I don't believe there has been any documented discussion on that. Indeed all of these are on the agenda, in fact, several have already been implemented. I will hijack this issue to use as the aggregate compatibility with other systems issue.

• [x] median
• [x] quantile
• [ ] corr
• [x] stddev_samp
• [x] stddev_pop
• [x] covar_pop
• [x] covar_samp
• [x] var_samp
• [x] var_pop
• [ ] approx_median
• [ ] approx_quantile
• [ ] approx_count_distinct
• [ ] product
• [ ] bool_and
• [ ] bool_or
• [ ] approx_count_distinct
• [ ] regr_avgx
• [ ] regr_avgy
• [ ] regr_count
• [ ] regr_intercept
• [ ] regr_r2
• [ ] regr_slope
• [ ] regr_sxx
• [ ] regr_sxy
• [ ] regr_syy
• [ ] mode
• [ ] argMin/argMax
• [ ] variance (alias for var_samp)
• [ ] any (alias for first)

It would be good to look at the Clickhouse aggregate set. They support many more aggregates than most systems, and of course Postgres' set of supported aggregates.

[willium]

@Mytherin great to hear! Indeed, parity with Clickhouse's aggregation set would be tremendous.

Do you have an idea of what blockers there are to implementing (and benchmarking) these?

[Mytherin]

For simple (one-pass) algorithms there is not really any blockers, besides actually implementing the algorithm. Exact median and quantile are more difficult; they would require materializing the lists, which is tricky when it comes to using them as grouped aggregates. There is already infrastructure to support materialization in the HT (for e.g. array_agg), so adding the algorithms there would not require any large infrastructural changes, but some more consideration would need to be given there to how we handle these cases.

[willium]

Exact median and quantile are more difficult; they would require materializing the lists, which is tricky when it comes to using them as grouped aggregates

Do we have a sense of what kind of performance is possible for such aggregations with DuckDB?

I've run some very basic tests over the weekend, and it seems quite a bit slower than I expected—but I haven't played much with indexes yet, so there is still ample possible upside.

Additionally, as I believe DuckDB doesn't allow for sub-queries in OFFSET or LIMIT, SQLite approaches seem less amenable.

[Mytherin]

Do we have a sense of what kind of performance is possible for such aggregations with DuckDB?

There are no structural roadblocks for these aggregations to have competitive performance with other columnar systems.

I've run some very basic tests over the weekend, and it seems quite a bit slower than I expected—but I haven't played much with indexes yet, so there is still ample possible upside.

What kind of queries have you run? If they involved ORDER BY statements on large amounts of data, then slow performance is expected right now. Our current order by operator is very slow and mainly aimed at ordering small amounts of data (in the order of 100s of rows). It is likely around 10~100X slower than it should be if properly optimized. This is just something we haven't gotten to yet.

Additionally, as I believe DuckDB doesn't allow for sub-queries in OFFSET or LIMIT, SQLite approaches seem less amenable.

That approach is fine if as a user you want to compute the median or quantile manually in a system that doesn't support it, but it is not efficient. Sorting the entire array of numbers is not required for a quantile or median computation, rather the system should use an algorithm such as quickselect to compute the median/quantiles. This will give much better performance, and is also what other systems use for exact median/quantile computation.

There is also the possibility of adding approximate median/quantile functions, which is sufficient for many use cases and is even faster than exact approaches. I think Clickhouse has both of these, and I think we should have both as well.

[hannesmuehleisen]

I'm implementing quantiles right now

[willium]

That’s so exciting! Thank you Hannes

[Mytherin]

The exact median and quantile are now implemented. I have also expanded the list of aggregates we want to support here.

[willium]

@Mytherin what's the best way to test these as you develop them? I'm not sure if you plan on cutting any intermediate releases.

[willium]

@Mytherin though it's on the fringes of practical utility, an aggregate that implements a binning algorithm (for histograms) would be incredible!