LevelDB 基本概念
LevelDB的架构，各个组件的基本原理，一些基本操作(open、增删改)，高级特性(options、自定义比较器)
OceanBase开发者大会分享
看了几位大佬的分享，总结一下
bustub数据库
卡耐基梅隆的bustub数据库，实验课程；包括：LRU-k实现、可扩展的hash表、B+的的增删改查、B+树的并发控制、各种SQL算子的执行和优化，并发处理
CPU and Cache Efficient Management of Memory-Resident Databases
CPU and Cache Efficient Management of Memory-Resident Databases
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的影响
Advanced Database Systems: Query Execution & Processing
这一部分是属于 执行引擎组件，由于现代系统从I/O变为CPU瓶颈，CPU的指令依赖、分支预测就阻塞了并行优化；MonetDB/X100就指出了火山模型、物化模型的问题，后使用了向量化/批模型来优化，为后续系统提供了方向。查询处理又包括：自顶向下vs字底向上；并行化包括：水平(exchange算子)、垂直、以及混合；worker的分配还包括单核单线程、单核pool；列存重建使用早期物化+SIP达到了早期物化的简单，同时兼具性能；主内存系统中二级索引和scan都有用，但需要综合考虑：选择性；硬件参数、数据布局、并发，优化器也需要配合重构整合；Oracle首创的混合行+列存储，又进一步提供了表达式替换(本质上是语法树子节点替换)
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比较范围，最后生成索引数组向量位)，通过测试结果都有大幅度提升，并且优化实现可以适用各种数据库