摘要

构建一个新的云数据仓库是一项艰巨的挑战，需要对查询引擎和周围的云基础设施进行大量建设。考虑到这个成熟的技术，作为一个小型创业公司进入这个市场似乎是一个艰巨的任务。在Firebolt，我们在不到18个月的时间里组建了一个高性能的云数据仓库。我们通过在现有项目的基础上建立我们的查询引擎，然后大量投资于差异化的功能来实现这一目标。本文介绍了我们的决策和一路走来的经验教训。

1 简介

Firebolt是一个现代云数据仓库，为支持面向用户的数据密集型应用而建立[11]。这些工作负载是具有挑战性的，因为用户期望查询在几十毫秒内返回。此外，面向用户的应用可以有成千上万的用户和查询同时进行。他们表现出许多每秒查询次数（QPS），以及高并发性。建立一个数据库管理系统是困难的，因为它由多个复杂的组件组成。这些组件包括查询引擎、存储引擎、事务管理器和系统目录。构建云数据仓库时，这一挑战被放大了，因为它给系统增加了额外的复杂层。这包括云平台基础设施，云存储管理，SaaS组件，以及更多。图1展示了Firebolt的高层架构，这就是一个例子。所有这些组件都是必要的，即使是一个光秃秃的系统。除此之外，还需要投入大量的工程力量来建立与众不同的功能。即使是一个大型团队，从头开始建立这样一个系统也需要多年时间。在Firebolt，我们能够在18个月内为运行生产工作负载的真正客户推出我们的云数据仓库。为了实现这一目标，我们用多个现有的组件组装了Firebolt。虽然有些只需要小的修改，但其他的被作为一个起点，最后却发生了很大的变化。本文介绍了我们如何用现有的组件组装我们的高性能查询引擎。它的结构如下。第2节重点介绍了在构建引擎本身时做出的决定。之后，第3节描述了我们如何利用开源工具来持续测试我们的查询引擎。我们在第4节中总结了我们的经验教训，并在第5节中得出结论。

图表 1

2 查询引擎

本节概述了用于组装我们的查询引擎的开放源码组件。Firebolt引擎的设计遵循教科书中的组件分离原则[21]。我们的SQL解析器接受Firebolt的SQL方言，并将用户的查询转换为抽象语法树（AST）。然后，逻辑规划器将这个AST转化为逻辑查询计划（LQP）。为了实现这一点，它使用逻辑元数据，如表和视图定义、数据类型和函数目录。然后使用逻辑转换来产生一个优化的LQP。第2.1和2.2节介绍了我们如何在Firebolt选择一个现有项目作为这些组件的基础。之后，Firebolt的物理规划器从LQP中构建一个分布式查询计划（DQP）。为了实现这一点，它使用物理元数据，如索引的存在，表的cardinalities，以及数据分布。我们的分布式运行时在Firebolt节点集群中协调DQP的执行。其职责包括调度、阶段间的数据交换和查询容错。最后，本地运行时在一个单一的Firebolt节点内执行关系运算。第2.3节概述了我们如何决定用一个现有的项目来为我们的运行时奠定基础。我们还介绍了在将规划器和运行时建立在现有项目基础上时遇到的一些工程挑战。第2.4节展示了规划器和运行时之间的通信是如何随着时间的推移而演变的。第2.5节概述了我们对定制的分布式运行时的推动。

2.1 sql方言

