分层回溯用于数据库的查询优化

摘要

数据库系统商用的巨大成功部分归功于成熟的查询优化技术.数据库查询优化器的核心组件是它的搜索策略或枚举算法.本文以回溯法为基础,提出了分层回溯解决查询优化问题的算法.分层回溯法在优化简单的查询时,可以提供"最优"的方案;而对于一些复杂的应用环境,它在枚举算法的高复杂性和算法产生方案的质量之间取一个权衡点,以产生"次优"的优化结果来换取算法的执行效率,大大节省了运行环境的资源.