基于ORV的并行多表连接查询算法

为提高数据仓库中多表连接的查询处理响应时间，本文结合数据仓库中多表连接的特点，利用面向对象中的消息机制，提出了一种基于ORV（对象关系视图）的并行多表连接查询算法，并对算法的磁盘I／O操作块数进行了分析，与单处理机及传统的多表连接算法进行了比较。     

内存存储模型上的多表连接优化技术研究

分析了面向先进硬件平台上的数据库优化技术,提出了基于内存存储模型的多表连接查询处理优化技术,采用内存存储模型存储维表并对维表主键进行顺序化,从而使维表的主键与内存维表记录的内存偏移地址相一致,实现对维表记录的内存直接访问。通过列存储技术减少维表记录的访问宽度,进一步优化维表访问的cache性能。与基于SQL Server 2005的查询执行计划的连接算法、join index连接算法以及基于列存储模型的优化连接算法进行了实验比较和性能分析,结果表明:基于内存存储模型的多表连接算法在处理星型结构数据仓库多谓词、多连接的复杂查询时具有很好的性能,与join index相比不需要额外的空间开销,与列存储数据模型相比具有更好的兼容性和性能。     

基于分组序号的聚集算法

联机分析处理OLAP(online analytical processing)查询作为一种复杂查询,当使用SQL(structured query language)语句来表述时,通常都包含多表连接和分组聚集操作,因此提高多表连接和分组聚集计算的性能就成为ROLAP(relational OLAP)查询处理的关键问题.提出一种基于分组序号的聚集算法MuGA(group number based aggregation with multi-table join),该方法充分考虑数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin(multi-table join)相结合,使用分组序号进行分组聚集计算,代替通常的排序或者哈希计算,从而有效地减少CPU运算以及磁盘存取的开销.算法的实验数据表明,提出的MuGA算法与传统的关系数据库聚集查询处理方法以及改进后的基于排序的聚集算法相比,性能都有显著提高.     

基于Hadoop 的高效连接查询处理算法CHMJ

提出了一种并行连接查询处理算法CoLocationHashMapJoin(CHMJ).首先,设计了多副本一致性哈希算法,将具有连接关系的表根据其连接属性的哈希值在机群中进行分布,在提升了连接查询处理中数据本地性的同时,保证了数据的可用性;其次,基于多副本一致性哈希数据分布,提出了HashMapJoin并行连接查询处理算法,有效地提高了连接查询的处理效率.CHMJ算法在腾讯公司的数据仓库系统中进行了应用,结果表明,CHMJ连接查询的处理效率比Hive系统提高了近5倍.     

联机分析查询处理中的一种聚集算法

联机分析处理(online analytical processing,简称OLAP)查询是涉及大量数据的即席复杂查询,从SQL(structured query language)角度来看,这些查询通常都包含多表连接和分组聚集操作.从OLAP查询处理角度出发,提出一种新的基于排序的聚集查询算法MuSA(sort-based aggregation with multi-table join).该方法充分考虑到数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin相结合,排序时采用     

数据仓库中雪花模式的Skyline-Join查询

Skyline查询能够有效地实现多目标最优化,而数据仓库中的OLAP也是针对多维数据进行分析,因此,针对Skyline查询在数据仓库中的应用,提出了数据仓库中雪花模式的Skyline-Join查询算法.该算法首先将子维表M-Join父维表,然后渐进选择式地对事实表和父维表进行连接.每次连接之前都对事实表进行分组和组内Skyline计算,删除组内非Skyline元组,这样可以减少许多不必要的连接操作,使得查询效率大大提高.通过实验证明,在事实表元组数量逐渐变大和维表个数逐渐增多的情况下,提出的算法比先Join后Skyline计算的naive算法效率上有明显改善.     

提高数据仓库中查询性能的一种并行多表连接算法

