论文部分内容阅读
随着硬件技术的飞速发展,内存价格越来越低,大内存容量已成为数据库服务器的标准配置,这在很大程度上缓解了数据库查询执行的磁盘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的进一步优化。