Introduction to Window Functions in SQL | Hacker News Reader

Introduction to Window Functions in SQL

khashtamov.com

196 pointsadilkhash45 comments

A few cool tricks I use with window functions:

1- To find blocks of contiguous values, you can use something similar to Gauss' trick for calculating arithmetic progressions: sort them by descending order and add each value to the row number. All contiguous values will add to the same number. You can then apply max/min and get rows that correspond to the blocks of values.

    select min(n), max(n) from (
      select n, n+row_number() over (order by n desc) group
      from numbers
    )
    group by group
    order by 1

2- You can use a window function with exponential/logarithms in order to calculate the accumulated inflation for the last n months:

    select date, inflation, (exp(accumulated)-1)*100 from (
      select date, inflation, sum(ln(1+(inflation/100))) over (order by date desc rows between current row and 11 following) as accumulated
      from inflation
    )

3- You can do all the paging in SQL (fetch page n of m) or simply add a column with the total number of rows (this often makes it easier to process the results).

Could you please develop how to do paging with window functions?

It's been some time since I've done serious work with SQL yet I remember that all paging solutions I've found (eg. top results on SO) are always platform-specific so having a platform-independent way of doing it would mean I could finally try to remember it.

Try this:

    select ord, table_name, first_name, last_name, total_rows 
    from (
        select table_name,
               row_number() over (order by table_name asc) ord,
               count(1) over () total_rows,
        from all_tables 
        where table_name like 'B%'
        order by table_name desc
    ) where  ord between 10 and 19
    order by ord

This is basically what Oracle Apex does. You can do this without window functions, but it gets a bit more complicated.

I like to add total_rows so that I can show a "rows 10 - 19 of 81" header. You can also get the very first and last values by adding theses columns:

    first_value(table_name) over (order by table_name asc rows between unbounded preceding and unbounded following) first_name,
    last_value(table_name) over (order by table_name asc rows between unbounded preceding and unbounded following) last_name

Alternatively, you could get the very last and very first whole rows by changing the outer where clause:

   ord=1 or rownum=1 or ord between 10 and 19

And then it would be easy to have a nice header with "rows 10 - 19 of 81 (Algiers to Zimbabwe)" with very little code.

If you mean pagination, then window functions are not the right tool. Keyset pagination in standard SQL:

• https://use-the-index-luke.com/sql/partial-results/fetch-nex...

• https://use-the-index-luke.com/no-offset

Both of these are bad for pagination - if the dataset isn't read-only. If the search criteria matches 100 rows at the time of the request, you may want to page through those matches, even if, by the time the client (human or machine) gets to page three, the query matches 80 or 110 rows - or worse, if the query still matches 100 rows, but not all of them are the same as the original 100!

You would normally capture such state by using cursors.

Could you elaborate on "using cursors" part? Are you talking about database-level cursors? If so, do you know any resources which cover this approach?

row_number() !

As in: SELECT * FROM (SELECT *, row_number() OVER (order by <some column - primary key column would be a good choice>) as rowidx FROM your_table) as numbered WHERE rowidx > ? AND rowid < ?

Introduction to Window Functions with the same examples (salaries per department)

https://www.postgresql.org/docs/13/tutorial-window.html

While you are at it, check out common table expressions as well

https://www.postgresql.org/docs/13/queries-with.html

okay, thanks :)

I've been working on a messaging app, and at the beginning I started out with Elasticsearch. Now, ES is really a wonderful tool and it got me pretty far, but its lack of window functions made one particular requirement impossible that we all take for granted in messengers: a listing of most-recently updated threads represented by the most recent message on each thread, sorted reverse chronologically. Here is the SQL that makes that happen:

  SELECT
    tm.*
  FROM
    (
      SELECT
        row_number() OVER (
          PARTITION BY tm_1.thread_id
          ORDER BY tm_1.delivered_at DESC
        ) AS "row",
        tm_1.*
      FROM
        thread_message tm_1
    ) tm
  WHERE
    tm."row" = 1;

