5 Use Cases for SQL Window Functions in a Real-Life Cat System
Window functions are an advanced SQL construct that you will likely come across when working with relational databases. Today I want to share a couple of real-life problems where window functions are beneficial or even essential.
Throughout the whole article, we’ll be working with the simplified schema from a cat information system. Assume a simplified schema with a single table:
CREATE TYPE class AS ENUM ('warrior', 'mage', 'rogue', 'scientist');
CREATE TABLE public.cats (
id bigserial NOT NULL,
"name" text NULL,
birth_date timestamptz NULL DEFAULT CURRENT_TIMESTAMP,
class class null,
level int8 NOT NULL,
CONSTRAINT user_pkey PRIMARY KEY (id)
);
Introduction: WTF WF?
Window functions are a construct that (as the name suggests) allows you to operate on a data window in your selection with standard familiar aggregate functions or special window functions.
Let’s look at the basic syntax in a simple example, finding the max level across all cats.
SELECT MAX(level) as max_level from cats;max_level|
---------+
12|
Window function allows you to use aggregations to get multiple, potentially different results, operating on a defined window data.
SELECT name, level, MAX(level) OVER() as max_level from cats limit 5;
name |level|max_level|
----------+-----+---------+
Cosmomeowt| 6| 12|
Meowrrior | 2| 12|
Ulysses | 1| 12|
Axe | 8| 12|
Motley | 2| 12|
Notice that
- we got the same result (12), but we got the result for each row,
- aggregation works as expected, even though the cat with level 12 did not get to the final result due to limit restriction,
- we could use the aggregate function without familiar GROUP BY,
- the result is the same for all rows.
The syntax (preview is barbarically simplistic) allows defining the following statement as a part of the SELECT statement:
/*<advanced aggregation expression>*/ OVER(/*<optional window expression>*/)
Getting the same result does not seem particularly useful, but the power comes from using known and special aggregation functions over multiple defined windows with custom filtering and order, as we’ll see below! With the introduction out of the way, let’s check a few real-world examples.
You can try all SQL queries on the same data in DB Fiddle.
Showcase kittens from all classes: Balance ORDER BY for different types
Let’s assume that we need to display on our homepage a preview of our freshest feline newcomers. We can’t afford to manipulate the future of the cat population by favoring one profession over the other.
- Show preview of 8 kittens. The youngest kittens must appear on the list.
- An equal number of representatives from each class must be on the list, if possible. This criterion takes precedence over the first one.
We need to push older cats back, but they can cut the queue by being representatives of an unpopular class.
This problem is fairly difficult to solve without window functions. One more naive solution is to use UNION, spell out all types and control the subselect using LIMIT based on the number of class types.
(select * from public.cats where cats."class" = 'warrior' order by birth_date desc limit 2)
union
(select * from public.cats where cats."class" = 'mage' order by birth_date desc limit 2)
union
(select * from public.cats where cats."class" = 'rogue' order by birth_date desc limit 2)
union
(select * from public.cats where cats."class" = 'scientist' order by birth_date desc limit 2)
Or a “dynamic” solution would be to use JOIN with LATERAL subselect
select distinct classes.class, cats.*
from public.cats as classes
join lateral (
select * from public.cats
where cats."class" = classes."class"
order by birth_date desc
limit 2
) cats on (true)
The latter is more obscure, but allows paginating the result in a single place, without having to control all subselects. The LATERAL allows us to define custom subselects to join for each value.
The solution with window functions that presents itself solves the problem not just more eloquently, but more efficiently, using a single pass through data (Note on efficiency: Efficiency is not immediately obvious, so I ran the queries on a larger dataset of 8K cats. LATERAL is extremely slow due to the required looping over the data, UNION is “okay”, but you can see that the execution plan grows in SEQ SCANs with each value of the class. Finally the WINDOW solution uses a single SEQ SCAN regardless of the variability of class).
select * from public.cats
order by row_number() over (
partition by class
order by birth_date desc
)
limit 8
All three approaches give us the same kitties. Here you can see the output (if we include the ROW_NUMBER, which is used for sorting)
name |class |birth_date |row_number|
----------+---------+-----------------------------+----------+
Una |warrior |2022-10-22 00:00:00.000 +0200| 1|
Cosmomeowt|scientist|2021-04-02 00:00:00.000 +0200| 1|
Cato |mage |2021-05-30 00:00:00.000 +0200| 1|
Sanjay |rogue |2021-03-09 00:00:00.000 +0100| 1|
Meowrrior |warrior |2022-01-02 00:00:00.000 +0100| 2|
Uzi |mage |2020-07-06 00:00:00.000 +0200| 2|
Endmund |rogue |2021-03-02 00:00:00.000 +0100| 2|
Whipple |scientist|2021-01-30 00:00:00.000 +0100| 2|
ROW_NUMBER is the first special function we can use in the window functions. It simply assigns a number that increments for every row in the result.
For the first time, we can see the window expression as well! PARTITION BY allows us to create “multiple” windows, which allows us to create multiple series of ROW_NUMBER (for each ). Finally ORDER BY provides instructions on how to sort data within the windows. For each class, we want to pick the youngest kittens. As a result, the youngest cat from each class will have row_number 1. The second 2 etc. Sorting the whole set by this number elegantly solves the problem.
Processing all cats on a memory-constrained computer: Limit by accumulative size
For the next case, we need to process all the cats in the database. The problem is, we are running on a potato PC and we know that we’d better not take a batch of data that is larger than X bytes.
The problem is that some cats are really small in terms of size in bytes, and some cats will take the whole size limit for themselves. If there is a single cat that exceeds the limit, we want to take just a single cat and make an exception to the rule, so the scrolling is not stuck in a “deadlock”.
Note: Lengths of different rows can be different because of the dynamic field TEXT.
In Postgres, we can get the size of a row in bytes with the following query.
select id, pg_column_size(cats.*) from public.cats limit 4
id|name |pg_column_size|
--+----------+--------------+
1|Cosmomeowt| 72|
2|Meowrrior | 72|
3|Ulysses | 64|
4|Axe | 64|
It roughly makes sense: id 8 + date 8 + class 4 + something for the name. Does not add up. Probably some padding, nevermind, we’re here for window functions, not nerdy byte counting.
Unfortunately, we cannot use an expression in LIMIT. But with window functions, we can limit the result in this fashion using a WHERE statement.
select * from (
select
cats.id, cats.name, pg_column_size(cats.*) as "size",
SUM(pg_column_size(cats.*)) over (order by id) as acc_size
from public.cats
) cat_sizes
where "acc_size" < 300 or "acc_size" = "size"
We need to use subselect to be able to reference the acc_size in the WHERE statement. To avoid deadlock, we allow the special case where acc_size is the same as size (matches the first row only). This condition is overshadowed by the first most of the time, which keeps capturing rows as long as the acc_size does not reach the defined limit.
The process is more obvious if we look at the data sample:
id|name |size|acc_size|
--+----------+----+--------+
1|Cosmomeowt| 69| 69|
2|Meowrrior | 69| 138|
3|Ulysses | 61| 199|
4|Axe | 61| 260|
The acc_size keeps progressively growing as the window grows larger. This is a problem that is inherently based on the window functions and I don’t think there is an alternative solution.
Talented cats from each year say goodbye: Deduplicate rows with preference
For all cats born in the same year, we must select the most leveled-up cat for each class to lead a course of their craft: e.g. For all cats born in 2008, we need the cat with the highest level in their class.
This problem is fairly similar to the first one but so common it’s worth mentioning. Alternative phrasing is to “deduplicate rows with the same X, keep only rows with Y, discard the rest “. This is again fairly complicated for multiple values of X, but as you can probably see now, it is relatively easy with window functions. Again using the ROW_NUMBER.
select *,
row_number() over (
partition by date_part('year', birth_date), class
order by level desc
) from public.cats
This will assign number 1 for all cats in focus, while others will have increasing series in the group. If this was a case for deduplication (all cats from same year and class are considered as duplicate, we want to keep only those with the highest level), we could easily filter out the cats to keep (row_number = 1) and those to remove (row_number > 1).
Voting groups: Divide rows in selection into X clusters
As the elections draw near, we must prepare the voting points. We have overall 5 workers validating the IDs and we must somehow assign all cats in the system to one of them. We also need each worker to have a consecutive line of cats (ordered by the name), e.g. 1) gets cats with names A-F, 2) G — Lm, 3) Ln — O, etc. The problem is that if we set the letters as fixed, the distribution of cats can cause an overload of some workers, while others slack.
For this, we can use another special function NTILE, which assigns appropriate cluster numbers for a given window. Its argument determines the number of clusters.
select *, ntile(5) over (order by name) from public.catsid|name |birth_date |class |level|ntile|
--+----------+-----------------------------+---------+-----+-----+
29|Arieh |2020-04-11 00:00:00.000 +0200|rogue | 3| 1|
4|Axe |2006-02-02 00:00:00.000 +0100|warrior | 8| 1|
19|Belphegor |2019-12-04 00:00:00.000 +0100|warrior | 1| 1|
31|Bephelgor |2021-02-12 00:00:00.000 +0100|warrior | 2| 1|
32|Cato |2021-05-30 00:00:00.000 +0200|mage | 1| 1|
11|Chubby |2013-11-24 00:00:00.000 +0100|warrior | 2| 1|
1|Cosmomeowt|2021-04-02 00:00:00.000 +0200|scientist| 6| 1|
21|Dynas |2020-11-17 00:00:00.000 +0100|rogue | 1| 2|
30|Elephant |2021-06-02 00:00:00.000 +0200|warrior | 1| 2|
...
CLCS (Cat Level Competitive Score): Relative score
Cats are rewarded based on their CLCS. That is a score depending on the relative position you take with your level compared to all the cats in the system: a relative level. We expect all the cats with the highest level (we already know it’s 12) to have a score of 1. All the cats with the lowest level should have a score equal to the relative size of the group sharing the level (0.1 if there are 10% of cats on the minimum level).
A window function (cumulative distribution) solves the problem for us again.
select *, cume_dist() over (order by level) from public.cats
In the result we can see that ¼ of cats have level one.
id|name |class |level|cume_dist|
--+----------+---------+-----+---------+
21|Dynas |rogue | 1| 0.25|
20|Uzi |mage | 1| 0.25|
19|Belphegor |warrior | 1| 0.25|
32|Cato |mage | 1| 0.25|
...14|Mimi |warrior | 11| 0.96875|
13|Lashpaw |rogue | 12| 1.0|
What about the performance?
Window functions by their definition require an “iterative” scan over the data, so you might easily run into trouble when querying large tables.
Most of the time, your best shot is to reduce the data through index search and window scan only the necessary portion. In some cases, a full scan with a window could be far better than combined complex queries, as I’ve learned recently when running the deduplication case.
Summary
We learned what window functions are and showcased several practical ways to use them. I encountered almost all of them in one form or another in my job. The sad truth is, however, that I am not working on a cat system (but if you happen to work on one, let me know, I might join you!)
Till then, I hope you liked it, reach me out if you have any questions or some other topic you’d like to read more about.
Originally published at https://www.ackee.agency on May 27, 2022.