DoubleCloud 即将停止运营。利用限时免费迁移服务迁移到 ClickHouse。立即联系我们 ->->

博客 / 工程

ClickHouse 中的 JIT

Maksim Kita

2022 年 11 月 23 日

这篇博文最初发布在Maksim 的个人博客上，我们推荐对性能工程、查询分析和规划、JIT 编译、系统编程和分布式系统等底层细节感兴趣的读者阅读。

在这篇文章中，我将描述什么是 JIT 编译，如何使用 LLVM 基础设施进行 JIT 编译，以及 JIT 编译在 ClickHouse 中是如何工作的。

这篇文章的大部分内容是对我在 C++ Russia 2021“ClickHouse 中的 JIT”、HighLoad 2022“ClickHouse 中查询的 JIT 编译”、C++ Russia 2022“ClickHouse 性能优化实践”等演讲的总结，还有一些额外的例子和我在这些演讲中没有涉及的内容。

首先，让我们从什么是 JIT 编译开始。JIT - 即时编译。其主要思想是在运行时生成机器代码并执行它。此类系统的示例包括 JVM Hotspot 和 V8。大多数数据库系统都支持 JIT 编译。

为了更好地理解 JIT 编译的工作原理，我们可以从底层开始 - 用我们自己的双手进行 JIT 编译。

考虑以下代码示例

int64_t sum(int64_t value_1, int64_t value_2)
{
    return value_1 + value_2;
}

int main(int argc, char ** argv)
{
    printf("Sum %ld\n", sum(1, 2));
    return 0;
}

我们有一个 `sum` 函数，它接受两个整数值，计算它们的和并返回它。在 `main` 函数中，我们打印 `sum` 函数使用常数 1 和 2 执行的结果。

如果我们使用 gcc 编译此示例并使用 objdump 探索二进制文件，我们可以提取 `sum` 函数的汇编代码。

g++ --version
g++ (Ubuntu 10.3.0-1ubuntu1~20.04) 10.3.0


$ g++ -O2 jit_example.cpp -o jit_example
$ objdump -D jit_example | grep sum -A5

0000000000001180 <_Z3sumll>:
  1180:	f3 0f 1e fa             endbr64
  1184:	48 8d 04 37             lea    (%rdi,%rsi,1),%rax /// %rax = %rdi + %rsi * 1
  1188:	c3                      retq
  1189:	0f 1f 80 00 00 00 00    nopl   0x0(%rax)

要理解这个汇编代码，我们需要知道在我的机器上，存在 `System_V_AMD64_ABI` 调用约定，其中前两个函数参数分别传递到 `rdi`、`rsi` 寄存器中，函数结果存储在 `rax` 寄存器中。在 `sum` 函数体中，`endbr64` 指令用于检测控制流违规，`lea` 指令用于计算 `rdi` 和 `rsi` 寄存器的和并将结果放入 `rax` 寄存器中。

现在让我们看看 ELF（可执行和可链接格式）。

ELF 由 ELF 头、程序头、节头和节组成。程序头表描述了段和节到段映射的信息，这些信息对于操作系统执行二进制文件（可执行文件的视角）是必要的。节头表描述了关于节的信息（链接器的视角）。更多信息可以在手册页和 linux 基础规范中找到。

我们对链接器的视角感兴趣。让我们看看 ELF 文件中使用了哪些节，使用 readelf。


$ readelf -S jit_example

There are 31 section headers, starting at offset 0x39a8:

Section Headers:

...

[16] .text             PROGBITS         0000000000001060  00001060
00000000000001a5  0000000000000000  AX       0     0     16
[18] .rodata           PROGBITS         0000000000002000  00002000
000000000000000d  0000000000000000   A       0     0     4
[25] .data             PROGBITS         0000000000004000  00003000
0000000000000010  0000000000000000  WA       0     0     8

...

Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

这里需要注意的重要事项是，`.text` 节具有 READ + EXECUTE 权限，`.rodata` 节仅具有 READ 权限，而 `.data` 节具有 READ + WRITE 权限。

如果我们检查 `.rodata` 节的转储，我们可以看到链接器将用作 `printf` 函数第一个参数的常量放入其中。

printf("Sum %ld\n", sum(1, 2));

$ readelf -x .rodata jit_example

Hex dump of section '.rodata':
0x00002000 01000200 53756d20 256c640a 00       ....Sum %ld..

我们可以明确地检查我们的 `sum` 函数是否在 `.text` 节中。

$ objdump -D jit_example | grep sum -A5

0000000000001180 <_Z3sumll>:
    1180:	f3 0f 1e fa          	endbr64
    1184:	48 8d 04 37          	lea    (%rdi,%rsi,1),%rax
    1188:	c3                   	retq
    1189:	0f 1f 80 00 00 00 00 	nopl   0x0(%rax)

$ readelf -x .text jit_example

