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算法.     

NES-Join算法的改进算法

NES-Join算法是一种无需外排序的连接运算算法,其复杂性优于经典的Sort-Merge Join算法及改进后的SDC-Join算法.在NES-Join算法基础上提出一种改进算法,该算法能够有效压缩原算法中未匹配记录暂存块中的空记录信息,从而使NES-Join算法更具实用性.通过实验和分析表明,改进后的NES-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.