Всем привет! Меня зовут Иван Привалов, я разработчик в команде BI Авито Финтеха и в этой статье расскажу, как мы сделали FIFO-сопоставление между N начислений и M списаний для бонусов. Заодно покажу подвох, без которого SQL быстро превращался в тыкву.

Статья будет полезна аналитикам и data-инженерам уровней мидл+, которые работают с финансовыми данными в Trino, Presto и Spark SQL.

В этой статье

• Что такое бонусы и зачем им FIFO

• Почему на один платёж приходятся N строк начисления и M трат

• Как мы переформулировали FIFO

• Где ломается наивный SUM в гранулярной витрине

• Как защищаем витрину от балансового расхождения из-за лагов

• Что мы из этого вынесли

Что такое бонусы и зачем им FIFO

Бонусы в Авито — виртуальные средства, которыми пользователи оплачивают услуги площадки: размещение и выделение объявлений, продвижение, доставку. Бонусы выпускаются по разным поводам: за активный тариф, в рамках маркетинговой акции, как компенсация за неудобства, по программам CPA. У каждого начисления есть срок жизни, и если за это время пользователь не успел воспользоваться бонусами, остаток сгорает.

С точки зрения хранилища у нас есть два независимых потока событий:

— лента начислений, по которой видно кому, когда и сколько начислили, а так же до какой даты эти бонусы живут;

— лента списаний и сгораний, когда пользователь использовал бонусы в качестве оплаты за услугу или у них кончился срок жизни.

В обычном бухгалтерском смысле начисления и траты — это два числа. Но этих данных недостаточно, поскольку нам нужно знать, что случилось с каждым бонусом, чтобы отразить это в налоговой и МСФО-отчётности, показать на аудите и корректно выгрузить в управленческие системы в конце концов. Бонус, выпущенный из тарифа, и из маркетинговой акции ложатся в строки P&L по-разному: первый закрывает выручку, второй идёт на расходы маркетинга. Чтобы их различить, нужно построить поимённое сопоставление между лентами начислений и списаний.

Это классический FIFO: первыми списываются самые ранние начисления, что создаёт большие проблемы для SQL, если надо обработать миллионы строк.

Почему на один платёж приходятся N строк начисления и M трат

Сырые события в DWH прилетают полуструктурированно, в формате JSON. И уже на этапе разбора одно начисление разворачивается в N строк с весами по подкатегориям объявлений и типам выручки:

accrual_id    microcat              revenue_type     amount
ACC-1         детская одежда        tariff           600
ACC-1         бытовая техника       vas              400

Это намеренная декомпозиция, чтобы бухгалтерии понимала, в каких долях и за что именно начислены бонусы. Сумма строк равна полной сумме начисления, но каждая доля несёт свою бухгалтерскую этикетку из микрокатегории и типа выручки, которую нельзя терять.

Следствие №1: уникальный id в исходниках присваивается паре из id начисления и микрокатегории. Это бакет для FIFO.

Списания, наоборот, атомарны. Одна трата равна одной строке с собственным набором атрибутов: дата, услуга, вертикаль, микрокатегория и тип выручки. Никакого внутреннего разворота у списаний нет.

Следствие №2: на стороне списаний M возникает по другой причине. За время жизни одного начисления пользователь тратит бонусы по частям: на разные услуги, в разные дни, по разным подкатегориям объявлений. Поэтому на одном платеже встречается M отдельных трат, иногда десятки. К ним добавляется событие сгорания остатка, если бонус не успел израсходоваться.

Сложность задачи в том, что слои асимметричны. Сторона начисления разнесена по подкатегориям для бухгалтерии, а списания по времени и услугам для поведенческой детализации. FIFO нужно делать по графу N×M аллокаций на каждом платеже.

Постановка задачи

На входе для каждого платежа мы имеем:

— N бакетов начислений с собственной суммой и атрибутами.

— M событий списаний и сгораний с ключом из даты, услуги, вертикали, микрокатегории и типа выручки. У каждого также своя сумма и атрибуты.

