博客 / 工程

ClickHouse 中的 JIT

Maksim Kita

2022年11月23日 - 35 分钟阅读

这篇博文最初发布在 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 函数中，我们打印使用常量 1 和 2 执行 sum 函数的结果。

如果我们使用 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 头部、程序头部、节头部和节组成。程序头表描述了关于段以及段到段的映射的信息，这对于操作系统执行二进制文件（可执行文件的角度）是必要的。节头表描述了关于节的信息（链接器的角度）。更多信息可以在 man page 和 linux base specification 中找到。

我们对链接器的角度感兴趣。让我们看看使用 readelf 在 ELF 文件内部有哪些节。


$ 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 指令的容器，这些指令按顺序执行，直到终止指令（返回、跳转）。
Module - IR 对象的容器，包括函数和全局变量。它还存储有关目标特性的信息。
PassManager - 模块 pass 管理器。
FunctionPassManager - 函数 pass 管理器。
PassManagerBuilder - 模块和函数优化 pass 的构建器，用于填充 PassManager 和 FunctionPassManager。
ObjectFile - 目标文件。
RuntimeDyld - 动态链接器，它接受目标文件并启动动态链接过程，分配和填充代码和数据节，解析重定位。
RTDyldMemoryManager - 动态链接器内存管理器。在链接期间分配必要的代码和数据节。链接期间分配的内存的所有者。
JITSymbolResolver - 在动态链接期间解析外部符号。

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

创建一个模块并用函数填充它。使用 PassManagerBuilder、FunctionPassManager 和 PassManager 应用优化。
在 PassManager 中设置 pass，以使用 TargetMachine 从模块发出 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 函数，并使用 IRBuilder 将 sum LLVM 函数（由 1 个 BasicBlock 组成）添加到模块中。这样的 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 列，其中每个值表示元素是否为空。
String 列包含 UInt8 数据列和带有偏移量的 UInt64 列。
Array 列包含数据列和带有偏移量的 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

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

当前接口的优点

代码隔离。在函数内部，很容易实现一些复杂的操作或进行重要的逻辑。它将在函数内部得到很好的隔离。
高效率。可以使用模板生成针对不同类型的特化。
编译器可以使用 SIMD 指令向量化循环。如前所述，列只是数组，因此大多数函数迭代数组并应用一些操作。

缺点

大量使用模板。对于某些函数，模板可能会变得复杂。
二进制代码膨胀。主要与大量使用模板有关。
AVX256、AVX512 指令在不使用 CPUID 进行运行时分派的情况下无法使用，因为 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。表达式表示为表达式 DAG，它具有 input、function 和 constant 类型的节点。

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

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

为了支持 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 缓存使用率。
更少的代码需要执行。它被放置在一个页面上。更好地利用 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 │
└────────────────────────────────────────┘

高层次架构如下所示

Aggregate 函数接口如下所示

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 聚合函数方法用于每个唯一的键。

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

此方法的其他问题

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

解决方案是显而易见的，我们需要将多个聚合函数融合为一个。基本上，聚合函数在聚合期间使用 4 个动作：create、add、merge、insertResultInto。我们可以融合多个函数的这些动作，以避免间接调用并减少虚函数调用的次数。

以下聚合函数支持编译

最常见的聚合函数 sum、count、min、max、avg、avgWeighted。
Nullable 聚合函数适配器。
聚合函数组合器 -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、updatePemutation 方法，它们返回或更新排列。此排列稍后可以使用 permute 方法有效地应用于任何列。

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

IColumn 的 compareAt 和 sort 光标 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 方法融合到一个函数中，以避免不必要的间接调用，并在比较器中指定多列时减少虚函数调用的次数。

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

现在，编译成本如何？表达式、聚合函数或 ORDER BY 比较器的 JIT 编译时间约为 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 settings 设置来控制，默认情况下，它们的值等于 3。为了避免不必要的重新编译，我们对 JIT 编译的代码使用 LRU 缓存。

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