DuckDB：一个可嵌入的分析型数据库
作者：Mark Raasveldt (m.raasveldt@cwi.nl) 和 Hannes Mühleisen (hannes@cwi.nl)
单元：CWI, 阿姆斯特丹
择要：SQLite的巨大乐成表明，人们需要一种不引人注目的进程内数据管明白决方案。然而，目前还没有针对分析型工作负载的此类体系。我们展示了DuckDB，这是一个新型的数据管理体系，旨在嵌入到其他进程中执行分析型SQL查询。在我们的演示中，我们将DuckDB与其他数据管明白决方案进行对比，以展示其在嵌入式分析场景中的性能。DuckDB作为开源软件，采用允许性允许证发布。
ACM参考格式：Mark Raasveldt 和 Hannes Mühleisen. 2019. DuckDB: an Embeddable Analytical Database. In 2019 International Conference on Management of Data (SIGMOD ’19), June 30-July 5, 2019, Amsterdam, Netherlands. ACM, New York, NY, USA, 4 pages. https://doi.org/10.1145/3299869.3320212
1. 弁言
数据管理体系已经演变为大型单体数据库服务器，作为独立进程运行。这在一定程度上是为了满足同时为多个客户端提供服务的需求，部分是由于数据完备性要求。尽管功能强大，但独立体系需要相当大的积极才气正确设置，数据访问受到其客户端协议的限定。数据管理体系还有一个完全不同的用例，即嵌入到其他进程中的体系，数据库体系是一个链接库，完全在“宿主”进程中运行。这类体系中最著名的代表是SQLite，它是部署最广泛的SQL数据库引擎，拥有凌驾一万亿个活泼数据库。SQLite专注于事务性（OLTP）工作负载，包含一个基于B树存储格式的行优先执行引擎。因此，SQLite在分析型（OLAP）工作负载上的性能非常差。
图1：体系全景
嵌入式分析数据管理体系的需求显而易见，这一需求主要来自两个方面：交互式数据分析和“边沿”盘算。交互式数据分析使用R或Python等工具进行。这些环境中通过扩展（如dplyr、Pandas等）提供的基本数据管理操作符与SQL查询中堆叠的关系操作符非常相似，但缺乏完备的查询优化和事务性存储。嵌入式分析数据管理体系也实用于边沿盘算场景。比方，目前的智能电表会将数据转发到中心位置进行分析。这在带宽有限的无线电接口上存在题目，同时也引发了隐私题目。可嵌入的分析数据库非常得当支持这种用例，数据可以在边沿节点上进行分析。交互式分析和边沿盘算这两个用例看似正交，但令人惊讶的是，不同的用例产生了相似的需求。比方，在这两种用例中，便携性和资源需求都是关键，对这两者都审慎的体系将在两种使用场景中表现精良。
在我们之前的研究中，我们开发了MonetDBLite，这是一个从MonetDB体系派生的嵌入式分析体系。MonetDBLite乐成地证明了嵌入式分析确实存在需求，它每月有数千次下载，并在环球范围内被使用，从荷兰中心银行到新西兰警察。然而，它的乐成也袒露了在非专用体系中难以办理的几个题目。我们为嵌入式分析数据库确定了以下需求：
- 对OLAP工作负载具有高服从，但不完全断送OLTP性能。比方，在仪表板场景中，多个线程使用OLTP查询更新数据，同时其他线程运行OLAP查询以驱动可视化，这是常见的用例。
- 高度稳定性，如果嵌入式数据库瓦解（比方由于内存不足），它会将宿主进程一起拉下。这种环境绝对不能发生。如果查询因资源不足而无法运行，需要能够干净地停止查询，而且体系需要优雅地适应资源争用。
- 高效地将表传输到数据库和从数据库传输出来至关重要。由于数据库和应用程序在同一进程中运行，因此它们共享同一个地点空间，这为高效数据共享提供了独特的机会，需要加以利用。
- 实用的“可嵌入性”和便携性，数据库需要能够在宿主运行的任何环境中运行。在编译或运行时对外部库（比方openssh）的依赖已被证明是题目。禁止信号处置惩罚、调用exit()以及修改单一进程状态（如区域设置、工作目次等）。在本次演示中，我们展示了我们的新体系DuckDB的能力。DuckDB是一个新开发的专用嵌入式关系数据库管理体系。DuckDB作为开源软件，采用允许性MIT允许证发布。据我们所知，尽管存在上述明白的需求，但目前还没有专用的嵌入式分析数据库。DuckDB不是研究原型，而是为了广泛使用而构建的，每次提交都会运行数百万次测试查询，以确保SQL接口的正确操作和完备性。我们初次展示DuckDB，将其与其他体系在小型设备上进行对比。我们将允许观众增加处置惩罚的数据集大小，并观察随着数据集大小变革的CPU负载和内存压力等各种指标。这将展示DuckDB在分析嵌入式数据分析中的性能。
2. 筹划与实现
DuckDB的筹划决议是基于其预期用途：嵌入式分析。总体而言，我们遵照“教科书式”的组件分离：解析器、逻辑规划器、优化器、物理规划器和执行引擎。事务和存储管理器是正交的组件。尽管DuckDB是数据管理体系的一个新类别，但其任何一个组件本身都不是革命性的。相反，我们结合了最得当我们用例的最新技能和算法。作为一个嵌入式数据库，DuckDB没有客户端协议接口或服务器进程，而是通过C/C++ API进行访问。别的，DuckDB提供了一个SQLite兼容层，允许从前使用SQLite的应用程序通过重新链接或库重载来使用DuckDB。SQL解析器源自Postgres的SQL解析器，尽可能地进行了精简。这使得DuckDB拥有一个功能完备且稳定的解析器，以处置惩罚其输入中最易变革的情势——SQL查询。解析器以SQL查询字符串为输入，并返回一个C布局的解析树。然后，该解析树立即被转换为我们本身的C++类解析树，以限定Postgres数据布局的使用范围。这个解析树由语句（比方SELECT、INSERT等）和表达式（比方SUM(a)+1）组成。逻辑规划器由两部分组成：绑定器和筹划天生器。绑定器解析全部引用架构对象（如表或视图）的表达式及其列名和类型。然后逻辑筹划天生器将解析树转换为基本逻辑查询操作符（如扫描、过滤、投影等）的树。在规划阶段之后，我们得到了一个完全类型解析的逻辑查询筹划。DuckDB对存储数据保持统计信息，这些统计信息作为规划过程的一部分在不同的表达树中传播。这些统计信息用于优化器本身，也用于在必要时通过升级类型来防止整数溢出。DuckDB的优化器使用动态规划进行连接顺序优化，对于复杂的连接图则使用贪婪回退。它还执行任意子查询的展平，如Neumann等人所述。别的，还有一组重写规则，通过执行比方公共子表达式消除和常量折叠来简化表达树。基数估计使用样本和HyperLogLog的组合来完成。这个过程的效果是查询的优化逻辑筹划。物理规划器将逻辑筹划转换为物理筹划，选择实用的实现方式。比方，扫描可能会根据选择性估计决定使用现有索引而不是扫描基础表，大概根据连接谓词在哈希连接和合并连接之间切换。DuckDB使用向量化解释执行引擎。由于便携性原因，选择了这种方法而不是SQL查询的即时编译（JIT）。JIT引擎依赖于大型编译器库（比方LLVM）及其额外的传递依赖项。DuckDB使用固定最大值数量（默以为1024）的向量。固定长度类型（如整数）存储为本地数组。可变长度值（如字符串）表示为指向单独字符串堆的本地数组的指针。如果向量中出现NULL值，则使用单独的位向量表示NULL值，只有在向量中出现NULL值时才会存在。这允许快速交集NULL向量以进行二进制向量操作，并制止冗余盘算。为了制止在过滤数据时（比方数据被过滤时）在向量内过分移动数据，向量可能具有选择向量，这是一个指向向量的偏移量列表，表明向量的哪些索引是相干的。DuckDB包含一个广泛的向量操作库，支持关系操作符，该库使用C++代码模板扩展全部支持的数据类型的代码。执行引擎以所谓的“向量火山”模型执行查询。查询执行从物理筹划的根节点拉取第一块数据开始。一块是效果集、查询中心效果或基础表的程度子集。该节点将递归地从子节点拉取数据块，终极到达扫描操作符，扫描操作符通过从长期表中读取来天生数据块。这一过程一直连续到到达根节点的数据块为空，此时查询完成。DuckDB通过多版本并发控制（MVCC）提供ACID合规性。我们实现了HyPer的可序列化MVCC变体，该变体专门针对混合OLAP/OLTP体系进行了优化。这种变体立即在原地更新数据，并将从前的状态存储在单独的取消缓冲区中，供并发事务和中断使用。由于DuckDB的主要用例是分析，但过去修改表的并行化仍然是一个常见需求，因此选择了MVCC，而不是更简朴的方案，如乐观并发控制。对于长期化存储，DuckDB使用读优化的DataBlocks存储布局。逻辑表被程度分区为列的块，这些块使用轻量级压缩方法压缩成物理块。块为每一列携带最小/最大索引，允许快速确定它们是否与查询相干。
别的，每个块为每一列携带一个轻量级索引，这可以进一步限定扫描的值的数量。
图2：演示设置示意图
3. 演示场景
在我们的交互式演示场景中，我们希望展示DuckDB的两大上风：在有限硬件资源上处置惩罚大数据集的能力，以及嵌入式操作的上风。我们的演示设置在一个桌子上，上面有一个屏幕、一个大旋钮和四台相同的基准盘算机。每台盘算机运行不同的DBMS：SQLite、MonetDBLite、HyPer和DuckDB。每个数据库都预先加载了TPC-H基准表，因为观众可能对这个模式比力熟悉。盘算机通过以太网连接到第五台“管理”盘算机，可用于配置在四台基准盘算机上重复运行的查询。屏幕上显示全部四台基准盘算机的实时指标，至少包括查询完成率（QpS）和内存压力。桌子上的旋钮控制当前配置查询从究竟表中读取的数据量。我们提出了两种演示场景：“预告”场景和“深入”场景。
对于“预告”场景，基准盘算机上预先配置了一个合适的查询。观众将被约请转动物理旋钮以增加/减少从究竟表中读取的数据量。这将立即影响预配置查询的中心效果和效果集大小，也会立即影响屏幕上显示的指标。图2说明了这种设置。
4. 当前状态和下一步筹划
停止本文撰写时，DuckDB已经运行了全部TPC-H查询和除两个之外的全部TPC-DS查询。我们预计在演示时将实现完备的TPC-DS覆盖。DuckDB还完成了SQLite的SQL逻辑测试套件中的大多数查询，该套件包含数百万个查询。DuckDB的下一步筹划是完成DataBlocks存储方案和子查询折叠，目前这些功能正在开发分支中。缓冲管理器尚未实现，但将会实现。DuckDB已经支持查询间并行化，但查询内并行化也将被添加。我们筹划实现一个工作盗取调度器，以在短查询和长查询之间平衡资源。一个特别的思量是允许与宿主应用程序平衡资源使用，这是嵌入式操作的一个特殊题目。与MonetDBLite一样，我们将实现R和Python等数据库API。一个更先辈的未来方向是自我查抄。我们已经学会不信任数据库运行的硬件。这在边沿盘算用例中尤其相干，因为硬件故障是常见的。一种方法是对全部长期化和中心数据保持校验和，并在校验扫描操作符上附加校验和验证。这可能不会对性能产生明显影响。向量化引擎特别得当这种操作，因为一块数据通常得当CPU缓存，额外的遍历不需要访问RAM。另一种增加对硬件信任的方法是受视频游戏开发者的开导，他们定期运行完备性查抄盘算，以确保CPU和RAM的正确运行。
致谢
我们感谢CWI数据库架构组以及全部过去、现在和未来的DuckDB贡献者。我们特别感谢TUM数据库组关于查询优化、窗口函数、存储和并发控制的论文，我们使用这些论文实现了DuckDB。
参考文献
Peter A. Boncz, Marcin Zukowski, 和 Niels Nes. 2005. MonetDB/X100: Hyper-Pipelining Query Execution. In CIDR 2005, Second Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2005. 225–237. http://cidrdb.org/cidr2005/papers/P19.pdf
Lukas Fittl. 2019. C library for accessing the PostgreSQL parser outside of the server environment. https://github.com/fittl/libpg_query
Richard Hipp. 2019. Database File Format. https://www.sqlite.org/fileformat.html
Richard Hipp. 2019. Most Widely Deployed and Used Database Engine. https://www.sqlite.org/mostdeployed.html
Harald Lang, Tobias Mühlbauer, Florian Funke, et al. 2016. Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016. 311–326. https://doi.org/10.1145/2882903.2882925
Wes McKinney. 2010. Data Structures for Statistical Computing in Python. In Proceedings of the 9th Python in Science Conference, Stéfan van der Walt and Jarrod Millman (Eds.). 51 – 56.
Guido Moerkotte 和 Thomas Neumann. 2008. Dynamic programming strikes back. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008. 539–552. https://doi.org/10.1145/1376616.1376672
Thomas Neumann. 2011. Efficiently Compiling Efficient Query Plans for Modern Hardware. PVLDB 4, 9 (2011), 539–550. https://doi.org/10.14778/2002938.2002940
Thomas Neumann 和 Alfons Kemper. 2015. Unnesting Arbitrary Queries. In Datenbanksysteme für Business, Technologie und Web (BTW), 16. Fachtagung des GI-Fachbereichs “Datenbanken und Informationssysteme” (DBIS), 4.-6.3.2015 in Hamburg, Germany. Proceedings. 383–402. https://dl.gi.de/20.500.12116/2418
Thomas Neumann, Tobias Mühlbauer, 和 Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015. 677–689. https://doi.org/10.1145/2723372.2749436
Thomas Neumann 和 Bernhard Radke. 2018. Adaptive Optimization of Very Large Join Queries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD ’18). ACM, New York, NY, USA, 677–692. https://doi.org/10.1145/3183713.3183733
Mark Raasveldt 和 Hannes Mühleisen. 2017. Don’t Hold My Data Hostage - A Case For Client Protocol Redesign. PVLDB 10, 10 (2017), 1022–1033. https://doi.org/10.14778/3115404.3115408
Mark Raasveldt 和 Hannes Mühleisen. 2018. MonetDBLite: An Embedded Analytical Database. CoRR abs/1805.08520 (2018). arXiv:1805.08520 http://arxiv.org/abs/1805.08520
Hadley Wickham, Romain François, Lionel Henry, 和 Kirill Müller. 2018. dplyr: A Grammar of Data Manipulation. https://CRAN.R-project.org/package=dplyr R package version 0.7.8.
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
