June 15, 2017

Introduction to Window Functions in MariaDB Server 10.2

By Guest

This is a guest post by Vicențiu Ciorbaru, software engineer for the MariaDB Foundation. 

Practical Examples Part 1

MariaDB Server 10.2 has now reached GA status with its latest 10.2.6 release. One of the main focuses of Server 10.2 was analytical use cases. With the surge of Big Data and Business Intelligence, the need for sifting and aggregating through lots of data creates new challenges for database engines. For really large datasets, tools like Hadoop are the go-to solution. However that is not always the most practical or easy-to-use solution, especially when you’re in a position where you need to generate on-the-fly reports. Window functions are meant to bridge that gap and provide a nice “middle of the road” solution for when you need to go through your production or data warehouse database.

The MariaDB Foundation has worked in collaboration with the MariaDB Corporation to get this feature out the door, as it was an area where the MariaDB Server was lagging behind other modern DBMS. Being an advanced querying feature, it is not trivial to explain. The best way to provide an introduction to window functions is through examples. Let us see what window functions can do with a few common use cases.

Generating an increasing row number

One of the simplest use cases (and one of the most frequent) is to generate a monotonically increasing sequence of numbers for a set of rows. Let us see how we can do that.

Our initial data looks like this:

SELECT
email, first_name,
last_name, account_type
FROM users
ORDER BY email;
 
+------------------------+------------+-----------+--------------+
| email                  | first_name | last_name | account_type |
+------------------------+------------+-----------+--------------+
| admin@boss.org         | Admin      | Boss      | admin        |
| bob.carlsen@foo.bar    | Bob        | Carlsen   | regular      |
| eddie.stevens@data.org | Eddie      | Stevens   | regular      |
| john.smith@xyz.org     | John       | Smith     | regular      |
| root@boss.org          | Root       | Chief     | admin        |
+------------------------+------------+-----------+--------------+

Now let’s add our window function.

SELECT
row_number() OVER (ORDER BY email) AS rnum,
email, first_name,
last_name, account_type
FROM users
ORDER BY email;
 
+------+------------------------+------------+-----------+--------------+
| rnum | email                  | first_name | last_name | account_type |
+------+------------------------+------------+-----------+--------------+
|    1 | admin@boss.org         | Admin      | Boss      | admin        |
|    2 | bob.carlsen@foo.bar    | Bob        | Carlsen   | regular      |
|    3 | eddie.stevens@data.org | Eddie      | Stevens   | regular      |
|    4 | john.smith@xyz.org     | John       | Smith     | regular      |
|    5 | root@boss.org          | Root       | Chief     | admin        |
+------+------------------------+------------+-----------+--------------+

So, a new column has been generated, with values always increasing. Time to dissect the syntax.

Notice the OVER keyword as well as the additional ORDER BY statement after it. The OVER keyword is required to make use of window functions. row_number is a special function, only available as a “window function”, it can not be used without the OVER clause. Inside the OVER clause, the ORDER BY statement is required to ensure that the values are assigned to each row deterministically. With this ordering, the first email alphabetically will have the rnum value of 1, the second email will have rnum value of 2, and so on.

Can we do more with this?

Yes! Notice the account_type column. We can generate separate sequences based on account type. The OVER clause supports another keyword called PARTITION BY, which works very similar to how GROUP BY works in a regular select. With PARTITION BY we split our data in “partitions” and compute the row number separately for each partition.

SELECT
row_number() OVER (PARTITION BY account_type ORDER BY email) AS rnum,
email, first_name,
last_name, account_type
FROM users
ORDER BY account_type,email;
 
+------+------------------------+------------+-----------+--------------+
| rnum | email                  | first_name | last_name | account_type |
+------+------------------------+------------+-----------+--------------+
|    1 | admin@boss.org         | Admin      | Boss      | admin        |
|    2 | root@boss.org          | Root       | Chief     | admin        |
|    1 | bob.carlsen@foo.bar    | Bob        | Carlsen   | regular      |
|    2 | eddie.stevens@data.org | Eddie      | Stevens   | regular      |
|    3 | john.smith@xyz.org     | John       | Smith     | regular      |
+------+------------------------+------------+-----------+--------------+

Looks good! Now that we have an understanding of the basic syntax supported by window functions (there’s more, but I won’t go into all the details at once) let’s look at another similar example.

Top-N Queries

The request is: “Find the top 5 salaries from each department.” Our data looks like this:

describe employee_salaries;

+--------+-------------+------+-----+---------+-------+
| Field  | Type        | Null | Key | Default | Extra |
+--------+-------------+------+-----+---------+-------+
| Pk     | int(11)     | YES  |     |    NULL |       |
| name   | varchar(20) | YES  |     |    NULL |       |
| dept   | varchar(20) | YES  |     |    NULL |       |
| salary | int(11)     | YES  |     |    NULL |       |
+--------+-------------+------+-----+---------+-------+

If we don’t have access to window functions, we can do this query using regular SQL like so:

select dept, name, salary
from employee_salaries as t1
where (select count(t2.salary)
       from employee_salaries as t2
       where t1.name != t2.name and
             t1.dept = t2.dept and
             t2.salary > t1.salary) < 5
order by dept, salary desc;

The idea here is to use a subquery to count the number of employees (via count()) from the same department as the current row (where t1.dept = t2.dept) that have a salary greater than the current row (where t2.salary > t1.salary). Afterwards, we accept only the employees which have at most 4 other salaries greater than theirs.

The problem with using this subquery is that if there is no index in the table, the query takes a very long time to execute the larger the employee_salaries table gets. Of course, you can add an index to speed it up, but there are multiple problems that come up when you do it. First, creating the index is costly and maintaining it afterwards adds overhead for each transaction. This gets worse if the table you are using is a frequently updated one. Even if there is an index on the dept and salary column, each subquery execution needs to perform a lookup through the index. This adds overhead as well. There must be a better way!

Window functions to the rescue. For such queries there is a dedicated window function called rank. It is basically a counter that increments whenever we encounter a different salary, while also keeping track of identical values. Let’s see how we would get the same result using the rank function:

Let’s start with generating our ranks for all our employees.

select
rank() over (partition by dept order by salary desc) as ranking,
dept, name, salary
from employee_salaries
order by dept, ranking;

+----------------+----------+--------+
|ranking | dept  | name     | salary |
+--------+-------+----------+--------+
|      1 | Eng   | Kristian |   3500 |
|      2 | Eng   | Sergei   |   3000 |
|      3 | Eng   | Sami     |   2800 |
|      4 | Eng   | Arnold   |   2500 |
|      5 | Eng   | Scarlett |   2200 |
|      6 | Eng   | Michael  |   2000 |
|      7 | Eng   | Andrew   |   1500 |
|      8 | Eng   | Tim      |   1000 |
|      1 | Sales | Bob      |    500 |
|      2 | Sales | Jill     |    400 |
|      3 | Sales | Tom      |    300 |
|      3 | Sales | Lucy     |    300 |
|      5 | Sales | Axel     |    250 |
|      6 | Sales | John     |    200 |
|      7 | Sales | Bill     |    150 |
+--------+-------+----------+--------+

We can see that each department has a separate sequence of ranks, this is due to our partition by clause. This particular sequence of values for rank() is given by our ORDER BY clause inside the window function’s OVER clause. Finally, to get our results in a readable format we order our data by dept and the newly generated ranking column.

Given that we have the result set as is, we might be tempted to put a where clause in this statement and filter only the first 5 values per department. Let’s try it!

select
rank() over (partition by dept order by salary desc) as ranking,
dept, name, salary
from employee_salaries
where ranking <= 5
order by dept, ranking;

Unfortunately, we get the error message:

Unknown column 'ranking' in 'where clause'

There is a reason for this! This has to do with how window functions are computed. The computation of window functions happens after all WHERE, GROUP BY and HAVING clauses have been completed, right before ORDER BY. Basically, the WHERE clause has no idea that the ranking column exists. It is only present after we have filtered and grouped all the rows. To counteract this problem, we need to wrap our query into a derived table. We can then attach a where clause to it. We end up with:

select *
from (select 
        rank() over (partition by dept order by salary desc)
               as ranking,
        dept, name, salary
      from employee_salaries) as salary_ranks
where (salary_ranks.ranking <= 5)
order by dept, ranking;

This query does not return an error. Here’s how the result set looks like with a few sample data points.

+----------------+----------+--------+
|ranking | dept  | name     | salary |
+--------+-------+----------+--------+
|      1 | Eng   | Kristian |   3500 |
|      2 | Eng   | Sergei   |   3000 |
|      3 | Eng   | Sami     |   2800 |
|      4 | Eng   | Arnold   |   2500 |
|      5 | Eng   | Scarlett |   2200 |
|      1 | Sales | Bob      |    500 |
|      2 | Sales | Jill     |    400 |
|      3 | Sales | Tom      |    300 |
|      3 | Sales | Lucy     |    300 |
|      5 | Sales | Axel     |    250 |
+--------+-------+----------+--------+

We have our result with window functions, but how do the two queries compare performance wise? Disclaimer, this is done on a development machine to give a rough idea of the performance differences. This is not a “go-to” benchmark result.
 

#Rows

Regular SQL (seconds)

Regular SQL + Index (seconds)

Window Functions (seconds)

2 000

1.31

0.14

    0.00

20 000

123.6

    12.6

    0.02

200 000

14326.34

1539.79

    0.21

2 000 000

...

...

5.61

20 000 000

...

...

76.04

The #Rows represent the number of entries in the table. Each department has 100 employees. For our queries, we can see the computation time grows in a polynomial fashion. For each 10x increase in the number of rows, for regular SQL (with or without an index), the computation time increases by a factor of 100x. On the other hand, for each 10x increase in the number of rows, for regular Window Functions, the computation takes only 10x amount of time. This is due to eliminating an entire subquery evaluation for each row in our final result set.

I’ll dive in more detail about the window function implementation in further articles, but for now this should give you a taste of what window functions can do.