The inner query groups all messages by thread, orders them to find the "most recent" message on a thread given my ordering requirements, and then assigns a row number to each such message such that I can pick the most recent message on each thread in the outside query. I still have no idea how I would have done this with Elasticsearch.

I find window functions to be an excellent way to find the max version of a set of things. The trick is to partition by some columns (similar to how you would use a group by), order by descending on your version number field, and use the row_number() function which is very lightweight. Then you filter for all entries where rownumber = 1 and voila you have the max version without having to link back on yourself!

Sadly, I've worked on a lot of codebases where even the "link back on yourself" trick was unknown to the developers, generally leading to devs dumping the entire dataset into an array and then manually iterating over it to find the max values. I wish developers would learn more SQL at the start of their careers...

Is this different than something like the following?

SELECT app_name, MAX_BY(version_number, updated_at) as version_number FROM table GROUP BY 1

Yes! I use this daily.

I made gifs to explain the different types of window functions: https://dataschool.com/how-to-teach-people-sql/how-window-fu...

What i like most about window functions is that they give me a way to do a sort of 'extended group by' which i have always wanted.

If you want to know the highest salary in each department, that's easy:

  select department, max(gross_salary)
  from salary
  group by department

If you want to know who it is who earns that salary, you might try to do this:

  select department, first_name, max(gross_salary)
  from salary
  group by department

But this doesn't work, because it's meaningless to ask for first_name in a situation where you're grouping by department. You could ask for an aggregation of all names, but there's no straightforward way to ask for the name of the person who earned that salary. You end up having to write a join against the group by, as in the article, which is pretty grim, and falls apart if you want to order by multiple columns to break ties.

Window functions let you re-frame this kind of group by like this:

  select department, gross_salary
  from (
    select *, row_number() over (partition by department order by gross_salary desc) as n
    from salary
  ) _
  where n = 1

Because the outer query is no longer a group by, you can select any columns you like. The natural query works fine:

  select department, first_name, gross_salary
  from (
    select *, row_number() over (partition by department order by gross_salary desc) as n
    from salary
  ) _
  where n = 1

This only works where the group by is based on an aggregate function that picks one value, like min or max. I somewhat think it was a mistake to model that kind of thing as an aggregation in the first place. If SQL had a way of picking one row from a group, rather than aggregating over it, that would be immensely useful.

> If SQL had a way of picking one row from a group, rather than aggregating over it, that would be immensely useful.

You can do this with a LATERAL join, if you want to avoid the jankiness of window functions. Lateral joins are just a programmatic way to introduce a correlated subquery. For example

    SELECT department, first_name, gross_salary FROM
        (SELECT DISTINCT department FROM salary) depts,
        LATERAL (
            SELECT first_name, gross_salary 
            FROM salary 
            WHERE department = depts.department 
            ORDER BY gross_salary DESC
            LIMIT 3
        )

This uses a limit of 3 to show off top-3 instead of just argmax, but you could clearly set that to one if you wanted. This construction can be pretty handy if you need the per-group rows to be something other than what a window function could handle.

> If SQL had a way of picking one row from a group, rather than aggregating over it, that would be immensely useful.

Well, there is a way which is window functions :) as shown by you.

The idea to expect exactly one first name of the person with the biggest salary is kinda wrong, since there can be more than one person, and this can obviously not described as a single column per group.

Note that aggregating is not limited to min, max, sum, etc. Postgres, for example, has array_agg which aggregates individual columns from each record of a group into an array, if that becomes necessary.

> The idea to expect exactly one first name of the person with the biggest salary is kinda wrong, since there can be more than one person, and this can obviously not described as a single column per group.

That's true. For this idea to work, there would need to be some framework for picking exactly one row from a group. The simplest thing would be to raise an error if there were multiple candidates, but perhaps there are better ways. I think the operation of picking exactly zero or one things from a group is so common that it's worth making provision for it.

With Kinetica you can use the 'arg_max' aggregate function

  select department, max(gross_salary), arg_max(gross_salary, first_name)
  from salary
  group by department

