Partitioning (and splitting) values to fill slots

user_1658533 0
Viewed 45

I have some sales data and I need to dispatch the quantities in available slots stored in a separate table.

Example of sales data:

id qty
1 1
2 1
3 1
4 1
5 3
6 9

create table sales (id serial primary key, qty int);

INSERT INTO sales (qty) VALUES (1),(1),(1),(1),(3),(9);

And here are the slots (size is cumulative):

name size
a 3
b 5
c 9

There is an "invisible" d slot for the remaining quantities. Of course, these slots are not fixed.

create table slots (id serial primary key, name text, size int);

insert into slots (name,size) values ('a',3),('b',5),('c',9);

This is the detailed process of the calculation (and expected result):

id qty used total slot comment
1 1 1 1 a
2 1 1 2 a
3 1 1 3 a Slot is full
4 1 1 4 b
5 3 1 5 b split this sale
5 cont. 2 6-7 c
6 9 2 8-9 c
6 cont. 7 10-16 d split again

My approach is the following:

WITH p1 AS (
    select sales.*,sum(qty) over (order by sales.id) AS tot 
    from sales 
    order by sales.id
)
, p2 AS (
    select p1.id
        ,p1.qty
        , 1+COALESCE(LAG(tot) OVER (ORDER BY p1.id) ,0) AS lag
        , p1.tot
    from p1
)
,p3 AS (
    SELECT id,qty,lag,tot
        , COALESCE( (SELECT id FROM slots WHERE lag<=size ORDER BY size LIMIT 1) , 999) AS slotmin
        , COALESCE( (SELECT id FROM slots WHERE tot<=size ORDER BY size LIMIT 1) , 999) AS slotmax
    FROM p2
)
SELECT p3.id
    ,p3.qty
    -- ,p3.lag
    -- ,p3.tot
    -- ,p3.slotmin
    -- ,p3.slotmax
    ,COALESCE(slots.size-lag+1,p3.qty) AS qtyconsumed
    ,1 AS so
from p3
LEFT JOIN slots ON slots.id=p3.slotmin AND slotmin<>slotmax
UNION
SELECT p3.id
    ,p3.qty
    -- ,p3.lag
    -- ,p3.tot
    -- ,p3.slotmin
    -- ,p3.slotmax
    ,COALESCE(p3.qty-(slots.size-lag+1),0) AS qtyconsumed
    ,2 AS so
from p3
LEFT JOIN slots ON slots.id=p3.slotmin
WHERE slotmin<>slotmax
ORDER BY id,so

I deliberately left some commented columns to ease understanding/debugging my mental process

Which gives the following result:

 id | qty | qtyconsumed | so 
----+-----+-------------+----
  1 |   1 |           1 |  1
  2 |   1 |           1 |  1
  3 |   1 |           1 |  1
  4 |   1 |           1 |  1
  5 |   3 |           1 |  1
    |     |           2 |  2
  6 |   9 |           2 |  1
    |     |           7 |  2
(8 lignes)

The code is pretty ugly and will only work for one split: I could very well have only one sale of qty=20 that should split to 4 slots.

My question unfolds in 2 parts:

  1. Is it possible to do that splitting in more than 2 slots without going through the mess of cursors or solutions alike? I am guessing WITH RECURSIVE but there could be something smarter.

  2. How can I optimize this (particularly the search for the closest slot in p3) because the real case involves millions of rows?

postgresql
1 Answers

I propose you a different approach based on the range types and range operations :

First we can calculate the range of quantities for every sale in the sales id order :

SELECT id, qty
     , int4range
          ( (1 + sum(qty) OVER w - qty) :: integer
          , sum(qty) OVER w :: integer
          , '[]'
          ) AS sale_range
  FROM sales
WINDOW w AS (ORDER by id)
 ORDER BY id

Then we can calculate the range of sizes for every slot in the slot size order :

SELECT name, size
     , int4range
          ( (1 + sum(size) OVER w - COALESCE(size, 0)) :: integer
          , CASE WHEN size IS NULL THEN NULL :: integer ELSE sum(size) OVER w :: integer END
          , '[]'
          ) AS slot_range
  FROM slots
WINDOW w AS (ORDER BY size)
 ORDER BY size

Finally we can simply JOIN both sub queries while testing the overlap between the sales ranges and the slots ranges in the ON clause. For the rows which match, the intersection between the sales range and the slot range provides the total value as expected, and the length of the intersected ranges (upper(range) - lower(range)) provides the used quantity :

WITH sales_ranges AS
(
SELECT id, qty
     , int4range
          ( (1 + sum(qty) OVER w - qty) :: integer
          , sum(qty) OVER w :: integer
          , '[]'
          ) AS sale_range
  FROM sales
WINDOW w AS (ORDER by id)
-- ORDER BY id -- this ORDER BY is useless here
), slots_ranges AS
(
SELECT name, size
     , int4range
          ( (1 + sum(size) OVER w - COALESCE(size, 0)) :: integer
          , CASE WHEN size IS NULL THEN NULL :: integer ELSE sum(size) OVER w :: integer END
          , '[]'
          ) AS slot_range
  FROM slots
WINDOW w AS (ORDER BY size)
-- ORDER BY size -- this ORDER BY is useless here
)
SELECT sa.id, sa.qty
     , upper(rg.range) - lower(rg.range) AS used
     , CASE
         WHEN upper(rg.range) = lower(rg.range) + 1
         THEN lower(rg.range) :: text
         ELSE lower(rg.range) || '-' || upper(rg.range) - 1
       END AS total
     , so.name AS slot
  FROM sales_ranges AS sa
 INNER JOIN slots_ranges AS so
    ON sa.sale_range && so.slot_range -- both ranges overlap
 CROSS JOIN LATERAL (SELECT sa.sale_range * so.slot_range) AS rg(range) -- compute the intersection of both ranges

The proposed solution assumes that slot "d" is created in table "slots" with a NULL size.

see the test result in dbfiddle

user_80600170
Related