PostgreSQL – Row by Row Subtraction with Single Input Number

postgresqlwindow functions

I want to subrtact dynamically from previous row subtraction result and as input i want to give a single number.

I have table a

CREATE TABLE a (id int, code text, qty numeric);

And data in it

INSERT INTO a (id,code,qty)
(1,'test',5),
(2,'test',3),
(3,'test',10);

1.sample – When input is 16 – Desired result would be:

id | qty
--------------
1  | 0
2  | 0
3  | 2

Calculation would be something like this

case when 16 > 5 then 16-5 else 5-16 end /* result 11, but displayed 0 */
case when 11 > 3 then 11-3 else 3-11 end /* result 8, but displayed 0 */
case when 8 > 10 then 8-10 else 10-8 end /* result 2 and displayed 2 */

2.sample – When input is 6 – Desired result would be:

id | qty
--------------
1  | 0
2  | 2
3  | 10 /* is optional to display */

Calculation would be something like this

case when 6 > 5 then 6-5 else 5-6 end /* result 1, but displayed 0 */
case when 1 > 3 then 1-3 else 3-1 end /* result 2 and displayed 2 */
case when ... end /* result 10, since input is fulfilled */

Best Answer

Fundamentally, this is a running total problem: for each row you are getting the running total of qty and subtracting a fixed value from it. More specifically, this is about how you want to use the running total. In this case you want to display a new qty value based on the result of the previous calculation. And there are essentially three cases here:

The result of the subtraction is negative.
The result of the subtraction exceeds the current row's qty.
The result is a non-negative value not exceeding qty.

The first case means that the supplied fixed value is more than necessary to exhaust the current running total – in other words, it exhausts all qty values from the beginning till the current row (including the current row). Therefore, we substitute a 0 for qty.

In the second case we just keep the qty, because the running total now exceeds the fixed value so much that the difference is greater than the current qty – so the latter stays intact.

The last case is when the fixed value either exactly covers all the qty values so far or is slightly less than the total but not much less: up to the amount of the current qty. In this case we show the difference between the running total and the fixed value.

The SQL for the above is this:

SELECT
  id,
  CASE
    WHEN balance < 0   THEN 0
    WHEN balance > qty THEN qty
    ELSE balance
  END AS qty
FROM
  (
    SELECT
      id,
      qty,
      SUM(qty) OVER (ORDER BY id ASC) - @fixedSum AS balance
    FROM
      a
  ) AS derived
;

where @fixedSum is the fixed value you want to subtract from the running total.

The central part of the solution is SUM(qty) OVER (ORDER BY id ASC) – the window aggregate function to get the running total of qty.

I am calculating the running totals here in a nested SELECT because the result of the subtraction needs to be referenced several times in a CASE expression, and you cannot reference a calculated column on the same level, you need to use nesting for that. The nesting can be in the form of either a derived table or a common table expression (CTE). The above solution uses a derived table.

There is a way to avoid nesting, though, and do all the calculations in a single SELECT using the functions LEAST and GREATEST:

SELECT
  id,
  qty,
  LEAST(
    qty,
    GREATEST(
      SUM(qty) OVER (ORDER BY id ASC) - @fixedSum,
      0
    )
  ) AS balance
FROM
  a

This method is much less straightforward than the one using CASE, though. Performance-wise, it would likely work the same.

The method works like this. First, you choose the greater value between the subtraction result and 0 using the GREATEST function. So, in terms of the cases listed above, if we have Case 1, GREATEST will yield 0. A non-zero result would mean we have one of the other cases.

The obtained value is then compared to the current qty and this time the lesser one of the two is chosen using the LEAST function. If we obtained 0 previously, LEAST will keep it. If we had the subtraction result and it is now found to be greater than qty, the LEAST function will give us qty (meaning this is Case 3). And if the difference happens to be less than qty, that is what LEAST will yield (Case 2).

Subqueries to determine most common attributes