Hex dump of section '.text':
0x00001060 f30f1efa 4883ec08 ba030000 00bf0100 ....H...........
...
0x00001180 f30f1efa 488d0437 c30f1f80 00000000 ....H..7........
0x00001190 f30f1efa 41574c8d 3d1b2c00 00415649 ....AWL.=.,..AVI
0x000011a0 89d64155 4989f541 544189fc 55488d2d ..AUI..ATA..UH.-
...
0x00001200 f30f1efa c3                         ....

现在我们拥有了用我们自己的双手做同样事情所需的一切。

1144:   48 8d 04 37             lea    (%rdi,%rsi,1),%rax
1148:   c3                      retq

int64_t jitSum(int64_t value_1, int64_t value_2)
{
    /// Allocate page with READ + WRITE + EXECUTE permissions
    char * res = static_cast(mmap(NULL, 4096, PROT_READ | PROT_WRITE | PROT_EXEC,
            MAP_PRIVATE | MAP_ANON, -1, 0));

    size_t instruction = 0;

    /// lea (%rdi, %rsi, 1), %rax => rax = rdi + rsi * 1
    res[instruction++] = 0x48;
    res[instruction++] = 0x8d;
    res[instruction++] = 0x04;
    res[instruction++] = 0x37;

    /// retq
    res[instruction++] = 0xc3;

    using SumFunction = int64_t (*)(int64_t, int64_t);
    SumFunction func = reinterpret_cast<SumFunction>(res);

    return func(value_1, value_2);
}

int main(int argc, char ** argv)
{
    printf("Sum %ld\n", jitSum(1, 2));
    return 0;
}

这个例子稍微复杂一点，所以让我解释一下这里发生了什么。

使用 `mmap` 为要执行的代码分配内存。我们也可以使用任何页面对齐的内存并使用 `mprotect` 保护它。
将编码后的指令直接放入内存：`48 8d 04 37` 用于 `lea`，`0xc3` 用于 retq 指令。
将我们的页面指针转换为我们期望的函数指针类型。之后函数就可以执行了。

我们可以验证它是否按预期工作。

$ g++ -O2 jit_example.cpp -o jit_example
$ ./jit_example

$ Sum 3

但有一个问题还没有得到解答，那就是我们如何从 JIT 代码与我们的程序交互。考虑这个例子

void test_function()
{
   printf("JIT example\n");
}

void jitTestFuncCall()
{
   /// Allocate page with READ + WRITE + EXECUTE permissions
   char * res = static_cast<char *>(mmap(NULL, 4096, PROT_READ | PROT_WRITE | PROT_EXEC,
       MAP_PRIVATE | MAP_ANON, -1, 0));

   size_t instruction = 0;

   /// movabs [pointer_to_test_function], %rax
   res[instruction++] = 0x48;
   res[instruction++] = 0xb8;

   ptrdiff_t test_function_raw_ptr = reinterpret_cast<ptrdiff_t>(test_function);
   memcpy(res + instruction, &test_function_raw_ptr, sizeof(ptrdiff_t));
   instruction += sizeof(ptrdiff_t);

   /// callq *%rax
   res[instruction++] = 0xff;
   res[instruction++] = 0xd0;

   /// retq
   res[instruction++] = 0xc3;

   using VoidFunction = void (*)(void);
   VoidFunction func = reinterpret_cast<VoidFunction>(res);
   func();
}

int main(int argc, char ** argv)
{
   jitTestFuncCall();
   return 0;
}

在这个例子中，我们想从 JIT 代码中调用 `test_function` 函数。我们与上一个例子中做了几乎相同的事情，但不是编码 `lea` 指令，而是编码 `movabs [pointer_to_test_function], %rax` 和 `callq *%rax` 指令。

我们可以验证它是否有效。

$ g++ -O2 jit_example.cpp -o jit_example
$ ./jit_example

$ JIT example

JIT 代码和主程序中代码之间所有交互通常都是这样完成的，我们在 JIT 代码中传递函数指针并在 JIT 代码中调用它。

在高层次上，用于 JIT 编译的 LLVM 具有以下功能

优化编译器。可以配置优化过程，并且还可以根据您的特定用例改变优化级别。例如，您可以首先在不进行优化的情况下编译代码，然后稍后使用优化重新编译它。
动态链接器，用于解析重定位、分配必要的代码和数据段以及准备已编译的对象文件以供执行。
LLVM IR（LLVM 中间语言表示）。
许多 LLVM 工具，如 IR 和汇编打印机。用于支持 GDB 和 perf 的特殊 JIT 工具。MCJIT、ORCJIT JIT 编译器。在 ClickHouse 中，我们不使用它们，但您可以查看它们的实现以了解它们内部的工作原理。

LLVM IR 是 LLVM 中使用的中间语言表示。

静态单赋值。每个变量只赋值一次。
强类型。如果您没有正确获取类型，编译将在 IR 验证阶段失败。
允许将高级构造映射到低级表示。LLVM IR 支持模块、函数和结构。

让我们看看它是什么样子

int64_t sum(int64_t value_1, int64_t value_2)
{
    return value_1 + value_2;
}

/usr/bin/clang++-12 -S -emit-llvm jit_example.cpp

