DuckDb Performance: min, max, and median vs quantile

I was playing with some classical statistics in DuckDB and I ran into something I'd like to share. It's about the measures minimum, maximum and median, and quantiles in general.

The short of it is:

1. Descriptive statistical measures minimum, maximum, and median occur rarely on their own: they are typically collected together, along with a number of other core descriptive statistics.
2. These measures are all special cases of quantiles: minimum is the 0th-quantile, maximum the 1st-quantile and median the 0.5th-quantile.
3. DuckDB provides aggregate functions for each of these measures. It was found that queries using min( expr ), max( expr ), and median( expr ) together are quicker than when using equivalent separate calls to quantile( expr, 0), quantile( expr, 1), and quantile( expr, 0.5) respectively.
4. Interestingly, quantile()'s second argument also accepts an array of quantile specifications, requesting multiple quantiles at once to be returned; also as an array. Calling quantile( expr, [0, 1, 0.5] ) was found to be considerably faster and less memory-intensive than multiple single quantile( expr, quantile ) calls for the 0th-, 1st- and 0.5th-quantile. This particular array-version call to quantile() was found to be only slightly slower than calling the min(), max(), and median() trio.
5. Some applications require a more extensive set of quantiles besides just the minimum, maximum and median, such as deciles or even percentiles. In those cases, collecting all quantiles of interest in one quantile()-call should be preferred over multiple calls each retrieving a single quantile.

You can skip directly to the benchmarks if you like; or you can read on from the top for some background info, and to learn about the considerations and ideas that went into this benchmark.

min, max, median, and quantiles

Just a bit of background on quantiles, and their relation to the classic measures min, max, and median.

Imagine a list of values, and sorting them in ascending order. (We'll assume it's already clear how the values can be compared to each other to determine their position in the sorted list.) Values may or may not be unique: after sorting, duplicate values simply appear adjacent to each other. Once this is done:

• The minimum is the first value of the sorted list.
• The maximum would be the last value of the sorted list.
• The median is the value found halfway the sorted list.

To get from here to the quantiles: imagine taking all list positions, and dividing each by the length of the list. (Here it's assumed list positions start counting from 1.) This yields the fraction of the number of values up to that position in the list.

Now, in essence, a percentile is one such position in the list, so that one can say:

the <fraction>th-quantile is <value>

Be careful when turning the wording around though:

<value> is the <fraction>th-quantile

Duplicate values span multiple quantiles. If that's the case, you should probably express that fact by specifying the quantile range:

<value> spans the <x>th- to the <y>th-quantiles

Stating some value is the xth-quantile implies there is exactly one quantile for that value, which in turns implies that value is unique. If that's the case, you should probably state that explicitly to remove any doubt.

Note: this is just a practical explanation: a quick refresher of what quantiles are, and how they relate to the classic statistical measures. This is not necessarily how an algorithm might calculate these measures; And, as we are about to see, there are some loose ends too.

Discrete vs Continuous Quantiles, and value-extrapolation

The method illustrated above features quantiles that correspond to concrete positions in the list; each has an actual fractional value. In the jargon, these are known as discrete quantiles.

But in practice, quantiles are often treated as a continuum: one could name any number from 0 to 1, and ask for its quantile value. If the required quantile doesn't match an actual position in the list, then the value corresponding to the smallest actual fraction including the required quantile is selected.

Example:

If there are 3 values with positions 1, 2, 3, and respective fractions 1/3, 2/3, 3/3, then the 0.5thquantile is the value at position 2. Why? No actual quantile corresponds to 0.5: 1/3 is too small and 2/3 is too large. But 2/3 is selected since it's the smallest actual quantile that covers the requested 0.5 proportion of the values.

There are more sophisticated implementations that try to return the "true" quantile value. This requires extrapolation between the value of the actual quantiles that occur in the list (i.e., the discrete quantiles) right before and after the required quantile.

Extrapolation applies in particular to values of numerical types, or of types that can be treated as if they are numerical, such as DATE, TIME, and TIMESTAMP. In these cases, the geometrical mean is used to extrapolate.

While value extrapolation may appear intuitive and harmless, I feel it's actually less so:

• By definition, extrapolation creates values that are not actually observed in the dataset. This in itself does not have to be a problem as long as you're aware of it, but it does add complexity and may lead to paradoxical results.
• Geometrical mean extrapolation may result in values that have a different type than that of the input domain, while the minimum and maximum will always retain the type of the argument. Again, one may work around this but it does introduce some untidiness which may be undesirable.
• Using the geometrical mean to extrapolate between the quantiles right before and after the requested quantile may lead to misleading results. Suppose you have 100 values. Let's say the 50th value is 50, and the 51st value is 51. With a naive geometrical mean the 0.5th quantile would be 50.5. But what if all prior values are all 50 while values 51 through 100 are more evenly distributed? It seems clear to me that if the purpose of extrapolation is to find a more true value, it should take the distribution of values into account, and the 0.5th-percentile should be a lot closer to 50 than 50.5.

However, this need not concern us right now: for several reasons, extrapolation doesn't matter much for how quantiles are used. (Some of the reasons are that for realisticly sized data sets, the difference between the extrapolated value and the discrete value becomes smaller and smaller; another reason is that the descriptive statistics can still provide a good or good-enough description of the dataset as a whole, even if the actual measure values are somewhat incaccurate. There are probably counter-arguments too, but that's not the topic of this article. )

