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.

Year-to-Date on Synapse Analytics 5: Using Window Functions

For one of our Just-BI customers we implemented a Year-to-Date calculation in a Azure Synapse Backend. We encountered a couple of approaches and in this series I'd like to share some sample code, and discuss some of the merits and benefits of each approach.

TL;DR: A Year-to-Date solution based on a SUM() window function is simple to code and maintain as well as efficient to execute. This as compared to a number of alternative implementations, namely a self-JOIN (combined with a GROUP BY), a subquery, and a UNION (also combined with a GROUP BY).

Note: this is the 5th post in a series.

• For sample data and setup, please see the 1st post in this series.
• For a solution based on a self-JOIN and GROUP BY, please find the 2nd post in this series.
• For a solution based on a subquery, please find the 3rd post in this series.
• For a solution based on a UNION, please find the 4th post in this series.

(While our use case deals with Azure Synapse, most of the code will be directly compatible with other SQL Engines and RDBMS-es.)

Using window functions

Nowadays, many SQL engines and virtually all major RDBMSes support window functions (sometimes called analytic functions). A window function looks like a classic aggregate function. In some respects it also behaves like one, but at the same time there are essential differences.

Aggregate functions

Consider the following example:

select sum(SalesAmount) as SumOfSalesAmount
,      count(*)         as RowCount
from   SalesYearMonth

The example uses two aggregate functions, SUM() and COUNT(). It returns a result like this:

SumOfSalesAmount	RowCount
109,846,381.43	38

Two things are happening here:

• Even though there are multiple rows in the SalesYearMonth table, the result consists of just one row. In other words, a collection of source rows have been aggregated into fewer (in this case, only one) result row.
• The functions have caclculated a value based on some aspect of the individual rows in the source collection. In the case of SUM(SalesAmount), the value of the SalesAmount column of each individual row was added to obtain a total. In the case of COUNT(*), each row was counted, adding up to the total number of rows.

Because the previous example uses aggregate functions, we cannot also select any non-aggregated columns. For example, while SalesYear and SalesMonth are present in the individual underlying rows, we cannot simpy select them, because they do not exist in the result row, which is an aggregate.

Window functions

Now, SUM() and COUNT() also exist as window functions. Consider the following query:

select SalesYear
,      SalesMonth
,      SalesAmount
,      sum(SalesAmount) over() as TotalOfSalesAmount
,      count(*)         over() as RowCount
from   SalesYearMonth

You might notice the last two expressions in the SELECT-list look almost identical to the aggregate functions in the previous example. The difference is that in this query, the function call is followed by an OVER()-clause. Syntactically, this is what distinguishes ordinary aggregate functions from window functions.

Here is its result:

SalesYear	SalesMonth	SalesAmount	TotalOfSalesAmount	RowCount
2011	5	503,805.92	109,846,381.43	38
2011	6	458,910.82	109,846,381.43	38
...more rows...
2014	6	49,005.84	109,846,381.43	38

Note that we now get all the rows from the underlying SalesYearMonth table: no aggregation has ocurred. But the window functions do return a result that is identical to the one we got when using them as aggregate functions, and that for each row of the SalesYearMonth table.

It's as if for each row of the underlying table, the respective aggregate function was called over all rows in the entire table. Conceptually this is quite like the construct we used in the subquery-solution. The following example illustrates this:

select SalesYear
,      SalesMonth
,      SalesAmount
,      (
           select sum(SalesAmount) 
           from   SalesYearMonth
       ) as TotalOfSalesAmount
,      (
           select count(*)
           from   SalesYearMonth
       ) as RowCount
from   SalesYearMonth

The window and the OVER()-clause

Thinking about window functions as a shorthand for a subquery helps to understand how they work and also explains their name: a window function returns the result of an aggregate function on a particular subset of the rows in the query scope. This subset is called the window and it is defined by the OVER()-clause.

The parenthesis after the OVER-keyword can be used to define which rows will be considered as window. When left empty (like in the example above) all rows are considered.

Controlling the window using the PARTITION BY-clause

If you compare the previous example with our prior subquery-solution, you'll notice that here, we do not have a WHERE-clause to tie the subquery to the current row of the outer query. That's why our result is calculated over the entire table, rather than with respect to the current year and preceding months, as in our prior subquery-solution. This is equivalent to the empty parenthesis following the OVER-keyword in the corresponding window-function example.

In the subquery-solution we wrote a WHERE-clause to specify a condition to tie the rows of the subquery to the current row. For window functions, we can control which rows make up the window window by writing a PARTITION BY-clause inside the parenthesis following the OVER-keyword.

The PARTITION BY-clause does not let you specify an arbitrary condition, like we could in a subquery. Instead, the relationship between the current row and rows in the window must be expressed through one or more attributes for which they share a common value. The following example may illustrate this:

select SalesYear
,      SalesMonth
,      SalesAmount
,      sum(SalesAmount) over(partition by SalesYear) as YearTotalOfSalesAmount
from   SalesYearMonth

In the example above, sum(SalesAmount) over(partition by SalesYear) means: calculate the total of SalesAmount over all rows where the value of SalesYear is equal to the value of the SalesYear in the current row.

The equivalent query using subqueries would be:

select OriginalSales.SalesYear
,      OriginalSales.SalesMonth
,      OriginalSales.SalesAmount
,      (
           select sum(YearSales.SalesAmount) 
           from   SalesYearMonth as YearSales
           where  YearSales.SalesYear = OriginalSales.SalesYear
       ) as YearTotalOfSalesAmount
from   SalesYearMonth as OriginalSales

The result is shown below:

SalesYear	SalesMonth	SalesAmount	YearTotalOfSalesAmount
2011	5	503,805.92	12,641,672.21
2011	6	458,910.82	12,641,672.21
...more rows...
2014	6	49,005.84	20,057,928.81

(Note that 12,641,672.21 is the sum of the SalesAmount for SalesYear 2011; 20,057,928.81 is the total for 2014.)

A partition for the preceding months?

It's great that the PARTITION BY-clause allows us to specify a window for relevant year, but it's still too wide: we want the window to contain only the rows from the current year, but only for this month and its preceding months. In the subquery-solution this was easy, as we could write whatever condition we want in the WHERE-clause. So we wrote:

where  SalesYtd.SalesYear   = SalesOriginal.SalesYear
and    SalesYtd.SalesMonth <= SalesOriginal.SalesMonth

Specifying SalesYear in the window functions' PARTITION BY-clause is equivalent to the first part of the subquery's WHERE-clause condition.

It's less clear what our partition expression should look like to select all months preceding the current month. It's not impossible though. For example, we can write an expression to mark whether the current SalesMonth is equal to or less than a specific month. For example:

-- every month up to and including june is 1, all months beyond june is 0
case
    when SalesMonth <= 6 then 1 
    else 0
end

If we can write such an expression, then of course, we can also use it in a PARTITION BY-clause, like so:

sum(SalesAmount) over (
  partition by 
    SalesYear
  , case
      when SalesMonth <= 6 then 1 
      else 0
    end
) 

Let's try and think what this brings us.

Suppose the value for SalesMonth is 6 (june), or less? The CASE expression would return 1, and the window function would take all rows into account for which this is the case. So january, february, march and so on, up to june would all get the total of those six months - that is, the YTD value for june.

On the other hand, if SalesMonth is larger than 6, the CASE expression evaluates to 0. So all months beyond june (that is: july, august, and so on up to december) form a partition as well, and for those months, whatever is the sum over those months would be returned.

Now, it's not really clear what the outcome means in case the month is beyond june. But it doesn't really matter - what is important, is that we now know how to calculate the correct YTD value for a given month. And, what we did for june, we can do for any other month. So, once we have the YTD expressions for each individual month, we can set up yet another CASE-expression to pick the right one according to the current SalesMonth.

Putting all that together, we get:

select SalesYear
,      SalesMonth
,      SalesAmount
,      case SalesMonth
         -- january
         when 1 then SalesAmount
         -- february
         when 2 then
           sum(SalesAmount) over(
             partition by 
               SalesYear
             , case when SalesMonth <= 2 then 1 else 0 end
           ) 
           
         ...more cases for the other months...
           
         -- december
         when 12 then
           sum(SalesAmount) over(
             partition by 
               SalesYear
             , case when SalesMonth <= 12 then 1 else 0 end
           ) 
       end as YtDOfSalesAmount
from   SalesYearMonth

Like with the UNION-solution, we are taking advantage of our knowledge of the calendar, which allows us to create these static expressions. We would not be able to do this in a general case, or where the number of distinct values is very large. But for 12 months, we can manage.

While it's nice to know that this is possible, there is a much, much nicer way to achieve the same effect - the frame specification.

Frame Specification

The frame specification lets you specify a subset of rows within the partition. The way you can specify the frame feels a bit odd (to me at least), as it is specified in terms of the current row's position in the window. Hopefully the following example will make this more clear:

select SalesYear
,      SalesMonth
,      SalesAmount
,      sum(SalesAmount) over(
         partition by SalesYear
         order by SalesMonth
         rows between unbounded preceding
         and current row
       ) as SalesYtd
from   SalesYearMonth

We already discussed the PARTITION BY-clause, all the clause after that are new.

The ORDER BY-clause sorts the rows within the window, in this case by SalesMonth. We need to rows to be ordered because of how the frame specification works: it lets you pick rows by position, relative to the current row. The position of the rows is undetermined unless we sort them explicitly, so if we want to pick rows reliably we need the ORDER BY-clause to guarantee the order.

The frame specification follows the ORDER BY-clause. There are a number of possible options here, but I will only discuss the one in the example. In this case, it almost explains itself: we want to use the current row, and all rows that precede it. Since we ordered by SalesMonth, this means all the rows that chronologically precede it. As this selection applies to the current partition, we will only encounter months here that are within the current year.

So here we have it: a YTD calculation implemented using a window functions. It's about the same amount of code as compared to the subquery solution, but more delcarative, as we do not need to specify the details of a condition. On the other hand, it is also less flexible than a subquery, but in general one should expect the window functions to perform better than the equivalent subquery.

Generalizing the solutions

So far all our examples were based on the SalesYearMonth table, which provides SalesYear and SalesMonth as separate columns. One might wonder what would it would take to apply these various methods to a realistic use case.

For example, it is likely that in a real dataset, the time would be available as a single column of a DATE or DATETIME data type. A single date column potentially affects the YTD calculation in two ways:

• Year: As the YTD is calculated over a period of a year and almost all solutions we described used the SalesYear column explicitly to implement that logic.
• Preceding rows: To calculate the YTD for a specific row, there has to be a clear definition of what rows are in the same year, but which precede it. In our examples we could use the SalesMonth column for that, but this might be a but different in a realistic case.
• Lowest Granularity: The lowest granularity of the SalesMonthYear table is at the month level, and we collected the YTD values at that level. (If we'd want to be precise we'd have to call that year-to-month).

Apart from the time aspect, the definition of the key affects all solutions that generate "extra" rows and require a GROUP BY to re-aggregate to the original granularity.

The Year

The ON-condition of the JOIN-solution and the WHERE-condition of the subquery-solution both rely on a condition that finds other rows in the same year, and the window function-solution uses the year in its PARTITION BY-clause.

It is usually quite simple to extract the year from a date, date/time or timestamp. In Synapse Analytics or MS SQL one can use the DATEPART or YEAR function to do this.

The UNION-solution has no direct dependency on the year.

The preceding rows

The need to find the preceding rows applies to all solutions that use the year to find the rows to apply the YTD calculation on. In our samples, this could all be solved using the SalesMonth column.

Again, it are the JOIN-solution and subquery-solution that used it in their condition, whereas the window function-solution uses it in its ORDER BY-clause.

In this case, the fix is more straighforward then with the year: instead of the month column, these solutions can simply use the date or date/time column directly. No conversion or datepart extraction is required.

Lowest granularity

The granularity is of special concern to the UNION-solution. The solution relies on an exhaustive and static enumeration of all possible future dates within the year. Already at the month level, this already required a lot of manual code.

Below the month, the next level would be day. While it would in theory be possible to extend the solution to that level, it is already bordering the impractible at the month level.

The Key

The key definition affects both the JOIN-solution and the UNION-solution, as that both require a GROUP BY over the key.

Year-to-Date on Synapse Analytics 4: Using UNION and GROUP BY

For one of our Just-BI customers we implemented a Year-to-Date calculation in a Azure Synapse Backend. We encountered a couple of approaches and in this series I'd like to share some sample code, and discuss some of the merits and benefits of each approach.

TL;DR: A Year-to-Date solution based on a SUM() window function is simple to code and maintain as well as efficient to execute. This as compared to a number of alternative implementations, namely a self-JOIN (combined with a GROUP BY), a subquery, and a UNION (also combined with a GROUP BY).

Note: this is the 4th post in a series.

• For sample data and setup, please see the 1st post in this series.
• For a solution based on a self-JOIN and GROUP BY, please find the 2nd post in this series.
• For a solution based on a subquery, please find the 3rd post in this series.

(While our use case deals with Azure Synapse, most of the code will be directly compatible with other SQL Engines and RDBMS-es.)

