Data partitions are assigned to reducer tasks using a cost-based and workload balancing approach. At least one of the initial data partitions remains unassigned in an unassigned partitions pool. Each reducer while working on its assigned partitions makes dynamic run-time decisions as to whether to: reassign a partition to another reducer, accept a partition from another reducer, select a partition from the unassigned partitions pool, and/or reassign a partition back to the unassigned partitions pool.