Seeking the truth about ad hoc join costs

In this paper, we re-examine the results of prior work on methods for computing ad hoc joins. We develop a detailed cost model for predicting join algorithm performance, and we use the model to develop cost formulas for the major ad hoc join methods found in the relational database literature. We show that various pieces of “common wisdom” about join algorithm performance fail to hold up when analyzed carefully, and we use our detailed cost model to derive op timal buffer allocation schemes for each of the join methods examined here. We show that optimizing their buffer allocations can lead to large performance improvements, e.g., as much as a 400% improvement in some cases. We also validate our cost model's predictions by measuring an actual implementation of each join algorithm considered. The results of this work should be directly useful to implementors of relational query optimizers and query processing systems. Edited by M. Adiba. Received May 1993 / Accepted April 1996     

ArBac算法在属性分组中的拼接树模型设计

本文通过对ArBac算法的分析,指出其挖掘性能对数据库属性数目的依赖问题。从而引入了对数据库进行属性分组的挖掘策略。最终提出了实现属性分组的拼接树模型。     

基于成本的数据库查询优化浅析

主要介绍基于成本的数据库查询优化的一些基本概念,针对多表连接的三种方法：嵌套循环链接、归并连接和混合连接进行分析和阐述．并成本估算,列出估算公式,     

并行数据库上的并行CMD－Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD－Join算法.理论分析和实验结果表明,并行CMD－Join算法的效率高于其它并行Join算法.     

I/O-efficient join dependency testing,Loomis–Whitney join,and triangle enumeration

We revisit two fundamental problems in database theory. The join-dependency (JD) testing problem is to determine whether a given JD holds on a relation r. We prove that the problem is NP-hard even if the JD involves only relations each of which has only two attributes. The JD-existence testing problem is to determine if there exists any non-trivial JD satisfied by r. We present an I/O-efficient algorithm in the external memory model, which in fact settles the closely related Loomis–Whitney enumeration problem. As a side product, we solve the triangle enumeration problem with the optimal I/O-complexity, improving a recent result of Pagh and Silvestri in PODS'14.     

跨流域调水条件下水库群联合调度图的多核并行计算研究

为提高跨流域调水条件下大规模复杂水库群优化调度的计算效率和求解精度,采用并行PSO算法进行联合调度图模型的多核并行求解。该算法充分利用PSO搜索速度快、天然并行性等特点,引入多种群思想保证种群的多样性,提高算法的全局收敛能力;采用基于分治策略的Fork/Join框架实现将子种群分配到不同CPU内核进行独立求解;利用Java并发过程中的同步和通信机制实现子种群间的信息交流,避免陷入局部最优。最后通过实例分析表明,多核并行PSO算法能够充分利用多核资源,有利于提高联合调度图模型的求解速度和精度,是解决大规模复杂水库群优化调度的一种高效实用的方法。     

关系数据库中的多表联接查询

联接查询是关系数据库中最主要的查询,本文通过实例说明关系数据库中进行多表联接查询时联接的顺序性。     

Faster joins, self-joins and multi-way joins using join indices

We propose a new algorithm, called Stripe-join, for performing a join given a join index. Stripe-join is inspired by an algorithm called ‘Jive-join’ developed by Li and Ross. Stripe-join makes a single sequential pass through each input relation, in addition to one pass through the join index and two passes through a set of temporary files that contain tuple identifiers but no input tuples. Stripe-join performs this efficiently even when the input relations are much larger than main memory, as long as the number of blocks in main memory is of the order of the square root of the number of blocks in the participating relations. Stripe-join is particularly efficient for self-joins. To our knowledge, Stripe-join is the first algorithm that, given a join index and a relation significantly larger than main memory, can perform a self-join with just a single pass over the input relation and without storing input tuples in intermediate files. Almost all the I/O is sequential, thus minimizing the impact of seek and rotational latency. The algorithm is resistant to data skew. It can also join multiple relations while still making only a single pass over each input relation. Using a detailed cost model, Stripe-join is analyzed and compared with competing algorithms. For large input relations, Stripe-join performs significantly better than Valduriez's algorithm and hash join algorithms. We demonstrate circumstances under which Stripe-join performs significantly better than Jive-join. Unlike Jive-join, Stripe-join makes no assumptions about the order of the join index.     

面向多核处理器平台的并行Hash JOIN算法设计与实现

利用多核处理器提供的强大计算能力提升数据库系统性能是当前国内外数据库研究的重要问题.利用基于多核处理器上的并行编程模型MSI和Intel处理器上的SIMD(单指令流多数据流)指令有效地加速了数据库查询的Join操作,与串行实现相比其最大加速可以达13倍.同时,还对比不同数据分块大小情况下对算法的影响,找到了优化的数据分块方法.     

基于关系的并行数据仓库的数据划分和操作

目前并行数据库的研究已经进入了实际应用阶段,而数据仓库的大数据量处理更需要并行处理能力的支持。针对数据仓库的特点,提出了一种可操作的并行化数据划分方法和物理存储方案,同时对基于该种数据存储的数据操作做了详细的讨论,并对各种Join操作的具体处理方法进行了归类论述。