To understand why modern relational query optimization works, we must first look at queries geometrically. A relational join can be modeled as a hypergraph where the attributes are vertices and the relations are hyperedges. Traditional database systems evaluate these queries using binary join trees (or join-project plans). However, as Hung Q. Ngo et al. demonstrate in Worst-case Optimal Join Algorithms., traditional plans can be asymptotically slower than theoretical optimal bounds because they often generate massive, unnecessary intermediate tables.
The maximum possible size of a join query's output is fundamentally bounded by the structural properties of its hypergraph. In Size Bounds and Query Plans for Relational Joins, Albert Atserias et al. established that the fractional edge cover number of a query's hypergraph precisely characterizes its worst-case output size (known as the AGM bound). This insight led to the development of worst-case optimal join (WCOJ) algorithms, which process multiple relations simultaneously variable-by-variable, ensuring that the execution time never exceeds this worst-case output bound.
The Zoo of Structural Widths
For complex queries, evaluating the global fractional edge cover is not enough. Instead, database theorists decompose the query hypergraph into a tree structure—a process known as tree decomposition—where variables are grouped into nodes called "bags." The computational difficulty of evaluating the query then depends on the "width" of these bags. This has led to a variety of structural width measures designed to identify "islands of tractability":
- Generalized Hypertree Width ($ghtw$): Measures complexity by the minimum number of hyperedges needed to completely cover the variables in each bag.
- Fractional Hypertree Width ($fhtw$): Generalizes $ghtw$ by allowing fractional combinations of edges to cover each bag, providing a tighter bound on the resources required.
- Submodular Width ($subw$): A broader metric based on submodular functions, originally designed to bound the complexity of Boolean decision queries.
The Convergence of Complexity Measures
While having multiple width metrics allows for precise theoretical categorization, it raises a practical concern: computing these advanced widths can be highly complex. However, recent research reveals that under realistic structural constraints, these seemingly distinct measures converge or become functionally equivalent.
This convergence happens because structural constraints collapse the mathematical gaps between different covering methods. For instance, in Semantic Width Revisited (Extended Abstract), Georg Gottlob et al. proved that when a query's underlying hypergraph has a bounded degree, its fractional hypertree width and generalized hypertree width converge to within a constant factor of each other. When the structural constraints are even tighter, the metrics become identical. In Forbidden Substructures for Tractable Conjunctive Query Answering with Degree 2, Matthias Lanzinger demonstrated that for degree-2 hypergraphs, generalized hypertree width and submodular width are functionally equivalent.
Crucially, this convergence is not just a theoretical artifact but a reflection of real-world data structures. In an empirical analysis conducted for The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions, Georg Gottlob et al. discovered that hypertree width and generalized hypertree width are exactly identical for the vast majority of real-world constraint satisfaction and database query instances. This means that the additional computational overhead of calculating generalized widths offers diminishing returns in practice, as standard hypertree width already captures the true structural complexity.
Extending to Functional Aggregations
Modern databases do more than just join tables; they compute complex aggregations, counts, and execute machine learning workloads. To unify these tasks, Mahmoud Abo Khamis et al. introduced the Functional Aggregate Query (FAQ) framework in Juggling Functions Inside a Database. The FAQ framework unifies relational joins, matrix multiplication, and probabilistic graphical model inference under a single algebraic umbrella using the InsideOut algorithm.
However, standard join width measures fail to provide tight bounds for non-Boolean aggregate queries. To address this, Mahmoud Abo Khamis et al. developed specialized width parameters in On Functional Aggregate Queries with Additive Inequalities and Functional Aggregate Queries with Additive Inequalities. By extending submodular width to general semirings, the authors established a tighter hierarchy showing that many aggregate queries are asymptotically easier to compute than standard structural measures predict. This allows complex machine learning models (like k-means and SVMs) to be trained over relational databases faster than the time it would take to compute the underlying data join.
For acyclic join-aggregate queries, Xiao Hu 0005 et al. introduced a novel structural parameter called free-connex fractional hypertree width ($fn\text{-}fhtw$) in Output-Optimal Algorithms for Join-Aggregate Queries. By integrating this parameter with an adaptive partitioning strategy, the authors achieved true output-optimal complexity, providing the first polynomial improvement over existing algorithms in 40 years.
From Theory to Physical Execution
While these structural width measures offer elegant asymptotic guarantees, translating them into physical database performance requires bridging the gap between theoretical bounds and constant-factor execution costs.
In Old Techniques for New Join Algorithms: A Case Study in RDF Processing, Christopher R. Aberger et al. demonstrated that while WCOJ algorithms offer a theoretical breakthrough for complex cyclic queries, they require classic database optimizations—such as index layout tuning, selection pushdown, and pipelining—to be practical for real-world workloads within engines like EmptyHeaded.
Furthermore, structural complexity directly dictates fine-grained data access operations. In Tight Fine-Grained Bounds for Direct Access on Join Queries, Nofar Carmeli et al. showed that the preprocessing time required to achieve fast direct access to specific query answers is governed by an "incompatibility number," which is intrinsically linked to the fractional hypertree width of the query. As highlighted in Optimal Joins using Compact Data Structures by Gonzalo Navarro et al., a key open frontier remains fully integrating these structure-specific optimizations with compact data structures to simultaneously optimize both query execution speed and storage footprint.
Key Foundational Work
Size bounds and query plans for relational joins (2008) — contributed 1 concept elements to this direction.
Old Techniques for New Join Algorithms: A Case Study in RDF Processing (2016) — contributed 1 concept elements to this direction.