Ranked Enumeration of Join Queries with Projections
Ranked Enumeration of Join Queries with Projections
复制标题
DOI：
10.14778/3510397.3510401
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Shaleen Deep;Xiao Hu;Paraschos Koutris
中科院分区：
文献类型：
--
作者：
Shaleen Deep;Xiao Hu;Paraschos Koutris
带有排序的连接查询评估是关系数据库管理系统中的一项基本数据处理任务。SQL以及诸如Cypher之类的自定义图查询语言通过允许用户经由ORDER BY子句指定顺序来提供此功能。在许多场景中，用户还希望快速看到前k个结果（由LIMIT子句表示），但是由于用户查询是以在线方式到达的，k的值并不是预先确定的。近期的工作在为不包含任何投影的连接查询的排序枚举确定最优算法方面取得了相当大的进展。在本文中，我们启动了对带有投影的查询按排序顺序枚举结果的问题的研究。我们的主要结果表明，对于任何无环查询，对于两个重要的排序函数：求和与字典序排序，在仅经过一个线性时间的预处理步骤之后，就有可能获得一个近线性（相对于数据库大小）的延迟算法。对于被称为星型查询的无环查询的一个实际子集，我们展示了一个更强的结果，它允许用户在使用更多预处理时间以获得更快的回答时间保证之间进行平滑的权衡。我们的结果也可扩展到包含循环和并集的查询。我们还进行了全面的实验评估，以证明我们易于实现的算法在运行时间上比开源关系数据库管理系统和专用图数据库中实现的最先进算法提高了多达三个数量级。
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.