Ranked Enumeration of Join Queries with Projections

Download PDF

Abstract

Join query evaluation with ordering is a fundamental data processing task in relational database management systems. \textsf{SQL} and custom graph query languages such as \textsf{Cypher} offer this functionality by allowing users to specify the order via the \sqlhighlight{ORDER BY} clause. In many scenarios, the users also want to see the first $k$ results quickly (expressed by the \sqlhighlight{LIMIT} clause), but the value of $k$ is not predetermined \reva{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 \emph{not} contain any projections. In this paper, we initiate the study of the problem of enumerating results in ranked order for queries {\em 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.