Range Partitioning

• To avoid redistribution skew replace hash partitioning with range partitioning.
• Each processor is allocated a sub-range of join attribute values
• Exact partitioning is difficult but approximate partitioning using sampling is relatively simple.
• The algorithm should try and balance the build relation since an imbalance in the number of building tuples is much worse than an imbalance in the number of probing tuples. This is because the imbalance in the number of building tuples per site gives rise to extra buckets in the local subjoins, increasing the number of I/Os significantly.