星型模式是当前数据仓库设计中广泛采用的逻辑模式，针对星型模式数据仓库中潜在的查询性能问题，结合数据仓库中的ORV，利用面向对象中的消息机制，提出了基于对象关系视图（ORV）的多表连接并行查询算法，并对算法的磁盘I／O操作次数、算法的时间复杂度进行了分析。     

基于动态镜像的实时数据仓库存取预处理技术研究

实时数据仓库是数据仓库技术的重要分支,而实时数据查询和实时数据导入引发的查询竞争问题一直是实时数据仓库技术研究的重点之一。查询竞争问题严重影响了查询分析的精度和效率,还降低了数据仓库的性能。提出了一种在数据仓库外部构建动态存储区域的方法,它采用动态镜像技术,有效地缓解查询竞争问题。同时,为了提高实时OLAP上的查询分析操作的性能,提出了蝇量级物化方法及蝇量级物化下的表连接算法FWMJoin(Fly-Weight Materialization Join)。基于TPC-H基准的实时数据仓库测试系统,针对动态镜像技术下的动态存储区域的OLAP性能进行分析与评估,并对实验结果进行总结。     

星型模型的轮廓连接查询算法

轮廓查询在多标准决策中具有重要应用价值,对于单表轮廓查询已有大量研究,但在实际中,轮廓查询的属性很可能分布在多张表中。如果在多表连接之后进行轮廓查询,随着维度和元组数目的增加,计算代价会越来越大。为此,针对数据仓库中星型模型的数据特点,提出了三种此模型下的多表连接轮廓查询算法并对算法进行了实验比较分析。结果表明,此算法比先连接再做单表轮廓查询的算法更为有效,并且这三种算法在不同特点的数据集合下会表现出各自的优势。     

一种复杂多维层次的连接和聚集算法

由于数据仓库中存储着不同粒度、容量巨大的数据记录，所以如何有效地执行联机分析处理(OLAP)查询操作，特别是连接和聚集操作，便成为数据仓库领域的核心问题之一．为此，提出了一种降低连接和聚集操作的新算法(join and aggregation based on the complex multi-dimensional hierarchies，JACMDH)．算法充分考虑了复杂多维层次的特点，在原有的位图连接索引(bitmap join index)的基础上，采用层次联合代理(hierarchy combined surrogate)和预先分组排序的方法，使得复杂的多维层次上的连接和聚集操作转化成事实表上的区域查询，从而在处理多维层次聚集的同时，提高了连接和聚集的效率．算法性能分析和实验数据表明，JACMDH算法和目前流行的算法相比，其性能有显著的提高．     

数据仓库中的一种提高多表连接效率的有效方法

联机分析处理OLAP查询经常涉及多表连接，所以提高多表连接的性能就成了提高OLAP查询处理的关键性问题．针对目前直接提高多表连接效率的方法、并行多表连接算法和连接索引，提出了变形多表连接索引．该方法基于使用SQL语句表述的查询模型库QMB建立一系列符合条件的变形多表连接事实表，并建立这些变形多表连接事实表的索引．在特定的多表连接查询中，变形多表连接事实表能替代原事实表与各维表连接，并在查询处理过程中动态更新．理论分析和实验结果表明，该方法可以有效地提高多表连接的查询效率．     

一种改进的联机分析处理中的聚集算法

联机分析查询处理是一种涉及大量数据的即席复杂查洵，它通常都包含分组聚集运算。分析了关系数据仓库星型模式存储结构和数据更新的特点，把实体关系看成分布式数据库中以内存排序缓冲区人小为分段条件的全局关系，对分组操作进行分布式聚集运算，给出了一种改进的MuSA算法，有效地提高了算法性能。     

一种并行处理多维连接和聚集操作的有效方法

