A recent SQL question

--*--BEGIN QUESTION--*--
In lieu of our internal guru being available I was wondering if anyone would be able to help me figure out how to query the data I need.

table1 - contract data

contractId subTaskId column1 column2 column_N
1 1 meta1 meta2 metaN
1 2 meta1 meta2 metaN
1 3 meta1 meta2 metaN
1 4 meta1 meta2 metaN
2 1 meta1 meta2 metaN
2 2 meta1 meta2 metaN
2 3 meta1 meta2 metaN
table2 - workflow tracking for each contract subTask

contractId subTaskId taskStep processStep column1 column_N
1 1 1 Processing meta1 metaN
1 1 2 Review meta1 metaN
1 1 3 Routing meta1 metaN
1 2 1 Processing meta1 metaN
1 2 2 Routing meta1 metaN
1 3 1 Processing meta1 metaN
1 3 2 Review meta1 metaN
1 3 3 Routing meta1 metaN
1 3 4 Final meta1 metaN
1 4 1 Processing meta1 metaN
1 4 2 Final meta1 metaN
2 1 1 Final meta1 metaN
2 2 1 Review meta1 metaN
2 3 1 Final meta1 metaN

Results

contractId subTaskId processStep table1.columns table2.columns
1 1 Routing table1.columns table2.columns
1 2 Routing table1.columns table2.columns
1 3 Final table1.columns table2.columns
1 4 Final table1.columns table2.columns
2 1 Final table1.columns table2.columns
2 2 Review table1.columns table2.columns
2 3 Final table1.columns table2.columns

The column1/2/N is just to represent that each table has a bunch of additional columns of metadata, most of which I'd like to be present in my results.

The following is about as close as I was able to get(newbie), but I couldn't figure out how to also bring in the data columns from table b.

SELECT
    a.*
FROM
    table1 a
    INNER JOIN
        (SELECT contractId, subTaskId, MAX(taskStep) AS taskStep
         FROM table2 GROUP BY contractId, subTaskId) AS b ON
        a.contractId = b.contractId
        AND a.subTaskId = b.subTaskId

Thank you!

--*--END QUESTION--*--

--*--BEGIN ANSWER--*--
Which database are you using? I'll assume Postgres because why not. :)

Others are asking what you're looking for because it isn't clear. My best guess is you want, per each contractId/subTaskId grouping, the row with the maximum taskStep within that grouping. The other columns come along for the ride.

In that case I'd say you're on the right track. Let's ignore the join for starters, to simplify the problem. I'll only look at table2.

So again, what you've started writing looks pretty good:

mwdb=# SELECT contractId, subTaskId, MAX(taskStep) AS taskStep
mwdb-#          FROM table2 GROUP BY contractId, subTaskId
mwdb-# ORDER BY contractId, subTaskId; --I added an ORDER BY so it looks nicer
 contractid | subtaskid | taskstep
------------+-----------+----------
          1 |         1 |        3
          1 |         2 |        2
          1 |         3 |        4
          1 |         4 |        2
          2 |         1 |        1
          2 |         2 |        1
          2 |         3 |        1
(7 rows)

Eyeballing these results and comparing to your expected output, so far looks good! It's the right number of rows and taskstep corresponds to the processStep you want. But how to pull in processStep?

I'll let you in on a little trick. When you use aggregate functions with a group by, you can't just (except in MySQL - but they cheat :)) pull in any arbitrary other column you want. See below:

mwdb=# SELECT contractId, subTaskId, MAX(taskStep) AS taskStep, processstep
mwdb-# FROM table2 GROUP BY contractId, subTaskId;
ERROR:  column "table2.processstep" must appear in the GROUP BY clause or be used in an aggregate function
LINE 1: ...contractId, subTaskId, MAX(taskStep) AS taskStep, processste...

But what if we slap an arbitrary aggregate function to bring it along for the ride? This is a trick I often use if the "along for the ride" column is the same for each combination of grouping columns. A quick demo:

--here's my test table
mwdb=# SELECT * FROM delete_me;
 a | b | c
---+---+---
 1 | 1 | 1
 1 | 2 | 1
 1 | 3 | 1
 2 | 1 | 1
 2 | 2 | 1
(5 rows)

--and here's my query that brings column c along for the ride
mwdb=# SELECT a, MAX(b) AS max_b, MIN(c) AS c FROM delete_me GROUP BY a;
 a | max_b | c
---+-------+---
 1 |     3 | 1
 2 |     2 | 1
(2 rows)

