Как быстро рассчитать количество дней с момента последних незакрытых продаж

У меня есть большой набор данных о продажах компании и полученных платежах.

Как я могу быстро найти последнюю продажу, которая не может быть покрыта общей суммой платежей для каждого клиента?

Например, предположим, что таблица данных выглядит следующим образом

Date Customer ID Type Amount
2024-01-01 1 SALE 100
2024-01-08 1 PAYMENT 50
2024-01-15 1 SALE 100
2024-01-22 1 PAYMENT 100
2024-01-02 2 SALE 200
2024-01-09 2 SALE 200
2024-01-16 2 PAYMENT 150

Для клиента 1 это будет 2024-01-15, так как общая сумма платежа составляет 150, поэтому первая продажа будет покрыта; а для клиента 2 это будет 2024-01-02, так как единственный платеж не может покрыть его первую продажу.

Пока что я использую оконную функцию для вычисления кумулятивных продаж и общих платежей. Затем использую эту сгенерированную таблицу для вычисления последней непокрытой продажи и другой статистики.

with cumsum_entry as (
    select 
        id, date, customer_id, type, amount,
        sum(amount) filter (where type='PAYMENT') over win_customer
          - sum(amount) filter (where type='SALE') over win_cumsum as cover
    from entry
    window win_customer as (partition by customer_id),
        win_cumsum as (partition by customer_id order by date rows between unbounded proceeding and current row)
)
select 
    customer_id,
    sum(amount) filter (where date >= '2024-01-01') as monthly_total,
    min(date) filter (where cover < 0) as latest_uncovered
from cumsum_entry
where date <= '2024-01-31'
group by customer_id

На самом деле я храню сгенерированную таблицу "cumsum_entry" как представление в PostgreSQL, а для остальной работы использую Django's orm, но основная логика та же, что и выше.

Очевидно, меня не устраивает скорость отклика (2 секунды для ~10^3 клиентов / ~10^5 записей). Как я могу еще больше оптимизировать время отклика? (Кроме модернизации аппаратного обеспечения, разумеется)

Настоящий вопрос заключается в том, как оптимизировать эти вычисления, не нарушая при этом другую (возможно, будущую) логику.

Допустим, что записи в cumsum_entry нельзя изменять и что мы не будем добавлять записи из прошлого. В этом случае решение довольно простое:

  • Теперь добавим поле customer_balance под cumsum_entry. Оно будет вычисляться как сумма всех предыдущих записей, где type='PAYMENT' минус сумма всех предыдущих записей, где type='SALE'.
  • Мы можем легко вычислить ее для всех существующих записей с помощью очевидного линейного решения. Также добавим обработку перед каждым сохранением новой cumsum_entry.
  • Теперь мы можем просто выбрать первую запись для каждого клиента, где customer_balance < 0.

Если вы можете изменять данные записей, добавленных ранее, то все становится немного сложнее. В этой ситуации вы вынуждены поддерживать все customer_balance значения в актуальном состоянии после каждого изменения. Фактически, все, что меняется, - это то, что вам нужно пакетно обновлять все записи после изменения с помощью SET customer_balance + <actual_change>.

Если количество таких записей станет слишком большим, то, на мой взгляд, следует рассмотреть решение, которое будет хранить продажи и платежи только в PostgreSQL, а эффективную структуру данных для этих вычислений поддерживать в оперативной памяти. Наиболее очевидными подходами здесь будут SQRT-декомпозиция или сегментное дерево, позволяющие обновлять и искать O(sqrt(n)) и O(log(n)) соответственно.

Вернуться на верх