Submodularity of Distributed Join Computation.

Area of Science:

• Computer Science
• Database Systems
• Distributed Computing

Background:

• Distributed equi-join computations often suffer from load imbalance due to join-attribute skew.
• Existing methods for skew mitigation involve fine-grained partitioning, which can increase input duplication and computational cost.
• The tradeoff between load expectation and variance in random load assignment strategies requires careful optimization.

Purpose of the Study:

• To develop a theoretically sound and practically effective method for optimizing distributed equi-join computations under join-attribute skew.
• To formally analyze the problem of minimizing load variance subject to load expectation constraints.
• To extend existing optimality guarantees to self-joins and more general load functions.

Main Methods:

• Formulated the load variance minimization problem as a monotone submodular maximization problem with Knapsack constraints.
• Applied provably near-optimal greedy algorithms to solve the formulated optimization problem.
• Validated the theoretical findings through experimental evaluation, comparing performance against deterministic load assignment.

Main Results:

• Demonstrated that minimizing load variance subject to expectation constraints is a solvable submodular maximization problem admitting near-optimal greedy solutions.
• Extended formal optimality guarantees to self-joins and generalized load functions (weighted sum of input/output).
• Experimental results confirmed that the theoretical approach yields effective algorithms for minimizing running time, even in deterministic scenarios.

Conclusions:

• The proposed greedy approach provides a provably near-optimal solution for distributed equi-join optimization under skew.
• The method is robust, applicable to self-joins and various load functions, and effective in practice.
• This work offers a significant advancement in efficiently handling skewed data in distributed database systems.