sql - 选择累积总和小于数字的地方(按优先级排序)

Question

我有一张 table ，上面有 id , cost , 和 priority列:

create table a_test_table (id number(4,0), cost number(15,2), priority number(4,0));

insert into a_test_table (id, cost, priority) values (1, 1000000, 10);
insert into a_test_table (id, cost, priority) values (2, 10000000, 9);
insert into a_test_table (id, cost, priority) values (3, 5000000, 8);
insert into a_test_table (id, cost, priority) values (4, 19000000, 7);
insert into a_test_table (id, cost, priority) values (5, 20000000, 6);
insert into a_test_table (id, cost, priority) values (6, 15000000, 5);
insert into a_test_table (id, cost, priority) values (7, 2000000, 4);
insert into a_test_table (id, cost, priority) values (8, 3000000, 3);
insert into a_test_table (id, cost, priority) values (9, 3000000, 2);
insert into a_test_table (id, cost, priority) values (10, 8000000, 1);
commit;

select 
    id,
    to_char(cost, '$999,999,999') as cost,
    priority
from 
    a_test_table;

        ID COST            PRIORITY
---------- ------------- ----------
         1    $1,000,000         10
         2   $10,000,000          9
         3    $5,000,000          8
         4   $19,000,000          7
         5   $20,000,000          6
         6   $15,000,000          5
         7    $2,000,000          4
         8    $3,000,000          3
         9    $3,000,000          2
        10    $8,000,000          1

从最高优先级(降序)开始，我想选择 cost 所在的行加起来少于(或等于)20,000,000 美元。

结果如下所示:

       ID COST            PRIORITY
---------- ------------- ----------
         1    $1,000,000         10
         2   $10,000,000          9
         3    $5,000,000          8
         7    $2,000,000          4

      Total: $18,000,000

如何使用 Oracle SQL 执行此操作？

Answer 1

这是一种在纯 SQL 中执行此操作的方法。我不会发誓没有更好的方法。

基本上，它使用递归公用表表达式(即 WITH costed... )来
计算总少于 20,000,000 的元素的所有可能组合。

然后它从该结果中获取第一个完整路径。

然后，它获取该路径中的所有行。

注意:逻辑假设没有 id超过 5 位数字。那是 LPAD(id,5,'0')东西。

WITH costed (id, cost, priority, running_cost, path) as 
( SELECT id, cost, priority, cost running_cost, lpad(id,5,'0') path
  FROM   a_test_table
  WHERE  cost <= 20000000
  UNION ALL 
  SELECT a.id, a.cost, a.priority, a.cost + costed.running_Cost, costed.path || '|' || lpad(a.id,5,'0')
  FROM   costed, a_test_table a 
  WHERE  a.priority < costed.priority
  AND    a.cost + costed.running_cost <= 20000000),
best_path as (  
SELECT *
FROM   costed c 
where not exists ( SELECT 'longer path' FROM costed c2 WHERE c2.path like c.path || '|%' )
order by path
fetch first 1 row only )
SELECT att.* 
FROM best_path cross join a_test_table att
WHERE best_path.path like '%' || lpad(att.id,5,'0') || '%'
order by att.priority desc;

+----+----------+----------+
| ID |   COST   | PRIORITY |
+----+----------+----------+
|  1 |  1000000 |       10 |
|  2 | 10000000 |        9 |
|  3 |  5000000 |        8 |
|  7 |  2000000 |        4 |
+----+----------+----------+

更新 - 较短的版本

此版本使用 MATCH_RECOGNIZE在递归 CTE 之后找到最佳组中的所有行:

WITH costed (id, cost, priority, running_cost, path) as 
( SELECT id, cost, priority, cost running_cost, lpad(id,5,'0') path
  FROM   a_test_table
  WHERE  cost <= 20000000
  UNION ALL 
  SELECT a.id, a.cost, a.priority, a.cost + costed.running_Cost, costed.path || '|' || lpad(a.id,5,'0')
  FROM   costed, a_test_table a 
  WHERE  a.priority < costed.priority
  AND    a.cost + costed.running_cost <= 20000000)
  search depth first by priority desc set ord
SELECT id, cost, priority
FROM   costed c 
MATCH_RECOGNIZE (
  ORDER BY path
  MEASURES
    MATCH_NUMBER() AS mno
  ALL ROWS PER MATCH
  PATTERN (STRT ADDON*)
  DEFINE
    ADDON AS ADDON.PATH = PREV(ADDON.PATH) || '|' || LPAD(ADDON.ID,5,'0')
    )
WHERE mno = 1
ORDER BY priority DESC;

更新 - 更短的版本，使用来自 OP 发布的 SQL*Server 链接的聪明想法

*编辑:删除了 ROWNUM=1 的使用在递归 CTE 的 anchor 部分，因为它取决于返回行的任意顺序。我很惊讶没有人因此指责我。 *

WITH costed (id, cost, priority, running_cost) as 
( SELECT id, cost, priority, cost running_cost
  FROM   ( SELECT * FROM a_test_table
           WHERE  cost <= 20000000
           ORDER BY priority desc
           FETCH FIRST 1 ROW ONLY )
  UNION ALL 
  SELECT a.id, a.cost, a.priority, a.cost + costed.running_Cost
  FROM   costed CROSS APPLY ( SELECT b.*
                              FROM   a_test_table b 
                              WHERE  b.priority < costed.priority
                              AND    b.cost + costed.running_cost <= 20000000
                              FETCH FIRST 1 ROW ONLY
                              ) a
)
CYCLE id SET is_cycle TO 'Y' DEFAULT 'N'
select id, cost, priority from costed
order by priority desc