DBCC-Join:一种新的高速缓存敏感的磁盘连接算法

摘要

随着CPU和内存的性能差距越来越大,系统设计者在CPU寄存器和内存之间插入高速缓存来弥补这个差距。高速缓存的数据存取速度远高于内存,所以数据库操作要获得更好的性能就必须考虑充分利用高速缓存。基于磁盘的连接操作是一种常用并且耗时的数据库查询操作,可是大多数传统的连接算法在设计时都没有考虑高速缓存的使用,从而使得这些连接算法无法充分利用CPU的能力。文中分析了传统的连接算法在高速缓存利用方面的问题,并且提出了一种新的可以充分利用高速缓存的磁盘连接算法DBCC-Join。连接位置索引对表JPIPT是用到的数据结构,说明了每个连接结果元组在各自表中的位置索引对。DBCC-Join的执行包括两个阶段:JPIPT构建阶段和结果输出阶段。JPIPT构建阶段对列存储化的连接属性执行高速缓存敏感的算法来构建连接位置索引对表。利用获得的JPIPT,结果输出阶段只需要对数据表执行一遍顺序扫描就可以获得结果。该文是第一篇提出利用高速缓存的磁盘连接算法的文章。实验表明,和传统磁盘连接算法相比,DBCC-Join算法可以获得一个数量级的加速比。