Database Systems: The Complete Book- P9: Database Systems and Database Design and Application courses offered at the junior, senior and graduate levels in Computer Science departments. Written by well-known computer scientists, this introduction to database systems offers a comprehensive approach, focusing on database design, database use, and implementation of database applications and database management systems | 780 CHAPTER 15. QUERY EXECUTION attributes so that joining tuples are always sent to the same bucket. As with union we ship tuples of bucket i to processor i. We may then perform the join at each processor using any of the uniprocessor join algorithms we have discussed in this chapter. To perform grouping and aggregation 7l E we distribute the tuples of R using a hash function h that depends only on the grouping attributes in list L. If each processor has all the tuples corresponding to one of the buckets of h then we can perform the 7t operation on these tuples locally using any uniprocessor 7 algorithm. Performance of Parallel Algorithms Now let us consider how the running time of a parallel algorithm on a p-processor machine compares with the time to execute an algorithm for the same operation on the same data using a uniprocessor. The total work disk I O s and processor cycles cannot be smaller for a parallel machine than a uniprocessor. However because there are p processors working with p disks we can expect the elapsed or wall-clock time to be much smaller for the multiprocessor than for the uniprocessor. A unary operation such as c R can be completed in 1 pth of the time it would take to perform the operation at a single processor provided relation R is distributed evenly as was supposed in Section . The number of disk I O s is essentially the same as for a uniprocessor selection. The only difference is that there will on average be p half-full blocks of R one at each processor rather than a single half-full block of R had we stored all of R on one processor s disk. Now consider a binary operation such as join. We use a hash function on the join attributes that sends each tuple to one of p buckets where p is the number of processors. To send the tuples of bucket i to processor i. for all i we must read each tuple from disk to memory compute the hash function and ship all tuples except the one out of p tuples that happens to belong to the bucket