На выходе для каждой пары из бакета начисления и события списания рассчитывается точная сумма аллокации. Получаем строки вида: трата 150 ₽ на платное размещение потратила 80 ₽ из начисления ACC-1 (детская одежда, тариф) и 70 ₽ из начисления ACC-2 (бытовая техника, продвижение).

Правило аллокации, FIFO: списания съедают бакеты в порядке поступления, целыми и без округлений.

Как мы переформулировали FIFO

В открытых источниках тему FIFO в SQL обычно разбирают на простой модели «1 начисление ↔ 2–3 списания». Реальные финансовые данные устроены сложнее, и наивные подходы здесь не подойдут.

? Trino не поддерживает процедурный SQL, рекурсия в его CTE ограничена и плохо параллелится. На N×M-графе на каждом из миллионов платежей задача не помещается в память.

? Простой JOIN по сумме или дате не моделирует «поедание» бонусов в порядке поступления, а даёт двойной счёт: одно списание матчится сразу с несколькими начислениями без правильного распределения долей. Получается, списание учтётся полностью столько раз, сколько существует строк для начислений.

? Текущая логика агрегации схлопывает строки до уровня id начисления, из-за чего теряется бухгалтерская детализация, ради которой источник развернул одно начисление в N строк. После такой агрегации восстановить детализацию невозможно.

? GROUP BY с MAX/SUM не учитывает гранулярность витрины и молча задваивает или утраивает суммы. Это вообще главная ошибка при потреблении подобных витрин, в разделе про гранулярность я к ней вернусь.

Мы решили переформулировать FIFO через геометрию и сделали это в три шага.

Шаг 1. На стороне начислений взяли бакеты с ключом (id начисления, микрокатегория). На стороне списаний берём атомарные траты плюс события сгораний.

Шаг 2. В рамках одного платежа вычисляем накопительную сумму по каждой ленте:

SUM(amount) OVER (
  PARTITION BY payin_ext
  ORDER BY ...
  ROWS UNBOUNDED PRECEDING
)

После этого каждый бакет начисления превращается в отрезок [acc_cum_start, acc_cum_end] на оси «накопленная сумма платежа». Каждая трата превращается в отрезок [w_cum_start, w_cum_end] на той же оси.

Шаг 3. FIFO эквивалентен пересечению отрезков. Если бакет начисления и трата накладываются на одну и ту же часть оси сумм, значит, эта трата частично или целиком съела этот бакет. Сумма аллокации равна длине пересечения.

FIFO как пересечение интервалов: бакеты начисления сверху, события трат снизу, на одной оси накопленной суммы платежа. Длина пересечения равна сумме аллокации

Этот трюк широко известен в задачах interval scheduling и timeline merging, но в финансовых задачах FIFO он почему-то редко используется явно. А именно здесь от него больше всего пользы: один и тот же SQL обслуживает вырожденные платежи из 1 бакета и 1 траты, а также сложные из десятков бакетов и десятков трат, без if/else.

Полный SQL-запрос в упрощённом виде, без технических полей витрины:

-- Шаг 0: подготовка стороны начислений, собираем бакеты
WITH accrual_buckets AS (
  SELECT
    payin_ext, accrual_id, accrual_microcat,
    SUM(accrual_amount) AS bucket_amount
  FROM raw_accruals
  GROUP BY payin_ext, accrual_id, accrual_microcat
),
 
-- Накопительная сумма на стороне начислений
accruals_cum AS (
  SELECT
    a.*,
    SUM(bucket_amount) OVER (
      PARTITION BY payin_ext
      ORDER BY accrual_id, accrual_microcat
      ROWS UNBOUNDED PRECEDING
    ) AS acc_cum_end,
    SUM(bucket_amount) OVER (
      PARTITION BY payin_ext
      ORDER BY accrual_id, accrual_microcat
      ROWS UNBOUNDED PRECEDING
    ) - bucket_amount AS acc_cum_start
  FROM accrual_buckets a
),
 