; Function Attrs: noinline nounwind optnone uwtable mustprogress
define dso_local i64 @_Z3sumll(i64 %0, i64 %1) #0 {
  %3 = alloca i64, align 8 /// alloca - allocate memory on stack
  %4 = alloca i64, align 8
  store i64 %0, i64* %3, align 8 /// store - store value in pointer
  store i64 %1, i64* %4, align 8
  %5 = load i64, i64* %3, align 8 /// load - load value from pointer
  %6 = load i64, i64* %4, align 8
  %7 = add nsw i64 %5, %6 /// nsw - No Signed Wrap
  ret i64 %7
}

我们在这篇文章的后面不会过多使用 LLVM IR，但我强烈建议您查看 LLVM IR 文档。

现在让我们看看 LLVM 的高级组件。

TargetMachine - 机器目标特定信息。允许的 CPU 指令、数据布局等。
LLVMContext - LLVM 全局数据的上下文。
IRBuilder - LLVM IR 的构建器。
Value - 所有计算值的基类（局部变量、全局变量、函数参数、常量）。
Function - BasicBlock 的函数容器。
BasicBlock - LLVM IR指令的容器，这些指令按顺序执行，直到终止指令（return，jump）。
Module - IR对象的容器，包括函数和全局变量。它还存储有关目标特性的信息。
PassManager - 模块通行证管理器。
FunctionPassManager - 函数通行证管理器。
PassManagerBuilder - 模块和函数优化通行证的构建器，用于填充PassManager和FunctionPassManager。
ObjectFile - 对象文件。
RuntimeDyld - 动态链接器，接收对象文件并启动动态链接过程，分配和填充代码和数据段，解析重定位。
RTDyldMemoryManager - 动态链接器内存管理器。在链接期间分配必要的代码和数据段。链接期间分配的内存的所有者。
JITSymbolResolver - 在动态链接期间解析外部符号。

使用LLVM高级组件进行JIT代码编译的策略

创建一个Module并用Functions填充它。使用PassManagerBuilder，FunctionPassManager和PassManager应用优化。
在PassManager中设置通行证，以使用TargetMachine从Module发出ObjectFile。
创建JITSymbolResolver以解析外部符号，例如memset。
为RuntimeDyld动态链接器创建RTDyldMemoryManager。
使用RuntimeDyld动态链接器解析重定位并为ObjectFile创建必要的代码和数据段。
使用RuntimeDyld动态链接器从编译后的代码中获取函数符号指针。

我们围绕JIT编译的包装器接口如下所示

class CHJIT
{
    struct CompiledModule
    {
        /// Size of compiled module code in bytes
        size_t size;

        /// Module identifier. Should not be changed by client
        uint64_t identifier;

        /// Map of compiled functions. Should not be changed by client
        std::unordered_map<std::string, void *> function_name_to_symbol;
    };

    /// Compile module. Client must fill module with necessary IR code.
    CompiledModule compileModule(std::function<void (llvm::Module &)> compile_function);

    /** Delete compiled module.
      * Pointers to functions from module become invalid after this call.
      */
    void deleteCompiledModule(const CompiledModule & module_info);

    /// Register external symbol for CHJIT instance to use, during linking.
    void registerExternalSymbol(const std::string & symbol_name, void * address);

    /// Total compiled code size for modules that are currently valid.
    inline size_t getCompiledCodeSize() const;
}

在实现中，我们的包装器使用与上面描述相同的策略。此外，它

为每个编译的模块存储RTDyldMemoryManager，以便在请求时可以删除它。
使用编译器memset，memcpy，memcmp可以生成的通用函数设置JITSymbolResolver。
使用自定义分配器进行JIT代码。
提供线程安全。

现在让我们看一个如何使用此抽象的小例子。

auto jit = DB::CHJIT();

auto compiled_sum_module = jit.compileModule([](llvm::Module & module)
{
    llvm::LLVMContext & context = module.getContext();
    llvm::IRBuilder<> b(context);

    llvm::Type * int64_type = b.getInt64Ty();
    std::vector params = {int64_type, int64_type};
    bool is_var_args = false;
    llvm::FunctionType * func_type =
        llvm::FunctionType::get(int64_type, params, is_var_args);

    llvm::Function::LinkageTypes linkage = 
    llvm::Function::ExternalLinkage;
    llvm::Function * function =
        llvm::Function::Create(func_type, linkage, "sum", module);

    /// Get first argument
    llvm::Value * first_argument = function->args().begin();

    /// Get second argument
    llvm::Value * second_argument = function->args().begin() + 1;

    /// Create function entry basic block
    llvm::BasicBlock * entry = 
    llvm::BasicBlock::Create(context, "entry", function);
    b.SetInsertPoint(entry);

    /// Sum arguments
    llvm::Value * sum = b.CreateAdd(first_argument, second_argument);

    /// Return sum result
    b.CreateRet(sum);
});

using SumFunc = int64_t (*)(int64_t, int64_t);
auto sum_func = 
reinterpret_cast(compiled_sum_module.function_name_to_symbol["sum"]);
printf("Sum %ld\n", sum_func(1, 2));

