数据库性能之翼:SQL 语句运行时编译

数据库性能之翼:SQL 语句运行时编译

摘要

现代服务器的一大特点是内存越来越大,对于运行在这些服务器上的数据库,性能的瓶颈是 CPU 而非内存;然而传统 SQL 执行模型即“火山模型” 诞生于内存是瓶颈的年代,其以行为单位的迭代执行过程虽然灵活,但对 CPU 非常不友好。

在这个大背景下,SQL 语句运行时编译技术应运而生,为传统的关系型数据库的 SQL 执行性能插上翅膀。

一些 SQL 编译的实现如下:

  1. Apache Spark Tungsten 引擎运行时将 SQL 语句的 Where 部分转换成抽象语法树,然后再讲抽象语法树运行时编译成 Java 字节码。
  2. Oracle 数据库将 SQL 语句运行时转换为 C\C++ 代码,然后将其编译为机器码。
  3. Postgres 11 中提供了基于 LLVM 的即时编译(JIT) 的 SQL 语句执行引擎。有实验证明 Postgres 上 SQL 语句编译技术能够将 Postgres 的事务处理能力提升20%之500%

随着 CPU 和多核瓶颈日益凸显,SQL 语句编译技术会成为重要的数据库性能提升技术。希望读者通过本篇博客能够了对 SQL 编译技术有个大概的认识。

为什么要进行 SQL 编译

通用(抽象) vs 定向优化

SQL 是一个非常优秀的抽象模型;对于使用者来讲,SQL 简单易用,不用关心 SQL
背后的诸如存储、同步及先写日志等细节;从而使得:

  1. SQL 可以运行在任何一台计算机上
  2. 开发人员不需要关心 SQL 语句的执行过程,通过陈述的方式描述业务逻辑

另外一方面,现代的计算机硬件在不断进步,SQL 语句运行速度的关键是针对这些硬件进行定向优化。

SQL 运行时编译正好可以弥补通用抽象和定向优化之间的性能差距。

火山模型

火山模型是数据库成熟的 SQL 语句解释执行方案,该模型是一个数据库执行器实现中非常流行的“设计模式”。该设计模式将关系型代数中的每一种操作抽象成一个 Operator,整个 SQL 语句在这种情况下形成一个 Operator 树;通过自顶向下的调用 next 接口,火山模型能够以数据库行为单位处理数据。
SQL
Volcano Model

火山模型有如下特点:

  1. 首先该模型以数据行为单位处理数据,每一行数据的处理,都会调用 next 接口多次;当 SQL 语句涉及的数据行数特别多的情况下,next 的调用次数会相当大。
  2. next 接口的调用,是通过虚函数机制;相比于直接调用函数,虚函数机制需要的 CPU 指令更多,因此也更加昂贵。
  3. 以行为单位的数据处理,会导致 CPU 缓存使用效率低下和一些不必要的复杂性;首先数据库必须记住处理到哪一行,以便处理跳到下一行;其次处理完一行后需要将下一行加载到 CPU 缓存中,而实际上 CPU 缓存所能存储的数据行数远不止一行。
  4. 火山模型最大的好处是工程上非常干净,每个Operator有良好的抽象,只需要关心自己负责的逻辑就可以,比如Filter只需要关心如何根据谓词过滤数据,Aggregates只需要关心如何聚合数据。

一言以蔽之,火山模型首先会导致更多的 CPU 指令,更为严重的是会导致 CPU 缓存效率低下,严重影响数据库的性能;而 SQL 语句编译技术就是针对这些问题进行优化。

SQL 编译技术细节

减少不必要的指令

从根本上讲,提高数据库性能的方法是减少 CPU 指令数量;有实验之处数据库处理事务过程中,正真有用的指令,即用于事务逻辑的指令不到5%
DB-Useful-Work
SQL 语句编译成机器码的过程,就是通过优化有效的降低 CPU 指令数的过程。

增加 CPU 缓存效率