I could have easily used MAX(c) instead of MIN(c) - it doesn't really matter. BUT we cannot use this trick in our original problem. This is because processStep is not unique for a given combination of contractId, subTaskId. If we try this trick we will essentially be grabbing an arbitrary value of processStep, like so:

--WRONG
mwdb=# SELECT contractId, subTaskId, MAX(taskStep) AS taskStep, MIN(processstep) AS processStep
FROM table2 GROUP BY contractId, subTaskId
mwdb-# ORDER BY contractId, subTaskId;
 contractid | subtaskid | taskstep | processstep
------------+-----------+----------+-------------
          1 |         1 |        3 | Processing
          1 |         2 |        2 | Processing
          1 |         3 |        4 | Final
          1 |         4 |        2 | Final
          2 |         1 |        1 | Final
          2 |         2 |        1 | Review
          2 |         3 |        1 | Final
(7 rows)

Comparing this to your expected results, we can see that processStep is not always correct. So now what?

Often I've seen coders solve this problem by writing a query that scans the table twice like so:

mwdb=# SELECT table2.contractId, table2.subTaskId, table2.taskstep, table2.processstep                                                                                          FROM table2 JOIN (SELECT contractId, subTaskId, MAX(taskstep) max_taskstep FROM table2 GROUP BY contractId, subTaskId) max_table2 ON table2.contractId=max_table2.contractId AND table2.subTaskId=max_table2.subTaskId AND table2.taskstep = max_table2.max_taskstep
ORDER BY table2.contractId, table2.subTaskId, table2.taskstep, table2.processstep
mwdb-# ;
 contractid | subtaskid | taskstep | processstep
------------+-----------+----------+-------------
          1 |         1 |        3 | Routing
          1 |         2 |        2 | Routing
          1 |         3 |        4 | Final
          1 |         4 |        2 | Final
          2 |         1 |        1 | Final
          2 |         2 |        1 | Review
          2 |         3 |        1 | Final
(7 rows)

TA-DA!!! However, this is not the best solution. Like I said before, we have to scan the table twice, which you should avoid in general if possible. Besides it's not the most elegant solution out there. However it's perfectly acceptable if it meets your performance criteria. Maybe you don't care about performance at all for your purposes.

If we EXPLAIN ANALYZE this query, we can see proof that the Postgres query planner decided to scan table2 twice. In our tiny table it doesn't really matter, but what if we had a billion rows in the table?

mwdb=# EXPLAIN ANALYZE SELECT table2.contractId, table2.subTaskId, table2.taskstep, table2.processstep FROM table2 JOIN (SELECT contractId, subTaskId, MAX(taskstep) max_taskstep FROM table2 GROUP BY contractId, subTaskId) max_table2 ON table2.contractId=max_table2.contractId AND table2.subTaskId=max_table2.subTaskId AND table2.taskstep = max_table2.max_taskstep
mwdb-# ORDER BY table2.contractId, table2.subTaskId, table2.taskstep, table2.processstep;
                                                                          QUERY PLAN                                                                       
--------------------------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=100.38..100.39 rows=1 width=44) (actual time=0.137..0.138 rows=7 loops=1)
   Sort Key: table2.contractid, table2.subtaskid, table2.taskstep, table2.processstep
   Sort Method: quicksort  Memory: 25kB
   ->  Merge Join  (cost=90.56..100.37 rows=1 width=44) (actual time=0.107..0.120 rows=7 loops=1)
         Merge Cond: ((table2.contractid = table2_1.contractid) AND (table2.subtaskid = table2_1.subtaskid) AND (table2.taskstep = (max(table2_1.taskstep))))
         ->  Sort  (cost=55.27..57.22 rows=780 width=44) (actual time=0.071..0.071 rows=14 loops=1)
               Sort Key: table2.contractid, table2.subtaskid, table2.taskstep
               Sort Method: quicksort  Memory: 26kB
               ->  Seq Scan on table2  (cost=0.00..17.80 rows=780 width=44) (actual time=0.049..0.057 rows=14 loops=1)
         ->  Sort  (cost=35.29..35.79 rows=200 width=12) (actual time=0.032..0.032 rows=7 loops=1)
               Sort Key: table2_1.contractid, table2_1.subtaskid, (max(table2_1.taskstep))
               Sort Method: quicksort  Memory: 25kB
               ->  HashAggregate  (cost=23.65..25.65 rows=200 width=12) (actual time=0.017..0.017 rows=7 loops=1)
                     Group Key: table2_1.contractid, table2_1.subtaskid
                     ->  Seq Scan on table2 table2_1  (cost=0.00..17.80 rows=780 width=12) (actual time=0.002..0.004 rows=14 loops=1)
 Planning time: 0.388 ms
 Execution time: 0.503 ms