Generalization: min, max, and median as Quantiles

With the rule in place to select the actual quantile value, the definitions of minimum, maximum, and median given earlier can now be generalized to quantiles:

• The 0th-quantile corresponds to the minimum. Of course, there is no actual fraction that corresponds to 0. But the smallest fraction that includes it, corresponds to the first value in the list, i.e. our original definition of the minimum.
• The 1th-quantile corresponds to the maximum, i.e. the last value in the list.
• The median corresponds to the 0.5th-quantile, as 0.5 is halfway between 0 and 1. For median, value extrapolation is often mentioned, probably because the simple definition as "halfway the list" poses an easy-to-spot problem when the list has an even number of values.

Quantiles in DuckDB

All these measures have an implementation in SQL as an aggregate function. And of course, DuckDB provides them too:

• min( expression ) implements minimum.
• max( expression ) implements maximum
• median( expression ) implements median.
• quantile( expression, quantile(s) ) implements quantile.

A few remarks concerning the implementation of these functions in DuckDB:

• While min() and max() are straightforward, median() applies value extrapolation for numeric types and temporal types. This means that the return type of median() may not match the type of its argument.
• The quantile()-function is actually an alias for quantile_disc(): the postfix _disc indicates it implements discrete quantiles. DuckDB also provides quantile_cont(), which implements continuous quantiles.
• While quantile_disc() and quantile_cont() examine the entire set of values, DuckDB also offers a family of approximate aggregate functions, including a few to estimate quantiles. These are approx_quantile() and reservoir_quantile(), which work by examining a sample of the values rather than all values. The idea here is that these functions may be faster to compute, but at the expense of returning an estimate of the quantile, rather than a precisely determined one.

What to use, under what circumstances, and how

Considering there are quite a number of options to potentially achieve the same or similar results, the question naturally arises, which should one use, and under what circumstances?

For now I just want to decide a simple dilemma:

The functions min(), max() and median() are well-known and have intuitive names, which is why I would prefer them. But quantile() is more general, and can achieve similar or even equivalent results, as well as handle other, more fine-grained quantiles. Is there a good reason to prefer one over the other?

So in the remainder of this article, I won't be looking into approximate quantile functions: I won't be measuring whether they are faster, and how much; nor will I be exploring how accurate their estimates are as compared to exact methods.

Also, I'm focusing only on quantile(), that is to say: quantile_disc(). That's because for my particular use case, I'm treating the descriptive statistics as summary of my dataset. For that purpose I prefer the quantile values to be drawn from my dataset rather then extrapolated.

With that said, this article will answer the question: when to use min(), max(), and median() vs quantile().

Calling quantile()

As the function signature suggests, quantile( expression, quantile(s) ) takes two parameters: the expression which provides the values as first argument, and a second argument. The second argument can be a single number between 0 and 1, specifying what quantile to return.

The interesting thing is that the second argument can also accept a list of numbers, each specifying a particular quantile. In this case, all specified quantiles are calculated in one go and the function returns the list of corresponding quantile values.

For statistical applications, this makes a lot of sense! Surely with regard to minimum and maximum: these measures almost always occur as a pair to indicate the entire value range. The median is a natural complement, adding basic but valueable information about the distribution of the data along the range. But many applications (for example in demographics) go even further, and are interested in deciles (quantile increments of 10%) or even percentiles (increments of 1%).

Quantiles must be specified as constants

Regardless of whether you're using quantile() to collect a single quantile, or multiple quantiles at once, the argument that specifies the quantiles must be a constant value. It can not be an expression that depends on a column. This makes sense: considering that quantile() is an aggregate function, the percentile definition should be invariant for the entire statement.

However, the requirement for a constant percentile specification may be inconvenient when its value is also to be used elsewhere. In those cases, one can sometimes store the percentile definition in a DuckDB-variable. As argument, the variable may be referenced using a call to getvariable( 'variablename' ), which is considered a constant value.

Benchmarking quantile()

After all this background, it's time to do some measurements to try and find some answers to my questions. To benchmark the functions, I used one of the NYC taxi trip parquet data files, in this case the "High Volume For-Hire Vehicle Trip Records" for January, 2023. The file is called fhvhv_tripdata_2023-01.parquet and has 24 columns and 18,479,031 (~18 million) rows.