Using a UNION

We mentioned how the solution with the JOIN relates each row of the main set with a subset of "extra" rows over which the YTD value is calculated by aggregating over the key of the main set using a GROUP BY.

It may not be immediately obvious, but we can also use the SQL UNION (or rather, UNION ALL) operator to generate such a related subset. Just like with the JOIN-solution, this can then be aggregated using GROUP BY. An example will help to explain this:

select      SalesYear
,           SalesMonth
,           sum(SumOfSalesAmount)      as SumOfSalesAmount
,           sum(YtdOfSumOfSalesAmount) as YtdOfSumOfSalesAmount
from (
    select  SalesYear
    ,       SalesMonth
    ,       SumOfSalesAmount
    ,       SumOfSalesAmount           as YtdOfSumOfSalesAmount
    from    SalesYearMonth
    union all
    -- JANUARY
    select  SalesYear
    ,       SalesMonth + 1            -- february
    ,       null
    ,       SumOfSalesAmount
    from    SalesYearMonth
    where   SalesMonth = 1
    union all
    select  SalesYear
    ,       SalesMonth + 2            -- march
    ,       null
    ,       SumOfSalesAmount
    from    SalesYearMonth
    where   SalesMonth = 1
    union all
    
    ... and so on, all for JANUARY ...

    union all
    select  SalesYear
    ,       SalesMonth + 11            -- december
    ,       null
    ,       SumOfSalesAmount
    from    SalesYearMonth
    where   SalesMonth = 1
    union all
    -- FEBRUARY
    select  SalesYear
    ,       SalesMonth + 1            -- march
    ,       null
    ,       SumOfSalesAmount
    from    SalesYearMonth
    where   SalesMonth = 2
    union all
    
    ... and so on, for the rest of FEBRUARY, 
        and then again for MARCH, APRIl, MAY, JUNE, JULY, AUGUST, SEPTEMBER, OCTOBER...   

    -- NOVEMBER
    select  SalesYear
    ,       SalesMonth + 1            -- december
    ,       null
    ,       SumOfSalesAmount
    from    SalesYearMonth
    where   SalesMonth = 11
) Sales
group by    SalesYear
,           SalesMonth

Duplicating metric-data so it contributes to the following months

In the top of the UNION we simply provide the entire resultset from SalesYearMonth, reporting the SumOfSalesAmount-metric as is, but also copying it to YtdSumOfSalesAmount. The other parts of the UNION are used to selectively duplicate the data for the SumOfSalesAmount-metric into the YtdSumOfSalesAmount, so that its data contributes to the YtdSumOfSalesAmount for all following months.

We start by grabbing january's data by applying the condition that demands that the SalesMonth equals 1:

-- JANUARY
select  SalesYear
,       SalesMonth + 1            -- february
,       null
,       SumOfSalesAmount
from    SalesYearMonth
where   SalesMonth = 1
union all
... repeat to duplicate january's data into february, march, and so on all the way up to december...

. This is done for a total of 11 times, each time adding 1, 2, 3 and so on - all the way up to 11 - to the SalesMonth attribute. This ensures january's data, as captured by the condition in the WHERE clause, is reported also in february (SalesMonth + 1), march (SalesMonth + 2), and so on, all the way up to december (SalesMonth + 11).

After the string of UNIONs for january appear more parts to duplicate the data also for february and all following months: -- FEBRUARY select SalesYear , SalesMonth + 1 -- march , null , SumOfSalesAmount from SalesYearMonth where SalesMonth = 02 union all ... repeat to duplicate february's data into march, april, and so on all the way up to december... . Again, february's data is selected by applying the condition

where   SalesMonth = 2

, and this happens now 10 times, again adding a number to the SalesMonth so it is duplicated to march, april, may, all the way up to december - in other words, all months following february.

What we thus did for january and februry is repeated for march, april, and so on for all months up to november. November is the last month we need to do this for: November's data still needs to be copied to december, but as december is the last month, that data only needs to be counted in december itself.

While it may seem wasteful to duplicate all this data, it really is not that different in that respect from the other solutions we've seen so far. It's just that now it's really in your face, because there is a pretty direct correspondence between the SQL code and the data sets that are being handled. The JOIN and subquery solutions hande similar amounts of data, it's just achieved with way less code, and in a far more implicit manner.

Original metric is retained

Note that the original metric also computes correctly, because the parts of the union only duplicate the data to the YTD column. The union parts that duplicate the data to the subsequent months select a NULL for the original metric. So the data for the original metric is never duplicated, and thus retains its normal value.

Drawbacks to the UNION-solution

The main drawback to the UNION-solution is its maintainability. A lot of code is required, far more than for any of the methods we have seen so far. Despite the indiviual patterns are simple (condition to get one month, adding a number to project that data to a future month), it is suprisingly easy to make a little mistake somewhere

We just argued that this solution is not so much different from the JOIN solution, but that remark only pertains to how the calculation is performed. The JOIN-solution generates the data it operates upon dynamically and declaratively; the UNION solution does this statically and explicitly. This is also why it is impossible to generalize ths approach for any arbitrary JOIN: YTD is a special case, because we know exactly how often we should duplicate the data as this is dictated by the cyclical structure of our calendar.

Next installment: Solution 4 - window functions

In the next installment we will present and discuss a solution based on a window functions.

Year-to-Date on Synapse Analytics 2: Using a self-JOIN and GROUP BY

For one of our Just-BI customers we implemented a Year-to-Date calculation in a Azure Synapse Backend. We encountered a couple of approaches and in this series I'd like to share some sample code, and discuss some of the merits and benefits of each approach.

TL;DR: A Year-to-Date solution based on a SUM() window function is simple to code and maintain as well as efficient to execute. This as compared to a number of alternative implementations, namely a self-JOIN (combined with a GROUP BY), a subquery, and a UNION (also combined with a GROUP BY).

Note: this is the 2nd post in a series. For sample data and setup, please see the first post in this series. (While our use case deals with Azure Synapse, most of the code will be directly compatible with other SQL Engines and RDBMS-es.)

Using a self-JOIN

The recipe for the set-oriented approach can be directly translated to SQL:

select      SalesOriginal.SalesYear
,           SalesOriginal.SalesMonth
,           max(SalesOriginal.SalesAmount) as SalesAmount
,           sum(SalesYtd.SalesAmount)      as SalesYtd
from        SalesYearMonth as SalesOriginal
inner join  SalesYearMonth as SalesYtd
on          SalesOriginal.SalesYear  = SalesYtd.SalesYear
and         SalesOriginal.SalesMonth >= SalesYtd.SalesMonth
group by    SalesOriginal.SalesYear
,           SalesOriginal.SalesMonth

