论文部分内容阅读
长期以来,数据库领域的主要研究方向是磁盘数据库,在磁盘数据库中,内存主要作为数据的临时缓冲区,用来提高数据库系统的性能,内存与磁盘之间的I/O操作是影响数据库性能的主要瓶颈。随着硬件技术的快速发展,内存的容量越来越大,价格也越来越便宜,现在拥有TB数量级内存的计算机已经出现,越来越多的数据可以放到内存中;同时磁盘数据库一直在研究减少I/O次数的技术,如异步IO、磁盘阵列、压缩技术等,使得I/O在很多情况下已经不是主要的或者是唯一的系统瓶颈,CPU对内存的访问延迟越来越重要。其他新硬件技术的出现如SMT、多核等也为数据库的发展提出了新的机遇。主存数据库越来越多的受到研究者以及工业界的关注。
主存数据库的优势主要体现在以下方面：
第一、主存数据库作为独立的数据库能够比磁盘数据库提供更快的响应速度和更高吞吐量的事务处理。磁盘数据库中的数据常驻磁盘,其体系结构、算法优化、缓冲区管理等各个方面的设计目标是减少内存读写磁盘的次数,但这种单纯以减少I/O为目标的数据库不能很好的适应硬件的发展现状,无法满足应用系统的高性能需求。
第二、主存数据库可以作为磁盘数据库的中间件缓存与后端的磁盘数据库一起协同工作。在三层体系结构中,应用服务器需要一个轻量级的、高性能的、易于安装和维护的、具有足够小代码长度的数据库系统,主存数据库恰好满足这些条件,因此可以作为磁盘数据库的中间件缓存。
本文主要研究主存数据库的索引和查询处理技术,查询处理技术主要集中在Cube By操作符算法以及Closed Cube By操作符算法上。主存数据库研究面临的挑战在于要改变传统磁盘数据库的优化目标,将有效的利用CPU等硬件资源,减少CPU与内存之间的交互作为新的着眼点,设计新的基于内存的高性能数据组织结构、数据访问和处理方法。快速的索引技术以及操作符算法是高性能数据库管理系统的重要组成部分,对能否很好的满足应用需求有着重要的作用。因此,本文将这些核心的数据库技术作为研究重点,主要的贡献如下:
1、提出一种主存数据库的索引结构J+-tree,并给出在J+tree上进行单值查询、范围查询、插入和删除操作的算法。J+-tree索引主要由两部分组成,上层是一个Judy数字树,下层是用双向指针链接起来的叶子结点。所有的关键字都按顺序存储在叶子结点中,每个叶子结点的最小关键字作为这个叶子结点的引用关键字存储到上层的Judy数据结构中。引用关键字被分解成多个字节,分层存储在Judy树中,Judy树的每一层至少可以存放关键字的一个字节。这种存储方式使得J+-tree的高度与存储的关键字的数目没有直接关系,索引树不会随着关键字数目的增多而变高,关键字本身的大小决定了树的高度,对于32位的关键字,J+-tree仅用五层就可以存储所有可能的值。在树结构上单值查询的快慢与树的高度成正比,同时单值查询也是插入和删除操作的重要组成部分,因此J+-tree可以提供快速的查询、插入和删除操作。实验表明,J+-tree是一种高性能的主存索引结构。
2、提出一种具有高效范围查询算法的索引结构PJ+-tree,并给出在PJ+-tree上进行单值查询、范围查询、插入和删除操作的方法。PJ+-tree基于J+-tree索引,将软件预取技术引入其中,进一步提高范围查询的性能。PJ+-tree由上下两部分组成,上层结构与J+-tree一致,下层的叶子结点除了包含指向左右兄弟结点的指针之外,增加了一个预取指针,指向要预取的叶子结点,通过这个指针可以很容易的得到要预取的结点的地址。进行范围查询的时候,在处理当前结点的同时发出对后面的结点的预取指令,这样多个结点的读取操作、结点的读取和处理操作可以重叠起来,加快查询速度。实验表明,预取技术的加入能够在不影响其他操作的情况下,有效的提高范围查询的效率。
3、提出一种高性能的方体计算方法CC-Culbing。Cube By是一个非常耗时的操作符,对系统整体性能有较大影响。CC-Cubing采用自底向上的聚集策略,使用多种优化技术提高计算速度。首先,它集成了宽度优先和广度优先的分片顺序,同时对多个属性进行分片,这种分片方式可以提高数据的利用率,减少读取数据的次数。其次,将预取技术引入到排序阶段,隐藏数据扫描引起的数据缺失。除此之外,CC-Cubing还使用一种缓存优化的排序算法转换方法,利用两种排序策略的指令数精确判断是否需要进行改变。实验表明,CC-Cubing是一种快速的方体计算方法,在多数情况下要比已有的BUC、Star-Cubing和MM-Cubing方法快3倍以上,有时具有4-5倍的加速比。
4、提出一种适应SMT及多核新硬件技术的并行方体计算方法CC-Cubing-SMT。这种方法在CO-Cubing的基础上使用基于两个线程的并行策略,各个属性的分片形成一个共享逻辑队列,每个线程从这个队列中获取分片,在得到的分片上进行计算,完成之后再从队列中取下一个分片继续执行。两个线程同时处于忙碌状态,工作负载在两个线程间均匀分布。CC-Cubing-SMT能够充分利用SMT以及多核技术提供的硬件资源,一个线程的缺失可与另一个线程的计算重叠起来。实验表明,CC-Cubing-SMT能够比CC-Cubing提高27％的性能。
5、提出一种高性能的封闭方体计算方法3C-Cubing。3C-Cubing在自底向上对数据进行聚集的同时,寻找覆盖聚集单元的封闭单元。它使用多种剪枝策略,避免不必要的递归调用。确定不需要经过判断可直接计算的分片,节省判断时间。为了进一步减少延迟,对多个属性进行预排序,并使用软件预取技术提高性能。实验表明,3C-Cubing方法是快速有效的,在多数情况下可比已有的C-Cubing(StarArray)和C-Cubing(MM)方法快2倍以上。