All tests are performed using the DuckDB command line, version 1.5.5 with standard settings, running on my laptop (HP EliteBook 850 G8 with an Intel i7-1185G7 and 32GB RAM, on Windows 11).

There's two different benchmarks:

1. Comparing 'classic' measures min(), max() and median() against quantile() - checking both the single- and multi-quantile mode.
2. Comparing the single quantile vs the multi-quantile version of the quantile() function. This tests the impact of adding more quantiles.

Each query provides real, user and sys timings. For this purpose, the real timings matter most, but the split allows for some interesting observations.

Comparing classic measures against the quantile()

As I explained, my first instinct would be to use min(), max() and median(). Because these are all just specific cases of quantiles, I'm trying to figure out whether there's any reason (not?) to switch to quantile() instead. Because these classical statistics are often collected together, and considering that quantile() can collect multiple quantiles in one go, both single- or multi-quantile versions of quantile() should be compared.

This benchmark tests one column at a time; the idea behind that is that the data type and the number of NULL-values in a column may reveal different aspects of the different aggregation functions.

A graph of the results is shown below:


The column name is on the vertical axis, and the query runtimes are on the horizontal axis. For each column, there are 3 series: green, blue and orange; for each color there are three shades: darkest (user), lighter (real) and lightest (sys).

1. The green groups are the classic aggregates min(), max() and median(). For each column, there is one such group. So in this case the query looks like:

   SELECT min( <column> )
   , max( <column> )
   , median( <column> )
   FROM read_parquet( 'fhvhv_tripdata_2023-01.parquet' );
   

2. The blue groups are the multi-quantile() calls, using [0, 1, 0.5] as quantiles specification, equivalent to the classic aggregates min(), max() and median(). So in this case the query looks like:

   SELECT quantile( <column>, [ 0, 1, 0.50 ] )
   FROM read_parquet( 'fhvhv_tripdata_2023-01.parquet' );
   

3. The orange groups are the single-quantile() calls, using 3 individual quantile() calls passing 0, 1 and 0.5 for the quantile argument. So in this case, the query looks like:

   SELECT quantile( <column>, 0 )
   ,      quantile( <column>, 1 )
   ,      quantile( <column>, 0.5 )
   FROM read_parquet( 'fhvhv_tripdata_2023-01.parquet' );
       

Observation #1

Classic statistics are fastest, but only slighly so as compared to a multi-quantile()

• For each column, the green group, calling the classical statistics min(), max() and median() is the fastest. (Avg: 0.75seconds; Stdev: 0.16)
• The blue group, calling the multi-quantile variant of quantile() is slightly slower than the green group. (Avg: 0.78seconds; Stdev: 0.20) The difference is consistent, but really quite small - on average, about 5% slower compared to the green group.
• The orange group, with multiple calls to the single-quantile variant of quantile(), is substantially slower than the blue and green groups (Avg: 1.52; Stdev: 0.43). On average they last twice as long as the classic statistics (50% slower).

In general we can conclude that if you only need min(), max() and median(), you're probably best off sticking to those functions. However, if you for some reason would want to use quantile(), performance will probably be acceptably close, provided you use the multi-quantile variant. It's also clear that the single-quantile variant of quantile() really incurs significant negative impact on performance, and this should probably be avoided.

Observation #2

The column data type and distinct value-count really appears to have a discernible effect, which is a little different for the classical statistics as compared to quantile():

• For the VARCHAR columns (hvfhs_license_num , originating_base_nu, dispatching_base_num, shared_match_flag, wav_request_flag, shared_request_flag, access_a_ride_flag, and wav_match_flag), the user-timing for the classical statistics appears to be a bit lower or the same as the real-timing. Both types of quantile() calls tend to have a user timing that is often a bit higher than the real-timing.
• For the TIMESTAMP-columns (request_datetime, on_scene_datetime, pickup_datetime and dropoff_datetime), as well as for the BIGINT columns (PULocationID and DOLocationID), the user timing is typically somewhat lower than the real timing. This applies to both the classical statistics as well as the quantile() calls. The BIGINT column trip_time is a bit of a mystery in this regard, as its user-timing is higher than the real timing.
• For the DOUBLE-columns (trip_miles, base_passenger_fare, tolls, bcf, sales_tax, congestion_surcharge, airport_fee, tips, and driver_pay), user time consistently exceeds the real time somewhat.

Even though the column type appears to have some effect on the performance, it is not clear whether and how this could be used to an advantage. Also, the differences are quite slight, and do not appear to affect the main observation. Perhaps more significant difference can be detected with either larger data sets or with other data types or column value distributions.

Observation #3