The self-JOIN

In our discussion of the set-oriented approach we mentioned combining the rows from the table with each other to produce all different combinations. In the code sample about, the JOIN-clause takes care of that aspect.

As you can see, the SalesYearMonth table appears twice: on the left hand and on the right hand of the JOIN-keyword, but using different aliases: SalesOriginal and SalesYtd. It is a so-called self-join.

Even though both aliases refer to an instance of the same SalesYearMonth base table, each has a very different role. We can think of the one with the SalesOriginal alias as really the SalesYearMonth table itself. The SalesYtd alias refers to an instance of the SalesYearMonth table that, for any given row from SalesOriginal, represents a subset of rows that chronologically precedes the row from SalesOriginal.

The ON-clause that follows controls which combinations should be retained: for each particular row of SalesOriginal we only want to consider rows from SalesYtd from the same year, which is why the first predicate in the ON-clause is:

SalesOriginal.SalesYear  = SalesYtd.SalesYear

Within that year, we only want to consider rows that precede it chronologically, and that explains the second predicate:

SalesOriginal.SalesMonth >= SalesYtd.SalesMonth

GROUP BY and SUM()

It is is important to realize the JOIN is only half of the solution.

While the JOIN takes care of gathering and combining all related rows necessary to compute the YTD value, the actual calculation is done by the SUM() function in the SELECT-list, and the GROUP BY defines which rows should be taken together to be summed.

In summary:

• the JOIN generates new rows by combining rows from its left-hand table with the rows from its right-hand table, bound by the condition in the ON-clause.
• The GROUP BY partitions the rows into subsets having the same combinations of values for SalesYear and SalesMonth.
• The SUM() aggregates the rows in each SalesYear, SalesMonth partition, turning its associated set of rows into one single row, while adding the values of the SalesAmount column together.

Note that the columns in the GROUP BY list are qualified by the SalesOriginal alias - and not SalesYtd. Also note that the GROUP BY columns form the key of the original SalesYearMonth table - together they uniquely identify a single row from the SalesYearMonth table. This is not a coincidence: it expresses precisely that SalesOriginal really has the role of being just itself - the SalesYearMonth table.

What about the other columns?

The GROUP BY affects treatment of the non-key columns as well. In this overly simple example, we had only one other column - OriginalSales.SalesAmount.

(Note that this is different from YtdSales.SalesAmount, which we aggregated using SUM() to calculate the YTD value)

Since OriginalSales.SalesAmount comes from the SalesOriginal instance of the SalesYearMonth table, we can reason that after the GROUP BY on the key columns SalesYear and SalesMonth, there must be exactly one SalesAmount value for each distinct combination of SalesYear and SalesMonth. In other words, SalesAmount is functionally dependent on SalesYear and SalesMonth.

Some SQL engines are smart enough to realize this and will let you refer to any expression that is functionally dependent upon the expressions in the GROUP BY-list in the SELECT-list. Unfortunately, Synapse and MS SQL Server are not among these and if we try we will get an Error:

Msg 8120, Level 16, State 1, Line 11
Column 'Sales.SalesAmount' is invalid in the select list because it is not contained in either an aggregate function or the GROUP BY clause.

The error message suggets we can do two things to solve it:

• either we aggregate by wrapping the SalesOriginal.SalesAmount-expression into some aggregate function
• or we expand the GROUP BY-list and add the SalesOriginal.SalesAmount-expression there.

To me, neither feels quite right.

SalesAmount is clearly intended as a measure, and it feels weird to treat them the same as the attributes SalesYear and SalesMonth. So adding it to the GROUP BY-list feels like the wrong choice. Besides, it also makes the code less maintainable, as each such column will now appear twice: once in the SELECT-list, where we need it no matter what, and once again in the GROUP BY-list, just to satisfy the SQL engine.

So, if we don't want to put it in the GROUP BY-list, we are going to need to wrap it in an aggregate function. We just mentioned that SalesAmount is a measure and therefore that does not sound unreasonable. However, we have to be careful which one we choose.

One would normally use SalesAmount as an additive measure and be able to use SUM() for that. But here, in this context, SUM() is definitily the wrong choice!

All we want to do is to "get" back" whatever value we had for SalesAmount, in other words, unaffected by the whole routine of join-and-then-aggregate, which we did only to calculate the YTD value. The "extra" rows generated by the JOIN are only needed to do the YTD calculation and should not affect any of the other measures. Using SUM() would simply add the SalesAmount just as many times as there are preceding rows in the current year, which simply does not have any meaningful application.

What we want instead is to report back the original SalesAmount for any given SalesYear, SalesMonth combination. We just reasoned that there will be just one distinct SalesOriginal.SalesAmount value for any combination of values in SalesOriginal.SalesYear, SalesOriginal.SalesMonth, and it would be great if we had an aggregate function that would simply pick the SalesOriginal.SalesAmount value from any of those rows. To the best of my knowledge, no such aggregate function exists in MS SQL Server or Synapse Analytics.

We can use MAX() or MIN(), or even AVG(). While this would all work and deliver the intended result, it still feels wrong as it seems wasteful to ask the SQL engine to do some calculation on a set of values while it could pick just any value.

Next installment: Solution 2 - using a subquery

In the next installment we will present and discuss a solution based on a subquery.

MySQL aggregate UDF Performance

At the MySQL User's conference 2008 I did a tutorial on MySQL User-defined functions. At the same conference, Brian Miezejewski and Mark Atwood did a talk on aggregate UDFs.

In relation their upcoming talk, Mark wrote a blog post reporting that MySQL Aggregate UDFs are three times slower than equivalent native functions:

I just proved to myself via testing and benchmarking that user defined aggregate functions are about three times slower than the call interface to the built-in functions.

Later on he posted an update, explaining that it looks like this result is probably "a MacOS thing".

It turns out to be a MacOS thing. On Linux, the performance penalty is less than 10%. Further research will surely be done.

I just tested it on Linux and Windows. For a simple aggregate UDF that is equivalent to the built-in COUNT() function, I found that the UDF is about 5% slower than the built-in function. Personally I think that's not too bad.

If you are interested in trying this on your own system, download these instructions. Would be cool if you could leave a comment here of your results, TIA

Calculating the Nth percentile in MySQL

Yesterday, I was on the freenode ##pentaho irc channel when Andres Chaves asked me how to calculate the N^th percentile in MySQL. He saw a solution somewhere using subqueries, but wasn't too happy about it.

A while ago I wrote about calulating the median in MySQL, and it turns out the N^th percentile can be calculated using a similar, single-pass approach, not relying on subqueries, UDFs, or user-defined variables.