(17 rows)

So how do we avoid scanning the table twice? Enter our savior, window functions!!!

Let's throw away the group by, and instead use the row_number() over (partition by contractid, subtaskid order by taskstep desc) window function. That probably looks like random gibberish if you haven't seen it before, but it all it means is: let's generate a row number (1, 2, 3, 4, etc.) that resets to one for every combination of contractid, subtaskid, and start counting from the largest taskstep within that combo. Why do we want this number? Well if we start with the largest taskstep for every contractid, subtaskid combo, then we know that #1 is the one we want to keep. We can throw out the rest!

Let's see it in action:

mwdb=# SELECT contractid, subtaskid, taskstep, processstep, ROW_NUMBER() OVER(PARTITION BY contractid, subtaskid ORDER BY taskstep DESC) AS rn
FROM table2
ORDER BY contractId, subTaskId;

 contractid | subtaskid | taskstep | processstep | rn
------------+-----------+----------+-------------+----
          1 |         1 |        3 | Routing     |  1
          1 |         1 |        2 | Review      |  2
          1 |         1 |        1 | Processing  |  3
          1 |         2 |        2 | Routing     |  1
          1 |         2 |        1 | Processing  |  2
          1 |         3 |        4 | Final       |  1
          1 |         3 |        3 | Routing     |  2
          1 |         3 |        2 | Review      |  3
          1 |         3 |        1 | Processing  |  4
          1 |         4 |        2 | Final       |  1
          1 |         4 |        1 | Processing  |  2
          2 |         1 |        1 | Final       |  1
          2 |         2 |        1 | Review      |  1
          2 |         3 |        1 | Final       |  1
(14 rows)

Now the task from here is simple. Keep only the rows with rn=1!

