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场景中也非常有效

阅读全文

Materialization Strategies in the Vertica Analytic Database: Lessons Learned

2023年1月7日

| 数据库

列存数据库会通过物化的方式来重建tuple，包括早期物化EM、延迟物化LM，延迟物化的性能更好，但实现更难，当出现join溢出时会出现，此时会退回到早期物化；论文在早期物化基础上增加了：边信息传递SIP技术，并给出了实现细节，如何创建SIP，如何做push down；使用EM+SIP技术，比原始的EM性能大幅度提升，并且在很多场景下比延迟物化LM性能更好

阅读全文

MonetDB/X100: Hyper-Pipelining Query Execution

2023年1月5日

| 数据库

2005年的一篇论文，通过分析MySQL、MonetDB发现这两种没有达到硬件上的预期效果，MySQL是因为经典的火山模型导致编译器没法利用循环流水线，出现大量CPU等待；而MonetDB避免了上述情况但使用了物化，又导致大量的内存带宽拷贝；这篇论文结合了这两者的特点，选择了向量化的执行方式，并配合了合适的cache size，使得执行效率大幅度提升

阅读全文

Access Path Selection in Main-Memory Optimized Data Systems Should I Scan or Should I Probe

2023年1月3日

| 数据库

CMU Query Execution & Processing课程的一篇论文，现代分析系统中scan越来越重要，但二级索引依然有用，通过对比硬件参数、数据布局、压缩、并发等综合情况考虑之下，来选择：scan执行或者index执行；通过性能评估发现，调节scan或者index并不是一个固定的值，而是根据不同的参数以及硬件情况，会动态变化的

阅读全文