Как не пересчитывать суммы и средние каждый раз

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

А теперь представим, что показатель должен быть свежайшим, а записи в таблицу делаются каждую секунду, и за месяц их набираются миллионы. Или другие требования, но суть та же — агрегировать те же данные каждый раз очень затратно. Обычные базы данных не предлагают таких оптимизаций. Как быть? Кто катается на велосипеде, мог задаться вопросом, как же это велокомпьютер может считать среднюю скорость бесконечно долго и каждую секунду, но не хранить все значения скорости. Сейчас, конечно, в велокомпьютер войдёт карта MicroSD, но они работали так же и годы назад, когда такой памяти не было.

Всё просто: в нём хранится пройденное расстояние и время. Каждую секунду нужно просто увеличить счётчик времени и добавить к одометру пройденное расстояние. Всего 2 величины по 4 или 8 байт, всего 2 операции сложения. Чтобы вывести среднее, нужно одно разделить на другое.

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

Если не знаем d1, то ничего сделать не получится.

Если мы изменили какое-то значение, уже учтённое, делаем то же дважды: удаляем старое значение из среднего и добавляем новое.

Владеющие математикой легко разложат в подобные формулы такие статистики как дисперсия, произведение, даже произведение каждой величины на каждую (или ковариация). Где применять такие знания на практике — вот пример.

Пользователи заполняют анкету из разных вопросов, где отмечают согласие по шкале от 1 до 100 (от сильного согласия до полного несогласия). Понадобилось подсчитать разницу между 2 пользователями, то есть среднеквадратическое отклонение между ответами на соответствующие вопросы:

i и j — разные пользователи. Также нужно посчитать разницу между пользователем Х и группой, и между ним и всеми остальными пользователями. (Я намеренно отступил от терминологии матстатистики, опустив в дисперсии деление на n. Суть и сложность вычислений от этого качественно не поменялась.)

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

Для нескольких пользователей нужно просто поменять условие:

или вообще убрать его, если сравнивать ответы со всеми. Очевидно, для этого придётся выбрать всю таблицу. Её, конечно, можно закэшировать — 50 вопросов и 10 000 анкет, то есть 500 000 строк, всего несколько мегабайт памяти. Но поскольку пользователи часто заполняют анкеты и часто смотрят результаты, не охота повторять вычислительные операции лишние разы, нужно оптимизировать.

На этой формуле в первой строке — формула дисперсии, точнее той части, которую надо оптимизировать. Xq — ответ данного пользователя (для которого считается показатель) на вопрос q, Vqu — ответ пользователя u на тот же вопрос q. Мы агрегируем по пользователям и вопросам. Если вопросов немного (m ≅ 50), то анкет много (n ≅ 10 000). Во второй строке — эта же формула, где сумма по пользователям (n, 10 000) изолирована. Сумма по q нависает над всем этим выражением, то есть данные должны быть разбиты по вопросам, и по ним нужно каждый раз агрегировать, но это всего 50 строк. А суммы по 10 000 пользователям, u, мы изолировали и можем посчитать и хранить. Если мы обозначим сумму ответов на вопрос q как Sq, а сумму квадратов как Rq, получаем очень компактную формулу:

Sq и Rq можно посчитать предварительно и сохранить в отдельной таблице.

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

50 ответов на 100 000 пользователей — 5 миллионов записей. На моём слабом ноутбуке (1,5 ГГц x2 и 2 ГБ памяти) таблицы строились примерно в течение получаса, и файл в зависимости от числа записей получался от десятков до сотен мегабайт.

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

И вот какие результаты, если мы считаем статистику различия ответов:

Если наша программа общается с БД, и нам нужна сумма по большому количеству строк (тысячи и больше), разумно дать это сделать базе, а не пересылать все данные в программу и суммировать — это увеличивает накладные расходы.

Однако если наши данные уже заранее суммированы, как в случае с анкетами из примера, то у нас есть всего 50 + 50 строк. Такие данные уже можно просто выбрать в исходном виде и обсчитывать в программе, где код будет гораздо лаконичнее.

Точно так же можно сделать и обновления сумм: не нужно писать сложные запросы UPDATE с объединением таблиц, можно выбрать данные, сложить и потом обновить при помощи INSERT OR REPLACE.

Вернёмся к примеру со спидометром. У нас есть среднее значение скорости в километрах в час. Мы можем линейно преобразовать его в метры в секунду. Если бы мы пересчитывали из км/ч в м/с, а только потом агрегировали, получилось бы то же самое.

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

На самом деле если у вас не OLAP, а просто ORM, вам не понадобится писать простыни запросов SQL, которые потом понадобится поддерживать и — хуже всего — понимать другому человеку. Такие оптимизации можно сделать в виде связанных моделей. Вот как можно организовать модели в Django:

Когда мы создаём ответ, мы добавляем его в разные суммы. Чтобы удалить, нужно просто вычесть значения. Чтобы изменить, мы вычитаем старое и добавляем новое значение.

В качестве увлекательного домашнего задания вы можете написать запрос, через ORM или на SQL, считающий среднеквадратическое отклонение из формулы выше.

Насколько целесообразно оптимизировать такие вычисления — отдельный вопрос. В примере с анкетами отчёты стали замедляться уже при паре тысяч пользователей, а с десятью тысячами каждый такой запрос выполнялся пару секунд. Такое количество данных вполне достижимо даже на небольшом проекте, а тем более на коммерческом предприятии. Обычные базы данных сегодня не делают таких оптимизаций автоматически. Оптимизации встроены в базы OLAP, но для небольшого предприятия они дóроги и громоздки. Поэтому такие небольшие оптимизации могут быть хорошим решением.

Цена за такую оптимизацию будет:

1. Вывести формулы и понимать их, для этого нужно хорошее владение математической статистикой. 2. Написать триггер или процедуру в ORM и отладить. 3. Подробно задокументировать систему, чтобы новый сотрудник после вас не начал использовать обычные агрегирующие функции.

Во-первых, как видно на замерах, основной тормоз в агрегатах (SUM, AVG) — вовсе не чтение диска, а именно суммирование.

Во-вторых, даже сложные агрегированные функции можно разложить и выделить в них агрегаты. Я показал как квадрат разности можно разложить на составляющие и выделить в нём сумму величин и сумму их квадратов. Суммы можно посчитать предварительно и хранить наготове.

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

В-третьих, добавлять новые данные, править и удалять старые можно даже не пересчитывая агрегат полностью. Ресурсоёмкость пересчёта тоже уменьшится в O(n) раз.

В-четвёртых, работая с малым числом строк, то есть только с агрегатами, количество данных уменьшится, и их можно будет забирать из БД и обсчитывать прямо в коде программы, уйдя от громоздких запросов SELECT или UPDATE.