包含比较运算的连接查询

《ACM Transactions on Database Systems》：Conjunctive Queries with Comparisons

联接查询中多关系比较处理的研究，提出新算法支持长短比较，并在Spark实现获得十倍性能提升。

　　

摘要

最近，包含跨多个关系的比较谓词的连接查询重新受到了关注，因为它们在OLAP查询、时空数据库以及对关系数据进行机器学习时具有重要意义。标准的技术——谓词下推（predicate pushdown）在这种比较中的效果有限。Willard提出了一种技术，可以处理在连接树中时间线性排列的短比较（时间复杂度为输入大小加上输出大小）。在本文中，我们描述了一种用于评估包含短比较和长比较的连接查询的新算法，并确定了一个可以实现线性时间复杂度的无环条件。我们还在Spark平台上实现了这一新算法，实验结果表明，在各种图形模式和分析查询中，该算法的速度比SparkSQL快一个数量级。