mwdb=# SELECT contractid, subtaskid, taskstep, processstep FROM (
mwdb(#   SELECT contractid, subtaskid, taskstep, processstep, ROW_NUMBER() OVER(PARTITION BY contractid, subtaskid ORDER BY taskstep DESC) AS rn
mwdb(#   FROM table2
mwdb(# ) sub
mwdb-# WHERE rn=1
mwdb-# ORDER BY contractId, subTaskId;
 contractid | subtaskid | taskstep | processstep
------------+-----------+----------+-------------
          1 |         1 |        3 | Routing
          1 |         2 |        2 | Routing
          1 |         3 |        4 | Final
          1 |         4 |        2 | Final
          2 |         1 |        1 | Final
          2 |         2 |        1 | Review
          2 |         3 |        1 | Final
(7 rows)

And that's your final answer! But before we go, let's prove that it's not scanning the table twice:

mwdb=# EXPLAIN ANALYZE SELECT contractid, subtaskid, taskstep, processstep FROM (SELECT contractid, subtaskid, taskstep, processstep, ROW_NUMBER() OVER(PARTITION BY contractid, subtaskid ORDER BY taskstep DESC) AS rn FROM table2) sub WHERE rn=1 ORDER BY contractId, subTaskId;

                                                      QUERY PLAN                                                     
-----------------------------------------------------------------------------------------------------------------------
 Subquery Scan on sub  (cost=55.27..82.57 rows=4 width=44) (actual time=0.069..0.096 rows=7 loops=1)
   Filter: (sub.rn = 1)
   Rows Removed by Filter: 7
   ->  WindowAgg  (cost=55.27..72.82 rows=780 width=44) (actual time=0.064..0.086 rows=14 loops=1)
         ->  Sort  (cost=55.27..57.22 rows=780 width=44) (actual time=0.054..0.055 rows=14 loops=1)
               Sort Key: table2.contractid, table2.subtaskid, table2.taskstep DESC
               Sort Method: quicksort  Memory: 26kB
               ->  Seq Scan on table2  (cost=0.00..17.80 rows=780 width=44) (actual time=0.008..0.013 rows=14 loops=1)
 Planning time: 0.197 ms
 Execution time: 0.168 ms
(10 rows)

I'll clean the formatting up on this post tomorrow perhaps. It's late and I have to go to bed. :)

Last-second note: To be fair, it did do a "subquery scan on sub" to get just the rn=1 rows, in addition to the "seq scan" on table2. The first query did two "seq scans", so in a sense, our new query did scan every row twice. So is this any better? Well in most real world cases, the window function query is still a better bet. You would often have a where clause on the "sub" query, and best to avoid having to filter the data twice. (Imagine a billion rows in the table and a complicated where clause...)

--*--END ANSWER--*--

Wow, MySQL finally has window functions now!

Aaaand they're buggy - https://stackoverflow.com/questions/49700278/distinct-and-lag-window-function.

Postgres queries using Window Functions, Part Deux

Since my post Postgres query using window functions, recursive query is my most popular of all-time (maybe not saying so much for my little blog :)), I thought I would write more on the subject. How about some useful examples?

A Cumulative Sum

First time I saw this my mind was blown - I didn't realize SQL could be so flexible! Maybe I have a table that represents sales per day:

mwrynn=# create table sales (sales_date date, dept varchar, total_sales numeric(10,2));

/* after some inserts which I'll skip, we have 4 days per dept (maybe it's a department store database) */

mwrynn=# select * from sales;

 sales_date | dept  | total_sales 

------------+-------+-------------

 2016-01-01 | men   |      100.00

 2016-01-01 | women |      140.00

 2016-01-02 | men   |       85.00

 2016-01-02 | women |       70.00

 2016-01-03 | men   |      135.00

 2016-01-03 | women |      135.00

 2016-01-04 | men   |      200.00

 2016-01-04 | women |      240.00

(8 rows)

/* now let's get a cumulative sum for each dept per day */

mwrynn=# select sales_date, dept, total_sales, sum(total_sales) over (partition by dept order by sales_date ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) from sales;

 sales_date | dept  | total_sales |  sum   

------------+-------+-------------+--------

 2016-01-01 | men   |      100.00 | 100.00

 2016-01-02 | men   |       85.00 | 185.00

 2016-01-03 | men   |      135.00 | 320.00

 2016-01-04 | men   |      200.00 | 520.00

 2016-01-01 | women |      140.00 | 140.00

 2016-01-02 | women |       70.00 | 210.00

 2016-01-03 | women |      135.00 | 345.00

 2016-01-04 | women |      240.00 | 585.00

(8 rows)

So simple! But the syntax is a little unintuitive, at least to me. Let's break down the key parts.

sum(total_sales): this is just your basic aggregate function sum()

over (): this means to apply the sum function OVER specific subsets, or partitions, of our data.

partition by: defines the partitions. Here we are telling Postgres, "split up the data by dept, aka into men and women, and apply our sum function to each as a completely separate subset (partition)"

order by: sort each partition by this clause, sales_date in our case.

ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: means to apply the sum for the current row and all preceding rows. This is known as the windowing frame. This is the key to achieving a cumulative sum - for each row, we want all the previous rows + the current row, but not the subsequent rows...

We can also run a simpler version of the query, taking the whole dataset as one partition instead of splitting by men and women:

 mwrynn=# select sales_date, dept, total_sales, sum(total_sales) over (order by sales_date ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) from sales;

 sales_date | dept  | total_sales |   sum   

------------+-------+-------------+---------

 2016-01-01 | men   |      100.00 |  100.00

 2016-01-01 | women |      140.00 |  240.00

 2016-01-02 | men   |       85.00 |  325.00

 2016-01-02 | women |       70.00 |  395.00

 2016-01-03 | men   |      135.00 |  530.00

 2016-01-03 | women |      135.00 |  665.00

 2016-01-04 | men   |      200.00 |  865.00

 2016-01-04 | women |      240.00 | 1105.00

(8 rows)

The rank() Function

We can riff off this same table/query and ask Postgres another query -- give me the rank of sales per dept, lowest to highest. I want to see on which date I sold the least, the most and everything in between. The key is in the rank() function...

mwrynn=# select sales_date, dept, total_sales, rank() over (partition by dept order by total_sales) from sales;

 sales_date | dept  | total_sales | rank 

------------+-------+-------------+------

 2016-01-02 | men   |       85.00 |    1

 2016-01-01 | men   |      100.00 |    2

 2016-01-03 | men   |      135.00 |    3

 2016-01-04 | men   |      200.00 |    4

 2016-01-02 | women |       70.00 |    1

 2016-01-03 | women |      135.00 |    2

 2016-01-01 | women |      140.00 |    3

 2016-01-04 | women |      240.00 |    4

(8 rows)

The ntile() Function

This function is called ntile(), perhaps as in a generic version of "quartile" or "percentile", in which you can specify any number. Let's say I want to put the above sales into buckets. I only have a small amount of data so we'll use a bucket number of 2 -- this allows us to bucket each row into either the lesser half of sales or the greater half.

mwrynn=# select sales_date, dept, total_sales, ntile(2) over (partition by dept order by total_sales) from sales;

 sales_date | dept  | total_sales | ntile 

------------+-------+-------------+-------

 2016-01-02 | men   |       85.00 |     1

 2016-01-01 | men   |      100.00 |     1

 2016-01-03 | men   |      135.00 |     2

 2016-01-04 | men   |      200.00 |     2

 2016-01-02 | women |       70.00 |     1

 2016-01-03 | women |      135.00 |     1

 2016-01-01 | women |      140.00 |     2

 2016-01-04 | women |      240.00 |     2

(8 rows)

Simple enough, right? So again we've partitioned by the mens vs. women dept, and we're getting the lesser half of sales (bucket 1) vs. the greater half of sales (bucket 2).

Wrapping Up

Well that's enough of window functions for now. We've only begun to scratch the surface, so I may come back and add to this post. If you have any questions or suggestions, let me know!

Postgres query using window functions, recursive query

As Tom Kyte says, "Analytics rock. Analytics roll." Among other things, Oracle's analytic queries allow a row in the resultset to reference other rows in the same resultset. This is tremendously powerful stuff. If you're not familiar with analytics, take a look at some of the magic Tom performs in that thread I just linked. Some simple use cases:
1) Get a cumulative sum - maybe you have a table of individual purchases and want to see how the sum of purchases progresses over time.
2) Perform your typical GROUP BY query using an aggregate function, BUT you don't want to roll up the data. You want to see every row in the table you're querying, with the AVG (or MAX, SUM, whatever) alongside it. See the first example in this Postgres doc.

