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

• 作者: 丁家满 李孟娟 游进国 章永彬 贾连印 陈玮
• 来源期刊: 昆明理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 查询优化 连接序 均衡割 分区动态规划 叉积
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 机械、电子信息与自动控制
• 页码范围: 52-56
• 页数: 5页
• 分类号: TP311
• 语种: 中文
• DOI: 10.16112/j.cnki.53-1223/n.2016.01.009

摘要

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