-- Шаг 0b: подготовка стороны списаний через UNION ALL трат и сгораний
consumption AS (
  SELECT payin_ext, writeoff_date, writeoff_purchase, ...,
         writeoff_amount, FALSE AS is_burn
  FROM writeoffs
  UNION ALL
  SELECT payin_ext, burn_date AS writeoff_date,
         'burn' AS writeoff_purchase, ...,
         burn_amount AS writeoff_amount, TRUE AS is_burn
  FROM burns
),
 
-- Накопительная сумма на стороне списаний
consumption_cum AS (
  SELECT
    c.*,
    SUM(writeoff_amount) OVER (
      PARTITION BY payin_ext
      ORDER BY writeoff_date, writeoff_purchase, ...
      ROWS UNBOUNDED PRECEDING
    ) AS w_cum_end,
    SUM(writeoff_amount) OVER (
      PARTITION BY payin_ext
      ORDER BY writeoff_date, writeoff_purchase, ...
      ROWS UNBOUNDED PRECEDING
    ) - writeoff_amount AS w_cum_start
  FROM consumption c
)
 
-- Сердце алгоритма: interval overlap join + длина пересечения
SELECT
  a.payin_ext,
  a.accrual_id, a.accrual_microcat,
  c.writeoff_date, c.writeoff_purchase, ...,
  GREATEST(0,
    LEAST(a.acc_cum_end, c.w_cum_end)
    - GREATEST(a.acc_cum_start, c.w_cum_start)
  ) AS allocated_amount
FROM accruals_cum a
JOIN consumption_cum c
  ON c.payin_ext = a.payin_ext
 AND c.w_cum_start < a.acc_cum_end
 AND c.w_cum_end   > a.acc_cum_start;

Несмотря на формальный вид «N×M», декартов взрыв не случается: условие w_cum_start < acc_cum_end AND w_cum_end > acc_cum_start чрезвычайно селективно на отсортированных интервалах. Каждая трата пересекается обычно с одним или двумя бакетами начисления, и движок это учитывает.

Мы обошлись без процедурного кода и курсора, поскольку сложность алгоритма линейная по числу пар (на практике O(N log N) с учётом сортировок window-функций).

Где ещё можно использовать подход

Cumulative sum + interval overlap join — это общая идея, не привязанная к бонусам. Например, я уже видел несколько подобных задач:

— Распределение оплат по нескольким счетам: те же интервалы, тот же overlap join.

— LIFO-партии: те же интервалы, обратный порядок ORDER BY в накопительной сумме.

— Налоговые партии (FIFO inventory) в учёте товаров: буквально из учебников бухучёта, но впервые сформулированные как чистый SQL и сразу с поддержкой внутренней разбивки партии.

— Страховые требования с разбивкой по видам ущерба, взаиморасчёты между сервисами с разнесением по статьям, развёрстка авансовых платежей по позициям договора.

Любая задача формата «M входящих событий закрыли N исходящих с разделением на доли», в которой сама сущность тоже разбита на подкатегории, это кандидат на такой паттерн.

Где ломается наивный SUM в гранулярной витрине

Витрина-результат имеет составной ключ:

payin_ext × accrual_microcat × writeoff_microcat × flow_type

Расшифровка: id платежа, микрокатегория со стороны начисления, микрокатегория со стороны траты, тип потока (writeoff, burn, accrual). Каждая строка — одна пара из бакета начисления и траты с аллокацией. Всё аккуратно и разнесено по бухгалтерским разрезам.

И здесь начинается подвох. Каждый бакет начисления повторяется в нескольких строках одного платежа по числу трат, которые его съели. Поле accrual_amount (сумма бакета) в этих строках одинаковое. Любой потребитель, пишущий SUM(accrual_amount) GROUP BY payin_ext, получит сумму, кратную числу строк. Цифры в отчёте растут в разы, при этом никакой ошибки в SQL формально нет, отчего баг очень тяжело заметить.

