Adaptive Recursive Query Optimization

性能关键的工业应用程序，包括大规模程序、网络和分布式系统分析，越来越依赖于递归查询进行数据分析。然而，传统的基于关系代数的查询优化技术在递归查询处理方面不具有良好的可扩展性，因为查询评估具有迭代性质，在单个查询执行过程中，关系的基数可能会不可预测地改变。为了避免容易出错的基数估计，自适应查询处理技术使用运行时信息来通知查询优化，但这些系统并不针对递归查询处理的特定需求进行优化。在本文中，我们介绍了一种创新技术——自适应元编程，它将递归查询优化和代码生成从编译时转移到运行时，利用有原则的元编程实现动态优化和重新优化，使得在查询执行开始前和之后都可以进行。我们提出了一种定制的连接顺序优化方法，适用于查询编译和执行的多个阶段。通过一个定制的Datalog引擎Carac，我们评估了自适应元编程的优化潜力，并展示了未优化的递归查询执行时间可以提高三个数量级，手动优化的查询可以提高6倍。

优化递归查询的运行效率，避免传统关系代数基于估计基数的查询优化技术在递归查询处理中的可扩展性问题。

采用自适应元编程技术，将递归查询的优化和代码生成从编译时转移到运行时，通过动态优化和重新优化来提高查询效率。

论文提出了一种适用于多个阶段的自定义连接顺序优化，通过Carac，一个自定义Datalog引擎，证明了自适应元编程的优化潜力，未经优化的递归查询执行时间可以提高三个数量级，手动优化的查询可以提高6倍。

与本论文相关的研究包括：《自适应查询处理：动态优化数据库系统的性能》、《递归查询处理的最新进展》、《递归查询优化：从理论到实践》等。