Orthogonal treatment of groups (nee Window functions)

[max-sixty]

Edit — this issue evolved into a much broader discussion of how we do groups. The original message is below, and I've tried to summarize the current state towards the end of the issue so it's easier for others to engage.

---

More than half the people I speak with about PRQL tell me that window functions are painful in SQL and would be a great feature to add to PRQL. I put window funcitons in the examples in the Readme at first, since I had the same experience in SQL.

For clarity: a window / analytic / analytical function is a function that takes other rows as an input, but instead of aggregating over many rows, it creates a new value for every row. For example, a moving average or lag. In SQL it's represented by the OVER keyword.

I haven't thought about this enough, but wanted to post an issue so we could start thinking about how to do it. A couple of initial options:

• A separate pipeline, with the column at the end, and the function (lag in this case) in the pipeline:

from prices
derive price_yesterday: (
  window
  by sec_id
  sort date
  lag 1
  price
)

• A function with lots of named args, with the function lag as a named arg (but how would this work for functions with 0 or >1 parameters?):

from prices
derive price_yesterday: (window by:sec_id sort:date lag:1 price)

• Eliminate window — because we have aggregate, we can't get confused about sum(foo) OVER and sum(foo), so possibly we don't need to have window:

from prices
derive price_yesterday: (price | lag rows:1 sort:date by:sec_id)

I don't think this is sufficiently thought through, and I'm sure these examples have inadequacies.

Here are some example queries we can use as cases: https://cloud.google.com/bigquery/docs/reference/standard-sql/analytic-function-concepts#get_the_most_popular_item_in_each_category

[aljazerzen]

For anyone new to window functions (like I just was): good tutorial with illustrations

A nice observation that we could use in language design is that we have 3 types of functions:

• scalar functions, which map a single value to a single value (e.g. FLOOR). They can be used in select and are applied to the whole column, on each value.
• multi-variate functions, which map many values to a single value (e.g. SUM or MIN). They can be used in aggregate and reduce each partition to one value.
• vector functions, which map a many values to many values (eg. RANK or LAG)/ They can be used as window functions in select and map column to column.

The problem is that when writing code you don't think about that. Is it advantageous if we force users to think about it?

If we would go this way, we would introduce new transform, let's say compute for lack of a better name:

from employees
compute rank(salary)

and with bounds and order:

from bills
sort issued_at
compute preceding:2 following:2 [
  rolling_avg_amount: avg(amount)
]
sort number

Here I've used sort in two places, where the first affects only compute and the second affects the output.

Note that we would be the first languages I know to differentiate between select and compute in this way: dplyr, pandas and polars all have window functions within their selects.

[max-sixty]

The problem is that when writing code you don't think about that. Is it advantageous if we force users to think about it?

I definitely think there would be some benefits of structuring the language to consider types much more than SQL does — it could have a similar benefit to how your variable scoping now allows for knowing what's available to the language.

Ideally there's a synthesis where users don't need to think about it that much, but the compiler can still be helpful (not always possible :) )

vector functions, which map a many values to many values (eg. RANK or LAG)/ They can be used as window functions in select and map column to column.

Yes great. Notably some, like AVG is both a reduction & vector function.

This is related to #54, which deals with a case similar to the "scalar" and "multi-variate" / (aka "reduction") functions.

---

Re the compute case, we do need some way to partition the values — see the by terms above. It could be as a transform of a window pipeline (the 1st case), an arg to a window function (2nd case), an arg to the vector function (3rd case), or something else.

Another option would be to make the partition primary, with something like a by arg to a map (still need to think about this more):

from employees
map by:title (    # or `compute`?
  sort:salary
  rank salary
)

---

One invariant that I think is important to keep in PRQL is that each transform should leave a valid result. Something like .group_by in pandas or dplyr doesn't do this (and in early discussion on PRQL, Hadley said this was one of his biggest regrets). So we shouldn't have:

from employees
window by:title   # Invalid result here
rank salary

[aljazerzen]

Notably some, like AVG is both a reduction & vector function.

Oh, that true, nice catch.

If we go this way, compiler will be able to infer the cardinality of the rows in resulting frame: only one, many or many for a set of keys. So we could actually provide correct typing for cases like #54, which is a huge plus.

---

Partitions

To me, the most consistent way of specifying partitions in compute/map would be by parameter, same as aggregate. The same as in your example.

For this approach the pro is that you can specify by only once, affecting many columns:

from employees
map by:title [    # or `compute`?
  rank salary,
  sum working_hours,
  min salary,
  max salary
]

