Is there an SQL statement to perform greedy number partitioning? (Oracle 19c)
I want to divide jobs among N processors.
Example,
Given the following workload data set:
job
---
4
60
50
1
100
6
Expected result set (assuming just N=2 where ties go to the processor with the fewest number of jobs assigned to it):
job processor
--- ---------
100 1
60 2
50 2
6 1
4 1
1 2
The following table may help clarify how those processors were assigned.
job processor length count
--- --------- ------ -----
100 1 100 1
60 2 60 1
50 2 110 2
6 1 106 2
4 1 110 3
1 2 111 3
Some combination of analytic functions and hierarchical queries seems like it could make this happen without having to resort to procedural code. Thanks in advance for your thoughts and assistance.
You can use a recursive CTE:
with tt as (
select job, row_number() over (order by job desc) as seqnum
from t
),
cte(job, seqnum, processor, proc1, proc2, lev) as (
select job, seqnum, 1, job as proc1, 0 as proc2, 1
from tt
where seqnum = 1
union all
select tt.job, tt.seqnum,
(case when cte.proc1 > cte.proc2 then 2 else 1 end),
(case when cte.proc1 > cte.proc2 then cte.proc1 else cte.proc1 + tt.job end),
(case when cte.proc1 > cte.proc2 then cte.proc2 + tt.job else cte.proc2 end),
lev + 1
from cte join
tt
on tt.seqnum = cte.seqnum + 1
)
select *
from cte
order by seqnum;
Here is a db<>fiddle.