假如你是一个初创公司的 CTO，想迅速推出一款面向 AP 市场可用的数据库产品，还得有差异化的功能（不然谁会用一个新产品），你会怎么做呢？
Firebolt 在 2022 年专门发了一篇论文：Assembling a Query Engine From Spare Parts[1] 来讲这个事情。核心思想就是，利用开源组件，像攒台式机一样攒出一个数据库。
让我们看下“装机清单”：
Firebolt 装机清单
了解数据库内核开发的同学都知道，一个数据库包含非常多的组件。就我所做的存储层来说，就可以列一个长长的清单，可以参考我之前写的这篇文章[2]。更遑论数据库的大头——查询引擎了。就算化简再化简，也需要解析器——Parser，计划生成——Planner，计划执行——Runtime。
当然，对于一个数据库来说，最重要的还有对外提供的接口—— SQL 。虽然有 ANSI SQL 这个标准在，但工业上真正使用的却是一个个的“方言”（dialect）。虽然说接口需要独立于实现，但不同的实现总会不可避免的冒出头来，影响到接口。而且，分布式数据库不可避免地会进行站队，选择某个方言。比如 TiDB 选择兼容 MySQL，而 Firebolt 选择兼容 Posgres。
组件选择
选定了兼容的 SQL 方言，下一步就是上面提到的几个重要组件的选择：Parser，Plannner，Runtime。让我们一块来看看 Firebolt 是怎么选的。
Parser & Planner
Parser 就是进行语法解析，将 SQL 语句进行分词，组织成语法树——AST。Planner 就是将 AST 基于规则和代价等进行优化成一个可以执行的算子树。
由于 Parser 和 Planner 的接口是 AST，而 AST 通常来说没有一个统一的标准——也即很难将从属于不同项目的 Parser 和 Planner 组合到一块。因此 Firebolt 倾向于寻找一个同时包括两个模块的项目。
Firebolt 对这两个模块的需求是：
- Parser 需要支持大部分 Postgres SQL 方言，包括 DDL、DML、DCL 和 DQL
- LogicPlanner 需要支持现代数仓的重要规则，如谓词下推、子查询去关联
- LogicPlanner 需要支持对规则变换（rule-based transformation）的扩展
- PhysicalPlanner 需要支持对基于代价的连接调序（cost-based join reordering）
- PhysicalPlanner 需要支持自定义的统计信息收集和代价模型
- Planner 需要支持复合数据类型，如数组、结构体
市面上当时针对这两个模块的开源项目还是挺多的，下面来逐一列举下其优劣：
项目 | 简介 | 优点 | 缺点 |
|---|---|---|---|
Postgres Parser | 1. 天然兼容 Postgres SQL 方言 2. libpg_query 已经将 Parser 和 Postgres 其他模块隔离了开来 | 1. 将 Planner 从 Postgres 项目中剥离出来工作量很大。 | |
Google ZetaSQL | 谷歌出品的一个 C 项目，包含 Parser 和 Analyzer | 1. 在谷歌诸多产品 BigQuery、Spanner、Dataflow、Dremel、F1 和 Procella 中被验证过 2. 项目简洁、充分测试、工业可用 | 1. 不支持 Postgres SQL 的很多功能 2. 只支持简单的算子树变换 3. Planner 功能也很简单 |
Apache Calcite | 一个开源供数据处理领域使用的查询处理和优化的 Java 项目 | 1. 支持多种 SQL 方言 2. 模块化良好，Planner 支持自定义 rule 3. 代码良好、测试充分、使用广泛（Hive，Storm，Flink，Druid 和 MapD） | 1. 不是用 C 写的，很难和其他组件进行代码集成 |
CWI Duckdb | 基于内存的、嵌入型的分析型数据库，C 编写 | 1. 测试充分，在交互式数据分析场景广泛使用 2. 同时支持基于规则和基于代价的计划改写 3. 使用 libpg_query 作为 Parser 的基准，因此对 Postgres SQL 方言兼容的很好 | 1. Firebolt 选型时还很不成熟 |
Hyrise | HPI 开发的一个内存型数据库 | 1. 简单的代码库 2. 同时支持基于规则和基于代价的计划改写 | 1. 是一个学术型项目 2. 测试不够充分、SQL 语法覆盖也不够 |
最后 Firebolt 基于种种考虑，选择了 Hyrise ：
- 使用 C 开发
- 同时支持基于规则和基于代价的计划改写
- 代码库简单易于重构
Firebolt 参考 Calcite 的设计和概念体系对 Firebolt 做了深度改写，比如增加了复合类型支持、修改了逻辑执行计划的表示等等。
Runtime
Runtime 是对优化过后的查询计划进行执行的组件，对数据库的性能有至关重要的影响。当时作为一个小创，Firebolt 依然选择了使用开源项目。
Runtime 有两种实现流派——向量化（vectorization）和代码生成（code generation），后者效率可能会高一些，但实现复杂度较高，需要投入的研发资源太多。
总结下，Firebolt 对 Runtime 项目的要求有：
- 支持向量化执行
- 有一定的扩展性，可进行分布式的数据处理改造
- 由于 Runtime 和存储引擎耦合性较高，因此项目最好同时实现了高效的列存引擎
相对 Parser 和 Planner 的多样性选择，Runtime 可供选择的项目相对较少（当时 Facebook Velox[3] 也没有开源）。最终 Firebolt 选择了 ClickHouse：
- 是一个向量化的执行引擎
- 经过充分的测试
- 有自己的列存格式——MergeTree，支持高效的数据裁剪
缝合 Planner 和 Runtime
由于 ClickHouse 的执行引擎要求的格式和 Hyrise 的产出格式并不一致，即后者生成的执行计划树（LQP）并不能被前者直接执行。为此，Firebolt 做了一个骚操作——将 LQP 逆向翻译（backtranslate）回 ClickHouse SQL。
这种方式可以 work，但并不高效，且会丢失一些优化信息。后来，Firebolt 将其进行了替换，将 LQP 直接翻译成了多阶段的分布式执行计划（类似 Spark 执行时的多阶段划分），并借助 protobuf 进行序列化和反序列化，传到每个执行节点上进行执行。当然，也要求对 ClickHouse 进行一定的改造。
分布式执行
尽管 ClickHouse 自己支持对某些 Query 的分布式执行，比如选择性的 table scan，分布式聚合、基于广播的 Join 等等。但数仓中更为普遍的一些 SQL 模式，ClickHouse 并不能对其进行很好的分布式执行。比如两个大表 Join、高基数分组聚合、分布式排序等等。
为此，Firebolt 实现了自己的分布式执行框架，将执行计划按 shuffle 算子切开划分成不同阶段。
小结
以上就是 Firebolt 初期作为一个人很少的小创，如何用十八个月迅速攒出一个商业可用的数仓项目，从而为后来获得大量融资[4]打下了基础。这也从另一个侧面反映了当前数据库开源生态的繁荣。
当然，为了商业可用，还有很多方面的需要打磨，其中最重要的就是对测试用例的覆盖，这里就不展开了，感兴趣的可以去读读论文原文[5]。
参考资料
[1]
Assembling a Query Engine From Spare Parts: https://www.firebolt.io/content/firebolt-vldb-cdms-2022
[2]
分布式数据库存储层组件: https://www.qtmuniao.com/2022/05/04/distributed-database-storage-components/
[3]
Facebook Velox: https://github.com/facebookincubator/velox
[4]
「Firebolt」完成1亿美元C轮融资: https://www.sohu.com/a/519415188_121118710
[5]
Assembling a Query Engine From Spare Parts: https://www.firebolt.io/content/firebolt-vldb-cdms-2022
