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