SQL Oracle - Multiprocessor Scheduling: Greedy Number Partitioning

Question

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.

Answer 1

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.

Answer 2

You can create a pipelined function using the types:

CREATE TYPE job_processor AS OBJECT(
  job       NUMBER,
  processor NUMBER
);

CREATE TYPE job_processor_list AS TABLE OF job_processor;

Then the function is:

CREATE FUNCTION partition_jobs (
  num_processors IN PLS_INTEGER
) RETURN job_processor_list PIPELINED
IS
  processor_time     SYS.ODCINUMBERLIST := SYS.ODCINUMBERLIST();
  processor_id       PLS_INTEGER;
  min_processor_time TABLE_NAME.JOB%TYPE;
BEGIN
  processor_time.EXTEND( num_processors );

  FOR i IN 1 .. num_processors LOOP
    processor_time(i) := 0;
  END LOOP;

  FOR j IN ( SELECT job FROM table_name ORDER BY job DESC ) LOOP
    processor_id       := 1;
    min_processor_time := processor_time( processor_id );
    
    FOR i IN 2 .. num_processors LOOP
      IF processor_time(i) < min_processor_time THEN
        processor_id       := i;
        min_processor_time := processor_time( processor_id );
      END IF;
    END LOOP;
    
    PIPE ROW ( job_processor( j.job, processor_id ) );
    processor_time( processor_id ) := processor_time( processor_id ) + j.job;
  END LOOP;
END;
/

Which, for the sample data:

CREATE TABLE TABLE_NAME ( job ) AS
SELECT   4 FROM DUAL UNION ALL
SELECT  60 FROM DUAL UNION ALL
SELECT  50 FROM DUAL UNION ALL
SELECT   1 FROM DUAL UNION ALL
SELECT 100 FROM DUAL UNION ALL
SELECT   6 FROM DUAL;

Then:

SELECT *
FROM   TABLE( partition_jobs( 2 ) );

Outputs:

JOB | PROCESSOR
--: | --------:
100 |         1
 60 |         2
 50 |         2
  6 |         1
  4 |         1
  1 |         1

and:

SELECT *
FROM   TABLE( partition_jobs( 3 ) );

Outputs:

JOB | PROCESSOR
--: | --------:
100 |         1
 60 |         2
 50 |         3
  6 |         3
  4 |         3
  1 |         2

db<>fiddle here