时至今日,海量数据时代的来临已经毋庸置疑。高速计算技术和先进的自动感应技术使得产生和收集大量数据成为可能,各行业获得数据量呈指数增长趋势。在最近的20年里,全球总的数据量以每年25.3％的速度增长。各行业可以利用海量数据的数据分析结果获得巨大的收益,这也充分说明了海量数据查询计算的价值。在海量数据的查询处理中,磁盘I/O操作费用是其执行操作的主要费用。在过去的20年间,主流单硬盘的容量增长了50000倍,与之对应的,在同一时期,磁盘的数据传输速率则只提高了375倍。在用户的角度看来,因为数据库系统需要存储和处理更多的数据,查询处理操作的时间增加了。现有的数据库查询技术只适用于中小规模的数据集,当处理海量数据时,现有数据库系统无法提供高效的数据操作算法和查询处理技术。面对目前的海量数据集,如何有效地执行数据分析来支持决策及科学探索是一个非常具有挑战性的问题,并且具有较大的学术和实用价值。本文的研究工作主要集中于海量数据的查询处理算法,因此本文将对一些常用的查询操作提出新的更加高效的并且适用于海量数据的查询算法,包括:连接查询、连接聚集查询、top-k查询和top-k join查询。本文的主要研究成果包括如下几个方面:　　首先,本文研究海量数据连接查询处理问题。连接查询是数据库系统中的一个重要而又昂贵的操作,其性能直接影响着数据库的整体性能。在海量数据上执行时,现有连接算法不但需要耗费大量时间和计算资源,而且在不同选择度下需要处理同样数量的数据。本文分析了现有连接算法在海量数据上执行时的性能问题,提出了一种新的基于磁盘的连接算法PI-Join,该算法可以有效地处理海量数据上的连接查询。本文提出了连接位置索引对表(JPIPT:Join Positional Index Pair Table)的概念,用来表示每个连接元组在各自数据表中的位置索引对。PI-Join的执行包括两个阶段:JPIPT构建阶段和结果输出阶段。JPIPT构建阶段对列存储化的连接属性执行高速缓存敏感的算法来构建连接位置索引对表。利用获得的JPIPT,结果输出阶段只需要对数据表执行一遍顺序扫描就可以获得结果。本文提供了算法的正确性证明和费用分析。实验表明,和传统磁盘连接算法相比,PI-Join算法可以获得达到一个数量级的加速比。　　第二,本文研究海量数据近似连接聚集查询处理问题。连接聚集查询是数据库中的一个常用的操作,它可以返回两个或者多个表的连接结果的统计信息。在某些场合下,近似连接聚集操作可以在少得多的响应时间内返回满足置信区间要求的近似结果,从而更受用户的欢迎。不过,现有方法无法以既高效又满足任意置信区间的方式来处理近似连接聚集。本文提出一种新的近似连接聚集查询算法pε-AJA((p,ε)-Approximate Join Aggregation)来有效地返回满足任意置信区间的近似连接聚集结果。本文提出且预计算两个数据结构:连接随机样本(JRS)和连接位置索引对表(JPIPT)。利用JRS,pε-AJA向用户返回近似结果的快速响应。如果利用JRS得到的近似结果没有满足给定的置信区间,pε-AJA利用JPIPT获得更多的随机连接元组。本文提出一种采样算法来获得给定数量的JPIPT样本,并且利用获得的JPIPT样本,本文提出算法通过对连接表的一遍顺序扫描获得连接元组。本文还提供了JPIPT和JRS有效的构建和维护算法。实验结果表明,pε-AJA可以获得相对于现有近似连接聚集算法3倍到2个数量级的加速比,可以获得相对于准确查询1到4个数量级的加速比,并且可以有效地完成JPIPT和JRS的构建和维护操作。　　第三,本文研究海量数据top-k查询处理问题。在海量数据上执行top-k查询时,随机读操作是受限的,NRA算法被用来处理只支持顺序读的top-k查询。NRA算法的执行分为两个阶段:增长阶段(不断累积top-k候选元组直到找到top-k结果的阈值)和收缩阶段(不断剪切候选元组直到获得最终top-k结果)。随着涉及的属性数量、元组数量和返回的结果数量的增大,NRA算法的增长阶段需要维护的候选元组也越来越多,其维护费用也越来越大。本文详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数。基于分析结果,本文提出一种新的海量数据top-k查询算法TKEP(Top-K with Early Pruning),该算法在查询处理的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组。本文给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果。实验结果表明,和传统的NRA算法相比, TKEP算法在增长阶段维护的元组数量可以减少3个数量级,TKEP算法可以获得1个数量级的加速比。　　第四,本文研究海量数据top-k join查询处理问题。PBRJ算法是一个概括了已有top-k join算法的模板,每个实例化的PBRJ算法需要拉策略P(确定从哪个连接表读取下一个元组)和界限模式B(确定PBRJ算法的阈值)。在海量数据上执行时,PBRJ算法需要扫描和维护大量候选元组,这将导致较大的执行费用。本文提出了一种新的海量数据top-k join算法TJJE(Top-k Join with JPIPT and EGRIT)。通过预计算的数据结构(EGRIT:Exponential Gap Range Information Table),TJJE算法首先估计要返回top-k join的结果需要在每个连接表中扫描的元组数量。接着,利用数据结构JPIPT(Join Positional Index Pair Table),TJJE算法确定包含最终top-k join结果的连接位置索引对元组。TJJE算法保证只需要对连接表的一遍扫描就可以获得JPIPT元组对应的连接元组,最终的top-k join结果只需要在获得的连接元组上执行一遍顺序扫描就可以获得。本文提供了TJJE算法的正确性证明和费用分析。实验结果表明,和PBRJ算法相比,TJJE算法维护的候选元组数量要少3个数量级,并且可以获得1个数量级的加速比。