Intraoperation Parallelism

Intraoperation Parallelism

1. Parallel Sort

   • Relation
     • Range-partitioning
       • Sorts partitions individually
       • Concatenates partitions
     • Using another method
       • Apply range-partitioning

2. Parallel Join

   • Processors
     • Work with part of join
     • Local process
   • Final accumulation

3. Cost of Parallel Evaluation of Operations

   • Start-up costs
   • Skew
   • Contention for resources
   • Cost of assembling

4. Other relational operations

   • Selection
   • Projection
   • Duplicate elimination
     • Sorting
   • Aggregation

5. Range-Partitioning Sort

   • Steps
     • Range-partitioning
       • Processors interaction
       • Requirements
         • Communication overhead
         • Disk I/O
     • Sorting each partition individually
       • Data parallelism
         • Processors
         • Same operation
         • Different data sets
   • Recommendations
     • Good range-partition vector
     • Use of virtual processors

6. Parallel External Sort-Merge

   • Processors
   • Local sorting
   • Corresponding disks
   • Merge

7. Fragment-and-Replicate Join

   • Special case
     • Asymmetric join
     • Partitions one relation
     • Replicates the second one
     • Final join operation
   • General case
     • Partitions the two relations

8. Partitioned Join

   • Equi-join
   • Forms of relation partitioning
     • Range-partitioning
       • Same partition vector
       • Both relations
     • Hash-partitioning
       • Both relations
       • Same hash function