数据库的查询执行计划中的集合操作优化技术

描述
集合操作是SQL查询中用于合并多个结果集的重要操作，主要包括UNION、UNION ALL、INTERSECT和EXCEPT（或MINUS）。数据库优化器需要为这些操作选择高效的执行策略，包括消除冗余操作、选择正确的算法（如排序合并、哈希）以及处理数据分布特性。集合操作优化直接影响复杂查询的性能，特别是在数据仓库和报表系统中。

解题过程

1. 集合操作的基本类型与语义分析

• UNION ALL：简单合并两个结果集，保留所有重复行，成本最低
• UNION：合并后去除重复行，需要额外的去重操作
• INTERSECT：返回两个结果集的交集（共同存在的行）
• EXCEPT：返回第一个结果集存在而第二个结果集中不存在的行

优化器首先分析语义需求，例如UNION ALL不需要去重，可直接采用流式合并，而其他操作需要考虑去重算法选择。

2. 集合操作的算法选择优化

• 排序合并算法：

  • 步骤1：对两个输入结果集分别排序
  • 步骤2：并行扫描两个有序集合，根据操作类型合并：
    • UNION：类似归并排序的去重合并
    • INTERSECT：只输出两个集合中都存在的键
    • EXCEPT：输出第一个集合独有的键
  • 适用场景：结果集已有序或需要有序输出时

• 哈希算法：

  • 步骤1：对第二个结果集构建哈希表
  • 步骤2：扫描第一个结果集，探测哈希表：
    • UNION：用哈希表记录已出现行，避免重复
    • INTERSECT：只输出在哈希表中存在的行
    • EXCEPT：输出在哈希表中不存在的行
  • 适用场景：内存充足且无排序要求时

3. 查询重写优化

• 谓词下推优化：将WHERE条件尽可能下推到各个子查询中，减少中间结果集大小

  • 示例：(SELECT ... WHERE condition1) UNION (SELECT ... WHERE condition2)
  • 优化：将公共条件提取到外层，减少重复计算

• 集合操作消除：

  • 当检测到子查询结果集互斥时，UNION可转为UNION ALL
  • 当INTERSECT操作的两个查询条件覆盖同一主键时，可简化为等值连接

4. 执行计划中的具体优化技术

• 早期去重：对UNION操作，先在各个子查询中去重，再合并，减少最终去重数据量
• 并行执行：将不同子查询分配到多个CPU核心并行执行，最后合并结果
• 索引利用：如果子查询的排序列有索引，可直接利用有序索引避免排序操作
• 物化策略选择：根据数据量决定是否物化中间结果，小结果集优先使用内存哈希表

5. 统计信息与代价估算

• 优化器收集各子查询的基数（行数）、数据分布统计
• 计算不同算法的代价：
  • 排序合并代价：子查询排序成本 + 合并成本
  • 哈希算法代价：建哈希表成本 + 探测成本
• 考虑内存使用：哈希算法需要足够内存，否则可能触发磁盘溢出

6. 高级优化技巧

• 部分结果集优化：对于LIMIT查询，优先执行可能产生结果的分支
• 集合操作交换律利用：重新排列UNION顺序，将高选择性子查询前置
• 位图索引优化：对低基数字段使用位图操作加速INTERSECT/EXCEPT

通过综合运用这些优化技术，数据库能够为集合操作生成高效的执行计划，显著提升复杂查询性能。实际优化效果取决于统计信息准确性、数据分布特征和系统资源状况。