云数据仓库并不存在于真空中--它们是一个更广泛的数据生态系统的一部分。这个生态系统包括ETL/ELT、BI、报告、数据科学、ML和数据观测的工具。例如，Fivetran, Dbt, Tableau, Looker和Monte-Carlo。这在图2中有所概述。随着用户在这些工具之上建立他们的应用程序，与更广泛的生态系统进行广泛的整合对Firebolt的成功至关重要。毕竟，没有人想要一个没有工具可以与之对话的云数据仓库。幸运的是，上述所有的工具都使用SQL与数据仓库对话。这大大简化了与生态系统的整合。然而，挑战仍然存在。尽管有ANSI SQL标准的存在，但几乎每个数据库都有自己的SQL方言。因此，上述工具需要各种自定义驱动程序、连接器和适配器来支持不同的数据库系统。要想在云数据仓库领域成为一家成功的初创公司，并让客户满意，从第一天起就与生态系统整合是至关重要的。作为一家小型创业公司，Firebolt不能指望生态系统工具背后的大公司花时间和资源致力于通过自定义连接器和驱动程序增加支持。为了便于生态系统的整合，我们决定Firebolt的SQL方言应该与现有的、广泛采用的SQL方言相似。选择Postgres方言作为北极星是一个简单的选择。它是非常流行的，并且高度符合标准的ANSI SQL。因此，数据栈中几乎所有的工具都支持Postgres SQL。值得注意的是，与Postgres SQL兼容并不意味着必须与Postgres线协议[19]兼容。我们的驱动通过一个自定义的基于HTTP的REST协议与Firebolt进行通信

图表 2

2.2 sql编译器和规划器

正如上一节所述，Firebolt的SQL分析器需要与Postgres SQL非常相似。它必须完全覆盖DDL、DML和DCL语句。然而，对DQL（即SELECT）语句的支持是最重要的，因为它们构成了大部分的工作负载。我们想把逻辑规划器建立在一个现有的项目上，以满足一系列广泛的要求。该计划器需要支持现代数据仓库中最重要的规则，如谓词推倒和子查询装饰关系。作为其中的一部分，该项目还需要有一个可扩展的框架用于基于规则的转换。这将使我们能够在扩大产品规模时轻松地添加Firebolt的特定规则。除了基于规则的转换，计划器还需要支持基于成本的连接重排。这包括允许我们建立自定义统计源和成本模型。鉴于Firebolt支持各种不同的索引类型，这一点尤其重要。例如，我们使用稀疏的主索引和辅助索引进行数据剪裁，以及专门的索引用于经常出现的广播连接[24]。最后，规划器需要支持复合数据类型，如数组和行（结构）类型。这些对于Firebolt所针对的面向用户的、数据密集型的应用是很受欢迎的。可以分别挑选不同的项目作为解析器和规划器的基线。然而，这两个组件有一个非常复杂的接口：查询的AST离开解析器，进入规划器进行语义分析。我们决定优先考虑那些同时包括解析器和规划器的项目。幸运的是，有许多开源项目，我们能够考虑将其作为Firebolt的SQL解析器和规划器的基础。以下是这些项目的概述。

Postgres分析器。鉴于我们希望符合Postgres SQL的要求，直接使用Postgres分析器是一个明显的选择。这种方法已经在其他多个系统中被成功使用[8, 20]。libpg_query项目1已经完成了将分析器与Postgres代码隔离的工作。它将原始的基于C的Postgres解析器打包成一个库[12]。虽然这使得在Postgres解析器的基础上建立一个系统变得相当容易，但是如果不把Postgres代码库的其他部分带进来，就很难隔离规划器的代码。对我们来说，这意味着虽然使用Postgres几乎不需要对解析层进行投资，但要建立一个满足我们需求的生产级规划器，则需要付出巨大的努力。

ZetaSQL。ZetaSQL是一个来自Google2的解析器和分析器，用C++构建。它是GoogleSQL的一个开源移植[23]。GoogleSQL为云计算产品BigQuery[17]、Spanner[3]和Dataflow，以及Google内部产品Dremel、F1[22]和Procella[7]提供支持。它是一个干净的构建、广泛的测试和可生产的系统。然而，ZetaSQL提供了一种有主见的方言，在许多基本功能上与Postgres SQL不一致。此外，ZetaSQL只支持初级的转换，没有功能丰富的规划器。

