Fragment-and-Replicate Join (Cont.) Both versions of fragment-and-replicate work with any join condition, since every tuple in r can be tested with every tuple in s. Usually has a higher cost than partitioning,since one of the relations (for asymmetric fragment-and-replicate)or both relations (for general fragment-and-replicate)have to be replicated. Sometimes asymmetric fragment-and-replicate is preferable even though partitioning could be used. E.g.,if s is small and ris large,and ris already partitioned,it may be cheaper to replicate s across all nodes,rather than repartition r and s on the join attributes. Question:how do you implement left outer join using above join techniques? Database System Concepts-7th Edition 22.17 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 22.17 ©Silberschatz, Korth and Sudarshan th Edition Fragment-and-Replicate Join (Cont.) ▪ Both versions of fragment-and-replicate work with any join condition, since every tuple in r can be tested with every tuple in s. ▪ Usually has a higher cost than partitioning, since one of the relations (for asymmetric fragment-and-replicate) or both relations (for general fragment-and-replicate) have to be replicated. ▪ Sometimes asymmetric fragment-and-replicate is preferable even though partitioning could be used. • E.g., if s is small and r is large, and r is already partitioned, it may be cheaper to replicate s across all nodes, rather than repartition r and s on the join attributes. ▪ Question: how do you implement left outer join using above join techniques?
Handling Skew Skew can significantly slow down parallel join ■Join skew avoidance Balanced partitioning vector Virtual node partitioning Dynamic handling ofjoin skew Detect overloaded physical nodes If a physical node has no remaining work,take on a waiting task (virtual node)currently assigned to a different physical node that is overloaded Example of work stealing Cheaper to implement in shared memory system,but can be used even in shared nothing/shared disk system Database System Concepts-7th Edition 22.18 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 22.18 ©Silberschatz, Korth and Sudarshan th Edition Handling Skew ▪ Skew can significantly slow down parallel join ▪ Join skew avoidance • Balanced partitioning vector • Virtual node partitioning ▪ Dynamic handling of join skew • Detect overloaded physical nodes • If a physical node has no remaining work, take on a waiting task (virtual node) currently assigned to a different physical node that is overloaded • Example of work stealing ▪ Cheaper to implement in shared memory system, but can be used even in shared nothing/shared disk system
Other Relational Operations Selection oe(r) If 0 is of the form a =v,where a;is an attribute and v a value. If r is partitioned on a;the selection is performed at a single node. If 0 is of the form I <=a<=u (i.e.,0 is a range selection)and the relation has been range-partitioned on a Selection is performed at each node whose partition overlaps with the specified range of values. In all other cases:the selection is performed in parallel at all the nodes. Database System Concepts-7th Edition 22.19 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 22.19 ©Silberschatz, Korth and Sudarshan th Edition Other Relational Operations Selection (r) ▪ If is of the form ai = v, where ai is an attribute and v a value. • If r is partitioned on ai the selection is performed at a single node. ▪ If is of the form l <= ai <= u (i.e., is a range selection) and the relation has been range-partitioned on ai • Selection is performed at each node whose partition overlaps with the specified range of values. ▪ In all other cases: the selection is performed in parallel at all the nodes
Other Relational Operations (Cont.) Duplicate elimination Perform by using either of the parallel sort techniques eliminate duplicates as soon as they are found during sorting. Can also partition the tuples (using either range-or hash-partitioning) and perform duplicate elimination locally at each node. ■Projection Projection without duplicate elimination can be performed as tuples are read from disk,in parallel. If duplicate elimination is required,any of the above duplicate elimination techniques can be used. Database System Concepts-7th Edition 22.20 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 22.20 ©Silberschatz, Korth and Sudarshan th Edition Other Relational Operations (Cont.) ▪ Duplicate elimination • Perform by using either of the parallel sort techniques ▪ eliminate duplicates as soon as they are found during sorting. • Can also partition the tuples (using either range- or hash- partitioning) and perform duplicate elimination locally at each node. ▪ Projection • Projection without duplicate elimination can be performed as tuples are read from disk, in parallel. • If duplicate elimination is required, any of the above duplicate elimination techniques can be used
Grouping/Aggregation Step 1:Partition the relation on the grouping attributes ■ Step 2:Compute the aggregate values locally at each node. Optimization:Can reduce cost of transferring tuples during partitioning by partial aggregation before partitioning For distributive aggregate Can be done as part of run generation Consider the sum aggregation operation: Perform aggregation operation at each node N;on those tuples stored its local disk results in tuples with partial sums at each node. Result of the local aggregation is partitioned on the grouping attributes,and the aggregation performed again at each node Ni to get the final result. Fewer tuples need to be sent to other nodes during partitioning. Database System Concepts-7th Edition 22.21 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 22.21 ©Silberschatz, Korth and Sudarshan th Edition Grouping/Aggregation ▪ Step 1: Partition the relation on the grouping attributes ▪ Step 2: Compute the aggregate values locally at each node. ▪ Optimization: Can reduce cost of transferring tuples during partitioning by partial aggregation before partitioning • For distributive aggregate • Can be done as part of run generation • Consider the sum aggregation operation: ▪ Perform aggregation operation at each node Ni on those tuples stored its local disk • results in tuples with partial sums at each node. ▪ Result of the local aggregation is partitioned on the grouping attributes, and the aggregation performed again at each node Ni to get the final result. • Fewer tuples need to be sent to other nodes during partitioning