开源的列存储数据库:MonetDB

21 sec read

MonetDB是一个开源的面向列的数据库管理系统。MonetDB被设计用来为较大规模数据(如几百万行和数百列的数据库表)提供高性能查询的支持。MonetDB最初由荷兰阿姆斯特丹大学的Peter Boncz和Martin Kersten等人创建,并于2004年9月30日有了第一个开源的发行版。

MonetDB的创新

  • 列存储:在传统中,关系数据库系统以行存储数据,方便整条记录的查询,而MonetDB使用的列存储,更好地利用CPU缓冲线去支持分析查询.
  • 批量查询代数:如CISC对抗RISC思想应用于CPU的设计中,MonetDB的代数在传统关系集代数上尽可能简化,允许在现代硬件上有更加快速的实现。
  • 有意识缓冲算法:这关键的一面,在于恰好地利用CPU缓冲和最优的内存访问模式,去突破内存瓶颈的限制。这叫做查询处理算法的一个新品种,我们将在根分区的散列连接中有详细的描述。
  • 内存访问代价模型:因为优化的查询工作在有意识缓冲算法的环境下,我们发展了一个构建代价模型,把内存访问代价都考虑进来的方法学。为了工作在不同的计算机,使用自动校准技术,这些模型在运行时被参数化。

存储模型

MonetDB的存储模型与传统的数据库截然不同。它表示关系表使用垂直存储,每一列以{(surrogate,value)}这样的表存储,称为BAT(Binary Association Table).左边的列,代理数字或对象id,称为头;右边的列为尾。MonetDB执行一种低级的被称为BAT代数的关系代数。在执行的时候,数据常存储在(intermediate中间)BAT,就算是查询的结果也是BAT的集合。BAT存储采用方式是两个简单的内存数组,一个数组是头,另一个是尾(列).对不同长度的类型我们把数组分成两段。一段with concatenated data values and 另一段with offsets into the former.对于小字符串值表来说,组合就实现了值字典了。

MonetDB在内部实现存储列是使用内存文件映射。它们被优化到特有的情况就是代理的列是一些升序的阿拉伯数字(0,1,2…);在某些情况下代理列是可以保持模糊的。代理列查询成为一种以快速数组下标读取尾的方式。实际上,这种在虚拟内存使用数组利用MMU快速把硬件地址映射为磁盘地址的机制去给数据库提供O(1)效率的数据库寻找机制。

从CPU开销的角度看,这种方法优于B-tree into slotted pages–这是传统数据库实现记录快速查找的方法。

运行模型

MonetDB的内核是一台抽象的机器,用MonetDB的汇编语言,也称为MAL。每一个关系代数运算对应一个MAL指令。每一个BAT代数运算映射一条简单的MAL指令,这具有零的自由度:它不会采用复杂的表达式作为参数。反而,复杂的表达式会被拆分成一系列的BAT代数运算,每一条都对整个列的值执行一个简单的操作(”bulk processing”)。这样就容许BAT代数的解析实现中忽略表达式解析引擎的实现。反而所有的BAT代数运算在实现的时候都会映射成一个简单的数组操作。

BAT代数运算具有的优势:紧凑的for-loops创造了指令的局部性,从而消除了指令在缓存miss的问题。这样简单的循环经得起编译器优化(循环流水线,阻塞,强度减少)和CPU无序的可能 。

软件架构

MonetDB 查询处理的方案分为三个软件层。 顶层是由查询语言解析器和一个启发式,language-and data model-specific 优化器组成。优化器主要是用来减少中间生成的数据和利用catalogue 知识 on join-indices。输出是一个用MAL表达的逻辑计划。

第二梯队包括一组优化的模块,这些模块组装成优化的管道。这些模块提供优化从符号处理到即时数据分布和执行。MAL程序被转化为更加有效的代码和加入资源管理指令。这种认识到不是所有的决定都可以组合在一起然后得出一个代价公式方法,突破了至今无处不在的基于代价的优化器。操作在普通的二维关系后端代数,这些优化模块共享所有的前端数据模型和查询语言。

第三梯度是MAL解析器,包含高度优化实现的二维关系代数运算的库。它们维持对象的属性是为了以后的算法能访问得到。举个例子,选择操作可以从sorted-nest of BAT的基础上提高效率。

SQL 前端

BAT 存储层次结合MAL代数提供了一个灵活的架构适应广泛的查询语言。关系表的列在前端被分解,BAT 头TID,尾values。对于每一个表,一个BAT被删除的地方被保留。三角的BAT被设计用来延迟更新到主列和允许相对廉价的快照隔离机制(只有三角BATs被赋值)。MonetDB/SQL为join indices 保留另外的BATs和value indices 是动态创建的。

总结

MonetDB完全基于内存映射文件,一旦需要swap到磁盘,性能就惨不忍睹。也就是说要处理的数据量不超过内存总量,才适合使用MonetDB。

官方网站:https://www.monetdb.org/Home

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

K-近邻算法KNN学习笔记

什么是K-近邻算法? K近邻法(k-nearest neighbor, k-NN)是1967年由Cover T
2 min read

使用Prophet进行时间序列预测

Prophet是Facebook开源的预测工具,相比ARIMA模型,Prophet真的是非常的简单。只要读入两
1 min read

采用时间序列预测股价变化

时间序列简介 在数学上,随机过程被定义为一族时间随机变量,即{x(t),t∈T},其中T表示时间t的变动范围。
5 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注