jit.deleteCompiledModule(compiled_sum_module);

这里我们创建我们的CHJIT包装器，调用compileModule函数并将sum LLVM函数（由1个BasicBlock组成）使用IRBuilder添加到Module中。这样的sum函数编译成这个IR

define i64 @sum(i64 %0, i64 %1) {
    entry:
    %2 = add i64 %0, %1
    ret i64 %2
}

然后转换成这个汇编程序（如果我们指定O3优化）

.text
	.file	"jit0"
	.globl	sum                             # -- Begin function sum
	.p2align	4, 0x90
	.type	sum,@function
sum:                                    # @sum
# %bb.0:                                # %entry
	leaq	(%rdi,%rsi), %rax
	retq
.Lfunc_end0:
	.size	sum, .Lfunc_end0-sum # -- End function

需要注意的另一件事是与LLVM的集成。LLVM在没有异常的情况下编译，并且在很多地方，断言用于验证不变量。在发布版本中，这可能是一个问题，因为这些断言没有被检查。在我们的案例中，最大的问题是，如果构造的LLVM IR格式不正确，LLVM将崩溃，或者编译的代码将被破坏，并可能在运行时崩溃。我们通过在CI/CD基础架构中进行额外的测试和AST模糊测试来解决这个问题。

ClickHouse是一个面向列的DBMS。它具有面向列的存储和向量化查询执行引擎。

在面向列的存储中，数据按列物理存储。

在查询期间，仅从磁盘读取必要的列。
更好的压缩，因为类似的数据几乎位于一起。

这两个因素都显著减少了查询执行期间的IO量。

向量化查询执行引擎以块为单位处理数据。块包含多列，最大行数为max_block_size（默认为65505）。每列存储为原始数据类型或其组合的向量

更好地利用CPU缓存和流水线。
可以使用SIMD指令处理数据。

最重要的组件是IColumn

class IColumn
{
    ...

    virtual ~IColumn() = default;

    [[nodiscard]] virtual Ptr filter(const Filter & filt, ssize_t result_size_hint) const = 0;

    [[nodiscard]] virtual Ptr permute(const Permutation & perm, size_t limit) const = 0;

    virtual void insertFrom(const IColumn & src, size_t n);

    virtual void insertRangeFrom(const IColumn & src, size_t start, size_t length) = 0;

    ...
}

它声明了所有具体列类型需要支持的方法，例如，filter或permute。在大多数函数中，IColumn被解包为具体类型。每列都存储为原始类型的数组或其组合。

数值列使用PaddedPODArray存储。它与std::vector几乎相同，但有一些区别

它使用支持realloc的分配器（对于大型内存块，它使用mremap实现）。
调整大小期间没有额外的memset。
在末尾填充15个字节。这允许更有效地实现memcpy函数，其中它没有处理尾部的额外检查。

其他列实现为数值列的组合

Nullable列包含数据列和UInt8列，其中每个值表示元素是否为空。
字符串列包含UInt8数据列和带有偏移量的UInt64列。
数组列包含数据列和带有偏移量的UInt64列。
Const列包含1个常数值。

执行引擎中的下一个重要组件是IFunction

class IFunction
{
    ...

    virtual ~IFunction() = default;

    virtual ColumnPtr executeImpl(
        const ColumnsWithTypeAndName & arguments,
        const DataTypePtr & result_type,
        size_t input_rows_count) const = 0;

    ...
}

有很多函数的专门化

不同类型及其组合的专门化。
常量列的专门化。

函数plus有

UInt8 UInt16 UInt32 UInt64      UInt8 UInt16 UInt32 UInt64
    Int8 Int16 Int32 Int64  ✕      Int8 Int16 Int32 Int64
            Float32 Float64             Float32 Float64

不同类型的专门化。此外，如果其中一列是常量列，则还具有专门化。结果20 x 20 = 400个单个plus函数的专门化。

当前接口的优势

代码隔离。在函数内部，很容易实现一些复杂的操作或进行非平凡的逻辑。它将在函数内部很好地隔离。
高效率。可以使用模板生成不同类型的专门化。
编译器可以使用SIMD指令向量化循环。如前所述，列只是数组，因此大多数函数都遍历数组并应用某些操作。

缺点

大量使用模板。对于某些函数，模板可能会变得复杂。
二进制代码膨胀。主要与大量使用模板有关。
如果没有使用CPUID的运行时分派，则无法使用AVX256，AVX512指令，因为ClickHouse作为具有最小指令集SSE4.2的可移植二进制文件分发。

现在让我们讨论Clickhouse查询执行。从高级别来看，ClickHouse查询执行如下

将查询解析为AST。
进行AST优化（大多数需要移动到逻辑查询计划上的优化）。
构建逻辑查询计划+进行逻辑查询计划优化。
构建物理查询计划+进行物理查询计划优化。
执行物理查询计划。

我们可以使用EXPLAIN查询轻松地检查每个步骤的输出。

解释AST

EXPLAIN AST value * 2 + 1 FROM test_table
WHERE value > 10 ORDER BY value;