火山模型以 Operator 为中心进行事务处理,其弊端非常明显;SQL 编译技术为了最大可能的将数据保留在 CPU 寄存器中,采取如下措施:

  1. 以数据为中心,同事处理多行数据,而不是一行;自底向上,而不是自顶向下。
    VS
  2. SQL 通过 LLVM 编译成机器码,编译优化使得数据能够尽可能久的停留在CPU寄存器中。实际上编译成机器码使得 SQL 语句能够得到硬件和编译器优化技术进步带来的替身,这是火山模型无法匹敌的。
  3. 同一批数据尽可能久的停留在 CPU 寄存器中,即数据不变而 Operator 流转,相比于火山模型,这种方式更像是数据不断地被 Push 给 Operator,而不是 Operator Pull 数据。

这种以多行数据为单位,基于 Push 的技术应用于数据库 SQL 执行引擎,可带来5倍的性能提升。

代码生成

代码到代码

这种方式基本上是将 SQL 语句转换成 C\C++ 代码,有如下特点:

  1. 对于给定的 SQL 语句,通过模板将其替换为同等逻辑的 C\C++ 代码,然后编译成机器码
  2. 一般情况下会另起一个进程或者线程,运行诸如 gcc 等成熟的编译器,对生成的 C\C++ 代码进行一步编译
  3. 编译好的代码通过运行时链接,可调用数据库其他方法
  4. 这种方式能够带来 SQL 语句执行效率的提升,然而如果 SQL 语句过大,可能导致编译时间长,总体时间反而不如解释执行的情况。

JIT

这种方式并非将 SQL 语句直接编译成机器码,而是首先将其编译成中间代码,比如 LLVM IR,有如下特点:

  1. 由于 JIT 的方式使得数据库编译器拥有 SQL 运行时的数据,通过数据生存周期分析等技术优化,有针对性的进行优化和编译,让数据能够尽可能久的停留在 CPU 缓存中;上述 Push 数据的 SQL 执行引擎成基于 JIT 实现。
  2. SQL 语句编译并非没有代价,实际上编译时间和 SQL 语句的复杂程度是线性关系;由于编译器拥有运行时数据,且数据库引擎以一组数据单位,因此编译器可以实时评估收益,在执行下一组数据的时候在如下方式间灵活无缝的切换:
  • 简单 SQL 语句解释执行
  • 中等规模的SQL 语句不经优化编译成机器码执行
  • 复杂的的 SQL 语句深度优化编译成机器码执行
  1. 简单的算法如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    //Dispatch
    dispatch(handleB, state):
    nextMorsel = grabMorsel()
    if (handleB.isCompiled()):
    handleB.fn(state, nextMorsel)
    else:
    VM.execute(handleB.byteCode, state, nextMorsel)
    choice = choice = extrapolatePipelineDurations(...)
    if (choice != DoNothing):
    unAsync(λ -> handleB.fn = handleB.compile(choice))

    //Evaluate
    // f: worker function
    // n: remaining tuples
    // w: active worker threads
    extrapolatePipelineDurations(f, n, w):
    r0 = avg(rateinthreadRates)
    r1 = r0*speedup1(f); c1 = ctime1(f)
    r2 = r0*speedup2(f); c2 = ctime2(f)
    t0 = n / r0 / w
    t1 = c1 + max(n - (w-1)*r0*c1, 0) / r1 / w
    t2 = c2 + max(n - (w-1)*r0*c2, 0) / r2 / w
    switchmin(t0, t1, t2):
    case t0: return DoNothing
    case t1: return Unoptimized
    case t2: return Optimized

作者的其他数据库文章链接

  1. SQL:数据世界的通用语
  2. 数据库性能之翼:SQL 语句运行时编译
  3. 每周一论文:A Survey of B-Tree Locking Techniques
  4. 每周一论文:An Empirical Evaluation of In-Memory Multi-Version Concurrency Control
  5. 数据库索引数据结构总结