如何在oracle中找到最接近的子集總和

Question

我有兩個表： 1）其中一個用於發票，有成千上萬的數據。在我的INVOICES表中，有發票和它們的價格給顧客。 2）另一個是債務。在我的DEBTS表中，每個客戶都有發票的全部債務。
我的目標是找到最近的款項和債務的發票。舉例來說，我有表：

債項表：

CUSTOMER_ID   TOTAL_DEBTS 
     3326660    444$  
     2789514    165$  
     4931541    121$ 

發票表：

CUSTOMER_ID  INVOICE_ID  AMOUNT_OF_INVOICE 
    3326660    1a     157$ 
    3326660    1b     112$ 
    3326660    1c     10$ 
    3326660    1d     94$ 
    3326660    1e     47$ 
    3326660    1f     35$ 
    3326660    1g     14$ 
    3326660    1h     132$ 
    3326660    1i     8$ 
    3326660    1j     60$ 
    3326660    1k     42$ 
    2789514    2a     86$ 
    2789514    2b     81$ 
    2789514    2c     99$ 
    2789514    2d     61$ 
    2789514    2e     16$ 
    2789514    2f     83$ 
    4931541    3a     11$ 
    4931541    3b     14$ 
    4931541    3c     17$ 
    4931541    3d     121$ 
    4931541    3e     35$ 
    4931541    3f     29$ 

我的目標表：

CUSTOMER_ID  TOTAL_DEBTS  CALCULATED_AMOUNT  INVOICES_ID 
    3326660    444$    444$    1a,1b,1f,1h,1i  
    2789514    165$    164$     2b,2f 
    4931541    121$    121$     3d 

，因爲我的桌子上有數以千計的數據，對我來說性能非常重要。我發現從代碼覆蓋： closest subset sum

但是，性能低。當我在calculeted_amount和total_debts之間找到相同的值時，我必須停止加法循環。

謝謝你的幫助。

Answer 1

使用遞歸查詢：

^demo

with 
    t1 as ( 
     select customer_id cid, total_debts dbt, invoice_id iid, amount_of_invoice amt, 
       row_number() over (partition by customer_id order by invoice_id) rn 
      from debts d join invoices i using (customer_id)), 
    t2 (cid, iid, ams, dbt, amt, sma, rn) as ( 
     select cid, cast(iid as varchar2(4000)), cast(amt as varchar2(4000)), 
       dbt, amt, amt, rn 
      from t1 
     union all 
     select t2.cid, 
       t2.iid || ', ' || t1.iid, 
       t2.ams || ', ' || t1.amt, 
       t2.dbt, t2.amt, t1.amt + t2.sma, t1.rn 
      from t2 
      join t1 on t1.cid = t2.cid and t1.rn > t2.rn and t2.sma + t1.amt <= t1.dbt), 
    t3 as (
     select t2.*, rank() over (partition by cid order by dbt - sma) rnk 
      from t2) 
select cid, iid, ams, dbt, sma from t3 where rnk = 1 

輸出：

CID IID       AMS        DBT  SMA   
------- ---------------------------- ------------------------------ -------- -------- 
2789514 2b, 2f      81, 83        165  164 
3326660 1a, 1d, 1e, 1g, 1h   157, 94, 47, 14, 132     444  444 
3326660 1b, 1c, 1d, 1e, 1f, 1g, 1h 112, 10, 94, 47, 35, 14, 132   444  444 
3326660 1a, 1c, 1f, 1h, 1i, 1j, 1k 157, 10, 35, 132, 8, 60, 42   444  444 
3326660 1a, 1b, 1f, 1h, 1i   157, 112, 35, 132, 8     444  444 
4931541 3d       121         121  121 

6 rows selected 

子查詢T1連接兩個表，並增加了用於未來數據合併列rn。 T2是分層的，它完成了工作的主要部分 - 結合所有數據直到達到債務。 T3使用功能rank過濾最佳解決方案。正如你所看到的CID 3326660有四種最好的組合。

對於大量的數據遞歸子查詢很慢，並且此解決方案不起作用，請注意。