┌─explain─────────────────────────────────────┐
│ SelectWithUnionQuery (children 1)           │
│  ExpressionList (children 1)                │
│   SelectQuery (children 4)                  │
│    ExpressionList (children 1)              │
│     Function plus (children 1)              │
│      ExpressionList (children 2)            │
│       Function multiply (children 1)        │
│        ExpressionList (children 2)          │
│         Identifier value                    │
│         Literal UInt64_2                    │
│       Literal UInt64_1                      │
│    TablesInSelectQuery (children 1)         │
│     TablesInSelectQueryElement (children 1) │
│      TableExpression (children 1)           │
│       TableIdentifier test_table            │
│    Function greater (children 1)            │
│     ExpressionList (children 2)             │
│      Identifier value                       │
│      Literal UInt64_10                      │
│    ExpressionList (children 1)              │
│     OrderByElement (children 1)             │
│      Identifier value                       │
└─────────────────────────────────────────────┘

解释逻辑查询计划

EXPLAIN PLAN SELECT value * 2 + 1 FROM test_table
WHERE value > 10 ORDER BY value;

┌─explain──────────────────────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY [lifted up part]))     │
│   Sorting (Sorting for ORDER BY)                                 │
│     Expression (Before ORDER BY)                                 │
│       Filter (WHERE)                                             │
│         SettingQuotaAndLimits                                    │
│           ReadFromMergeTree (default.test_table)                 │
└──────────────────────────────────────────────────────────────────┘

解释物理查询计划

EXPLAIN PIPELINE SELECT value * 2 + 1 FROM test_table
WHERE value > 10 ORDER BY value;

┌─explain────────────────────────────────────┐
│ (Expression)                               │
│ ExpressionTransform                        │
│   (Sorting)                                │
│   MergingSortedTransform 16 → 1            │
│     MergeSortingTransform × 16             │
│       LimitsCheckingTransform × 16         │
│         PartialSortingTransform × 16       │
│           (Expression)                     │
│           ExpressionTransform × 16         │
│             (Filter)                       │
│             FilterTransform × 16           │
│               (SettingQuotaAndLimits)      │
│                 (ReadFromMergeTree)        │
│                 MergeTreeThread × 16 0 → 1 │
└────────────────────────────────────────────┘

在SQL查询执行的不同步骤中，执行引擎需要计算表达式。例如

EXPLAIN PIPELINE SELECT value * 2 + 1 FROM test_table
WHERE value > 10 ORDER BY value;

┌─explain────────────────────────────────────┐
│ (Expression)                               │
│ ExpressionTransform                        │
│   (Sorting)                                │
│   MergingSortedTransform 16 → 1            │
│     MergeSortingTransform × 16             │
│       LimitsCheckingTransform × 16         │
│         PartialSortingTransform × 16       │
│           (Expression)                     │
│           ExpressionTransform × 16         │
│             (Filter)                       │
│             FilterTransform × 16           │
│               (SettingQuotaAndLimits)      │
│                 (ReadFromMergeTree)        │
│                 MergeTreeThread × 16 0 → 1 │
└────────────────────────────────────────────┘

在查询执行期间，执行引擎需要评估value > 10和value * 2 + 1表达式。在物理查询计划中，此步骤称为ExpressionTransform。表达式表示为具有input，function和constant类型节点的表达式DAG。

plus(plus(a, multiply(b, c)), 5) DAG的示例

DAG解释的主要问题是数据在函数之间移动。操作没有融合。例如，对于这样的DAG plus(plus(a, b), c))，首先执行plus(a, b)并将结果存储在临时列中。然后执行plus，其中包括临时列和列c。

为了支持JIT编译，在IFunction接口中添加了支持

class IFunction
{
    ...

    bool isCompilable(const DataTypes & arguments) const;

    llvm::Value * compile(
        llvm::IRBuilderBase & builder,
        const DataTypes & arguments_types,
        std::vector<llvm::Value *> arguments) const;

    ...
}

如果可以为特定数据类型编译函数，则必须在isCompilable方法中返回true。并在compile方法调用期间，使用IRBuilder对参数应用逻辑并返回结果。

目前支持编译

二元运算符。例如：plus，minus，multiply，xor。
一元运算符。例如：abs。
逻辑函数。例如：and，or，not。
条件函数。例如：if，multiIf。
位移位函数。例如：bitShiftLeft。

JIT表达式编译算法

对于DAG中的每个节点，计算children_size，compilable_children_size。
按compilable_children_size降序对节点进行排序，以便首先编译具有最多子节点的节点。
检查节点是否可以使用启发式方法进行编译。目前，我们要求节点至少包含1个可编译的子节点。
将节点及其可编译的子节点一起编译成一个函数。此函数接收原始列数据指针并返回表达式结果。
用特殊的LLVMFunction节点替换DAG中的节点。LLVMFunction执行方法将列转换为原始数据并调用编译后的函数。

假设我们有这样的DAG plus(plus(a, multiply(b, c)), 5)

JIT编译后，DAG将如下所示