The percentile....

So, what is a percentile exactly? Here's what the wikipedia says:

A percentile is the value of a variable below which a certain percent of observations fall. So the 20th percentile is the value (or score) below which 20 percent of the observations may be found.

....and the median

The wikipedia continues and hints at the relationship between the N^th percentile and the median:

The 25th percentile is also known as the first quartile; the 50^th percentile as the median.

Sidenote: as I understand it, this latter remark concerning the median is not entirely correct. The median is "the middle value": the number of observations with a higher value is equal to the number of observations that has a lower value. For a series with an even number of observations, say {1,2,3,4}, there isn't one middle value, there are two, in this case: 2 and 3. Typically, the median is computed by taking the arithmic mean of the two middle values, which would be (2+3) / 2 = 2.5 in this particular case. But for this example, the 50th percentile would be 3 and not 2.5. However, in most practical cases the values are fairly evenly distributed and sufficiently large, which means the difference between the median and 50th percentile will be small or absent.

However, the median and percentile problems are quite similar: in both cases, a value is picked or computed that is higher than the value found in a particular portion of the total number of observations. For the median, the requirement is that that particular portion is equal to the number of observations that exceeds it; for the N^th percentile the requirement is that that portion constitutes N percent of the total number of observations.

The Solution

In the following example, we calculate the 90^th percentile of film lengths:

SELECT  SUBSTRING_INDEX(
            SUBSTRING_INDEX(
                GROUP_CONCAT(                 -- 1) make a sorted list of values
                    f.length
                    ORDER BY f.length
                    SEPARATOR ','
                )
            ,   ','                           -- 2) cut at the comma
            ,   90/100 * COUNT(*) + 1         --    at the position beyond the 90% portion
            )
        ,   ','                               -- 3) cut at the comma
        ,   -1                                --    right after the desired list entry
        )                 AS `90th Percentile`
FROM    sakila.film AS f

Here, the literal 90 represents which percentile we want, that is, "the 90^th percentile".

(If you like, you can leave out the SEPARATOR ',' bit, as the default separator is a comma anyway. I just wanted to have a clear indication for the source of the ',' arguments in the SUBSTRING_INDEX() calls)

Explanation

The median and N^th percentile problem can be solved using a similar apporoach: first, we use the string aggregate function GROUP_CONCAT() to create an ordered list of values. Then we use the substring variation SUBSTRING_INDEX() to find and excise a list entry at a particular desired position.

The differences between the solutions for the median and the N^th is mainly in which entry we have to pick from the list. (See my prior article for the full story on median). For the N^th percentile, we first calculate the desired portion of the total number of observations. Because N is defined as a percentage, we divide by 100 to get the actual fraction of the total number of observations:

    N / 100

Then, we multiply by the total number of observations to find the number of observations that make up the actual portion of observations within the specified percentile:

    N / 100 * COUNT(*)

Because we want to find the observation for which the specified portion has a lower value, we need to look at the next entry instead of the last entry within the portion, so we add 1:

    N / 100 * COUNT(*) + 1

Caveats

There are a number of things to look out for:

Percentile value not unique

When we calculate the 90^th percentile of the film lengths, we get 173:

+-----------------+
| 90th Percentile |
+-----------------+
| 173             |
+-----------------+

If we check the result by counting the portion of films with a length lower than 173 we see:

mysql> SELECT 100 * COUNT(IF(f.length < 173, 1, NULL))/COUNT(*) `Percentage`
    -> FROM   film AS f;
+------------+
| Percentage |
+------------+
|    89.4212 |
+------------+

The reason that we do not get 90% is that there are multiple occurrences of films with length equal to 173:

mysql> SELECT title FROM film WHERE length = 173;
+----------------------+
| title                |
+----------------------+
| BALLROOM MOCKINGBIRD |
| CONQUERER NUTS       |
| FIRE WOLVES          |
| GLADIATOR WESTWARD   |
| PIZZA JUMANJI        |
| TALENTED HOMICIDE    |
| VELVET TERMINATOR    |
+----------------------+
7 rows in set (0.01 sec)

So, even though we may have picked the entry at the right position, this may still be a value within the specified portion instead of beyond. The definitions I found for the N^th percentile do not stipulate any mechanism to deal with this kind of ambiguity, whereas for the median, the correct value is always found by averaging the left and right median if necessary.

What about NULL

The second caveat are NULL values. Currently this method does not work when the column for which you want to caculate percentile values is nullable. It is possible to work around this though. If you can exclude the rows with the NULL value entirely, you can simply add a WHERE clause. This is a good idea also because it will cull the number of rows to process.

It may not be acceptable to throw away the rows with NULL values, for example if there is another expression in your SELECT list that needs to do something with all rows. You can then still work around it, with some extra hassle. It would involve tweaking the GROUP_CONCAT to ignore NULL values. This could be done like this:

GROUP_CONCAT(
    IF(<column> IS NULL
    ,   ''
    , <column>) 
    ORDER BY <column>
    SEPARATOR ','
)

This will ensure that GROUP_CONCAT() does not also return NULL when a NULL value is present in the specified column. If there are NULL values, these will end up as a list of comma's in the head of the result:

,,,,<non-null-value1>,...,<non-null-valueN> -- 4 NULL values

Assuming we know the number of NULL's (and we do) we can clean up our list easily with just SUBSTRING():

SUBSTRING(
    GROUP_CONCAT(
        IF(<column> IS NULL
        ,   ''
        , <column>) 
        ORDER BY <column>
        SEPARATOR ','
    )
,   SUM(IF(<column> IS NULL, 1, 0)) + 1
)

Because we are ignoring the NULL values in our list, we must likewise ignore them in our calculation of the portion of rows. So, instead if COUNT(*) we should use COUNT(<column>) in order to not count the NULL values.

group_concat_max_len

When using GROUP_CONCAT(), an issue that should always be on your radar is the maximum length of the GROUP_CONCAT() result. If the result value exceeds the maximum length, the GROUP_CONCAT() result will be truncated, and a warning will be issued:

1 row in set, 1 warning (0.00 sec)

mysql> show warnings;
+---------+------+--------------------------------------+
| Level   | Code | Message                              |
+---------+------+--------------------------------------+
| Warning | 1260 | 1 line(s) were cut by GROUP_CONCAT() |
+---------+------+--------------------------------------+

It is really important to be aware of any warnings, as a truncation of the GROUP_CONCAT() result messes up the entire calculation.

The maximum length of the GROUP_CONCAT() result is controlled through the group_concat_max_len system variable.

It can be set thus:

SET @@group_concat_max_len := <num-bytes>

The maximum practical value is the maximum packet size, which is available as the max_allowed_packet system variable. This means you can write:

