摘要: 最近几年来，随着计算机内存容量的飞快提高，很多数据库应用都可以把数据集全部放在内存中操作。这样的话，内存访问已经取代硬盘访问成为新的系统性能瓶颈。而随着处理器和内存之间速度差距的增大，这个问题越来越突出。已有的研究表明，查询执行速度很大程度上取决于L2 cache的访问延迟。为了减小这个延迟，很多研究者提出应该提高数据的空间局部性，并给出了很多算法，如PAX、Data Morphing等。这些算法发挥了很好的效果，极大地降低了L2 cache miss的数目，提高了查询执行速度。然而，这些算法只是针对单个查询，只考虑数据的空间局部性，对于多个查询并行执行的情况，这些算法没有考虑不同查询之间的数据共享问题，无法从整体上进一步提高数据在L2 cache中的共享程度。事实上，很多数据库应用中都存在着大量的数据共享：用户或者经常并行执行相同模式的查询，或者执行的查询并不相同，但这些查询却在操作着相同的数据集。针对这样的现象，本文提出了一个称为MiniTasking的新思想，能够有效地提高多个并行查询中数据的时间局部性，从而进一步减少cache miss的数目，提高查询性能。MiniTasking通过在以下三个层面有效地利用多个查询之间的数据共享，从而提高查询实现效率：（1）首先，MiniTasking根据多个并行查询所共享的数据的特性和cache的配置，选择一组查询作为一个整体进行处理；（2）对于每组查询，MiniTasking给出这些查询的物理操作符树（physical operator tree），然后根据它们的物理操作符所共享数据的情况以及这些操作符的实现方式和依赖关系，把物理操作符分成不同的组；（3）对于每一组物理操作符，MiniTasking把它们分成规模适当的mini-tasks，然后以数据为中心来调度这些mini-tasks，访问相同数据的mini-tasks（即使来自不同的查询）在一起执行。MiniTasking是已有的力图提高访问数据的空间局部性的算法的良好补充，它可以和PAX、Data Morphing等算法一起很好地协同工作。MiniTasking对于多查询优化（MQO）算法也是一个很好的补充。本文基于University of Wisconsin-Madison的存储管理系统Shore进行开发，实现了TPC-H中6个最具代表性的查询，然后进行了一系列测试和实验。本文在TPC-H查询测试环境中所做的实验表明，对于传统的NSM数据格式，MiniTasking能够把L2 cache miss的数目降低83%，从而把查询执行时间降低24%。针对PAX数据格式，MiniTasking也能进一步地降低65%的cache miss，从而把查询速度再提高9%。在对TPC-H查询吞吐量的测试中，MiniTasking能够把系统的最终性能提高20%。实验结果还表明，MiniTasking的参数配置基本上和查询类型无关。本文下一步需要考虑的是，MiniTasking如何与现有的数据库管理系统的查询执行引擎相结合。