Поэтому витрина защищается от наивного потребителя: в каждой строке есть предсчитанные tot_accrual_by_payin, tot_writeoff_by_payin, tot_burn_by_payin. Это настоящие суммы платежа, одинаковые во всех строках. Правильный паттерн потребителя — это any_value:

SELECT
  payin_ext,
  any_value(tot_accrual_by_payin)  AS accrued,
  any_value(tot_writeoff_by_payin) AS spent,
  any_value(tot_burn_by_payin)     AS burned
FROM bonus_flows_fifo_subcat
WHERE constant = 1
GROUP BY payin_ext;

Если потребителю нужна разбивка по выручке или подкатегориям, он использует amount_flow. Это сумма конкретной аллокации, которая привязана к паре бакет ↔ траты и не удваивается.

Главное правило проектирования FIFO-витрин: правильные суммы должно быть невозможно посчитать неправильно. Предсчитанные tot_*_by_payin + any_value проще и безопаснее, чем DISTINCT-фильтрация или сложные оконные функции на стороне потребителя.

Как защищаем витрину от балансового расхождения из-за лагов

Бонус закрыт, когда он целиком исчерпан: accrued = spent + burned. Казалось бы, это можно проверять по дате expire: срок истёк, бонус закрыт, но практика показала, что так делать нельзя.

У любой витрины есть лаг, когда срок жизни закончился, но событие сгорания ещё не доехало в DWH. Такой бонус по дате формально закрыт, но баланс не сошёлся и если строить отчёт по expire_date < today, мы будем считать живые бонусы закрытыми и получим расхождения.

Мы решили эту задачу с помощью балансового фильтра одной строкой:

WHERE abs(accrued - spent - burned) < 0.01

Этот фильтр одновременно:

— отсекает живые бонусы (для них spent + burned < accrued);

— защищает от лагов: если для запоздавших burn-событий баланс не сошёлся, они тоже отсеются.

В наших данных это даёт около 98% сходимости на бонусах, закрытых по сроку, и 100% на досрочно потраченных. Потерянные 2% это те самые, у которых сгорание ещё не доехало. Они автоматически вернутся в выборку, как только догрузится источник.

Граничные случаи и шрамы

? Смена источника на середине истории. В день, когда мы переезжали со старой модели на новую, исходные таблицы расщепились, и появился риск потерять или задвоить данные. Проблему решили оператором UNION ALL с фильтрами по дате: cut date разделяет периоды, после неё используется только новая модель.

? Поле «мигрированный флаг». Часть записей перенеслась из старой модели в новую. Их отсекаем фильтром, чтобы не задвоить с pre-cut периодом.

? Семантика поля hold_operation. До cut date это числовые id, а после — текстовые лейблы. Переписывать витрину ради унификации не стали, поэтому появилась публичная особенность модели — потребители разрешают её через справочник.

Что мы из этого вынесли

? У нас была задача учитывать бонусы строго в соответствии с историей начислений — раньше пришло → раньше ушло. Проблема в том, что на N начислений приходится M строк списаний, поэтому наивные способы подсчёта не сработали.

? Мы разобрались с задачей при помощи бакетирования. За единицу начисления взяли бакет из id начисления и микрокатегории, а траты оставили атомарными по одной строке.

? По дороге встретились с проблемой неверных подсчётов. Наивный SUM многократно умножал траты, поскольку бакет начислений списывался с каждой строки трат.

? Вторая проблема — алгоритм неверно подсчитывал пограничные бонусы, срок которых формально истёк, но данные до витрины ещё не добрались. Задачу решили с помощью балансового уравнения: WHERE abs(accrued - spent - burned) < 0.01. Также решили и другие проблемы: отсеяли живые бонусы и защитились от лагов.

? Итоговый паттерн — cumulative sum + interval overlap join — позволяет решать FIFO на миллионах строк без курсоров и процедурного кода.

Теперь мы правильно подсчитываем каждый бонус.

Аналитики Авито пишут много статей, а ещё ведут недушный Телеграм-канал «Коммуналка аналитиков» Подписывайтесь!