А является ли ClickHouse самой быстрой системой во всех сценариях?
А является ли ClickHouse самой быстрой системой во всех сценариях?
— в частных случаях можно выиграть...
... пока я этого не заметил.
А является ли ClickHouse самой быстрой системой во всех сценариях?
Работает с данными только с помощью mmap.
Не поддерживает сжатие данных.
Не поддерживает индексы и не сортирует хранимые данные.
Почти не поддерживает SQL.
Выполняет один запрос быстрее чем ClickHouse?
Выполняет один запрос быстрее чем 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
Скорость сканирования данных в ГБ/сек.
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 хотя бы на одном запросе?
Умеет использовать не только CPU но и GPU.
Работает только с данными, помещающимися в память.
Не поддерживает сжатие данных.
Не поддерживает индексы и не сортирует хранимые данные.
Почти не поддерживает GROUP BY по строкам.
Выполняет один запрос быстрее чем ClickHouse?
Выполняет один запрос быстрее чем 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]);
}
...
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]);
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