Ranked Enumeration of Join Queries with Projections

Shaleen Deep, Xiao Hu, Paraschos Koutris

Abstract

Join query evaluation with ordering is a fundamental data processing task in relational database management systems. SQL and custom graph query languages such as Cypher offer this functionality by allowing users to specify the order via the ORDER BY clause. In many scenarios, the users also want to see the first $k$ results quickly (expressed by the LIMIT clause), but the value of $k$ is not predetermined as user queries are arriving in an online fashion. Recent work has made considerable progress in identifying optimal algorithms for ranked enumeration of join queries that do not contain any projections. In this paper, we initiate the study of the problem of enumerating results in ranked order for queries with projections. Our main result shows that for any acyclic query, it is possible to obtain a near-linear (in the size of the database) delay algorithm after only a linear time preprocessing step for two important ranking functions: sum and lexicographic ordering. For a practical subset of acyclic queries known as star queries, we show an even stronger result that allows a user to obtain a smooth tradeoff between faster answering time guarantees using more preprocessing time. Our results are also extensible to queries containing cycles and unions. We also perform a comprehensive experimental evaluation to demonstrate that our algorithms, which are simple to implement, improve up to three orders of magnitude in the running time over state-of-the-art algorithms implemented within open-source RDBMS and specialized graph databases.

Introduction: The Challenge of Projections in Ranked Joins

In modern data analytics, the ability to retrieve the "best" results first is critical. SQL queries typically use the ORDER BY and LIMIT k clauses to facilitate this. However, real-world queries frequently involve projections—using the DISTINCT keyword or selecting only a specific subset of columns.

Standard Database Management Systems (RDBMS) typically handle these "join-project" queries through a rigid three-step pipeline:

  1. Materialization: Compute the full join result.
  2. Deduplication: Apply the projection to remove duplicate rows.
  3. Sorting: Sort the final deduplicated results based on the ranking function.

The primary bottleneck is the first step. The full intermediate join result can be orders of magnitude larger than the final projected output. For example, if two authors have co-authored 1,000 papers, a join query for unique "co-author pairs" might generate 1,000 intermediate rows just to produce a single unique pair of names. If a user only requires the top 100 pairs, materializing millions of intermediate rows is a massive waste of computational resources and memory. This research addresses the challenge of generating these results directly in ranked order with minimal delay between each result, bypassing the materialization bottleneck.

Methodology: Multiway Joins and Join Trees

The proposed solution shifts away from traditional binary join plans toward multiway join plans centered around join trees.

A join tree representation for an acyclic query, illustrating nodes and attribute anchors.

Acyclic Queries and Near-Linear Delay

For any acyclic query, the authors developed an algorithm that provides near-linear delay. The process begins with a linear-time preprocessing step (utilizing the Yannakakis algorithm) to prune "dangling" tuples that cannot contribute to any join result. Following this, priority queues are strategically embedded within the join tree.

Strategic placement of priority queues (PQ) within the join tree to enable efficient ranked enumeration.

This architecture allows the system to "stream" the top results on-the-fly. By maintaining these priority queues at each node, the algorithm can incrementally reconstruct and deduplicate results without ever materializing the full intermediate join. A specialized "cell" data structure is used to store pointers to children in the join tree, further avoiding redundant computations.

Star Query Tradeoffs

For "star queries"—a common subset of queries where all relations join on a single central attribute—the paper introduces a "smooth tradeoff" algorithm. This allows users to balance preprocessing and query performance: by investing more time and space in preprocessing, they can achieve significantly lower delay during the enumeration phase.

Ranking Functions

The framework specifically supports two vital ranking functions:

  • SUM: Ranking by the sum of attribute weights.
  • LEXICOGRAPHIC: Ranking by a sequence of attributes.

Experimental Insights

The authors evaluated their approach against state-of-the-art systems like MariaDB, PostgreSQL, and Neo4j using a variety of datasets, ranging from DBLP and IMDB to massive graphs like Friendster (1.8 billion tuples) and Memetracker (418 million tuples).

Key Findings

  • Performance Leap: The proposed algorithm, LinDelay, outperformed traditional engines by up to three orders of magnitude. On large-scale datasets where traditional engines often timed out or exhausted memory, LinDelay returned top results in seconds.
  • Memory Efficiency: Because it avoids full materialization, the memory footprint is significantly reduced. In one benchmark, MariaDB required 40GB of RAM, while LinDelay needed only ~3GB.
  • Limit-Awareness: Unlike traditional engines that take roughly the same time regardless of the LIMIT value, LinDelay is truly limit-aware; response times for small $k$ are nearly instantaneous.
  • Lexicographic Advantage: Lexicographic ranking was found to be 2-3x faster than sum-based ranking because its inherent structure allows the algorithm to bypass some priority queue overhead.

Conclusion and Future Directions

This research provides the first efficient algorithms for ranked enumeration of join queries with projections. By moving away from blocking materialization steps, the authors achieve near-linear delay and massive performance gains. While the current work focuses on main-memory settings, future extensions could explore distributed environments, disk-based I/O optimizations, and non-monotone ranking functions.

Summary updated

Abstract

Join query evaluation with ordering is a fundamental data processing task in relational database management systems. SQL and custom graph query languages such as Cypher offer this functionality by allowing users to specify the order via the ORDER BY clause. In many scenarios, the users also want to see the first $k$ results quickly (expressed by the LIMIT clause), but the value of $k$ is not predetermined as user queries are arriving in an online fashion. Recent work has made considerable progress in identifying optimal algorithms for ranked enumeration of join queries that do not contain any projections. In this paper, we initiate the study of the problem of enumerating results in ranked order for queries with projections. Our main result shows that for any acyclic query, it is possible to obtain a near-linear (in the size of the database) delay algorithm after only a linear time preprocessing step for two important ranking functions: sum and lexicographic ordering. For a practical subset of acyclic queries known as star queries, we show an even stronger result that allows a user to obtain a smooth tradeoff between faster answering time guarantees using more preprocessing time. Our results are also extensible to queries containing cycles and unions. We also perform a comprehensive experimental evaluation to demonstrate that our algorithms, which are simple to implement, improve up to three orders of magnitude in the running time over state-of-the-art algorithms implemented within open-source RDBMS and specialized graph databases.
BibTeX
@article{deep2022ranked,
  author = {Shaleen Deep and Xiao Hu and Paraschos Koutris},
  title = {{Ranked Enumeration of Join Queries with Projections}},
  journal = {Proc. VLDB Endow.},
  year = {2022},
  url = {https://openreview.net/forum?id=EBtFYfCmh1},
}
Figure