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

Question

我是在一个事实表（比如说发票历史表）的基础上建立功能，它将简单地不断向右追加。date

|   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)，但逻辑非常简单，大家都能理解。但是直到最近，当我们开始处理一张大表的时候，这种方法才爆发。

之前我一直在想窗口函数，但我不知道有没有更高效（计算效率和存储效率）的方法？

我想到的是使用窗口函数，但看起来我的逻辑是一个自定义的范围，只是比一个固定的寻找N行回来，而不是它应该寻找5天回来？在HiveImpala中是否可以，如果不可以，我想我得用 补天 然后使用windows功能。欢迎大家提出建议？

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

---

更新

刚刚跑了一个使用2000万行真实数据的基准，时间上的节省非常可观。

• 自连接与过滤： 128分钟
• 使用窗口功能，包括日期转换：15分钟（戈登的回答），最重要的是，这种方法可以保证不引入重复，因为同一客户和同一产品可能会在同一天购买多次
• Hive不支持内联相关的子查询，但GBM的解决方案应该可以有效地避免完全的卡托式连接。