基于均衡割的无叉积分区连接算法

贾连印^1,2，章永彬²，李孟娟³，丁家满²，游进国²，陈玮²

1. 昆明理工大学云南省计算机技术应用重点实验室2. 昆明理工大学信息工程与自动化学院3. 云南师范大学图书馆

摘 要：连接序问题是数据库查询优化中最重要且最具挑战性的问题.传统的动态规划算法通常具有指数级复杂度.基于图形分割的相关理论,提出均衡割分区算法(BCP),通过均衡割将查询图分割成大小相对均衡的分区,避免一次性处理所有连接的关系.BCP算法分区不会产生叉积,并且可以轻易地集成进任何查询优化器中.在Postgre SQL上实现了该算法,并和Postgre SQL现有的分区算法——迭代动态规划算法(IDP)进行对比.实验结果表明:对25个关系以内的随机连接查询,BCP不仅在平均效率上优于IDP算法,而且对分区大小变化也有更好的适应性.

关键词：查询优化;连接序;均衡割;分区动态规划;叉积;