Как я ускорил одну агрегатную функцию в ClickHouse

Как я ускорил одну
агрегатную функцию в ClickHouse

ClickHouse не тормозит.

А является ли ClickHouse самой быстрой системой во всех сценариях?

ClickHouse не тормозит.

А является ли ClickHouse самой быстрой системой во всех сценариях?

— в частных случаях можно выиграть...
  ... пока я этого не заметил.

ClickHouse не тормозит.

А является ли ClickHouse самой быстрой системой во всех сценариях?

DBMS-X

Работает с данными только с помощью mmap.

Не поддерживает сжатие данных.

Не поддерживает индексы и не сортирует хранимые данные.

Почти не поддерживает SQL.

Выполняет один запрос быстрее чем ClickHouse?

DBMS-X

Выполняет один запрос быстрее чем ClickHouse?

SELECT sum(x) FROM table

x Nullable(Float64)

— суммирование 1 млрд чисел double.

ClickHouse: 0.116 sec
DBMS-X:     0.066 sec

AWS c5.metal, 96 vCPU

Sanity Check — считаем байты

Скорость сканирования данных в ГБ/сек.

double — 8 байт + маска NULL, возможно 1 байт,
всего 9 байт на значение в оперативке.

Нужно обработать 9 ГБ данных в памяти.

ClickHouse: 0.116 sec,  78 ГБ/сек.
DBMS-X:     0.066 sec, 136 ГБ/сек.

STREAM benchmark:      160 ГБ/сек.

160 ГБ/сек. — максимальная скорость
сканирования памяти на данной машине.

Как быстрее всего суммировать числа?

1. Используем доступные ядра CPU
 (делим работу по потокам).

2. Используем векторную обработку запроса
 (только простые циклы, никаких виртуальных вызовов внутри).

3. Обрабатываем данные по блокам
 (правильно используем кэш CPU).

4. Кэшируем несжатые данные в оперативке
 (убираем разжатие, десериализацию, копирования).

Как быстрее всего суммировать числа?

Исполняемый базой данных код должен быть таким же,
как если бы вы вручную написали идеальный код на C++.

template <typename T> T sum(const T * ptr, const T * end) { T res{}; while (ptr < end) { res += *ptr; ++ptr; } return res; }

Как быстрее всего суммировать числа?

while (ptr < end) { res += *ptr; ++ptr; }

Но разве это идеальный код на C++?

— можно развернуть цикл;
— можно векторизовать цикл;
— выравнивание;
— префетч;

Но разве компилятор C++ не обязан сам это делать?

Как быстрее всего суммировать числа?

$ g++ -O2 main.cpp && ./a.out Res: 499999999067108992.000, time: 2.561, 3.123 GB/sec. $ g++ -O3 main.cpp && ./a.out Res: 499999999067108992.000, time: 1.590, 5.033 GB/sec. $ g++ -O3 -msse4.2 main.cpp && ./a.out Res: 499999999067108992.000, time: 1.560, 5.129 GB/sec. $ g++ -O3 -mavx2 main.cpp && ./a.out Res: 499999999067108992.000, time: 1.188, 6.733 GB/sec. $ g++ -O3 -march=native main.cpp && ./a.out Res: 499999999067108992.000, time: 1.192, 6.710 GB/sec.

Как быстрее всего суммировать числа?

$ clang++ -O2 main.cpp && ./a.out Res: 499999999067108992.000, time: 0.726, 11.013 GB/sec. $ clang++ -O3 main.cpp && ./a.out Res: 499999999067108992.000, time: 0.724, 11.044 GB/sec. $ clang++ -O3 -msse4.2 main.cpp && ./a.out Res: 499999999067108992.000, time: 0.733, 10.918 GB/sec. $ clang++ -O3 -mavx2 main.cpp && ./a.out Res: 499999999067108992.000, time: 0.728, 10.983 GB/sec. $ clang++ -O3 -march=native main.cpp && ./a.out Res: 499999999067108992.000, time: 0.741, 10.792 GB/sec.

Как быстрее всего суммировать числа?

