Выберите, где накопленная сумма меньше числа (в порядке приоритета) - PullRequest
Новая
       10

Выберите, где накопленная сумма меньше числа (в порядке приоритета)

0 голосов
/ 08 февраля 2019

У меня есть таблица со столбцами 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?

Ответы [ 3 ]

0 голосов
/ 08 февраля 2019

Вот способ сделать это на чистом 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;

ОБНОВЛЕНИЕ - Еще более короткая версия, с использованием умной идеи из SQL * Server link ОП опубликовала

* Редактировать: удалено использование ROWNUM=1 в якорной части рекурсивного CTE, поскольку оно зависит от произвольного порядка, в котором будут возвращаться строки.Я удивлен, что никто не обмолвился меня об этом.*

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
0 голосов
/ 09 февраля 2019

@ ypercubeᵀᴹ в чате DBA-SE опубликовано это решение .Это довольно лаконично. 

with  rt (id, cost, running_total, priority) as
(
    (
    select 
        id,
        cost,
        cost as running_total,
        priority
    from 
        a_test_table
    where cost <= 20000000 
    order by priority desc
    fetch first 1 rows only
    )

    union all

        select 
            t.id,
            t.cost,
            t.cost + rt.running_total,
            t.priority
        from a_test_table  t
             join rt 
             on t.priority < rt.priority      -- redundant but throws
                                              -- "cycle detected error" if omitted

             and t.priority =                             -- needed 
                 ( select max(tm.priority) from a_test_table tm
                   where tm.priority < rt.priority
                     and tm.cost + rt.running_total <= 20000000 )
    )
    select *
    from rt ;

(@ ypercubeᵀᴹ не заинтересован в том, чтобы публиковать его сам.)

0 голосов
/ 08 февраля 2019

Я слишком глуп, чтобы делать это простым SQL, поэтому я попробовал PL / SQL - функцию, которая возвращает sa table .Вот как: перебирая все строки в таблице, я вычисляю сумму;если он ниже предела, хорошо - добавьте ID строки в массив и продолжайте.

SQL> create or replace function f_pri (par_limit in number)
  2    return sys.odcinumberlist
  3  is
  4    l_sum   number := 0;
  5    l_arr   sys.odcinumberlist := sys.odcinumberlist();
  6  begin
  7    for cur_r in (select id, cost, priority
  8                  from a_test_table
  9                  order by priority desc
 10                 )
 11    loop
 12      l_sum := l_sum + cur_r.cost;
 13      if l_sum <= par_limit then
 14         l_arr.extend;
 15         l_arr(l_arr.last) := cur_r.id;
 16      else
 17         l_sum := l_sum - cur_r.cost;
 18      end if;
 19    end loop;
 20    return (l_arr);
 21  end;
 22  /

Function created.

Подготовка среды SQL * Plus, чтобы вывод выглядел более красиво: 

SQL> break on report
SQL> compute sum of cost on report
SQL> set ver off

Тестирование: 

SQL> select t.id, t.cost, t.priority
  2  from table(f_pri(&par_limit)) x join a_test_table t on t.id = x.column_value
  3  order by t.priority desc;
Enter value for par_limit: 20000000

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

SQL> /
Enter value for par_limit: 30000000

        ID       COST   PRIORITY
---------- ---------- ----------
         1    1000000         10
         2   10000000          9
         3    5000000          8
         7    2000000          4
         8    3000000          3
         9    3000000          2
           ----------
sum          24000000

6 rows selected.

SQL>
...