Calcite。Apache Calcite是一个框架，为数据处理系统提供查询处理、优化和查询语言支持[4]。它包括多种SQL方言的解析器和一个模块化的、可扩展的、支持可插拔规则的查询计划器。Calcite建立得很好，并经过了实战测试。它被用于许多高知名度的开源系统，如Apache Hive、Apache Storm、Apache Flink、Druid和MapD3。与我们考虑的其他用C++编写的替代品相比，Calcite是用Java实现的。

DuckDB。DuckDB是一个源自CWI[20]的内存中、进程中分析数据库系统。它经过了广泛的测试，被广泛用于交互式数据分析。DuckDB的查询计划器同时支持基于规则的优化和基于成本的连接重排。DuckDB使用libpg_query项目作为他们解析器的基线，提供Postgres SQL的复杂性。现在，DuckDB把它的解析器移植到了C++14上。在我们决定以一个项目作为我们的分析器和规划器的基础时，DuckDB明显没有现在这么成熟。

Hyrise。Hyrise是一个在HPI开发的内存数据库[13]。它有一个相对简单的代码库，使得它很容易被重构和扩展。与DuckDB类似，它支持基于规则的优化和基于成本的连接重排。然而，作为一个学术项目，Hyrise没有经过战斗测试，也没有广泛的SQL覆盖。我们很早就决定，我们希望规划器和运行时是用相同的编程语言编写的。我们认为，在建立一个新的系统时，这并不是一个硬性要求。已经有多个成功的系统使用基于JVM的规划器和用C++编写的高性能运行时[5, 10]。

尽管如此，我们相信用一种语言编写的引擎可以使我们在创业时有很高的速度。数据库系统中的很多工作都发生在规划器和运行时间的交叉点上。这对Firebolt来说尤其如此，因为我们必须整合来自不同开源项目的两个组件。规划器和运行时是用相同的编程语言编写的，这使得开发人员可以很容易地在堆栈中工作，并将上下文切换到最小。由于我们决定采用C++编写的运行时，我们希望规划器也能跟上。这就给我们留下了一个选择，即Hyrise或DuckDB。我们决定以Hyrise项目为基础，因为它的简单性和可扩展性。在为Firebolt的生产做好准备时，Hyrise是一个学术系统，对SQL的支持有限，这被证明是一个挑战。对于今天建立一个新的数据库系统的工程师来说，使用DuckDB很可能是一个更好的起点。这是因为自从我们开始构建Firebolt以来，DuckDB已经非常成熟了，而且现在已经被广泛使用。同时，对于我们的用例来说，使用Hyrise确实是一个不错的选择。事实上，鉴于它的相对简单性，我们最初选择它的直觉被证明是正确的。我们投入巨资使Firebolt的解析和规划层为生产做好准备。现在，它在Hyrise中的开源根基已经很难辨认。我们增加的内容包括对解析器的广泛扩展，以提供良好的SQL覆盖率，并对规划层进行了相当大的改动。在其他方面，我们增加了对复合数据类型的广泛支持，改变了逻辑查询计划的表示方法，使其更容易建立基于规则的优化，并为规划器增加了各种新规则。我们对逻辑查询计划的重新设计在很大程度上受到Calcite的启发。由于它是可扩展和功能丰富的开源查询计划的黄金标准，我们决定利用Calcite的关系代数表示中的许多概念。这使得我们的计划器在新的SQL功能和优化能力方面能够适应未来的需要并具有可扩展性。

2.3 运行时

