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

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