多个函数被融合成一个函数，并且常量被内联。

此外，JIT帮助我们实现了以下功能

改进的L1，L2缓存使用。
更少的代码需要执行。它位于1页上。更好地使用CPU分支预测器。
消除间接寻址。
多个操作在一个函数中融合。编译器可以执行更多优化。
根据需要使用目标CPU指令（AVX256，AVX512）。LLVM编译器可以在编译期间使用您的CPU的最新可用指令集（AVX2，AVX512）。

改进的L1，L2缓存使用非常重要。如果我们检查著名的数字表，主内存引用比L2缓存访问慢20倍，比L1缓存访问慢200倍。

考虑这样的例子SELECT a + b * c + 5 FROM test_table。此表达式DAG plus(plus(a, multiply(b, c)), 5)编译成这样的LLVM IR

define void @"plus(plus(UInt64, multiply(UInt64, UInt64)), 5 : UInt8)"(i64 %0, ptr %1) {
entry:
  %2 = getelementptr inbounds { ptr, ptr }, ptr %1, i64 0
  %3 = load { ptr, ptr }, ptr %2, align 8
  %4 = extractvalue { ptr, ptr } %3, 0
  %5 = getelementptr inbounds { ptr, ptr }, ptr %1, i64 1
  %6 = load { ptr, ptr }, ptr %5, align 8
  %7 = extractvalue { ptr, ptr } %6, 0
  %8 = getelementptr inbounds { ptr, ptr }, ptr %1, i64 2
  %9 = load { ptr, ptr }, ptr %8, align 8
  %10 = extractvalue { ptr, ptr } %9, 0
  %11 = getelementptr inbounds { ptr, ptr }, ptr %1, i64 3
  %12 = load { ptr, ptr }, ptr %11, align 8
  %13 = extractvalue { ptr, ptr } %12, 0
  %14 = icmp eq i64 %0, 0
  br i1 %14, label %end, label %loop

end:                                              ; preds = %loop, %entry
  ret void

loop:                                             ; preds = %loop, %entry
  %15 = phi i64 [ 0, %entry ], [ %26, %loop ]     /// PHI loop counter
  %16 = getelementptr i64, ptr %4, i64 %15        /// Adjust first argument ptr using loop counter
  %17 = load i64, ptr %16, align 8                /// Load first argument data from adjusted ptr
  %18 = getelementptr i64, ptr %7, i64 %15        /// Adjust second argument ptr using loop counter
  %19 = load i64, ptr %18, align 8                /// Load second argument data from adjusted ptr
  %20 = getelementptr i64, ptr %10, i64 %15       /// Adjust third argument ptr using loop counter
  %21 = load i64, ptr %20, align 8                /// Load third argument data from adjusted ptr
  %22 = mul i64 %19, %21                          /// Multiply second and third argument
  %23 = add i64 %17, %22                          /// Add first argument
  %24 = add i64 %23, 5                            /// Add constant 5
  %25 = getelementptr i64, ptr %13, i64 %15       /// Adjust result ptr using loop counter
  store i64 %24, ptr %25, align 8                 /// Write result value thought adjusted result ptr
  %26 = add i64 %15, 1                            /// Increment loop counter
  %27 = icmp eq i64 %26, %0                       /// Check if loop need to be terminated
  br i1 %27, label %end, label %loop              /// Terminate loop or jump to the next iteration
}

此LLVM IR可以表示为这样的代码

void aPlusBMulitplyCPlusConstant5(
    int64_t * a,
    int64_t * b,
    int64_t * c,
    int64_t * result,
    size_t size)
{
    for (size_t i = 0; i < size; ++i)
    {
        result[i] = a[i] + b[i] * c[i] + 5;
    }
}

结果汇编中生成的循环将如下所示


.LBB0_8:                                # %vector.body
    vmovdqu	(%r11,%rax,8), %ymm1
    vmovdqu	(%r9,%rax,8), %ymm3
    vmovdqu	32(%r11,%rax,8), %ymm2
    vmovdqu	32(%r9,%rax,8), %ymm4
    vpsrlq	$32, %ymm3, %ymm5
    vpsrlq	$32, %ymm1, %ymm6
    vpmuludq	%ymm1, %ymm5, %ymm5
    vpmuludq	%ymm6, %ymm3, %ymm6
    vpmuludq	%ymm1, %ymm3, %ymm1
    vpsrlq	$32, %ymm4, %ymm3
    vpmuludq	%ymm2, %ymm3, %ymm3
    vpaddq	%ymm5, %ymm6, %ymm5
    vpsllq	$32, %ymm5, %ymm5
    vpaddq	%ymm5, %ymm1, %ymm1
    vpsrlq	$32, %ymm2, %ymm5
    vpmuludq	%ymm2, %ymm4, %ymm2
    vpaddq	(%r14,%rax,8), %ymm1, %ymm1
    vpmuludq	%ymm5, %ymm4, %ymm5
    vpaddq	%ymm3, %ymm5, %ymm3
    vpsllq	$32, %ymm3, %ymm3
    vpaddq	%ymm3, %ymm2, %ymm2
    vpaddq	32(%r14,%rax,8), %ymm2, %ymm2
    vpaddq	%ymm0, %ymm1, %ymm1 /// in ymm0 there is constant 5
    vmovdqu	%ymm1, (%r10,%rax,8)
    vpaddq	%ymm0, %ymm2, %ymm2
    vmovdqu	%ymm2, 32(%r10,%rax,8)
    addq	$8, %rax
    cmpq	%rax, %r8