https://www.kinetica.com/docs/concepts/sql.html#sql-aggregat...

Here's an alternative I use all the time (without window functions) that I don't think is widely known! Works on SQL Server and I think is more performant?:

  SELECT department, first_name, salary
  FROM salary AS s
  WHERE s.[salary] = (
    SELECT MAX(ex.[salary])
    FROM salary AS ex
    WHERE s.[department] = ex.[department])

I like how the article teaches by explicit example. Very helpful when it comes to data.

The "lag" and "lead" SQL functions are particularly useful when analysing sequences of timestamped events (GPS fixes, task completions etc). They allow you to easily return the delta of a value (time/distance) between the current and previous row, which is really useful if you want to compare expected vs actual on those deltas.

Question for the pros: In doing some data engineering work, I found that creating temporary tables and dropping them after the run was much more performant and memory-efficient than using CTEs. No other change was made to the queries in the CTE, just putting them in a separate CREATE TABLE AS... script before the part that needed the calculations.

Why is this the case? Shouldn't CTEs be more efficient?

Until postgres 12 (if you were using postgres) CTEs were an optimization fence. Where filters would not get pushed down into the CTE if they were only specified outside the CTE (but in fields from the CTE).

https://paquier.xyz/postgresql-2/postgres-12-with-materializ...

Well, filters won't get pushed down to previous CREATE TABLE either.

You already got a good response for postgres.

If you where speaking of MSSQL, it does treats non-recursive[1] CTE's as equivalent to to a view, and effectively inline it. So if things were faster with a temp table than a CTE it would mean that the query optimizer came up with a bad query plan. The most likely reason being that your query was complicated enough that you confused the cardinality estimator, so it ends up choosing really bad join types.

[1] Recursive queries in MSSQL are more complicated. They spool, but not necessarily all rows get spooled right away. So an infinite result recursive CTE does not necessarily fail. In any case predicate pushdown still occurs.

Really depends on query complexity. Keep in mind that creating a CTE doesn't really materialize any of the resulting steps' data, it's just a way to encapsulate logic. Chaining together complex CTEs is effectively the same as creating layers of views, which can also be a performance problem.

In the case of a temp table, you're likely intelligently (manually) going through the process of whittling down the data to only what you need and in the most efficient ways possible. Maybe you're filtering by date upfront, then by some other filter, removing as many rows as is possible as quickly as possible. With the CTE(s), it might be creating a list of many filters with a lot of joins in one step, and the optimizer may not understand which filters can remove the most rows the most easily.

> creating a CTE doesn't really materialize any of the resulting steps' data

Well, at least with PostgreSQL -- all CTEs were always materialized. It was optimized only in the version 12.

Analytic functions as they are known by in Oracle, SQL have been around for more than a decade. They are useful for calculating running balances, getting a previous or next row value, doing a "group by" for a subset of columns.. etc. They're the best thing in SQL "since sliced bread".

https://towardsdatascience.com/analytical-functions-in-oracl...

Wow I love me a window function!

Favorite/weirdest thing I learned to do most recently with window functions is using/abusing min() and max(). If there is no value in a column in a particular window, min and max will give NULL.

We use this to do really interesting stuff (entirely in sql!) like "partition usage into sessions where a session is defined as a bunch of activity by a user where they did an action at least once every 30 minutes"

SQL could really use some standard aggregation function that returns null for no rows, the value of a single row and error if there is more than one row.

That kind of query happens all the time, and min/max behavior isn't the safest one.

Previous discussion on SQL Window functions: https://news.ycombinator.com/item?id=20872114

Helpful resource: http://www.windowfunctions.com/

i would also recommend the wonderful https://modern-sql.com/

SQL is only secondary in my work but I'd rather go with the explicit and verbose queries rather than with stuff with surprises like how the last_value gives wrong results when used the way you'd expect i.e. the reverse of first_value.

if you understand the window ranges, especially the default one there is no surprise at all