---

Sort

I wouldnt mix inline pipelines into transforms, it can get confusing why some things have to be in a new line and some don't. Instead I would also put sort as a parameter to the map/compute:

from employees
map by:title sort:salary [    # or `compute`?
  rank salary
]

Or, even better, infer it from the current state of the pipeline:

from employees
sort salary
map by:title [    # or `compute`?
  rank salary
]

This way, there is less parameters users have to remember, while still being intuitive.

The downside is that the SQL output would also contain ORDER BY, which could only be avoided with putting another sort null at the end.

---

Naming

I don't like compute because it does not covey the "many to many" aspect of these functions.

I don't like map because in MapReduce, it means "one value to one value".

I don't like shuffle, because it does not convey that we are adding a new column.

I don't like partition, because in a lot of cases, there will be only one partition.

I don't like window, because it does not make sense for rank, quantile and many other functions.

Maybe something about fully-connected layer of a neural network? Something about vector functions? Something about new column for every row?

---

... is that each transform should leave a valid result

Fully agree.

[max-sixty]

If we go this way, compiler will be able to infer the cardinality of the rows in resulting frame: only one, many or many for a set of keys. So we could actually provide correct typing for cases like #54, which is a huge plus.

I strongly agree, this could be really good

[max-sixty]

I've been trying to think about what the OVER (PARTITION BY ...)s are doing conceptually. I started down a few paths, and came back to where I started, so there's no need to read the whole thing...

---

A reduction function is quite simple; it just reduced each group to a single row:

A vector function with a partition / grouping creates a mini-table table for each group. In SQL, because there's generally no nesting (i.e. everything is a flat 2D table) the by field gets "unnested":

---

An aside: in databases with nesting, the OVER (PARTITION BY foo) function is equivalent to doing:

1. ARRAY_AGG ... GROUP BY title to get the arrays of engineer -> [50,200], manager -> [120,130,150], etc
2. Run the vector function over each group (making the middle result)
3. Unnest the by so title fills down (making the final result)

---

So one option for this is:

• Use something like group or map or nest to mean "build the groups", and it would take a quasi-pipeline to run over each group. A bit like the dplyr / spark / pandas API, but the function would be an argument to this rather than a subsequent transform (consistent with every transform leaving a correct result).
• Use something like compute to mean "apply this many-to-many function" (or another term, I know you say you don't like it, and I agree on the specific reason, though overall it seems decent relative to the other choices)

So that would mean we'd have something like:

from employees
group title (
  sort title
  compute [sum salary]
)

But if we do that, then we should be doing that for aggregates too:

from employees
group title (
  aggregate [sum salary]
)

---

I can see the elegance of that. I'm obv hesitant to make a big change to the language at this point, and I'd need to sit on it for a couple of days before having a view. My sense is that the current model of doing aggregate by:title [] rather than than group title (aggregate [...]) is broadly equivalent and possibly easier to scan. The current approach is almost as orthogonal — we have aggregate for the reduction functions and compute (or similar) for the vector functions, not some long list. aggregate will also cover the case of making arrays.

---

So that brings us back to where we started!

Naming

I'm not sure on the word. I agree compute isn't ideal. calculate is basically the same. map in theory is nice — it is literally a mapping — and it's not always one-to-one. But maybe it has too much baggage. Its synonyms, like morph or functor are too weird. vec is too technical.

Sort

I get that you're less keen on pipelines-in-pipelines. I agree it's some mental overhead in simple cases, and so we shouldn't require them. But it does introduce a nice orthogonality. Say we want to "compute the two best selling items with a price higher than $100". It would be very nice to have:

from orders
{expression}

...for the case of the whole table, and:

from orders
compute by:country (
  {expression}
)

...for the case of each group. Which supplying sort:foo or having the sort outside the compute doesn't achieve.

Indeed, note that in the current language, we have

from employees
aggregate [
  (salary * 2 | sum)    # possible, rather than `sum (salary * 2)`
]

...as a mini-pipeline.

BUT that said, I don't have a fully fleshed out proposal, and I'd be happy to go with the sort:foo for the moment. I prefer that to having sort outside the pipeline, since that specifies too much work — sorting the whole table rather than within each group.

[aljazerzen]

The idea behind having sort in the outer pipeline instead of as a param, it that if you have two consecutive sorts, we can use only the last when translating to SQL. But if there is compute between the two sorts, it is affected by the first sort. This way, you reduce the number or params one has to remember. It can also think of the sorts as they have direct effect only the the conceptual model of current pipeline value, while only some of the sorts have to be translated into ORDER BY for SQL statement to produce the same result as the conceptual model.

(I hope that makes sense...)

---

About the group: I really like it.

As I've written here #9 we have common use-case where it would make sense for take to also have by parameters, because in-effect you want to group by some fields and take only the top row ordered by some other column.

So aggregate, compute and take need by parameter and two of them also need sorting. Unifying them under a group context seems an elegant solution.

But I would propose a few changes to the syntax:

Group:

from employees
group title (
  sort salary
  derive [r: rank]  # compute is the same a derive within group context
  select [count - r]
)

from employees
group title (
  aggregate [sum salary]
)

from employees
group title (
  sort salary order:desc
  take 1      # this will return all columns, but only the row within a group that contains the highest salary
)

Group essentially introduces a new context where it is allowed to use aggregate, select, derive, sort and take. The normal context can use all transforms, but aggregate will always reduce to a single number and using sum in a select will produce a SELECT SUM(...) OVER ().

Two things:

• it would be attentive to the parser if we would replace parenthesis (pipeline) with braces {pipeline}. It would make it much easier to parse inline and frame pipelines.
• we should go and start writing queries with this change, before starting to write any code. Maybe rewrite all the examples and add new ones. If it does feel more natural, this is the way to go.

[max-sixty]

Great, I'm thinking about this. It would be quite a change!

It does seem to be quite nice, in both conceptual elegance and readability. You're right that to really understand we should write some examples.¹

Thanks for the examples, they're good. I agree with your points.

---

Much more narrowly:

The idea behind having sort

I very much understood the point the sort as the prior transformation — I just thought it was less coherent to have an integral part of the transformation outside of the main block. (it does fit with the pipeline notion though)

it would be attentive to the parser if we would replace parenthesis (pipeline) with braces {pipeline}. It would make it much easier to parse inline and frame pipelines.

Would this be so (expression) is an parenthesized expression, but {pipeline} was required for all pipelines? We previously had that anything parenthized expression with line breaks was a pipeline (or more specifically any line break was a pipeline outside of a list or prior to a new statement like table).

Footnotes

1. Though I am most of the way through a big update to how the documentation works with examples, hopefully I'll get that out so we don't have conflicts... ↩

[aljazerzen]

# https://www.databasestar.com/complex-sql-query-example
# https://www.databasestar.com/sample-bookstore-database/

from co:cust_order
join ol:order_line [co.order_id = ol.order_id]
derive [
  order_month:s"DATE_FORMAT({co.order_date}, '%Y-%m')",
  order_day:s"DATE_FORMAT({co.order_date}, '%Y-%m-%d')",
]
group [order_month, order_day] (
  aggregate [
    num_orders:s"COUNT(DISTINCT {co.order_id})"
    num_books:count ol.book_id
    total_price:sum ol.price
  ]
)
group [order_month] (
  sort order_day order:asc
  select running_total_num_books:sum num_books
)
group [] (
  sort order_day order:asc
  select num_books_last_week:lag num_books 7
)
sort order_day order:asc

How does it look?

[max-sixty]

Here's one pass:

• The main change is to not use group if we're not grouping by anything — my vision of this change was that we could make PRQL even more orthogonal by having functions within a group scope operate on groups exactly the same way that they would operate on a full table without the group scope. But that means that it doesn't make sense to have an empty group.
  • I also wasn't sure whether I was understanding the intent of the existing query — what does the table look like after the group [order_month] transform? Presumably it's no longer possible to get the previous week's sales at that point. Forgive me if I'm missing something!
• (Ironically given the subject of the issue), I'm still not sure how to specify window / analytic functions!

  • Should we have a specific transform for "functions which use other values in the column" — the definition of window functions — or are they just functions? i.e. is this OK:

    derive num_books_last_month: lag num_books 1
    

    or do we need:

    window (derive num_books_last_month: lag num_books 1)
    

    or:

    derive (
       num_books_last_month: window lag num_books 1
    )
    

  • Where do we define window attributes? On the function? On the window (or whatever name we use?

    • For a full list of things that can be in a window clause this reference was helpful: https://cloud.google.com/bigquery/docs/reference/standard-sql/analytic-function-concepts#def_window_frame

  • I don't like window, because it does not make sense for rank, quantile and many other functions.

    I'm less averse to the name window after thinking about it — it is a window over the column. It's not a moving window in the case of rank / quantile, but it says "look at the whole column rather than just my row"

  • We could use designations like rolling or expanding, which would make describing common windows simpler. It would bring us to a synthesis of a pandas / spark specification and a SQL spec.

  • I definitely think that unifying group by and partition by into a single orthogonal concept would solve one of the existing pain points of SQL window functions.

• I made a couple of cosmetic changes / roadmap changes. (Possibly that's a distraction)

from co:cust_order
-join ol:order_line [co.order_id = ol.order_id]
+join ol:order_line [order_id]
derive [
-  order_month:s"DATE_FORMAT({co.order_date}, '%Y-%m')",
-  order_day:s"DATE_FORMAT({co.order_date}, '%Y-%m-%d')",
+  order_month:f"{co.order_date:%Y-%m}",
+  order_day:f"{co.order_date:%Y-%m-%d}",
]
group [order_month, order_day] (
  aggregate [
    num_orders: s"COUNT(DISTINCT {co.order_id})"
    num_books: count ol.book_id
    total_price: sum ol.price
  ]
)
group [order_month] (
  sort order_day order:asc
  select running_total_num_books: sum num_books
)
-group [] (
-  sort order_day order:asc
-  select num_books_last_week:lag num_books 7
- )
+sort order_day order:asc
+derive num_books_last_month: lag num_books 1  # Not sure about this
- sort order_day order:asc

Overall I think we're onto something but still need to pin down some of the details :). Your examples are v helpful in that regard.

[max-sixty]

One concern about the group approach is that it could make doing the simplest queries a bit more verbose. Say we just want to "select the sum of salary by country":

SQL:

SELECT
  title,
  SUM(salary)
FROM
  employees
GROUP BY
  title

Existing PRQL:

from employees
aggregate by:title [sum salary]

Proposed PRQL:

from employees
group title (
  aggregate [sum salary]
)

But:

• It's not that much more verbose
• I generally think we should focus on making the difficult queries much more readable and coherent, rather than making simple queries a bit more concise.

To focus on the orthogonality point, there is a nice orthogonality to both:

Proposed PRQL — aggregation over groups

from employees
group title (
  aggregate [sum salary]
)

Proposed PRQL — no groups:

from employees
aggregate [sum salary]   # same transform outside a group, same effect

Proposed PRQL — using groups as partitions:

from employees
group title (        # No need for `GROUP BY` & `PARTITION BY`, similar to how we consolidate `WHERE` and `HAVING`
  window [sum salary]
)

[aljazerzen]

Oh, yeah I made a mistake:

from co:cust_order
join ol:order_line [order_id]
derive [
  order_month:f"{co.order_date:%Y-%m}",
  order_day:f"{co.order_date:%Y-%m-%d}",
]
group [order_month, order_day] (
  aggregate [
    num_orders: s"COUNT(DISTINCT {co.order_id})"
    num_books: count ol.book_id
    total_price: sum ol.price
  ]
)
group [order_month] (
  sort order_day order:asc
-  select running_total_num_books: sum num_books
+  derive running_total_num_books: sum num_books
)
sort order_day order:asc
derive num_books_last_month: lag num_books 1

[aljazerzen]

I would change only your last example:

from employees
group title (        # No need for `GROUP BY` & `PARTITION BY`, similar to how we consolidate `WHERE` and `HAVING`
  select [sum salary]  # Or derive, depending on what you want
)

So rules would be as follows:

• select/derive
  • can contain only scalar functions (FLOOR) and window functions (SUM, LAG, RANK)
  • will not change the number of rows,
  • when used within a group, they will produce PARTITION BY
  • order by is determined by last preceding sort (within or outside of group)
  • window is determined by parameters or select/derive¹
• aggregate
  • can contain only aggregation functions (SUM)
  • will reduce rows to the number of partitions (which is one when not used in a group)

Now:

• there is no need for window, compute or map

• select/derive/aggregate are completely orthogonal to group

• this is OK:

  derive num_books_last_month: (lag num_books 1)
  

• the query could be simplified even further, because we can move sort earlier in the pipeline:

...
group [order_month, order_day] (
  aggregate [
    num_orders: s"COUNT(DISTINCT {co.order_id})"
    num_books: count ol.book_id
    total_price: sum ol.price
  ]
)
+sort order_day order:asc
group [order_month] (
-  sort order_day order:asc
   derive running_total_num_books: sum num_books
)
-sort order_day order:asc
derive num_books_last_month: lag num_books 1

Yes, simple queries will be a bit more verbose, but complex queries will be easier to write and understand. I think that outweighs the cons by a lot.

Footnotes

1. could be a window context just as group, but what about window functions within group? I think having select/derive params is cleaner. ↩