SET @@group_concat_max_len := @@max_allowed_packet;

and you will never be bothered by this problem again. The GROUP_CONCAT() result can still be too large though (namely, larger than the maximum packet size) but in that case you will get a proper error instead of a truncated result.

You should realize that setting the group_concat_max_len to a high value may lead to memory problems, as each GROUP_CONCAT() invocation may individually reserve the specified amount of memory to deal with its result.

Finally...

I will maintain this percentile calculation as a snippet on the MySQL Forge site. Please go there to find the latest version.

Now, finally, I have a question for you. When I wrote about the median calculation, I mentioned that I thought it was an original method, and I asked whether someone could deny that claim. I did not get any reaction, so I'd like to repeat my question: Do you know of any book or text or blog that describes this technique? If so, let me know so I can provide proper accreditation.

TIA, Roland.

UDFs at the MySQL User's conference

The MySQL User's conference will be held in less than a month from now!!!

This year there is quite a good number of sessions on adding your own functions and procedures, such as:

• Advanced Stored Procedures


• A Tour of External Language Stored Procedures for MySQL


• Code Generators for MySQL Plugins and User Defined Functions (UDFs)


• Extending MySQL


• Using User-defined Functions and Aggregates to Speed Up Your Data Warehouse Processing


• Writing MySQL user-defined functions

I will be doing the 3 hour tutorial on writing user-defined functions, and I am currently adding the last few final touches to my slides.

My tutorial will be very much a hands-on experience. The ambition is to allow people with some programming skills in either C/C++, PHP or Java to leave the room with a bunch of UDFs they created themselves during one of labs. With that and the supporting materials (slides and a handout with detailed instructions) the attendees will be able to write UDFs themselves, and have the knowledge that allows them to make a sensible decision when they have to choose between stored SQL functions, UDFs or raw expressions built of built-in functions.

Allow me to tell you a bit about UDFs - you might decide you want to take my tutorial ;)

User-defined functions

User-defined functions or UDFs are often confused with Stored SQL functions but unrightly so. Other than the fact that stored functions and user-defined functions can be created by the user (as opposed to hard-wired, built-in functions), they have little in common. If you want to know exactly what the difference is and what the strengths and weaknesses are of either feature, my tutorial is for you.

Features

For now I don't want unveil too much but I think that it might be good to point out a number of key advantages of using UDF's over stored SQL functions:

• Flexible argumentlists - UDFs allow a flexible number of dynamically typed arguments, and it is possible to identify arguments by name (rather than position).


• The ability to leverage the functionality from external libraries - UDFs can be linked to existing libraries in order to expose their functionality to SQL statements


• Aggregate functions - UDFs can compute a value for a collection of rows just like the built-in functions COUNT and GROUP_CONCAT

Neither of these features is available to stored SQL functions, and a generic workaround is simply impossible or far from trivial. So - UDFs might be for you if you need one of these things.

Performance

Another reason to use UDFs might be performance. UDFs are much, much better than stored SQL functions when it comes to computation. To prove this fact, I'd like to share a number of benchmarks I did.

For the benchmarks I use a stored procedure like this:

create procedure sp_<SOME-NAME>_benchmark(p_num int unsigned)
begin
    declare v_num int unsigned default 0;
    declare v_return <SOME-DATA-TYPE>;
    declare v_begin int unsigned default unix_timestamp();    
    while v_num < p_num do
        set v_return := <SOME-EXPRESSION>;
        set v_num := v_num + 1;
    end while;
    call sp_store_function_benchmark(
        '<SOME-NAME>'
    ,   p_num
    ,   unix_timestamp() - v_begin
    );
end;

As you can see, the procedure repeats the evaluation of <SOME-EXPRESSION>, depending on the specified number of iterations passed to the parameter p_num. Depending on the benchmark, an expression is plugged in place of <SOME-EXPRESSION>. The variable v_return is used to capture the evaluation result, and a suitable data type is used in place of <SOME-DATA-TYPE>. Before running the loop, the time is recorded. After the loop, the elapsed time, the number of repetitions and the benchmark name are stored in a table for later analysis. This allows me to test a series of increasing repetitions of the same expression.

I also use a sp_noop_benchmark() procedure that is identical to the one described above, except that it omits the assignment of the expresion. So, it lacks this line:

        set v_return := <SOME-EXPRESSION>;

This allows us to isolate the time spent on evaluating the expression and doing the assignment. I also use another control measurement that uses an assignment like this:

        set v_return := <SOME-LITERAL-VALUE>;

This allows us to estimate the time spent on the value assignment, which can be used to get a bit closer to the actual time spent only on expression evaluation alone. (Of course, this assumes that the time spent on the assignment alone is comparable for expressions, function calls and literals).

All these measurements were made by comparing single, complete calls many times. All tests were done on Ubuntu Gutsy Gibbon using MySQL 5.1.23. Compilation of UDFs was performed using gcc version 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2). No optimizations were employed.

Stored functions and UDFs

To compare UDFs and Stored functions, I first used simple "Hello World" expressions that all evaluate to a VARCHAR(14). This was measured:

• String literal sp_string_benchmark. The expression was:

  v_return := 'Hello, String!';



• Stored SQL function sp_ssf_benchmark. The expresion was:

  v_return := ssf_hello_world();

  The ssf_hello_world() itself was:

  
  create function ssf_hello_world()
  returns varchar(14)
  return 'Hello, SSFs!!!';



• User defined function sp_udf_benchmark. The expression was:

  v_return := udf_hello_world();

  The UDF itself was:

  
  my_bool udf_hello_world_init(
    UDF_INIT *initid, UDF_ARGS *args,
    char *message
  ){
    return 0;
  }
  char *udf_hello_world(
    UDF_INIT *initid, UDF_ARGS *args
  , char* result, unsigned long* length
  , char *is_null, char *error 
  ){
    *length = 14;
    return "Hello, UDFs!!!";
  }

Here are the raw results:

