数据库查询优化中的半连接物化与反半连接优化技术

我们来讲解“数据库查询优化中的半连接物化与反半连接优化技术”。

1. 问题描述与背景
   在数据库查询中，EXISTS 和 NOT EXISTS 子查询是非常常见的模式。它们通常用于检查主查询（外查询）中的某一行，是否在子查询（内查询）的结果中存在（或不存在）。这类查询在逻辑上定义了一个“半连接”（Semi-Join）或“反半连接”（Anti-Semi-Join）关系。

   • 半连接（Semi-Join）：对于左表（外查询表）的每一行，只要在右表（子查询结果）中找到至少一个匹配行，就返回左表的这一行。注意：即使右表有多个匹配行，左表的这一行也只返回一次。EXISTS 子查询通常实现为半连接。
   • 反半连接（Anti-Semi-Join）：与半连接相反，对于左表的每一行，只有在右表中找不到任何匹配行时，才返回左表的这一行。NOT EXISTS 子查询通常实现为反半连接。
     数据库优化器的核心任务之一，就是将这类相关性或非相关性的子查询，高效地转换为等价的连接操作，并为其选择最优的执行算法。“物化”（Materialization）是其中一种关键的执行策略。

2. 基础概念：子查询的“物化”
   “物化”是指将子查询的结果集预先计算出来，并存储在一个临时数据结构（通常是内存中的哈希表或磁盘上的临时表）中。这个临时存储的结果被称为“物化表”。物化的主要优点是，对于外查询的每一行，我们不需要反复、重新执行整个子查询，而只需在物化表中进行高效的查找（如哈希查找）。

3. 半连接物化优化技术详解
   当我们遇到一个 EXISTS 子查询时，例如：

   SELECT * FROM orders o
   WHERE EXISTS (
       SELECT 1 FROM customers c
       WHERE c.id = o.customer_id AND c.country = 'USA'
   );
   

   优化器可能会采用“半连接物化”策略。其执行步骤如下：

   • 步骤1：子查询执行与物化：首先，独立地执行子查询 SELECT customer_id FROM customers WHERE country = 'USA'。注意，这里只选择连接列customer_id，而不需要所有列，以减小物化表的大小。将满足条件的customer_id去重后，构建一个哈希表（或在内存不足时使用磁盘临时表）。
   • 步骤2：探测连接：然后，顺序扫描orders表（外查询表）的每一行。对于每一行，提取其customer_id，并在上一步建立的物化哈希表中进行查找。
   • 步骤3：决定输出：如果找到（哈希表命中），说明该订单的客户来自美国，满足EXISTS条件，则输出orders表的这一行。一旦找到，就停止对该行在哈希表中的进一步查找（这正是“半”的含义，不关心有多少个匹配，只关心是否存在）。如果未找到，则丢弃该行。

4. 反半连接物化优化技术详解
   对应地，对于一个 NOT EXISTS 子查询，例如：

   SELECT * FROM products p
   WHERE NOT EXISTS (
       SELECT 1 FROM order_items oi
       WHERE oi.product_id = p.id
   );
   

   优化器可能会采用“反半连接物化”策略。其执行步骤与半连接物化类似，但判断逻辑相反：

   • 步骤1：子查询执行与物化：执行子查询 SELECT DISTINCT product_id FROM order_items，将所有被订购过的产品ID去重后物化到一个哈希表中。
   • 步骤2：探测连接：顺序扫描products表的每一行，提取id，并在物化哈希表中查找。
   • 步骤3：决定输出：如果未找到（哈希表未命中），说明该产品从未被订购过，满足NOT EXISTS条件，则输出products表的这一行。如果找到，则丢弃该行。

5. 技术优势与适用场景

   • 优势：
     1. 避免重复计算：子查询只执行一次并物化，避免了对外查询的每一行都重新执行子查询（即“相关执行”），这对复杂或数据量大的子查询尤其高效。
     2. 利用高效数据结构：哈希表提供了接近O(1)的查找速度，使得探测阶段非常快。
     3. 自然去重：在构建物化表时，通常会对子查询结果去重，这恰好符合EXISTS/NOT EXISTS的语义（不关心具体匹配次数），减少了数据量。
   • 适用场景：
     • 子查询结果集相对较小（能装入内存最佳）。
     • 外查询结果集较大。
     • 子查询本身是非相关的，或通过优化（如上述例子，子查询的筛选条件country='USA'是独立的）可以部分或全部先于连接执行。

6. 优化器的决策与权衡
   优化器在选择是否使用物化策略时，会进行代价估算，并与其他可能的执行方式比较，例如：

   • 直接相关执行：对于外查询的每一行，都执行一次子查询。在子查询很小或能利用高效索引时可能更优。
   • 转换为常规连接：将EXISTS子查询改写为INNER JOIN，NOT EXISTS改写为LEFT JOIN ... WHERE ... IS NULL，然后由优化器选择嵌套循环、哈希连接或排序合并连接等算法。物化本质上是哈希连接的一种特化和优化形式，专为半/反连接语义设计。
   • 决策因素：包括子查询结果集的大小、可用内存、连接列上是否有索引、数据分布等。统计信息的准确性在这里至关重要。

总结：半连接物化与反半连接物化是优化器处理EXISTS和NOT EXISTS子查询的核心技术之一。其核心思想是“计算一次，多次查找”，通过将内查询结果预先计算并存储在高效的数据结构中，来大幅加速对外查询行的条件判断过程，是子查询去关联化和高效执行的重要手段。