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

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

> SELECT avg(amount) FROM transfer;
65.125965782378
generated in 3850 seconds

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

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

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

Другие преобразования

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

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

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

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

Анкеты

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

i и j — разные пользователи. И ещё разницу между пользователем Х и группой (или всеми пользователями вообще). Запрос к базе данных, без оптимизации, получился такой:

    SELECT
        avg(power(my_answer.value - his_answer.value, 2))

    FROM
        answer AS my_answer
            INNER JOIN answer AS his_answer ON my_answer.question_id = his_answer.question_id

    WHERE
        my_answer.user_id = X AND
        his_answer.user_id = Y

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

    ...
    WHERE
        his_answer.user_id IN (Z) AND
        ...

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

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

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

Замеры

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

import sys, sqlite3, random, itertools

USERS = xrange(100000)
QUESTIONS = xrange(50)

conn = sqlite3.connect('aggregation.sqlite3')
cur = conn.cursor()

cur.execute('drop table if exists answer');
cur.execute('create table answer (user_id integer, question_id integer, value integer)')

for u, q in itertools.product(USERS, QUESTIONS):
	cur.execute('insert into answer values (?, ?, ?)', (u, q, random.randint(1, 100)))

# индексы строим уже после ввода данных,
# чтобы во время вставки лишний раз не перестраивать бинарное дерево
cur.execute('create index answer_user on answer (user_id)')
cur.execute('create index answer_question on answer (question_id)')
conn.commit()

cur.execute("""
	create table answer_summary as
	select question_id, sum(value) value, sum(value*value) value_square, count(*) num
	from answer
	group by question_id
	""")

cur.execute('create unique index answer_question on answer_summary (question_id)')

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

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

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

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

Побочные эффекты

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

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

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

Где подход не работает

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

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

Не всё так сложно

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

class Question(Model):
    text = CharField()


class Answer(Model):
    user = ForeignKey(User)
    question = ForeignKey(Question)
    value = IntegerField()


class AnswerAggregate(Model):
    question = ForeignKey(Question, related_name='aggregates')
    summ = IntegerField()
    summ_of_squares = IntegerField()
    answers_count = IntegerField()


def add_to_aggregates(*kwargs):
    answer = kwargs['instance']
    answer.question.aggregates.update(
        summ=F('summ') + answer.value,
        summ_of_squares=F('summ_of_squares') + answer.value ** 2,
        answers_count=F('answers_count') + 1
    )


def remove_from_aggregates(*kwargs):
    answer = kwargs['instance']
    answer.question.aggregates.update(
        summ=F('summ') - answer.value,
        summ_of_squares=F('summ_of_squares') - answer.value ** 2,
        answers_count=F('answers_count') - 1
    )


signals.post_add.connect(add_to_aggregates, model=Answer)
signals.pre_update.connect(remove_from_aggregates, model=Answer)
signals.post_update.connect(add_to_aggregates, model=Answer)
signals.pre_delete.connect(remove_from_aggregates, model=Answer)

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

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

Цена улучшений

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

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

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

Итог

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

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

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

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

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

Для дочитавших до конца: листинг в самом начале статьи — вымышленный.

Автор: siberiano