Fast Join Project Query Evaluation using Matrix Multiplication
Fast Join Project Query Evaluation using Matrix Multiplication
复制标题
DOI：
10.1145/3318464.3380607
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Shaleen Deep;Xiao Hu;Paraschos Koutris
中科院分区：
文献类型：
--
作者：
Shaleen Deep;Xiao Hu;Paraschos Koutris
在过去的几年中，人们花了很多精力开发连接算法，以实现关系数据库上连接查询的最坏情况最优性。为此，数据库社区在开发高效算法方面取得了相当大的成功，这些算法可以实现全连接查询（即没有投影的连接）的最坏情况最佳运行时。但是，除了在查询执行计划中下推投影运算符的一些简单技术之外，对于使用投影的连接求值知之甚少。这样的查询在实体匹配、图分析和压缩图搜索中有大量的应用。在本文中，我们研究了一类带投影的连接查询如何使用最坏情况最优算法和矩阵乘法来更快地求值。至关重要的是，我们的算法是由最终结果的输出大小参数化的，允许选择最佳的执行策略。我们将我们的算法作为子程序实现，并将性能与最先进的技术进行比较，以显示它们可以提高多达50倍。更重要的是，我们的实验表明，矩阵乘法是一个有用的操作，可以帮助加快连接处理，因为高度优化的开源库也具有高度并行性。
In the last few years, much effort has been devoted to developing join algorithms to achieve worst-case optimality for join queries over relational databases. Towards this end, the database community has had considerable success in developing efficient algorithms that achieve worst-case optimal runtime for full join queries, i.e., joins without projections. However, not much is known about join evaluation with projections beyond some simple techniques of pushing down the projection operator in the query execution plan. Such queries have a large number of applications in entity matching, graph analytics and searching over compressed graphs. In this paper, we study how a class of join queries with projections can be evaluated faster using worst-case optimal algorithms together with matrix multiplication. Crucially, our algorithms are parameterized by the output size of the final result, allowing for choosing the best execution strategy. We implement our algorithms as a subroutine and compare the performance with state-of-the-art techniques to show they can be improved upon by as much as 50x. More importantly, our experiments indicate that matrix multiplication is a useful operation that can help speed up join processing owing to highly optimized open source libraries that are also highly parallelizable.