For the classic statistics and the multi-quantile version of quantile(), sys measurements appear to be inconsequential: they are consistently low compared to the real and user measurments (green: 0.12; blue: 0.11), and their averages are virtually the same. I suspect that for these groups, the sys time measurement mostly has to do with time spent reading the parquet data which needs to happen anyway, regardless of what functions are tested. But for the single quantile calls to quantile() the sys measurements are consistently higher (Avg: 0.26), and not only in absolute sense: the share of the sys measurement in proportion to the real measurements is also noticeably higher: 0.17 (green: 0.16, blue: 0.14). To be sure, this may be a small increase which does not have an immediate practical consequence. But it does show that more quantile calls require more system calls, which I suspect come down to memory allocation.

More info on that in the next benchmark.

Comparing single- vs multi- quantile() variants

The idea behind this benchmark is to compare the single- and multi- variants of the quantile() function to see which one you should prefer. The results are shown in the chart below:


The query runtimes are on the vertical axis, and the number of quantiles on the horizontal axis.

For the quantiles, a set of 11 values 0.00, 0.01, 0.05, 0.10, 0.25, 0.50, 0.75, 0.90, 0.95, 0.99 and 1.00 is tested. For convenience these are stored in a DuckDB variable:

SET VARIABLE quantiles = [0.00, 0.01, 0.05, 0.10, 0.25, 0.50, 0.75, 0.90, 0.95, 0.99, 1.00];

There are 2 series: blue and orange, again in three shades (user: darkest; real: lighter; sys: lightest).

1. Again, the blue groups are the multi-quantile quantile() calls. The function is applied to all columns using a COLUMNS( * ) expression. So in this case the query looks like:

   SELECT quantile( COLUMNS( * ), getvariable('quantiles')[1:<iteration>] )
   FROM read_parquet( 'fhvhv_tripdata_2023-01.parquet' );
   

   The <iteration> is varied, starting with 1, and incremented to 2, 3, and so on, all the way up to 11, requesting a new additional quantile for each iteration.
2. The orange groups again are the single-quantile quantile() calls. Like for the blue series, the call is applied on all columns using a COLUMNS( * ) expression. The difference is that here, for each iteration, an additional call, including a COLUMNS( * ) expression is required.
   
   So, for the 1st iteration the query looks like:

   SELECT quantile( COLUMNS( * ), getvariable('quantiles')[1] )
   FROM read_parquet( 'fhvhv_tripdata_2023-01.parquet' );
   

   For the 2nd, it becomes

   SELECT quantile( COLUMNS( * ), getvariable('quantiles')[1] )
   ,      quantile( COLUMNS( * ), getvariable('quantiles')[2] )
   FROM read_parquet( 'fhvhv_tripdata_2023-01.parquet' );
   

   ...And so on.
   
   One might guess this should go up all the way up to 11 too, but alas: the series stops at 7. Further iterations resulted in an out of memory error, so the benchmark could not be completed. That said, the iterations that did run already provide ample information!

Observation #1

The blue group - the multi-quantile calls - demonstrate moderate and predictable runtime increases as more quantiles are requested. Each iteration is a few percents slower than the previous one, but considering the fact that each iteration also collects another quantile, that seems perfectly acceptable.

The orange group with the single-quantile calls fares quite differently! Here, each next iteration takes about twice the time of the previous iteration. As a result, it becomes unacceptably slow very quickly, and even then runs into an out of memory error after iteration 7.


Perhaps the slowdown for each iteration is all down to time required for memory allocation, or perhaps there is some other reason - this cannot be concluded from this test. But we can definitely conclude that the multi-quantile call should be preferred whenever collecting more than quantile at once.

In conclusion

I hope you enjoyed this post! I'm happy I could just resolve some questions from my end. I think the takeaways are clear:

• If you only need min(), max() and median(), you're fine! You don't need to switch to quantile() for performance reasons. That said, it also doesn't hurt, provided you use the multi-quantile() version of quantile().
• If you need to collect multiple quantiles beyond min(), max() and median(), you should probably be using quantile( expr, [...quantiles...] ).
• If you're using single quantile quantile() calls, you're either doing something very special, or you're doing something wrong. At any rate, beware of out of memory errors, and investigate whether you can bunch up several single quantile calls into one multi-quantile call - it will save memory and probably increase performance, potentially a lot!

If you found this interesting, you might want to investigate some of the topics that were mentioned but not explored any further, such as:

• Approximate aggregate functions, like approx_quantile() and reservoir_quantile().
• Using quantile_cont() instead of quantile_disc(), especially if you require value extrapolation.
• The quantile_cont() function also supports array syntax for specifying multiple quantiles. It's definiteley worth comparing that to both its single quantile version, as well as to quantile_disc(). They appear to have quite different implementations, going by their type signatures. Therefore, there may be interesting and perhaps unexpected differences in performance.

Feel free to leave some feedback - I read and respond to your comments.