在非 O(N^2) 时间内使用滚动窗口的 SQL 构建功能

Question

我正在事实表(例如发票历史记录)之上构建功能，该功能只会继续附加到右侧。基本发票历史记录表可能如下所示:

|   date     |   customer   | product  | amount  | feature c-p (past 5 days) |  ...
-----------------------------------------------------------------------------------
| 2020/01/01 |      CA      |   P1     | 10      |    NA                     |
| 2020/01/02 |      CA      |   P1     | 5       |    10   = 10              |
| 2020/01/05 |      CA      |   P1     | 20      |    15   = 5 + 10          |
| 2020/01/07 |      CA      |   P1     | 20      |    25   = 20 + 5          |
                                                  (01/01 out of range above) |
| 2020/01/15 |      CA      |   P1     | 100     |    25   = 10 + 5 + 20     |
| 2020/01/17 |      CA      |   P1     | 200     |    100  = 100             |
| 2020/01/31 |      CA      |   P1     | 20      |    0    = 0               |

起初，我们写了使用自联接的逻辑类似于:

select 
    c.date, 
    c.customer, 
    c.product, 
    c.amount, 
    sum(c.amount2)
from
    (select 
        i1.*,
        i2.date as date2, 
        i2.amount as amount2
    from invoice i1
    inner join invoice i2
    on i1.customer = i2.customer 
    and i1.product = i2.product 
    and i1.date < i2.date and i1.date >= i2.date - 5    -- where we customize the window
    ) c   
group by 
    c.date, 
    c.customer, 
    c.product, 
    c.amount

如果我没记错的话，这个自连接本身是 O(N^2)，但逻辑非常简单，每个人都可以理解。但直到最近，当我们开始使用一张大 table 时，这种方法才爆发。

我之前在考虑窗口函数，但我不确定是否有更高效(计算高效和存储高效的方式)的方法？

我想到的是使用窗口函数，但看起来我的逻辑是一个自定义的超范围，而不是固定的 N 行，而不是它应该回溯 5 天？在 Hive/Impala 中是否有可能，如果没有，我想我将不得不 补缺天数然后使用windows函数。对任何建议开放？

(今天我们使用的是 Hive/Impala，但如果其他数据库中确实有更有效的方法，我当然愿意接受)。

更新

刚刚运行了一个使用 2000 万行真实数据的基准测试，节省的时间非常可观:

自连接过滤:128 分钟

使用包括日期转换的窗口函数:15 分钟(Gordon 的回答)，最重要的是，这种方法保证不会引入重复，因为同一客户和同一产品可能会在同一天多次购买

Hive 不支持内联相关子查询，但 GBM 的解决方案应该可以有效避免完全笛卡尔连接

Answer 1

Hive 支持 range ，但只有我认为的数字。幸运的是，您可以将日期转换为数字并仍然使用它:

select t.*,
       sum(amount) over (partition by customer, product
                         order by days
                         range between 5 preceding and 1 preceding
                        )
from (select t.*,
             datediff(date, '2000-01-01') as days
      from t
     ) t;

一个问题是很难区分 2020-01-01 和 2020-01-31。这两个都返回 NULL .如果你真的想区分它们，那么你可以使用 lag()和 case :

select t.*,
       (case when datediff(date, prev_date) > 5 then 0
             when prev_date is null then null
             else sum(amount) over (partition by customer, product
                                    order by days
                                    range between 5 preceding and 1 preceding
                                   )
        end)
from (select t.*,
             datediff(date, '2000-01-01') as days,
             lag(date) over (partition by customer, product order by date) as prev_date
      from t
     ) t;