Database Systems: The Complete Book- P9

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
Nội dung trích xuất từ tài liệu:
Database Systems: The Complete Book- P9 780 CHAPTER 15. QUERY EXECUTION p-ARALLEL ALGORITHJ,lS FOR RELATIONAL OPERATIONS 781 attributes, so that joining tuples are always sent to the same bucket. As if we used a two-pass sort-join at each processor, a naive ~arallel with union, we ship tuples of bucket i to processor i. We may then perform algorithm would use 3(B(R) + B(S))/P disk 110s a t each processor, since the join at each processor using any of the uniprocessor join algorithms the sizes of the relations in each bucket would be approximately B(R)/P and we have discussed in this chapter. B(S)Ip, and this type of join takes three disk I / 0 7 sper block occupied by each of + the argument relations. To this cost we would add another ~ ( B ( R ) B(s))/P To perform grouping and aggregation ~ L ( R )we distribute the tuples of , disk 110s per processor, to account for the first read of each tuple and the R using a hash function h that depends only on the grouping attributes storing away of each tuple by the processor receiving the tuple during the hash in list L. If each processor has all the tuples corresponding to one of the and distribution of tuples. UB should also add the cost of shipping the data, buckets of h, then we can perform the y~ operation on these tuples locally, but ,ye elected to consider that cost negligible compared with the cost of using any uniprocessor y algorithm. disk 110 for the same data. The abo-e comparison demonstrates the value of the multiprocessor. While 15.9.4 Performance of Parallel Algorithms lve do more disk 110 in total - five disk 110s per block of data, rather than three - the elapsed time, as measured by the number of disk 110s ~erformed Now, let us consider how the running time of a parallel algorithm on a p + at each processor has gone down from 3(B(R) B(S)) to 5(B(R) + B(S))/P, processor machine compares with the time to execute an algorithm for the a significant win for large p. same operation on the same data, using a uniprocessor. The total work - XIoreover, there are ways to improve the speed of the parallel algorithm so disk 110s and processor cycles - cannot be smaller for a parallel machine that the total number of disk 110s is not greater than what is required for a than a uniprocessor. However, because there are p processors working with p uniprocessor algorithm. In fact, since we operate on smaller relations at each disks, we can expect the elapsed, or wall-clock, time to be much smaller for the processor, nre maJr be able to use a local join algorithm that uses fewer disk multiprocessor than for the uniprocessor. I / 0 3 s per block of data. For instance, even if R and S were so large that we :j unary operation such as ac(R) can be completed in llpth of the time it need a t~f-o-pass algorithm on a uniprocessor, lye may be able to use a One-Pass would take to perform the operation a t a single processor, provided relation R algorithnl on (1lp)th of the data. is distributed evenly, as was supposed in Section 15.9.2. The number of disk Ke can avoid tlvo disk 110s per block if: when we ship a block to the 110s is essentially the same as for a uniprocessor selection. The only difference processor of its bucket, that processor can use the block imnlediatel~as Part is that t,here will, on average, be p half-full blocks of R, one at each processor, of its join 11ost of the algorithms known for join ...