SQL Особенности здания с использованием скользящего окна за время, отличное от O (N ^ 2) - PullRequest
Новая
       53

SQL Особенности здания с использованием скользящего окна за время, отличное от O (N ^ 2)

2 голосов
/ 02 мая 2020

Я строю элементы поверх таблицы фактов (скажем, истории счетов), которая будет просто добавляться справа. Базовая таблица истории счетов-фактур c может выглядеть следующим образом: 

|   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               |

Сначала мы записали логический c использования самосоединения в чем-то похожем на: 

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), если я не ошибаюсь, но логика c очень проста для всех. Но только в последнее время этот подход взорвался, когда мы начали работать с большим столом.

Раньше я думал об оконных функциях, но я не уверен, есть ли более эффективный (эффективный для вычислений и эффективного хранения) способ сделать это?

Что я имел в виду, это использовать оконную функцию, но, похоже, моя логика c - это настраиваемый диапазон, а не фиксированный N строк назад, вместо этого он должен оглядываться назад на 5 дней назад? Возможно ли это в Hive / Impala, если нет, я думаю, мне придется заполнить пропущенные дни и затем использовать функции windows. Открыты для любого предложения?

(Сегодня мы используем Hive / Impala, но если в других базах данных действительно есть более эффективный способ, я, безусловно, открыт для него).

update

Просто запустили тест на использование 20 миллионов строк реальных данных, и экономия времени существенна:

  • самостоятельное объединение с фильтрацией: 128 минут
  • с использованием оконной функции, включая преобразование даты: 15 минут (ответ Гордона), что наиболее важно, этот подход гарантированно не приводит к дублированию, поскольку один и тот же клиент и один и тот же продукт могут быть куплены несколько раз в один и тот же день
  • Hive не поддерживает встроенный коррелированный подзапрос, но решение GBM должно быть эффективным, чтобы избежать полного декартового объединения

Ответы [ 2 ]

1 голос
/ 02 мая 2020

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;

Одна проблема заключается в том, что довольно трудно различить guish между 2020-01-01 и 2020-01- 31. Оба они возвращают NULL. Если вы действительно хотите различать guish их, то вы можете использовать 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;
1 голос
/ 02 мая 2020

Если вам повезло запустить базу данных, которая поддерживает предложение range для оконных функций с интервалами (как, например, Postgres, начиная с версии 11), вы можете сделать: 

select
    t.*,
    sum(amount) over(
        partition by customer, product
        order by date
        range between interval '5 day' preceding and interval '1 day' preceding
    ) feature_cp
from mytable t

Демонстрация на DB Fiddle : 

date       | customer | product | amount | feature_cp
:--------- | :------- | :------ | -----: | ---------:
2020-01-01 | CA       | P1      |     10 |       <em>null</em>
2020-01-02 | CA       | P1      |      5 |         10
2020-01-05 | CA       | P1      |     20 |         15
2020-01-07 | CA       | P1      |     20 |         25
2020-01-15 | CA       | P1      |    100 |       <em>null</em>
2020-01-17 | CA       | P1      |    200 |        100
2020-01-31 | CA       | P1      |     20 |       <em>null</em>

В противном случае, я бы рекомендовал использовать коррелированный подзапрос. Это немного более эффективно, чем ваш запрос на объединение, поскольку позволяет избежать необходимости во внешней агрегации: 

select
    t.*,
    (
        select sum(amount) 
        from mytable t1 
        where 
            t1.customer = t.customer 
            and t1.product = t.product
            and t1.date < t.date
            and t1.date >= t.date - interval '5 day'
    ) feature_cp
from mytable t
...