首先，让我们看看物理查询计划中聚合是什么样子的

EXPLAIN PIPELINE SELECT sum(UserID)
FROM default.hits_100m_single GROUP BY WatchID;

┌─explain────────────────────────────────┐
│ (Expression)                           │
│ ExpressionTransform                    │
│   (Aggregating)                        │
│   Resize 16 → 1                        │
│     AggregatingTransform × 15          │
│       StrictResize 16 → 16             │
│         (Expression)                   │
│         ExpressionTransform × 16       │
│           (SettingQuotaAndLimits)      │
│             (ReadFromMergeTree)        │
│             MergeTreeThread × 16 0 → 1 │
└────────────────────────────────────────┘

高级架构如下所示

聚合函数接口如下所示

class IAggregateFunction
{
    ...

    virtual ~IAggregateFunction() = default;

    /// AggregateDataPtr pointer to aggregate data for unique key during GROUP BY

    /// Create empty data for aggregation with `placement new` at the specified location.
    virtual void create(AggregateDataPtr place) const = 0;

    /** Adds a value into aggregation data on which place points to.
      * columns points to columns containing arguments of aggregation function.
      * row_num is number of row which should be added.
      */
    virtual void add(
        AggregateDataPtr place,
        const IColumn ** columns,
        size_t row_num,
        Arena * arena) const = 0;

    /// Merges state (on which place points to) with other state of current aggregation function.
    virtual void merge(AggregateDataPtr place, ConstAggregateDataPtr rhs, Arena * arena) const = 0;

    /// Inserts results into a column. This method might modify the state (e.g.
    /// sort an array), so must be called once, from a single thread.
    virtual void insertResultInto(AggregateDataPtr place, IColumn & to, Arena * arena) const = 0;

    ...
}

一般来说，聚合函数由其状态和对该状态的操作定义

创建状态。
将值添加到状态。
合并状态。如果使用多个线程执行聚合，则需要此操作。
将状态具体化为列值，并将此具体化值插入结果列中。此操作在聚合结束时执行一次。

对于每个聚合函数，状态可能不同。例如，对于sum函数，它可以只是UInt64。对于avg函数，它可以是UInt64表示总和，UInt64表示计数，在状态具体化期间，最终值计算为总和除以计数。

在聚合过程中，为每个唯一的聚合键创建状态并存储在哈希表中。我们有一个高度优化的哈希表框架（值得单独发帖），我们在其中存储聚合函数的状态。

现在让我们举一个查询示例

SELECT sum(UserID)
FROM default.hits_100m_obfuscated
GROUP BY WatchID

在此示例中，聚合键为WatchID，我们有一个sum聚合函数，UserID是sum聚合函数的参数。

在聚合执行期间

对于每一行，在哈希表中查找聚合键（在我们的例子中为WatchID）的聚合状态。如果聚合状态存在，则将聚合函数参数值（在我们的例子中为UserID）添加到聚合状态。否则，为该聚合键创建聚合函数状态，并将聚合函数参数值添加到聚合状态。
对于每个唯一的聚合键，如果使用多个线程进行聚合，则合并聚合函数状态（大多数情况下，ClickHouse中正在进行并行GROUP BY运算符处理）。
对于每个唯一的聚合键，具体化聚合函数状态并将结果插入最终列中。

在这些步骤中，我们调用

每个唯一键的create聚合函数方法。
每行的add聚合函数方法。
每个唯一键的merge聚合函数方法。
每个唯一键的insertResultInto聚合函数方法。

主要问题是我们执行了大量的虚函数调用。在多个聚合函数的情况下，情况更加糟糕，因为我们必须执行与单个函数示例中相同数量的虚函数调用，此外还要乘以聚合函数的数量。

这种方法的其他问题

对于可空列，我们有一个可空包装器，它包装任何聚合函数以处理可空列。这引入了额外的间接层。
我们还有聚合组合器，例如-If、-Array。它们包装任何聚合函数并添加特定逻辑。这引入了额外的间接层。例如：SELECT sumIf(column, metric > value)。

解决方案很明显，我们需要将多个聚合函数融合成一个。基本上，聚合期间的聚合函数使用 4 个操作：create、add、merge、insertResultInto。我们可以将这些操作融合到多个函数中，以避免间接调用并减少虚函数调用的数量。

编译支持以下聚合函数

最常见的聚合函数sum、count、min、max、avg、avgWeighted。
可空聚合函数适配器。
聚合函数组合器-If。

例如，如果我们采用查询