But did you know Postgres now has Analytics too, as of 8.4? They are called Window Functions in the Postgres world. (I suppose you could call them "queries that use window functions", or even "analytic queries" as Oracle can't force you not to use the phrase.)

I had a requirement. Stripped down to the core, the requirement was to translate this:

ID | expire
---+---------
 7 |  8/20/2011
 6 | 
 5 |  8/15/2011
 4 |  8/15/2011
 3 |
 2 |
 1 |  8/10/2011

To this:

 ID | expire
---+---------
 7 |  8/20/2011
 6 |  8/15/2011
 5 |  8/15/2011
 4 |  8/15/2011
 3 |  8/10/2011
 2 |  8/10/2011
 1 |  8/10/2011

The translation is: If expire is null, look down to the next older expire. If THAT one is null too, look down again, and so on. The solution that worked very well for me was to use Window Functions, plus recursive ("WITH RECURSIVE") queries.

Edit: A helpful commenter provided this simpler solution: select
 id, max(expire) over (order by id rows between unbounded preceding and current row) as expire
 from t 
order by id desc

The windowing clause in this query says: order the rows by id ascending, and for each row, get the max value of expire looking backwards from this row to all previous rows. Pretty simple! The Oracle solution should be the same, btw.

I'll leave my older code and thought processes in this article for posterity.

Step 1 was to use Window Functions to structure a view of the table above, such that the previous and next IDs could be found in each row, almost like a linked list data structure:

ID   prev_ID  next_id  expire

---  -------  -------  --------

 7     null      6     8/20/2011

 6      7        5

 5      6        4     8/15/2011

 4      5        3     8/15/2011

 3      4        2

 2      3        1

 1      2       null   8/10/2011

(In the real world, my IDs aren't always such simple, gap-free numbers, so I cannot use any simple math tricks, such as finding prev_ID by subtracting 1 from ID.)

Step 2 was to use WITH RECURSIVE to traverse from row to row, via the pointers in our linked list, to form the end resultset we're looking for. This entailed another little trick. Coalesce two expires (the current and the parent) to make the non-null values bubble up.

I'll post the SQL when I get to it.
Creating the view, transaction, with window functions:

CREATE VIEW transaction AS
select
id,
lag(id) over (partition by account_id order by id asc) lag_id,
lead(id) over (partition by account_id order by id asc) lead_id,
expire
from trans;

Recursive query against transaction:

WITH RECURSIVE recur(
id,
expire
) AS (
select
id,
expire
from transaction where lag_id is null
union all
select
transaction.id,
coalesce(transaction.expire, recur.expire)
from transaction, recur
where transaction.lag_id=recur.id
)
select * from recur;

I'm really pleased with the advanced querying features Postgres has been putting out. Actually, WITH RECURSIVE is ANSI standard, as it turns out, and you can even find it in SQL Server, DB2 and Oracle 11g (though Oracle has had its own way of performing recursive queries using CONNECT BY, for ages).