+----------+------+--------+-----+-----+
| repeated | noop | string | UDF | SSF |
+----------+------+--------+-----+-----+
|        0 |    0 |      0 |   0 |   0 |
|   500000 |    3 |      4 |   6 |   8 |
|  1000000 |    7 |      9 |  10 |  16 |
|  1500000 |   10 |     13 |  16 |  25 |
|  2000000 |   13 |     17 |  21 |  33 |
|  2500000 |   16 |     22 |  25 |  42 |
|  3000000 |   19 |     27 |  31 |  50 |
|  3500000 |   23 |     31 |  36 |  58 |
|  4000000 |   26 |     36 |  41 |  67 |
|  4500000 |   30 |     40 |  45 |  75 |
|  5000000 |   33 |     44 |  51 |  83 |
|  5500000 |   36 |     49 |  55 |  90 |
|  6000000 |   39 |     53 |  61 |  99 |
|  6500000 |   42 |     57 |  66 | 107 |
|  7000000 |   45 |     62 |  71 | 115 |
|  7500000 |   49 |     66 |  76 | 123 |
|  8000000 |   52 |     71 |  81 | 131 |
|  8500000 |   56 |     75 |  86 | 140 |
|  9000000 |   58 |     80 |  90 | 147 |
|  9500000 |   62 |     83 |  96 | 156 |
| 10000000 |   64 |     88 | 101 | 164 |
+----------+------+--------+-----+-----+

And here is a graph:

At a glance we see that doing nothing is the fastest, followed by the assignment of a literal string. After that, comes the UDF and the stored SQL function is by far the slowest. Another thing that is immediately apparent is that the execution time increases proportionally as the number of repetitions is increased. This means that we can essentially forget the entire series and focus on the measurements with the highest number of repetitions (which is presumably more accurate than the earlier measurements).

But exactly how much faster is the UDF as compared to the SQL function? Well, it depends on how you look at it. If we just divide the raw execution time of the stored function by that of the UDF, we see that the ratio is:

164/101 = 1.60

This would tempt us into thinking that UDF's are about 60% faster.

However, when we calculate it like this, we are also counting the overhead of the benchmark procedures themselves. We get a better result if we focus on only the expression assignments. We can express the performance in terms of the time required to execute the no-operation benchmark. So:

noop / udf = 64 / 101 = .63

and

noop / ssf = 64 / 164 = .39

This correction indicates that the UDF performs at 63% of the no-operation benchmark, whereas the stored SQL function performs at 39% of the no-operation benchmark. We could say that relative to the no-operation benchmark, UDFs are 24% faster as compared to SQL functions

Now we could stretch it a bit more and try to isolate only the time spent on evaluating the functions. To do that, we'd have to assume that "assignment" costs the same, no matter if we are assigning from a stored SQL function, user-defined function or string literal. If we do that, we get this figure:

literal / udf = 88 / 101 = .87

and

literal / ssf = 88 / 164 = .54

This correction indicates that the UDF performs at 87% of the string-literal benchmark, whereas the stored SQL function performs at 54% of the string-literal benchmark. This would indicate that relative to the string literal assignment, UDFs are 33% faster than SQL functions.

Now, I can imagine that a lot of people will have some reservations against this method of correcting the measurements. Personally I think the method is valid, although the result itself is not that useful. I mean, in real life, the fact is that we will be assigning the value of the function, and from that perspective it doesn't help us much to know how fast it would have been if we didn't perform an assignment. Another reservation that we may have is that this benchmark still doesn't tell us much more than the relative differences in overhead. Basically, both the UDF and the stored function are empty - so this benchmark can tell us nothing about performance in a more realistic case where the function is actually doing some work.

Addition

In an attempt to measure at least some basic processing I decided to benchmark addition too. I took a INTEGER as data type and did the following benchmarks:

• Integer literal: sp_num_benchmark with the expression:

  v_return := 3;



• Addition operator: sp_opr_benchmark with the expression:

  v_return := 1+2;



• UDF: sp_udf_benchmark with the expression:

  v_return := UDF_ADD(1,2);

  The code for the UDF is

  my_bool udf_add_init(
    UDF_INIT *initid
  , UDF_ARGS *args
  , char *message
  ){
    if(args->arg_count!=2){
      strcpy(message, "Require two arguments");
      return 1;
    } else {
      args->arg_type[0]= INT_RESULT;
      args->arg_type[1]= INT_RESULT;
    }
    initid->maybe_null= 1;
    return 0;
  }
  
  long long udf_add(
    UDF_INIT *initid
  , UDF_ARGS *args
  , char *is_null
  , char *error 
  ){
    if((args->args[0]==NULL)||(args->args[1]==NULL)){
      *is_null= 1;
      return 0;
    } else {
      return (*((long long*)args->args[0])) + (*((long long*)args->args[1]));
    }
  }
  



• Stored SQL function: sp_ssf_benchmark with the expression:

  v_return := SSF_ADD(1,2);

  The code for the function is

  
  create function ssf_add(l int, r int)
  returns int
  return l+r;
  

Here is the raw data:

+--------------+------+-----+-----+-----+-----+
| repeat_count | noop | num | opr | udf | ssf |
+--------------+----- +-----+-----+-----+-----+
|            0 |    0 |   0 |   0 |   0 |   0 |
|       500000 |    3 |   5 |   5 |   6 |   9 |
|      1000000 |    7 |   9 |   9 |  11 |  18 |
|      1500000 |   10 |  14 |  13 |  16 |  27 |
|      2000000 |   13 |  19 |  18 |  21 |  35 |
|      2500000 |   17 |  23 |  22 |  26 |  47 |
|      3000000 |   20 |  27 |  27 |  33 |  56 |
|      3500000 |   23 |  33 |  33 |  38 |  62 |
|      4000000 |   27 |  38 |  36 |  43 |  74 |
|      4500000 |   30 |  42 |  42 |  50 |  83 |
|      5000000 |   34 |  46 |  47 |  54 |  91 |
|      5500000 |   36 |  51 |  60 |  68 | 108 |
|      6000000 |   42 |  56 |  59 |  67 | 115 |
|      6500000 |   45 |  60 |  62 |  71 | 123 |
|      7000000 |   47 |  65 |  69 |  78 | 132 |
|      7500000 |   50 |  67 |  71 |  84 | 143 |
|      8000000 |   54 |  72 |  78 |  89 | 149 |
|      8000000 |   54 |  73 |  78 |  89 | 149 |
|      8500000 |   59 |  78 |  79 |  92 | 157 |
|      9000000 |   60 |  85 |  85 |  99 | 168 |
|      9500000 |   65 |  89 |  92 | 104 | 178 |
|     10000000 |   67 |  91 |  95 | 111 | 189 |
+--------------+------+-----+-----+-----+-----+ 

And here is the graph of the results:

We can immediately see that the result is quite similar to what we saw in the previous measurements. Let's look at the performance relative to assigning a literal integer:

    int / opr = 91 / 95 = 0.96

and

    int / udf = 91 / 111 = 0.82

and

    int / ssf = 91 / 189 = 0.48

So, A direct addition operator is less than 5% slower than a literal assignment. The UDF 18% slower than the literal assignment and 14% slower than the addition operator. The stored SQL function is quite a good deal slower: 48% slower than the direct addition operator and 34% slower than the UDF. If we want to compare only UDFs vs stored SQL functions, we should compare relative to the addition operator, which gives a minutely different result:

    opr / udf = 95 / 111 = 0.83

