Worst-case Optimal Binary Join Algorithms under General 𝓁p Constraints

Sai Vikneshwar Mani Jayaraman, Corey Ropell, Atri RudraarXiv 2021 · arXiv

Abstract

Worst-case optimal join (WCOJ) algorithms have traditionally relied on input relation sizes or degree bounds. However, these statistics often fail to capture the skewness of real-world power-law graphs. This paper introduces a novel WCOJ algorithm for binary relations that utilizes general $\ell_p$-norm size bounds, specifically for $p \in (1, 2]$. Our algorithm is $p$-agnostic, avoids the significant poly-logarithmic overhead of previous state-of-the-art methods like PANDA, and resolves open questions regarding the feasibility of reaching the polymatroid bound without such factors. Empirical results on SNAP datasets demonstrate that $\ell_2$-norm bounds are significantly tighter than traditional size-based (AGM) or degree-based bounds.

1. Introduction

Worst-case optimal join (WCOJ) algorithms represent a cornerstone of modern database theory, ensuring that join queries are processed in time proportional to the maximum possible output size. To date, research has focused on two primary statistics: relation size ($p=1$) and maximum degree ($p=\infty$). While effective for uniform data, these metrics struggle with the heavy-tailed distributions characteristic of real-world networks. This paper bridges this gap by exploring $\ell_p$-norm constraints for $p \in (1, 2]$, offering a more nuanced approach to bounding join sizes in skewed datasets.

2. Problem Statement

The primary challenge in WCOJ research is twofold. First, traditional bounds like the Atserias-Grohe-Marx (AGM) bound do not account for the "heavy hitters" in power-law graphs, leading to loose estimates. Second, existing algorithms that attempt to incorporate degree bounds, such as PANDA, suffer from a "doubly-exponential" poly-logarithmic overhead. This overhead makes them theoretically interesting but practically unviable for large-scale systems. The goal is to develop an algorithm that is both worst-case optimal under $\ell_p$ constraints and free from large constant or poly-log factors.

3. Methodology

The proposed solution is a three-tiered, $p$-agnostic algorithmic framework. Being $p$-agnostic means the execution logic does not require knowledge of the specific $\ell_p$ norm; this information is only used for theoretical performance guarantees.

  • Prefix-Join: A variation of Leapfrog-TrieJoin (LFTJ) optimized for Directed Acyclic Graphs (DAGs). It processes vertices in topological order, efficiently intersecting incoming and outgoing relations.
  • Acyclic-Join: To handle cyclic queries (e.g., triangle joins), the algorithm multiplexes Prefix-Join across all possible spanning acyclic subgraphs, terminating as soon as the first subgraph completes.
  • Forward-Join: This component addresses degree skew by "bucketing" tuples based on their degrees in powers of two. Acyclic-Join is then executed on combinations of these buckets.

The theoretical foundation rests on a new Linear Program (LP+) that generalizes standard edge-covering LPs to incorporate $\ell_p$ constraints, providing a tighter theoretical bound on join results.

4. Experimental Evaluation and Results

The authors evaluated the tightness of the $\ell_2$-norm bounds using several real-world graph datasets from the SNAP collection, including collaboration networks (ca-GrQc, ca-HepTh) and social networks (facebook-combined, soc-Epinions1).

As shown in the table above, the $\ell_2$-norm bound consistently outperforms traditional metrics. For triangle queries, the $\ell_2$ bound was between 2.75x and 18.19x tighter than the AGM bound. Furthermore, it showed up to a 6.63x improvement over bounds relying solely on maximum degrees. These results validate the intuition that $\ell_p$ norms, particularly $\ell_2$, are better suited for power-law distributions where the exponent $\alpha \in (2, 3)$.

5. Key Insights

  • Power-Law Alignment: For graphs with a power-law exponent $\alpha$, the optimal bound is typically achieved at $p = \alpha - 1$.
  • Algorithmic Simplicity: By replacing complex entropy-based inequalities with a bucketing and acyclic decomposition strategy, the algorithm eliminates the poly-log data factor that hindered previous work.
  • Robustness: The $p$-agnostic nature allows database engines to leverage any available $\ell_p$ statistics without modifying the core execution engine.

6. Conclusion and Future Work

This work provides a significant step toward practical WCOJ algorithms beyond simple size bounds. By resolving the poly-log overhead issue for binary relations, it opens the door for more efficient graph processing. Future research will focus on extending these results to general hypergraphs (arity > 2) and relaxing the girth requirements for $p > 2$. Additionally, engineering these algorithms to compete with high-performance commercial join engines remains a priority.

Summary updated

Abstract

Worst-case optimal join algorithms have so far been studied in two broad contexts -- $(1)$ when we are given input relation sizes [Atserias et al., FOCS 2008, Ngo et al., PODS 2012, Velduizhen et. al, ICDT 2014] $(2)$ when in addition to size, we are given a degree bound on the relation [Abo Khamis et al., PODS 2017]. To the best of our knowledge, this problem has not been studied beyond these two statistics even for the case when input relations have arity (at most) two. In this paper, we present a worst-case optimal join algorithm when are given $\ell_{p}$-norm size bounds on input relations of arity at most two for $p \in (1, 2]$. ($p=1$ corresponds to relation size bounds and $p=\infty$ corresponds to the degree bounds.) The worst-case optimality holds any fixed $p \in (2, \infty)$ as well (as long as the join query graph has large enough girth). Our algorithm is {\em simple}, does not depend on $p$ (or) the $\ell_{p}$-norm bounds and avoids the (large) poly-log factor associated with the best known algorithm PANDA [Abo Khamis et al., PODS 2017] for the size and degree bounds setting of the problem. In this process, we (partially) resolve two open question from [Ngo, 2018 Gems of PODS]. We believe our algorithm has the {\em potential} to pave the way for practical worst-case optimal join algorithms beyond the case of size bounds.
BibTeX
@misc{jayaraman2021worst,
  author = {Sai Vikneshwar Mani Jayaraman and Corey Ropell and Atri Rudra},
  title = {{Worst-case Optimal Binary Join Algorithms under General 𝓁p Constraints}},
  year = {2021},
  eprint = {2112.01003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.01003},
}
Figure