分类 数据库 中的文章

What Goes Around Comes Around

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

阅读全文

bustub数据库

2023年3月20日
| 数据库
卡耐基梅隆的bustub数据库，实验课程；包括：LRU-k实现、可扩展的hash表、B+的的增删改查、B+树的并发控制、各种SQL算子的执行和优化，并发处理

阅读全文

Efficiently Compiling Efficient Query Plans for Modern Hardware

2023年2月5日
| 数据库
这是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

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

阅读全文

Implementing Database Operations Using SIMD Instructions

2023年2月1日
| 数据库
介绍了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

2023年1月27日
| 数据库
这是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

2023年1月19日
| 数据库
现代数据库由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

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

阅读全文

Accelerating Analytics with Dynamic In-Memory Expressions

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

阅读全文

  1. 1
  2. 2
  3. 3
  4. 4