分类 数据库 中的文章

What Goes Around Comes Around

Stonebraker的论文,介绍了 9个不同时代的数据模型;层次数据库IMS,以及网络数据库CODASYL,这两者都是逻辑数据、物理数据耦合,之后出现了关系模型,有了数据独立;再往后就是各种对关系模型的补充,如实体-关系模型、关系模型++、语义数据模型、OO模型、对象关系模型、半结构模型等;从中我们可以总结到:查询优化器很有用、技术的争论通常由市场和其他因素决定,简单模型比复制模型更容易实现数据独立、KISS 保持简单是很重要的、除非用户使用中出现很大问题否则他们不会买单、没有编程语言社区的支持想在语言上做改进突破很难、新技术的推广,需要标准化,或者大力度的推广、schema-last 可能只合适小部分场景

阅读全文

bustub数据库

卡耐基梅隆的bustub数据库,实验课程;包括:LRU-k实现、可扩展的hash表、B+的的增删改查、B+树的并发控制、各种SQL算子的执行和优化,并发处理

阅读全文

Efficiently Compiling Efficient Query Plans for Modern Hardware

这是HyPer的一篇论文(HyPer是由德国莫尼黑大学主导的OLAP、OLTP混合型主内存数据库),介绍了code-gen的具体实现,最初HyPer的code-gen是生成了C++代码,然后使用gcc编译;但编译时间很长,再加上优化时间就更长了,甚至比查询执行时间还长;于是HyPer做了优化,改用LLVM,将code-gen的核心代码转为了LLVM的IR,这个IR是调用LLVM的API生成的,不是手写的所以相对容易一些,对于一些简单的操作是生成了LLVM,于是复杂的操作,如scan、join、sort需要将LLVM和C++混合执行,LLVM可以直接调用C++,所以不存在性能损失;通过最后执行来看,LLVM的code-gen从编译、优化时间,SQL执行时间,都比其他系统有很大提升

阅读全文

Generating code for holistic query evaluation

英国爱丁堡大学的一篇论文,从传统系统到现代系统的变化一个重要点是:内存增大很多,以前的I/O瓶颈对于现在来说不那么重要了,反而是CPU和内存瓶颈;而之前的火山模型对于CPU利用率来说很不好,大量的虚函数调用,多层级的函数调用增加了cache miss,也会产生更多的指令,不利于并行化和cache局部性;这篇论文提出了一个代码模板,通过识别不同的查询计划算子,来对应的生成不同的代码(对应一个大函数),不同函数之间通过物化来连接,之后通过编译器GCC来编译这段C代码,还可以对代码最O2级别优化(但会增加运行期执行时间)来达到更好的效果,论文对比了join、sort、聚合,虽然使用的是NSM存储模型,但是执行效果来看跟MonetDB的DSM差不多了;代码生成的缺点是对于小查询会有额外的开销(编译、优化、link时间)

阅读全文

Implementing Database Operations Using SIMD Instructions

介绍了SIMD指令一些基本概念,并行流水线,以及分支预测失败带来的影响;论文中提到了使用SIMD指令的方式,以及不同平台产生的差异;之后用伪代码的方式描述几个数据库常用操作;scan操作详细对比了标量版和SIMD版的区别,以及如何消除分支的方式,还有返回选中的一个元素、多个元素的标量、SIMD方式;聚合的实现方式SIMD有提供相关的操作 SIMD_min、SIMD_max即可,对于索引部分主要是介绍树结构索引,详细讨论了中间节点、叶子节点的实现方式;在有序元素上使用二分效率是非常高的,但也会有分支预测失败问题,论文中给出了混合二分+顺序扫描方式;最后是join处理方式,这里只列出了nested-loop join的SIMD实现,Duplicate-outer、Duplicate-inner、Rotate-inner

阅读全文

Rethinking SIMD Vectorization for In-Memory Databases

这是Oracle联合哥伦比亚大学做的研究,论文中讨重点讨论了数据并行化(线程、指令、数据),也就是SIMD实现;论文中给出了一些基本的SIMD操作,如selective sotre/load、gather、scatter,在论文发表的时候,这几个操作主流CPU不是全支持,只能通过一些模拟操作来支持,如permutation等;通过定义这四个最基本的操作,再往上就可以定义数据库查询中比较重要的操作了,如:scan、hash-table(horizontal、vertical、build、线性探测、double hash、cuckoo hash)、bloom filter、分区(radix、hash、range);通过hash、分区等操作,又可以定义出排序、join等更复杂的操作,相当于是层层搭积木;测试结果SIMD会有大幅度性能提升,但也受到cache size的影响

阅读全文

SIMD-Scan: Ultra Fast in-Memory Table Scan using onChip Vector Processing Units

现代数据库由I/O瓶颈转向了CPU瓶颈,利用多核能力加速全表扫描,但是向量化的能力没能充分发挥。使用向量化包括:内嵌汇编、硬件厂商提供的跨平台库函数、编译器指示符、编译器自动优化,每种都是可用性和可控性之间的权衡。论文中引入了两项优化:使用SIMD方式在寄存器中解压 轻量压缩数据(使用concatenate、shift、shuffle、mark等指令完成);使用SIMD完成等值和范围查找(使用掩码指令,将4个元素加载到寄存器中,再通过min、max比较范围,最后生成索引数组向量位),通过测试结果都有大幅度提升,并且优化实现可以适用各种数据库

阅读全文

Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines

现代数据库很多都采用了向量化执行,也就是利用 SIMD 指令,SIMD指令在碰到分支时,会出现部分元素不满足条件,导致不活跃影响利用率吞吐量下降,论文中利用了 AVX512指令集的:mark指令、permute指令、compress、expand,来实现重填充算法和策略;包括:全消费策略(需增加寄存器,主要利用buffer),以及部分消费策略(增加新寄存器,利用mark),在能放入cache的场景中,这两种算法表现的都不错,是scalar的两倍,但对于复杂场景,以及cache放不下的场景则表现退化,另外如何设置 阈值也是一个开放问题

阅读全文

Accelerating Analytics with Dynamic In-Memory Expressions

Oracle12推出了混合行/列的存储格式,磁盘(buffer pool)中按列存储,内存中按列存储加速OLAP场景;而表达式求值在很多场景下是黑盒,不易监控、也占用资源,Oracle捕获了频繁使用的表达式,将表达式物化到内存中,然后在查询计划中,根据代价来改变查询计划,将原始的查询计划的子树,替换为内存中的物化表达式,在OLAP场景中大幅度提升性能,在混合OLTP场景中也非常有效

阅读全文