随着并行计算算法的完善和廉价、功能强大的多处理机系统的成熟，使得采用多处理机系统来并行处理多维数据仓库的连接和聚集操作成为当前有效提高OLAP查询处理性能的首选技术．为此，提出一种降低连接和聚集操作开销的并行算法PJAMDDC(parallel join and aggregation for multi-dimensional data cube)．算法充分考虑了多维数据立方体的存储机制和多处理机分布系统的结构特点，在原有聚集计算多维数据立方体的搜索点阵逻辑结构的基础上，采用多维数据仓库的层次联合代理(hierarchy combined surrogate)和对立方体的搜索点阵进行加权的方法，使得立方体数据在多个处理机间的分配达到最佳的状态，从而在分割多维数据的同时，提高了并行处理多维连接和聚集操作的效率．算法实验评估表明，PJAMDDC算法并行处理多维数据仓库的连接和聚集操作是有效的．     

一种改进的分组序号聚集算法

ROLAP是OLAP（联机分析处理）中使用最广泛的一种类型,其主要功能是管理决策所需要的总结数据。总结数据一般都涉及多表连接和分组聚集操作,提高这些操作的性能成为提高OLAP操作响应速度的关键。为此,提出一种基于分组序号的新聚集算法IMuGA。算法充分利用时间维表特殊性,通过对事实表关键字直接获得分组属性值,减少了多表连接中时间维度的连接次数,提高了联机分析处理查询效率。实验结果表明,该算法是有效的。     

Parallel Star Join+DataIndexes: efficient query processing in data warehouses and OLAP

On-line analytical processing (OLAP) refers to the technologies that allow users to efficiently retrieve data from the data warehouse for decision-support purposes. Data warehouses tend to be extremely large, it is quite possible for a data warehouse to be hundreds of gigabytes to terabytes in size (Chauduri and Dayal, 1997). Queries tend to be complex and ad hoc, often requiring computationally expensive operations such as joins and aggregation. Given this, we are interested in developing strategies for improving query processing in data warehouses by exploring the applicability of parallel processing techniques. In particular, we exploit the natural partitionability of a star schema and render it even more efficient by applying DataIndexes-a storage structure that serves both as an index as well as data and lends itself naturally to vertical partitioning of the data. DataIndexes are derived from the various special purpose access mechanisms currently supported in commercial OLAP products. Specifically, we propose a declustering strategy which incorporates both task and data partitioning and present the Parallel Star Join (PSJ) Algorithm, which provides a means to perform a star join in parallel using efficient operations involving only rowsets and projection columns. We compare the performance of the PSJ Algorithm with two parallel query processing strategies. The first is a parallel join strategy utilizing the Bitmap Join Index (BJI), arguably the state-of-the-art OLAP join structure in use today. For the second strategy we choose a well-known parallel join algorithm, namely the pipelined hash algorithm. To assist in the performance comparison, we first develop a cost model of the disk access and transmission costs for all three approaches.     

Improving performance by creating a native join-index for OLAP

The performance of online analytical processing (OLAP) is critical for meeting the increasing requirements of massive volume analytical applications. Typical techniques, such as in-memory processing, column-storage, and join indexes focus on high performance storage media, efficient storage models, and reduced query processing. While they effectively perform OLAP applications, there is a vital limitation: mainmemory database based OLAP (MMOLAP) cannot provide high performance for a large size data set. In this paper, we propose a novel memory dimension table model, in which the primary keys of the dimension table can be directly mapped to dimensional tuple addresses. To achieve higher performance of dimensional tuple access, we optimize our storage model for dimension tables based on OLAP query workload features. We present directly dimensional tuple accessing (DDTA) based join (DDTAJOIN), a technique to optimize query processing on the memory dimension table by direct dimensional tuple access. We also contribute by proposing an optimization of the predicate tree to shorten predicate operation length by pruning useless predicate processing. Our experimental results show that the DDTA-JOIN algorithm is superior to both simulated row-store main memory query processing and the open-source column-store main memory database MonetDB, thanks to the reduced join cost and simple yet efficient query processing.