I've always wondered and perhaps someone here might know....do postgres' CTEs translate into big select/sub select queries under the hood? Or are they something special entirely? Ie (forgive formatting as I'm on phone) does:

With mything as ( Select * from table where... ),

Myotherthing as ( Select * from mything where... )

Get translated to

Select * from (select * from ( select * from...)...)...)

So I'm just wondering are CTEs just easier to read, or do they offer any other known optimizations? We use them loads but mainly just for keeping larger queries easier to manage

It's a bit hidden (or rather not pronounced enough) in the general docs but there are performance implications of using CTEs:

https://www.postgresql.org/docs/13/queries-with.html

> A useful property of WITH queries is that they are normally evaluated only once per execution of the parent query, even if they are referred to more than once by the parent query or sibling WITH queries. Thus, expensive calculations that are needed in multiple places can be placed within a WITH query to avoid redundant work. Another possible application is to prevent unwanted multiple evaluations of functions with side-effects. However, the other side of this coin is that the optimizer is not able to push restrictions from the parent query down into a multiply-referenced WITH query, since that might affect all uses of the WITH query's output when it should affect only one. The multiply-referenced WITH query will be evaluated as written, without suppression of rows that the parent query might discard afterwards. (But, as mentioned above, evaluation might stop early if the reference(s) to the query demand only a limited number of rows.)

> However, if a WITH query is non-recursive and side-effect-free (that is, it is a SELECT containing no volatile functions) then it can be folded into the parent query, allowing joint optimization of the two query levels. By default, this happens if the parent query references the WITH query just once, but not if it references the WITH query more than once. You can override that decision by specifying MATERIALIZED to force separate calculation of the WITH query, or by specifying NOT MATERIALIZED to force it to be merged into the parent query. The latter choice risks duplicate computation of the WITH query, but it can still give a net savings if each usage of the WITH query needs only a small part of the WITH query's full output.

There are some examples below this text as well.

thanks very much for the reply, it was a case of RTFM on my end!

Not 100% about the newest versions of Postgres. But certainly in older versions CTEs created query planner boundaries.

So the planner would optimise each CTE separately, but wouldn’t optimise the entire query with all CTEs together, which of course can result in some slightly nonsensical query plans.

To my knowledge this is considered a limitation rather than a feature as it can cause performance issues with some queries.

EDIT: Some quick Googling suggests the CTEs are no longer optimisation fences, and their handling can be tweaked on a CTE by CTE basic in Postgres 12 onwards [1]

[1] https://www.depesz.com/2019/02/19/waiting-for-postgresql-12-...

In postgresql 12 a patch [0] is merged to remove the optimization fence certain conditions. From the changelog [1]

" Allow common table expressions (CTEs) to be inlined into the outer query (Andreas Karlsson, Andrew Gierth, David Fetter, Tom Lane)

Specifically, CTEs are automatically inlined if they have no side-effects, are not recursive, and are referenced only once in the query. Inlining can be prevented by specifying MATERIALIZED, or forced for multiply-referenced CTEs by specifying NOT MATERIALIZED. Previously, CTEs were never inlined and were always evaluated before the rest of the query. "

[0] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit... [1] https://www.postgresql.org/docs/12/release-12.html

In theory, both forms should get optimized similarly by the DB, but the practice will likely differ from database to database, and maybe even from DB version to DB version.

There are though things that CTEs can do and sub-selects can't (e.g. WITH RECURSIVE)

Didn't know about WITH RECURSIVE, very cool - thanks

I've been encountering a lot of issues, when doing dedicated queries, specially when a team is small, I've found is sometimes more useful to just do the grouping or left join (if more than 2 are required) manually.

The problem is ofc scalability, if your team is small it is better to just have some few, but very specific queries, and do whatever transactions required on a layer above.

It may be the difference between correcting a few lines, vs reworking 20+ different queries, and testing each one individually.

Finally, comprehensive article about Windows Functions.

I thought the same. Assumed it was some Microsoft BS. Thankfully it's not :D

Reply on news.ycombinator.com