SELECT
    sum(UserID),
    avg(ClientIP),
    sum(CounterClass),
    min(CounterID),
    max(WatchID)
FROM default.hits_100m_obfuscated
GROUP BY WatchID

多个聚合函数将被融合成一个

SELECT
    sum_avg_sum_min_max(
        UserID,
        ClientIP,
        CounterClass,
        CounterID,
        WatchID)
FROM default.hits_100m_obfuscated
GROUP BY WatchID

首先，让我们看看物理查询计划中ORDER BY的样子

EXPLAIN PIPELINE SELECT WatchID FROM hits_100m_single
ORDER BY WatchID, CounterID;

┌─explain──────────────────────────────────┐
│ (Expression)                             │
│ ExpressionTransform                      │
│   (Sorting)                              │
│   MergingSortedTransform 16 → 1          │
│     MergeSortingTransform × 16           │
│       LimitsCheckingTransform × 16       │
│         PartialSortingTransform × 16     │
│           (Expression)                   │
│           ExpressionTransform × 16       │
│             (SettingQuotaAndLimits)      │
│               (ReadFromMergeTree)        │
│               MergeTreeThread × 16 0 → 1 │
└──────────────────────────────────────────┘

在物理查询计划中，我们有多个转换协同工作以执行排序

PartialSortingTransform — 对单个块进行排序，如果指定了LIMIT，则应用特殊优化。
MergeSortingTransform — 使用 k 路归并算法对多个块进行排序，此转换的输出是已排序块的流。
MergingSortedTransform — 使用k 路归并算法对多个已排序块的流进行排序。

PartialSortingTransform 中单个块的排序可以在批处理中执行，无需间接调用。IColumn 中有getPermutation、updatePemuration方法，它们返回或更新排列。此排列稍后可以使用permute方法有效地应用于任何列。

问题在于 MergeSortingTransform 和 MergingSortedTransform。它们必须执行 k 路归并算法，并且此算法对单个行而不是列进行操作。在最坏的情况下，在我们的 MergeSortingTransform、MergingSortedTransform 期间，我们将对每一行应用ORDER BY WatchID, CounterID比较器N * log(N) * 2次。

IColumn compareAt 和排序游标greaterAt方法的代码示例

class IColumn
{
    ...
    virtual int compareAt(size_t n, size_t m, const IColumn & rhs, int nan_direction_hint) const = 0;
    ...
}

struct SortCursor : SortCursorHelper<SortCursor>
{
   using SortCursorHelper<SortCursor>::SortCursorHelper;

   /// The specified row of this cursor is greater than the specified row of another cursor.
   bool greaterAt(const SortCursor & rhs, size_t lhs_pos, size_t rhs_pos) const
   {
       for (size_t i = 0; i < impl->sort_columns_size; ++i)
       {
           const auto & sort_description = impl->desc[i];
           int direction = sort_description.direction;
           int nulls_direction = sort_description.nulls_direction;
           int res = direction * impl->sort_columns[i]->compareAt(lhs_pos, rhs_pos,
               *(rhs.impl->sort_columns[i]), nulls_direction);

           if (res > 0)
               return true;
           if (res < 0)
               return false;
       }

       return impl->order > rhs.impl->order;
   }
};

对于列式数据库来说，最糟糕的事情是按行处理元素。这里最大的问题是，对于ORDER BY比较器中指定的每一列，我们都会调用compareAt方法。如果比较器中指定了多列，我们可以将多个compareAt方法融合到单个函数中，以避免不必要的间接调用并减少虚函数调用的数量。

对于可空列，性能可能会更好，因为在其compareAt方法的实现中，它首先检查空值，如果两个值都不为空，则使用内部列的compareAt方法。

现在，编译成本如何？表达式的 JIT 编译时间、聚合函数或 ORDER BY 比较器大约为 5-15 毫秒，并且随着代码大小线性增长。平均编译后的函数为代码部分使用 1 页，为数据部分使用 1 页。在大多数配置中，4096 * 2 = 8192 字节。

ClickHouse 内部使用CompileExpressionsMicroseconds、CompileExpressionsBytes指标进行内省，这些指标可用于每个查询。

SELECT
    ProfileEvents['CompileExpressionsMicroseconds'] AS compiled_time,
    ProfileEvents['CompileExpressionsBytes'] AS compiled_bytes
FROM system.query_log
WHERE compiled_time > 0;

┌─compiled_time─┬─compiled_bytes─┐
│         16258 │           8192 │
│         26792 │           8192 │
│         15280 │           8192 │
│         11594 │           8192 │
│         14989 │           8192 │
└───────────────┴────────────────┘

在 ClickHouse 中，我们仅在看到一些相同重复的表达式时才执行表达式的编译。聚合函数和 ORDER BY 比较器也是如此。此数字可以使用min_count_to_compile_expression、min_count_to_compile_aggregate_expression、min_count_to_compile_sort_description 设置进行控制，默认情况下它们的值等于 3。为了避免不必要的重新编译，我们使用 LRU 缓存来存储 JIT 编译的代码。

JIT 编译可以将动态配置转换为静态配置