SELECT DISTINCT title
FROM   archived
WHERE  showurl = (
   SELECT showurl
   FROM   archived
   GROUP  BY 1
   ORDER  BY count(*) DESC, 1
   LIMIT  1
   )
AND    reference = (
   SELECT reference
   FROM   archived
   GROUP  BY 1
   ORDER  BY count(*) DESC, 1
   LIMIT  1
   );

I added DISTINCT to the outer SELECT to fold duplicate titles. It's undefined what you need exactly.

Shorter with window functions

A more modern / sophisticated / elegant approach would be with two window functions in the ORDER BY clause, allowing for a very terse query:

SELECT title
FROM   archived
ORDER  BY count(*) OVER (PARTITION BY showurl)   DESC
         ,count(*) OVER (PARTITION BY reference) DESC
LIMIT 1;

Not necessarily faster than the first solution, though. Again, guessing what you might want exactly, I only retrieve a single winning title.

The trick here is to partition the rows by showurl and reference, run a count over each partition and order descending by that count. This way, you can determine a winner in a single query level.

This will not work, if there is no row with the most common showurl and the most common reference at the same time. Again, exact requirements would be needed ...

-> SQLfiddle demo.

PostgreSQL – Select Unique IDs Where Second Column is Unique

In Postgres, this is simpler with DISTINCT ON:

SELECT *
FROM (
   SELECT DISTINCT ON (sec)
          id, sec
   FROM   tbl
   ORDER  BY sec, id DESC
   ) sub
ORDER  BY id DESC
LIMIT  4;

Detailed explanation in this related answer on SO:

Select first row in each GROUP BY group?

For a big table and small LIMIT, neither this nor @a_horse's solution are very efficient. The subquery will plough through the whole table, wasting a lot of time ...

Recursive CTE

I have tried and failed to solve similar problems with a recursive CTE in the past and resorted to a procedural solution with PL/pgSQL. Example:

Self-join unique pairs

Finally, here is a working rCTE:

WITH RECURSIVE cte AS (
   (  -- parentheses required
   SELECT id, '{}'::int[] AS last_arr, ARRAY[sec] AS arr
   FROM   tbl
   ORDER  BY id DESC
   LIMIT  1
   )
   UNION ALL
   (
   SELECT b.id, c.arr
        , CASE WHEN b.sec = ANY (c.arr) THEN c.arr ELSE b.sec  || c.arr END
   FROM   cte c
   JOIN   tbl b ON b.id < c.id
   WHERE  array_length(c.arr, 1) < 4
   ORDER  BY id DESC
   LIMIT  1
   )
   )
SELECT id, arr[1] AS sec
FROM   cte
WHERE  last_arr <> arr;

It's not as fast or elegant as I had hoped for and not nearly as fast as the function below, but faster than the query above in my tests.

PL/pgSQL function

Fastest by far:

CREATE OR REPLACE FUNCTION f_first_uniq(_rows int)
   RETURNS TABLE (id int, sec int) AS
$func$
DECLARE
   _arr int[];
BEGIN
   FOR id, sec IN
      SELECT t.id, t.sec FROM tbl t ORDER BY t.id DESC
   LOOP
      IF sec = ANY (_arr) THEN
         -- do nothing
      ELSE
         RETURN NEXT;
         _arr := _arr || sec;
         EXIT WHEN array_length(_arr, 1) >= _rows;
      END IF;
   END LOOP;
END
$func$  LANGUAGE plpgsql;

Call:

SELECT * FROM f_first_uniq(4);

SQL Fiddle demonstrating all three.

Could be made out to work for any table with table and column names as parameters and dynamic SQL with EXECUTE ...

Why bother?

In a test table with only 30k rows the function ran 2000x faster than the above query (which already ran ~ 30% faster than a_horse's version). This difference grows with the size of the table. Performance of the function is about constant, while the query's performance gets progressively worse, since it tries to find distinct values in all of the table first. Try this in a table with a million rows ...