运行时是一个查询引擎的核心。它负责查询评估，必须实现数据类型、函数和关系运算符，如连接和聚合。与解析层和规划层类似，Firebolt可以选择从头开始建立一个新的查询引擎，或者从现有的开源项目中启动一个。许多数据库公司决定从头开始建立他们的运行时间。例如CockroachDB [2], Databricks [5] 和 Snowflake [10] 。我们认为，为了颠覆数据仓库领域，作为一家小型创业公司，从现有的代码库开始，将我们相对有限的工程资源分配给Firebolt独特的差异化功能，是一个更好的选择。在决定使用哪个项目作为我们的运行时间的基线时，我们有几个基本的护栏。为了支持面向用户的数据密集型应用，我们需要一个高性能的查询引擎，以实现低延迟的查询处理。有两种现代方法来构建高性能的运行时--矢量化[6]和代码生成[18]。我们决定将Firebolt建立在一个矢量化的运行时之上。虽然建立一个低延迟的代码生成引擎是可能的，但它需要大量投资于先进的编译栈[15, 16]。这增加了引擎的复杂性，使得新的工程师更难加入，并保持高开发速度。同时，代码生成引擎和矢量化引擎对于OLAP工作负载的表现往往是相似的[14]。我们还希望这个引擎是健壮的，并且对分布式数据处理有基本的支持。虽然有各种有趣的学术性和实验性的开源查询引擎，但其中许多还没有为生产做好准备，或者不支持分布式查询执行。从一个经过实战检验的、可横向扩展的引擎开始，我们可以迅速组建一个强大的查询引擎，可以处理大量数据集。除了运行时间，我们还想启动我们的存储引擎，特别是文件格式。为了建立一个高性能的查询引擎，存储引擎必须使用列式数据布局来有效支持OLAP工作负载[1]。在引导查询运行时和存储引擎时的挑战与引导解析器和规划器时遇到的挑战相似。可以分别选择不同的系统作为存储引擎和查询运行时间的基线。然而，这两个组件共享复杂的接口，以便在各层之间传输数据并促进数据修剪。因此，选择一个单一的项目来提供这两个组件，可以大大方便建立一个高性能的系统。虽然有多个项目可以作为SQL解析器和规划器的基线，但在选择高性能的分布式运行时时，选择就比较少了。我们很快就把选择范围缩小到了ClickHouse[9]。ClickHouse的设计是快速的5，这些说法得到了基准测试的支持6。ClickHouse使用矢量查询执行，通过LLVM对运行时代码生成的有限支持。ClickHouse在生产环境中经过了严格的测试和广泛的应用7。最后，ClickHouse也有自己的柱状文件格式，叫做MergeTree8。MergeTree与查询运行时紧密结合，可以有效地修剪数据。所有上述的原因使得我们很容易选择ClickHouse作为Firebolt运行时的基础。

2.4 连接规划器和运行时

第2.2节介绍了我们使用Hyrise作为查询计划器的基础的决定。之后，第2.3节展示了为什么我们选择将Firebolt运行时建立在ClickHouse之上。本节概述了我们在计划器和运行时之间的通信方式是如何随着时间的推移而演变的。Firebolt集群中的每个节点都可以作为查询协调器，运行解析器和规划器，并作为运行时工作者，执行更大的查询计划的一部分。这在图1中显示。当一个查询进入系统时，它被路由到其中一个节点。然后这个节点充当协调者。在对查询进行解析和规划后，它需要启动查询的执行。为了实现这一点，它需要将规划者的优化LQP转化为基于ClickHouse的运行时能够理解的表示。ClickHouse的SQL方言可以作为这样一种表示。ClickHouse解析器将ClickHouse SQL转化为一个可以直接执行的内部解析树。我们用它来快速建立一个初始版本的跨组件通信。通过一个我们称之为 "回译 "的过程，规划器中的LQP被转换回ClickHouse SQL中的一个表示。这个表示法产生了一个ClickHouse查询计划，它符合Firebolt计划器所选择的优化的LQP。这种方法使我们能够迅速得到一个工作产品，但也有许多问题。当以这种方式连接规划器和运行时，很多时间都花在了生成ClickHouse SQL上，只是为了再次被ClickHouse分析器瞬间消耗掉。更重要的是，当回到基于SQL的表述时，很多关于LQP结构的有价值的上下文都丢失了。正因为如此，我们决定完全取代回译流程。现在，Firebolt LQP被直接转换为分布式查询计划。然后，这个分布式查询计划被分解成多个阶段。协调器将阶段发送到Firebolt集群内的不同工作者，以促进分布式查询的执行。对于跨网络通信，我们使用一个自定义的、基于protobuf的序列化格式。在工作节点上，这种序列化格式被用来组装运行时的矢量关系运算符。在未来，Substrait9可能是使用自定义序列化格式的一个可行的选择。然而，在写这篇文章的时候，Substrait仍在快速发展中，并且会有一些突破性的变化。