$ g++ -O3 -march=native -S main.cpp && cat main.s .L11: vmovups (%rax), %xmm1 vmovupd (%rax), %ymm3 addq $32, %rax vaddsd %xmm1, %xmm0, %xmm0 vunpckhpd %xmm1, %xmm1, %xmm1 vaddsd %xmm1, %xmm0, %xmm0 vextractf128 $0x1, %ymm3, %xmm1 vaddsd %xmm1, %xmm0, %xmm0 vunpckhpd %xmm1, %xmm1, %xmm1 vaddsd %xmm1, %xmm0, %xmm0 cmpq %rdx, %rax jne .L11

Цикл развёрнут, но не векторизован.

Как быстрее всего суммировать числа?

$ clang++ -O3 -march=native -S main.cpp && cat main.s .LBB2_2: # =>This Inner Loop Header: Depth=1 vaddsd (%rdi), %xmm0, %xmm0 addq $8, %rdi cmpq %rsi, %rdi jb .LBB2_2

Цикл не развёрнут, не векторизован... но это лучше на моей машине.

Почему компилятор не векторизует цикл?

Цикл с double, float — не векторизует.

Цикл с int — векторизует.

Почему компилятор не векторизует цикл?

Цикл с double, float — не векторизует.

Цикл с int — векторизует.

— Потому что это противоречит стандарту C++ и IEEE-754.

(a + b) + c != a + (b + c).

Почему компилятор не векторизует цикл?

Это можно «исправить», надо всего-лишь:

$ clang++ -O3 -march=native -ffast-math main.cpp && ./a.out Res: 499999999500000000.000, time: 0.362, 22.086 GB/sec. $ g++ -O3 -march=native -ffast-math main.cpp && ./a.out Res: 499999999268435456.000, time: 0.392, 20.428 GB/sec. $ clang++ -O3 -march=native -ffast-math -S main.cpp && cat main.s .LBB2_4: # =>This Inner Loop Header: Depth=1 vaddpd (%rdi,%rcx,8), %ymm0, %ymm0 vaddpd 32(%rdi,%rcx,8), %ymm1, %ymm1 vaddpd 64(%rdi,%rcx,8), %ymm2, %ymm2 vaddpd 96(%rdi,%rcx,8), %ymm3, %ymm3 addq $16, %rcx cmpq %rcx, %rdx jne .LBB2_4

