Frequency approximation (count-min sketch)

[davidkohn88]

Discussion for #6 with original issue listed below:

What's the functionality you would like to add

Approximate counts for the various values in a dataset, such as Count-Min Sketch.

How would the function be used

SELECT approx_frequency(value, 'ERROR') FROM data;
approx_frequency
-----------------
              42

CREATE MATERIALIZED VIEW distinct_per_hour
WITH (timescaledb.continuous) AS
SELECT time_bucket(INTERVAL '1 hour', time) AS bucket,
    approx_frequencies(value),
FROM data
GROUP BY bucket;

SELECT approx_frequency(approx_frequencies, 'IDLE') FROM distinct_per_hour LIMIT 4;
         bucket         | approx_frequency 
------------------------+------------------
   2020-01-03 01:00:00  |               10
   2020-01-03 02:00:00  |                8
   2020-01-03 03:00:00  |                8
   2020-01-03 04:00:00  |               11

Why should this feature be added?

Mainly for continuous aggregates and other circumstances where you want to chose which elements to analyze after aggregation.

[davidkohn88]

I like this functionality a lot and I can see a lot of cases where this would be useful where you're trying to get reasonable approximations of how often given values occur in a time period. I'm not sure how useful it is compared to just grouping by the other value though...is it much more space efficient in certain distributions? Can you also derive the cardinality approximation like #3 ?