Research On Database Hash Connection Algorithm

The join operation is one of the fundamental relational database query operations. It facilitates the retrieval of information from two different relations. Many techniques and method are used to implement joins, Hash join is found to perform better than other algorithms, but partition overflow is said to occur when using traditional hash join algorithm. If partition overflow occur during joining, it would seriously reduce the efficiency. It is important to study and improve the hash join algorithm to improve query efficiency.To Solve the shortcoming of partition overflow, it will propose a new algorithm——hash-merge join(HMJ, for short), it is the way of implement hash join by using merging ideas, and improve the traditional hash join algorithms. The new algorithm has two phases:the hashing phase and the merging phase. The hashing phase considers the hash value of hash table as key value, and the data in the hash table are sorted on the join attribute with hash value and as a partition. Followed by similar processing of other data, the relation is order based on the hash value and the original key value. The merging phase is merging both relations for producing the joins result. The algorithm does not produce partition overflow. The operators including hash inner join, outer join and semi-join are designed and implemented with the new algorithm of hash join based on relation database according to the characteristics of operator. During the implementation of the algorithm, decomposition storage model is used to store the temp data and loser tree is used to merge.The experimental results confirm that whether it is the inner join, the outer join or the semi-join, the new algorithm proposed performs more than the original ones.