Но так делать нельзя :(

Почему компилятор не векторизует цикл?

-ffast-math использовать нельзя.
Потому что это ломает точность вычислений.

Kahan Summation:

while (ptr < end) { double compensated_value = *ptr - compensation; double new_sum = sum + compensated_value; compensation = (new_sum - sum) - compensated_value; sum = new_sum; ++ptr; }

Почему компилятор не векторизует цикл?

-ffast-math использовать нельзя.
Потому что это ломает точность вычислений.

Kahan Summation:

while (ptr < end) { double compensated_value = *ptr - compensation; double new_sum = sum + compensated_value; compensation = (sum + compensated_value - sum) - compensated_value; sum = new_sum; ++ptr; }

Почему компилятор не векторизует цикл?

-ffast-math использовать нельзя.
Потому что это ломает точность вычислений.

Kahan Summation:

while (ptr < end) { double compensated_value = *ptr - compensation; double new_sum = sum + compensated_value; compensation = 0; sum = new_sum; ++ptr; }

Можно развернуть отдельный цикл вручную

/// Vectorized version template <typename Value> void NO_INLINE addMany(const Value * __restrict ptr, size_t count) { /// Compiler cannot unroll this loop, do it manually. /// (at least for floats, most likely due to the lack of -fassociative-math) /// Something around the number of SSE registers * the number of elements fit in register. constexpr size_t unroll_count = 128 / sizeof(T); T partial_sums[unroll_count]{}; const auto * end = ptr + count; const auto * unrolled_end = ptr + (count / unroll_count * unroll_count); while (ptr < unrolled_end) { for (size_t i = 0; i < unroll_count; ++i) partial_sums[i] += ptr[i]; ptr += unroll_count; } for (size_t i = 0; i < unroll_count; ++i) sum += partial_sums[i]; while (ptr < end) { sum += *ptr; ++ptr; } }

Можно развернуть отдельный цикл вручную

#pragma GCC push_options #pragma GCC optimize ("-ffast-math") template <typename T> __attribute__((__noinline__)) T sum(const T * ptr, const T * end) { T res{}; while (ptr < end) { res += *ptr; ++ptr; } return res; } #pragma GCC pop_options

Только для gcc.

Развернул цикл и...

Поднял машину в AWS, воспроизвёл результаты.

              median, 1000 queries
ClickHouse:   0.090 sec  
DBMS-X:       0.093 sec

ClickHouse на три миллисекунды быстрее!

ClickHouse не тормозит.

А является ли ClickHouse самой быстрой системой во всех сценариях?

Может ли кто-то стать быстрее ClickHouse хотя бы на одном запросе?

DBMS-Y

Умеет использовать не только CPU но и GPU.

Работает только с данными, помещающимися в память.

Не поддерживает сжатие данных.

Не поддерживает индексы и не сортирует хранимые данные.

Почти не поддерживает GROUP BY по строкам.

Выполняет один запрос быстрее чем ClickHouse?

DBMS-Y

Выполняет один запрос быстрее чем ClickHouse?

SELECT passenger_count, avg(total_amount) FROM trips GROUP BY passenger_count

passenger_count UInt8, total_amount Float32

— вычисление avg по ключу 0..255.

ClickHouse: 0.827 sec (MergeTree)
ClickHouse: 0.395 sec (MergeTree + uncompressed cache)
ClickHouse: 0.332 sec (Memory)
DBMS-Y:     0.204 sec

Xeon E5-2650v2, 32 logical CPU

Какой был бы идеальный код?

Для выполнения запроса:

SELECT key, avg(value) FROM table GROUP BY key

Структура данных:

Lookup таблица, 256 ячеек
— массив пар sum, count.

Алгоритм:

Просто цикл по входным данным
и обновление состояния в ячейке.

Какой был бы «идеальный» код?

struct State { float sum = 0; size_t count = 0; void add(float value) { sum += value; ++count; } }; void process(const vector<uint8_t> & keys, const vector<float> & values) { State map[256]{}; size_t size = keys.size(); for (size_t i = 0; i < size; ++i) map[keys[i]].add(values[i]); return map[0].result(); }

Какой код реально используется?

Используется loookup таблица.

Но есть всякие мелочи:

1. Состояния хранятся не прямо в ней,
 а по указателю, выделяются в отдельной арене.

2. В каждой ячейке хранится ещё один бит, занята ли она.

3. Буфер для lookup таблицы выделяется отдельно.

4. Размер lookup таблицы хранится отдельно и обновляется при insert.

Четыре возможности по оптимизации!

Четыре возможности по оптимизации

Я попробовал все.

Они помогли, но недостаточно.

Наш код уже «идеальный».

Но он работает недостаточно быстро,
нужна какая-то магия!

Развернуть цикл

Создать несколько таблиц состояний.
Агрегировать в разные, а потом слить вместе.

State map[256 * UNROLL_COUNT]{}; size_t size = keys.size(); size_t i = 0; size_t size_unrolled = size / UNROLL_COUNT * UNROLL_COUNT; for (; i < size_unrolled; i += UNROLL_COUNT) for (size_t j = 0; j < UNROLL_COUNT; ++j) map[256 * j + keys[i + j]].add(values[i + j]); for (size_t key = 0; key < 256; ++key) for (size_t j = 1; j < UNROLL_COUNT; ++j) map[key].merge(map[256 * j + key]); for (; i < size; ++i) map[keys[i]].add(values[i]);

Развернуть цикл по-другому

struct State4 { float sum[4]{}; size_t count[4]{}; ... }; State4 map[256]{}; size_t size = keys.size() / 4 * 4; for (size_t i = 0; i < size; i += 4) { map[keys[i]].add<0>(values[i]); map[keys[i + 1]].add<1>(values[i]); map[keys[i + 2]].add<2>(values[i]); map[keys[i + 3]].add<3>(values[i]); } ...

Буферизация и Batching

State map[256]{}; static constexpr size_t BUF_SIZE = 16384 / 256 / sizeof(float); /// Should fit in L1d. float buffers[256 * BUF_SIZE]; float * ptrs[256]; for (size_t i = 0; i < 256; ++i) ptrs[i] = &buffers[i * BUF_SIZE]; size_t size = keys.size(); const auto * key = keys.data(); const auto * key_end = key + size; const auto * value = values.data(); while (key < key_end) { *ptrs[*key] = *value; if (++ptrs[*key] == &buffers[(*key + 1) * BUF_SIZE]) /// Calculation is better than L1d load. { ptrs[*key] -= BUF_SIZE; map[*key].addBatch<BUF_SIZE>(ptrs[*key], BUF_SIZE); } ++key; ++value; } for (size_t i = 0; i < 256; ++i) map[i].addBatch<4>(&buffers[i * BUF_SIZE], ptrs[i] - &buffers[i * BUF_SIZE]);

Вариация на тему Bucket Sort

State map[256]{}; size_t size = keys.size(); /// Calculate histograms of keys. using CountType = UInt32; static constexpr size_t HISTOGRAM_SIZE = 256; CountType count[HISTOGRAM_SIZE * UNROLL_COUNT]{}; size_t unrolled_size = size / UNROLL_COUNT * UNROLL_COUNT; for (const UInt8 * elem = keys.data(); elem < keys.data() + unrolled_size; elem += UNROLL_COUNT) for (size_t i = 0; i < UNROLL_COUNT; ++i) ++count[i * HISTOGRAM_SIZE + elem[i]]; for (const UInt8 * elem = keys.data() + unrolled_size; elem < keys.data() + size; ++elem) ++count[*elem]; for (size_t i = 0; i < HISTOGRAM_SIZE; ++i) for (size_t j = 1; j < UNROLL_COUNT; ++j) count[i] += count[j * HISTOGRAM_SIZE + i]; /// Row indices in a batch for each key. PODArray<UInt32> indices(size); UInt32 * positions[HISTOGRAM_SIZE]; positions[0] = indices.data(); for (size_t i = 1; i < HISTOGRAM_SIZE; ++i) positions[i] = positions[i - 1] + count[i - 1]; for (size_t i = 0; i < size; ++i) *positions[keys[i]]++ = i; /// Update states. UInt32 * idx = indices.data(); for (size_t i = 0; i < HISTOGRAM_SIZE; ++i) for (; idx < positions[i]; ++idx) map[i].add(values[*idx]);

А во сколько раз разворачивать цикл?

При тестировании на разных серверах получаются разные результаты.

На процессорах AMD EPYC, Ryzen больше кэш
— можно разворачивать в 8 раз.

На процессорах Intel это вызывает ужасные тормоза
— и можно максимум в 4 раза.

А во сколько раз удаётся ускорить?

На модельном коде:

Baseline:   360 million rows/sec., 1804 MiB/sec.
Optimized: 1339 million rows/sec., 6695 MiB/sec. x3.72

Реальный запрос в ClickHouse:

ClickHouse (old): 0.332 sec.
DBMS-Y:           0.204 sec
ClickHouse (new): 0.197 sec. x1.69

Выводы

Если какая-то система на каком-то вырожденном запросе
  работает чуть-чуть быстрее ClickHouse
— это значит, что я ещё не оптимизировал код,
  и сделаю это завтра.

Внутреннее устройство ClickHouse позволяет
выполнять оптимизации под задачу и железо.

Бонус

Batch Aggregator:
https://github.com/ClickHouse/ClickHouse/pull/6435

Ускорение функции sum:
https://github.com/ClickHouse/ClickHouse/pull/10992

Ускорение GROUP BY 8bit key:
https://github.com/ClickHouse/ClickHouse/pull/13055 https://github.com/ClickHouse/ClickHouse/pull/13056 https://github.com/ClickHouse/ClickHouse/pull/13084 https://github.com/ClickHouse/ClickHouse/pull/13091 https://github.com/ClickHouse/ClickHouse/pull/13096 https://github.com/ClickHouse/ClickHouse/pull/13099

И тест с примерами:
https://github.com/ClickHouse/ClickHouse/blob/master/
 src/Common/tests/average.cpp

.