MFV (Most Frequent Values)

Contents

• Syntax
• Examples
• Literature
• Related Topics

Warning

This MADlib method is still in early stage development. There may be some issues that will be addressed in a future version. Interface and implementation is subject to change.

MFVSketch: Most Frequent Values variant of CountMin sketch, implemented as a UDA.

Produces an n-bucket histogram for a column where each bucket counts one of the most frequent values in the column. The output is an array of doubles {value, count} in descending order of frequency; counts are approximated via CountMin sketches. Ties are handled arbitrarily.

mfvsketch_top_histogram( col_name,
                         n
                       )

The MFV frequent-value UDA comes in two different versions:

• a faithful implementation that preserves the approximation guarantees of Cormode/Muthukrishnan,
• and a "quick and dirty" version that can do parallel aggregation in Greenplum at the expense of missing some of the most frequent values.

In PostgreSQL the two UDAs are identical. In Greenplum, the quick version should produce good results unless the number of values requested is very small, or the distribution is very flat.

Examples

1. Generate some data.

   CREATE TABLE data(class INT, a1 INT);
   INSERT INTO data SELECT 1,1 FROM generate_series(1,10000);
   INSERT INTO data SELECT 1,2 FROM generate_series(1,15000);
   INSERT INTO data SELECT 1,3 FROM generate_series(1,10000);
   INSERT INTO data SELECT 2,5 FROM generate_series(1,1000);
   INSERT INTO data SELECT 2,6 FROM generate_series(1,1000);
   

2. Produce a histogram of 5 bins and return the most frequent value and associated count in each bin.

   SELECT mfvsketch_top_histogram( a1,
                                   5
                                 )
   FROM data;
   

   Result:

                   mfvsketch_top_histogram
    -------------------------------------------------------------
   [0:4][0:1]={{2,15000},{1,10000},{3,10000},{5,1000},{6,1000}}
   (1 row)
   

Literature

This method is not usually called an MFV sketch in the literature; it is a natural extension of the CountMin sketch.

Related Topics

File sketch.sql_in documenting the SQL functions.

Module CountMin (Cormode-Muthukrishnan).