[Feature request] Expose HyperLogLog accumulate/merge/estimate functions as SQL functions

(I hope this is the right channel to make feature requests - I could not find any guidance on this; sorry if it is not!)

I know DuckDB already implements an approximate count of distinct items via the approx_count_distinct() function. It would be great if these could be complemented with functions that allow working directly with underlying HLL data structures, similar to how it is implemented in Google's BigQuery and Snowflake. They are very useful when one wants to store pre-computed distinct counts at a more granular level but may need to get count estimates after an additional re-aggregation.

I am not familiar enough with the Snowflake/BQ vs. DuckDB implementation compatibility, but the ability to use HLL structures exported from Snowflake/BQ in DuckDB would be a cherry on top.

Does this work for you? #2998

We have not documented this properly.

Thanks - it may just do the trick based on what I can see described. Let me have a look over the next few days and report back if this works with HLL. Appreciate a quick reply!

@lnkuiper

@lnkuiper - unfortunately, I had no luck with it. A basic SELECT APPROX_COUNT_DISTINCT(column) EXPORT_STATE FROM test; fails with error Binder Error: Cannot use EXPORT_STATE on aggregate functions with custom destructors.

Also, while trying to reproduce steps using simple sum() in the linked #2998 issue, I noticed a few issues that would make it difficult to use COMBINE/FINALIZE/EXPORT_STATE as-is even if the above worked. TLDR;:
1 . EXPORT_STATE/AGGREGATE_STATE type can be converted to BLOB but not the other way around, and attempting to view a column of AGGREGATE_STATE crashes duckdb;
2. COMBINE is currently not supported as an aggregation function in LIST_AGGREGATE, limiting its usefulness when aggregation is needed across rows.

Happy to keep on testing if there's anything obvious I missed to make it work!

Test data:

CREATE TABLE test (id_var VARCHAR, value double); 
INSERT INTO test VALUES ('a', 42);
INSERT INTO test VALUES ('a', 12);
INSERT INTO test VALUES ('b', 42);

Any attempt to query the aggregate state itself will crash duckdb. For example:

Creating a table that stores the "interim" results works as expected,
CREATE TABLE partial_sums AS (select id_var, SUM(value) EXPORT_STATE as state FROM test GROUP BY 1);
One can use the states to compute results, e.g this works:
SELECT id_var, FINALIZE(state) FROM partial_sums;
It is possible to "see" the state by converting it to BLOB:
SELECT id_var, state::BLOB FROM partial_sums;
However, I don't think there's a way to convert it back to the state from BLOB representation (at least I could not find the type to cast to - it's not AGGREGATE_STATE).
Any attempt to query the column storing the export state (e.g. select id_var, state FROM partial_sums) will crash duckdb with error terminate called after throwing an instance of 'duckdb::TypeMismatchException' what(): Mismatch Type Error: Type AGGREGATE_STATE<sum(DOUBLE)::DOUBLE> does not match with VARCHAR. Cannot cast AGGREGATE_STATE to anything but BLOB.
Having said that, it is possible to persist a database with a table where a column is of EXPORT_STATE type and afterward reopen it.

COMBINE currently works across columns, whereas typical HLL use cases are to-reaggregate among rows (to obtain distinct counts across previously aggregated groups). List aggregation functions do not seem to work in this case, e.g.
select list_aggregate(list(state), 'COMBINE')::BLOB FROM partial_sums;
fails with Error: Catalog Error: COMBINE is not an aggregate function

Thanks for the detailed report!

Aggregate states are binary format, so casting them to blob is possible, but reading them will not make much sense (it should, of course, not crash DuckDB! Thanks for finding this). We also cannot export states for every aggregate function (yet), because serializing aggregate states is complicated for specific aggregate functions (although it should be possible for HLL).

Aggregate states can be stored in tables, for example, if you have a big table test, and aggregate over it once, and keep the aggregate state in a table called test_agg_states, then you can append rows to test, and compute the full aggregates over test by using the cached aggregate state + only the appended rows.

COMBINE does not work for the list_aggregate function because list_aggregate is not an aggregate function, but a scalar function. For example, if you have a table lists with column my_list INT[], then you can do:

SELECT list_aggregate(my_list, 'sum') from lists;

Which returns the sum of the contents of every list. There is one resulting sum for each input list, hence why it is a scalar function, not an aggregate function.

Re-aggregating across rows is possible, if I understand your question correctly:

-- create table with test data
create table test as select range % 4 grp, range val from range(100);
-- aggregate and export state per group
create table test_agg as select grp, sum(val) export_state state from test group by grp;
-- demonstrating of what's in the test_agg table
select grp, finalize(state) from test_agg;
┌───────┬─────────────────┐
│  grp  │ finalize(state) │
│ int64 │     int128      │
├───────┼─────────────────┤
│     0 │            1200 │
│     1 │            1225 │
│     2 │            1250 │
│     3 │            1275 │
└───────┴─────────────────┘
-- putting it all together
with re_agg as (
  -- re-aggregate over the test table
  select grp, sum(val) export_state state from test group by grp
), joined as (
  -- join with previous exported grouped aggregate states
  select test_agg.grp, test_agg.state as state1, re_agg.state as state2
  from test_agg, re_agg
  where test_agg.grp = re_agg.grp
) -- finally, combine the grouped aggregate states
select grp, finalize(combine(state1, state2)) as total_sum from joined;
┌───────┬───────────┐
│  grp  │ total_sum │
│ int64 │  int128   │
├───────┼───────────┤
│     0 │      2400 │
│     1 │      2450 │
│     2 │      2500 │
│     3 │      2550 │
└───────┴───────────┘

As expected, we get exactly double the sum. As you can see, you could keep a table with grouped aggregate states, aggregate over new rows, and combine the aggregate states of the new rows with 'cached' grouped aggregate states, avoiding an expensive full re-aggregation.

Does this help?

(sorry for responding slowly)

Thanks, that's helpful. I'm still unclear how I could aggregate across rows that store the state in a more "basic" example, though. E.g getting a grand total from states - is that possible?

-- create table with test data
create table test as select range % 4 grp, range val from range(100);
-- aggregate and export state per group
create table test_agg as select grp, sum(val) export_state state from test group by grp;
-- demonstrating of what's in the test_agg table
select grp, finalize(state) from test_agg;
┌───────┬─────────────────┐
│  grp  │ finalize(state) │
│ int64 │     int128      │
├───────┼─────────────────┤
│     0 │            1200 │
│     1 │            1225 │
│     2 │            1250 │
│     3 │            1275 │
└───────┴─────────────────┘

-- how can I get to an overall total?
select sum(state) from test_agg; -- (this of course does not work)

And, of course, the most important question - how difficult would be to enable state export functionality for the hyperloglog-based counts? (i.e. to have SELECT APPROX_COUNT_DISTINCT(column) EXPORT_STATE FROM test; to work, including support for those states to be combined/finalized)

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 30 days.

This issue was closed because it has been stale for 30 days with no activity.

You can now do this operation with the new datasketches extension.

https://github.com/rustyconover/duckdb-datasketches

Internal duckdb#5383: Range Join Sorting

Internal duckdb#5383: IEJoin Sorting

Internal duckdb#5383: Range Join Pinning

Internal #5383: Range Join Sorting (#19174)

vendor: Update vendored sources to duckdb/duckdb@3ba8cc3

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Repository navigation

[Feature request] Expose HyperLogLog accumulate/merge/estimate functions as SQL functions #5383

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Sunbelt Computer Software

PL/B Language Development and Support

[Feature request] Expose HyperLogLog accumulate/merge/estimate functions as SQL functions #5383

Description

Activity

lnkuiper commented on Nov 17, 2022

kamicollo commented on Nov 18, 2022

kamicollo commented on Nov 27, 2022

lnkuiper commented on Nov 28, 2022

kamicollo commented on Dec 5, 2022

github-actions commented on Jul 29, 2023

github-actions commented on Aug 28, 2023

rustyconover commented on Dec 31, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions