High-Performance Parallel Database Processing and Grid Databases- P6

High-Performance Parallel Database Processing and Grid Databases- P6: Parallel databases are database systems that are implemented on parallel computingplatforms. Therefore, high-performance query processing focuses on queryprocessing, including database queries and transactions, that makes use of parallelismtechniques applied to an underlying parallel computing platform in order toachieve high performance.
Nội dung trích xuất từ tài liệu:
High-Performance Parallel Database Processing and Grid Databases- P6230 Chapter 8 Parallel Universal Qualification—Collection Join Queries Case 1: ARRAYS a(250, 75) b(210, 123) f(150, 50, 250)Hash Table 1 Hash Table 2 Hash Table 3 50(f) 150(f) 75(a) 210(b) 123(b) 250(f) 250(a)Case 2: SETS a(250, 75) Sort a(75, 250) b(210, 123) b(123, 210) f(150, 50, 250) f(50, 150, 250) Hash Table 1 Hash Table 2 Hash Table 3 50(f) 150(f) 75(a) 210(b) 123(b) 250(f) 250(a) Figure 8.7 Multiple hash tablescollision will occur between h(150,50,25) and collection f (150,50,250). Collisionwill occur, however, if collection h is a list. The element 150(h/ will be hashed tohash table 1 and will collide with 150( f /. Subsequently, the element 150(h/ willgo to the next available entry in hash table 1, as a result of the collision. Once the multiple hash tables have been built, the probing process begins. Theprobing process is basically the central part of collection join processing. The prob-ing function for collection-equi join is called a function universal. It recursively 8.4 Parallel Collection-Equi Join Algorithms 231checks whether a collection exists in the multiple hash table and the elementsbelong to the same collection. Since this function acts like a universal quantifierwhere it checks only whether all elements in a collection exist in another collection,it does not guarantee that the two collections are equal. To check for the equalityof two collections, it has to check whether collection of class A (collection in themultiple hash tables) has reached the end of collection. This can be done by check-ing whether the size of the two matched collections is the same. Figure 8.8 showsthe algorithm for the parallel sort-hash collection-equi join algorithm.Algorithm: Parallel-Sort-Hash-Collection-Equi-Join// step 1 (disjoint partitioning): Partition the objects of both classes based on their first elements (for lists/arrays), or their minimum elements (for sets/bags).// step 2 (local joining): In each processor, for each partition // a. preprocessing (sorting) // sets/bags only For each collection of class A and class B Sort each collection // b. hash For each object of class A Hash the object into multiple hash tables // c. hash and probe For each object of class B Call universal (1, 1) // element 1,hash table 1 If TRUE AND the collection of class A has reached end of collection Put the matching pair into the resultFunction universal (element i, hash table j): Boolean Hash and Probe element i to hash table j If matched // match the element and the object Increment i and j // check for end of collection of the probing class. If end of collection is reached Return TRUE If hash table j exists // check for the hash table result D universal (i, j) Else Return FALSE Else Return FALSE Return resultFigure 8.8 Parallel sort-hash collection-equi join algorithm232 Chapter 8 Parallel Universal Qualification—Collection Join Queries8.4.4 Parallel Hash Collection-Equi Join AlgorithmUnlike the parallel sort-hash explained in the previous section, the algorithmdescribed in this section is purely based on hashing only. No sorting is necessary.Hashing collections or multivalues is different from hashing atomic values. If thejoin attributes are of type list/array, all of the elements of a list can be concatenatedand produce a single value. Hashing can then be done at once. However, thismethod is applicable to lists and arrays only. When the join attributes are of typeset or bag, it is necessary to find new ways of hashing collections. To illustrate how hashing collections can be accomplished, let us review howhashing atomic values is normally performed. Assume a hash table is implementedas an array, where each hash table entry points to an entry of the record or object.When collision occurs, a linear linked-list is built for that particular hash tableentry. In other words, a hash table is an array of linear linked-lists. Each of thelinked-lists is connected only through the hash table entry, which is the entry pointof the linked-list. Hash tables for collections are similar, but each node in the linked-list can beconnected to another node in the other linked-li ...