面向共享Cache多核处理器的数据库查询执行优化技术研究

论文摘要

随着硬件技术的飞速发展,内存价格越来越低,大内存容量已成为数据库服务器的标准配置,这在很大程度上缓解了数据库查询执行的磁盘I/O代价,也促进了内存数据库的普及应用,给数据库带来性能提升的同时,也造成了新问题。由于处理器速度增长的速度远大于内存,导致处理器花费大量时间等待数据从内存取到CPU缓存（Cache）,内存访问已经成为数据库查询执行的主要代价之一。与此同时,单核处理器的性能提升空间已经十分有限,导致处理器的发展趋势转向多核处理器,多核处理器已经成为处理器市场的主流,并且得到了飞速发展。同样,多核处理器给数据库带来性能提升的同时也带来了挑战。首先,基于单线程模式的查询执行算法使得数据库不能充分利用多核处理器的并行计算资源,其次,多核处理器的核心间一般共享部分资源,比如Cache和内存带宽,在内存访问成为数据库主要代价的前提下,由于多线程同时访问共享Cache造成的共享Cache访问冲突给数据库性能提升带来了较大负面影响,再次,有限的内存带宽和多核处理器各个核心间的负载不均衡也影响了线程的执行效率。因此如果要充分利用共享Cache多核处理器提升数据库性能,既要从多线程并行执行角度优化查询执行的性能,同时也要改善多线程执行时的Cache访问性能,特别是减少共享Cache访问冲突。目前面向多核处理器的数据库查询执行优化研究仍处于初步阶段,存在许多问题亟待解决。数据库查询执行性能优化一直是国内外数据库研究者广泛关注的问题,是数据库领域充满挑战性的一个研究方向,论文的研究目的是面向共享Cache多核处理器优化查询执行的性能。本文在全面分析和总结国内外数据库领域相关研究工作的基础上,针对查询执行在共享Cache多核处理器中面临的性能瓶颈,面向数据库查询执行性能优化的需求,对几类基础的数据库查询操作,比如数据库排序、数据库连接查询和数据库索引的优化技术进行研究。本文的主要工作和创新点包括下面几个方面:（1）提出了基于共享Cache多核处理器的数据库排序多线程执行框架,该框架基于Inplaced Flash QuickSort（IFQS）算法。针对IFQS的三个执行阶段的数据访问特点,分别提出了各自的多线程执行模式和相应的Cache性能优化措施,特别是减少了共享Cache访问冲突。（2）提出了基于数据划分策略的多线程Hash连接执行框架,该框架采用Radix-Join算法,分为聚集划分和聚集连接两个阶段。通过深入分析多线程Radix-Join算法在共享Cache多核处理器中运行时的性能瓶颈,有针对性地对该框架的性能进行优化。对于聚集划分阶段,提出了一种自适应的多线程聚集划分策略;对于聚集连接阶段,提出了基于聚集大小分类的多线程聚集连接执行策略,并优化了聚集连接时的内存访问。上述优化技术能够较大地减少多线程执行时的共享Cache访问冲突和处理器核心间的负载不均衡,以提高线程的执行效率。（3）针对索引嵌套循环连接,提出了共享Cache敏感的索引嵌套循环连接多线程执行框架（SCS-INLJPEF）。SCS-INLJPEF采用流水线式多线程执行模式,根据查询执行计划中的数据操作节点合理设置流水线中的操作,提出了共享Cache敏感的缓存结构用于管理SCS-INLJPEF中的各种缓存,并给出了SCS-INLJPEF执行时的内存访问代价模型,然后根据该模型在流水线的各个操作间合理分配处理器计算资源,达到减少处理器核心间负载不均衡和改善线程Cache访问性能的目的。（4）针对无索引的嵌套循环连接,提出了基于数据划分策略的嵌套循环连接多线程执行框架,该框架采用Radix-Join算法中的数据划分策略,同样分为聚集划分和聚集连接两个阶段。针对聚集划分阶段,通过设置合理的聚集划分线程启动时机减少共享Cache访问冲突;针对聚集连接阶段Cache访问性能较差的缺点,利用每个聚集数据量很小的特点和聚集连接线程顺序访问聚集带来的优势,提出了多线程聚集连接执行策略,利用预取线程改善聚集连接线程Cache性能,并通过合理设置预读线程参数使该框架适应于不同的处理器核心数,并减少共享Cache访问冲突。（5）将流水线式多线程执行模式用于索引访问性能优化,提出了CSB+-Trees多线程访问模块（CSBT-MAM）。CSBT-MAM基于CSB+-Trees的树结构层次设置流水线中的操作,通过分析CSBT-MAM的处理流程,给出了其内存访问模型,然后基于该模型合理划分CSB+-Trees中的节点,设置流水线中操作的数量和对应的工作集,达到改善索引访问线程Cache性能的目的,并根据该节点划分分配处理器的计算资源,最后将CSBT-MAM用于SCS-INLJPEF的进一步优化。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景及研究意义
• 1.1.1 多核处理器
• 1.1.2 课题研究意义
• 1.2 相关研究现状
• 1.2.1 面向多核处理器的数据库优化
• 1.2.2 基于Cache 访问优化的数据库优化
• 1.2.3 研究现状总结与分析
• 1.3 本文的主要工作
• 1.4 论文的组织结构
• 第二章 共享Cache 敏感的数据库内存排序多线程执行框架
• 2.1 相关工作
• 2.2 基于共享Cache 多核处理器的数据库排序优化
• 2.2.1 数据库排序多线程执行框架
• 2.2.2 QuickSort 执行性能比较、分析及问题描述
• 2.2.3 数据分类及其优化
• 2.2.4 数据交换及其优化
• 2.2.5 键值子集排序及其优化
• 2.3 SCS-MSF 性能分析
• 2.3.1 时间复杂度分析
• 2.3.2 SCS-MSF 内存访问代价分析
• 2.3.3 多线程键值子集排序加速比分析
• 2.3.4 多查询并行执行条件下SCS-MSF 性能分析
• 2.4 实验与结果分析
• 2.4.1 实验设置
• 2.4.2 参数设置及性能测试
• 2.4.3 SCS-MSF 优化策略性能测试
• 2.4.4 SCS-MSF 性能测试
• 2.5 结论
• 第三章 基于数据划分策略的Hash 连接多线程优化技术
• 3.1 相关工作
• 3.2 Hash 连接多线程执行框架
• 3.3 Hash 连接多线程框架优化
• 3.3.1 多线程Radix-Join 执行性能比较、分析及问题描述
• 3.3.2 Radix-Join 算法参数优化
• 3.3.3 聚集划分线程优化
• 3.3.4 聚集连接线程优化
• 3.3.5 内存访问优化
• 3.4 Hash 连接多线程执行框架性能分析
• 3.4.1 多线程聚集划分加速比分析
• 3.4.2 Hash 连接Cache 访问性能分析
• 3.4.3 多查询并行执行条件下Hash 连接优化性能分析
• 3.5 实验结果与分析
• 3.5.1 实验设置
• 3.5.2 参数设置及性能测试
• 3.5.3 聚集划分性能测试
• 3.5.4 聚集连接性能测试
• 3.5.5 Hash 连接性能比较分析
• 3.6 结论
• 第四章 面向共享Cache 多核处理器的嵌套循环连接优化
• 4.1 相关工作
• 4.1.1 NLJ 相关研究现状
• 4.1.2 流水线式多线程查询执行研究现状
• 4.2 基于流水线式多线程执行模式的索引嵌套循环连接优化
• 4.2.1 INLJ 多线程执行框架
• 4.2.2 SCS-INLJPEF 执行性能比较、分析及问题描述
• 4.2.3 缓存访问优化
• 4.2.4 SCS-INLJPEF 数据访问代价模型
• 4.2.5 线程执行优化
• 4.2.6 多查询并行执行条件下SCS-INLJPEF 性能分析
• 4.2.7 实验结果与分析
• 4.2.8 本节总结
• 4.3 基于Radix-Join 算法的非索引嵌套循环连接优化
• 4.3.1 基于Radix-Join 的NINLJ 多线程执行框架
• 4.3.2 聚集划分优化
• 4.3.3 聚集连接优化
• 4.3.4 多查询并行执行条件下NINLJ 多线程执行框架性能分析
• 4.3.5 实验结果与分析
• 4.3.6 本节总结
• 4.4 结论
• 第五章 基于流水线式多线程执行模式的索引访问优化技术
• 5.1 相关工作
• +-Trees 访问性能优化'>5.2 基于共享Cache 多核处理器的CSB⁺-Trees 访问性能优化
• +-Trees 多线程访问模块'>5.2.1 基于流水线的CSB⁺-Trees 多线程访问模块
• 5.2.2 CSBT-MAM 数据访问模型
• 5.2.3 CSBT-MAM 参数优化
• 5.2.4 CSBT-MAM 缓存设置
• 5.2.5 CSBT-MAM 性能分析
• 5.3 实验与结果分析
• 5.3.1 实验设置
• 5.3.2 索引节点划分性能测试
• 5.3.3 线程参数性能测试
• 5.3.4 索引访问整体性能测试
• 5.4 CSBT-MAM 应用及性能测试
• 5.5 结论
• 第六章 总结与展望
• 6.1 主要研究成果
• 6.2 下一步研究工作
• 致谢
• 参考文献
• 作者在学期间取得的学术成果
• 作者在学期间参加和完成的科研项目