SQL Oracle - 多处理器调度：贪心数字分区

Question

是否有SQL语句来进行贪心数划分？ (甲骨文 19c)

我想在 N 个处理器之间分配作业。

示例，

给定以下工作负载数据集：

job
---
4
60
50
1
100
6

预期结果集（假设只有 N=2，其中关系分配给分配给它的作业数量最少的处理器）：

job  processor
---  ---------
100  1
 60  2
 50  2
  6  1
  4  1
  1  2

以下 table 可能有助于阐明这些处理器的分配方式。

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

分析函数和分层查询的某种组合似乎可以实现这一点，而无需诉诸过程代码。预先感谢您的想法和帮助。

Answer 1

您可以使用递归 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 是一个 db<>fiddle.

Answer 2

您可以使用以下类型创建流水线函数：

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

CREATE TYPE job_processor_list AS TABLE OF job_processor;

那么函数就是：

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;
/

其中，对于示例数据：

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;

然后：

SELECT *
FROM   TABLE( partition_jobs( 2 ) );

输出：

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

和：

SELECT *
FROM   TABLE( partition_jobs( 3 ) );

输出：

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

db<>fiddle here

SQL Oracle - 多处理器调度：贪心数字分区

SQL Oracle - Multiprocessor Scheduling: Greedy Number Partitioning

sql

oracle

greedy

analytic-functions

hierarchical-query