Research On Hash Join Algorithm In DM Database

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