and

    opr / ssf = 95 / 189 = 0.5

Built-in functions and UDFs

While I was busy doing benchmarks, I also figured that it'd be nice to figure out how UDFs and built-in functions compare performance-wise. To make things slightly more realistic than simply returning a value, I chose to implement my own version of CONCAT().

Because CONCAT can take on a number of arguments I decided to measure the effect of a varying number of arguments too. I ended up choosing VARCHAR(10) for the data type, and tested these different benchmarks:

• Built-in function sp_bif<1..10>_benchmark - where <1..10> is a number from 1 to 10, and where the expression was:

  v_return := CONCAT(0[,1[,...,9]);

  That is, 10 different CONCAT measurements, from CONCAT(0) to CONCAT(0,1,2,3,4,5,6,7,8,9)


• UDF sp_udf<1..10>_benchmark - where <1..10> is a number from 1 to 10, and where the expression was:

  v_return := UDF_CONCAT(0[,1[,...,9]);

  That is, 10 different measurements of my UDF implementation of concat, from UDF_CONCAT(0) to UDF_CONCAT(0,1,2,3,4,5,6,7,8,9).The code for my UDF_CONCAT is:

  
  my_bool udf_concat_init(
    UDF_INIT *initid, UDF_ARGS *args
  , char *message
  ){
    int i;  
    size_t bytes = 0;
    for(i=0;iarg_count; i++){
      args->arg_type[i] = STRING_RESULT;
      bytes += args->lengths[i];
    }
    if(!(initid->ptr= malloc(bytes))){
      strcpy(message, "Error allocating memory.");
      return 1;
    } else {
      return 0;
    }
  }
  
  char *udf_concat(
    UDF_INIT *initid, UDF_ARGS *args
  , char* result, unsigned long* length
  , char *is_null, char *error 
  ){
    int i;  
    char *buff = initid->ptr;
    *length = 0;
    for(i=0;iarg_count; i++){
      if(args->args[i]==NULL){
        *is_null = 1;
        break;
      } else {
        memcpy(buff + *length, args->args[i], args->lengths[i]);
        *length += args->lengths[i];
      }
    }
    return buff;
  }
  
  void udf_concat_deinit(
    UDF_INIT *initid
  ){
    if(initid->ptr){
      free(initid->ptr);
    }
  }
  




I also measured the same string literal assignment and the noop benchmarks as control measurements. I won't give the raw results here - send me an email or post a comment if you'd like to have them. I do have a graph of the result here:
Note that for this graph I already subtracted the no-operation benchmark. This was done to make it easier to examine the data sets of the UDFs and Built-in functions. The graph does include the literal string benchmark, which is the orange line nearest to the X axis.

Now, what do we see here apart from the control benchmark? Basically, we see two bundles of series. The bundle nearest to the X axis corresponds with the built-in CONCAT() benchmarks. The bundle above that corresponds to the UDF benchmarks. So, this tells us that on every occasion, the built-in CONCAT() was faster than the UDF.

We can also see that there is a relatively small but measurable effect for passing more arguments. The calls with fewer arguments are consistently faster than the calls with more arguments within both the group of built-in and UDF calls.

Frankly, I didn't expect to see this. I had imagined that the effect of passing more arguments would be larger, so I expected to see pairs of UDF/Built-in function calls having the same number of parameters. Clearly, I was wrong.

So how much faster are UDFs? Well, if we look at the raw ratios of execution times for the largest number of repetitions, we see:

UDF_CONCAT(0) / CONCAT(0) = 91 / 107 = .85

Interestingly, if we compare that for the calls with 10 arguments we see the same ratio:

UDF_CONCAT(0,1,2,3,4,5,6,7,8,9) / CONCAT(0,1,2,3,4,5,6,7,8,9) = 91 / 107 = .85

So, UDF_CONCAT() would seem to be 15% slower than the built-in CONCAT(). Interestingly, there seems to be no difference between the call with the larger number of arguments, indicating that the performance impact of passing another argument is about the same for UDFs as it is for built-in functions.

What happens if we express the execution time relative to the no-operation benchmark? Well, we get:

noop / UDF_CONCAT(0)                     = 64 / 107 = .60
noop / CONCAT(0)                         = 64 /  91 = .70

and

noop / UDF_CONCAT(0,1,2,3,4,5,6,7,8,9)   = 64 / 122 = .52
noop / CONCAT(0,1,2,3,4,5,6,7,8,9)       = 64 / 104 = .62

Here we see that relative to the no-operation benchmark, the UDF is 10% slower than the built-in function. We could say that 10% is quite a lot, but it is more than half as large as the difference between UDFs and stored SQL functions.

We see something interesting if we look at the execution time relative to the execution time spent on the string literal assignment:

string / UDF_CONCAT(0)                   = 88 / 107 = .82
string / CONCAT(0)                       = 88 /  91 = .87

and

string / UDF_CONCAT(0,1,2,3,4,5,6,7,8,9) = 88 / 122 = .72 
string / CONCAT(0,1,2,3,4,5,6,7,8,9)     = 88 / 104 = .85

Here, the difference between the single argument calls is only 5%, wereas the difference becomes more 12% for the calls with 10 arguments. This is interesting because in the comparison with the no-operation benchmark we did not detect a difference caused by the the amount of arguments.

My current suspicion is that we are actually witnessing the effect of the length of the left hand expression in the assignment operation. Our string literal is a VARCHAR(14), and it should probably be a CHAR(1) for the comparison to the single argument calls and a CHAR(10) for the comparison with the 10 argument calls.

Conclusion

The UDFs I tested are

• somewhere around and between 25% to 33% faster than stored SQL functions


• somewhere around and between 5% to 20% slower than built-in functions

Another interesting finding is that argument passing seems to have about the same impact on UDFs as it has on built-in functions. A single argument seems to cost about 1% of the function performance in both cases. For stored SQL functions no such data is currently available.

Discussion

Currently, all functions call are single complete function calls. That means that for UDFs, the initialization function and the row-level function are both called exactly once per UDF instance. When using UDFs in multi-row SQL statements, the initialization function will be called only once per occurence of the UDF, and the row-level function will be called for each row. For functions where the initialization function is relatively expensive, this means that the performance observed in these benchmarks is probably poorer that it can be. A new set of benchmarks should be done to measure the performance of functions in multi-row SQL statements.

Finally

So, are you interested? If you are, go and register for the conference. You can contact me and get a 20% discount! Of course I'd love to see you attend my tutorial too!

See you at the conference!