3 经验

在下文中，我们想简要地总结一下在建设Firebolt时学到的一些经验。选择一个坚实的基础。特别是对于查询分析器和规划器来说，各种成熟的项目都可以作为一个基线。虽然我们发现Hyrise是一个很好的基础，并对我们当时的选择感到满意，但我们还是建议今天组装新系统的工程师使用DuckDB或Calcite。虽然高性能分布式运行时的选择较少，但我们发现ClickHouse是一个强大的、可扩展的基础。当构建一个生产系统时，我们建议选择经过战斗考验的项目作为起点。用单一语言构建。用单一的编程语言编写的项目来组装系统，可以使速度更快。这在初创公司的早期尤其如此，因为开发人员可能需要经常在不同的组件之间切换，或者在整个堆栈中构建功能。连接不同的系统。当选择不同的系统，例如规划器和运行时，工程团队需要大量投资在这些组件之间建立干净的接口。当把解析器和规划器，或者运行时和存储引擎建立在不同的项目上时，我们预计会有类似的效果。正因为如此，我们建议选择尽可能少的系统来组装一个新的数据库管理系统。我们在Firebolt只选择了两个用相同编程语言编写的系统。将它们连接起来并变成一个可生产的系统，所需的努力还是很大的。将这些系统越来越接近需要协同努力，并且仍在进行中。我们在第2.5节中概述的新的分布式执行栈就是这方面的一个例子。但仍有许多工作要做。一个很好的例子是统一规划器和运行时的类型系统。我们相信，不需要整合不同的项目是从头开始建立一个新系统的主要好处。也许有些令人惊讶的是，Apache Arrow15项目在组成Firebolt的查询引擎时并没有发挥重要作用。许多现有的开源项目使用Arrow来获取数据进入和离开系统。在Firebolt，所有的数据传输都发生在运行时的分布式基元中，以及从运行时返回数据给用户的时候。因此，我们不需要与Arrow集成，例如促进跨项目的数据传输。我们预计，随着Arrow和相关项目在开源项目中得到更广泛的采用，由不同组件组成的数据库系统将变得更加容易。测试系统。我们建议尽早与尽可能多的测试框架集成。虽然这在开始时可能看起来是一个很大的工作，但从长远来看，它是有回报的。它可以让团队迅速捕捉到目标SQL方言中潜在的兼容性问题，以及与其他系统相比在运行时行为的细微差别。然而，对测试案例的失败进行分类，以弄清哪些是指向潜在的问题，哪些是比较良性的，这需要大量的时间。

4 结论

在本文中，我们展示了我们如何使用不同的开源组件作为踏脚石来组装Firebolt查询引擎。这些组件在表1中进行了总结。大量高质量的开源项目使我们有可能在不到18个月的时间内建立Firebolt。作为一家初创公司，走这条路线是一个明智的选择。它使组织能够迅速汇聚到一个工作系统。鉴于该领域成熟的商业系统的数量，这使得工程团队能够专注于差异化的功能。我们感谢开源社区，并打算在可能的情况下做出回馈。组建本文所述的系统仅仅是第一步。构建一个世界级的高性能数据库系统是一场马拉松，而不是一场短跑--只有当系统的第一个版本开始运行时，艰苦的工作才开始。对我们来说，决定做一个开源根基的硬分叉是至关重要的。它允许我们灵活地完全重新设计系统，以更好地满足我们客户的需求。Firebolt正在大力投资其工程团队，大型项目正在进行，以改善或重写我们的存储、执行和元数据层。我们期待着在未来的出版物中分享更多关于这些项目的信息。