数据库查询优化中的表达式预处理优化原理解析（进阶篇）
字数 4574 2025-12-07 15:42:54

数据库查询优化中的表达式预处理优化原理解析（进阶篇）

在之前的“表达式预处理优化原理解析”基础篇中，我们讨论了常量折叠、常量传播、公共子表达式消除等基本技术。本篇（进阶篇）将深入探讨在更复杂场景下的表达式预处理高级优化技术，包括复杂表达式规范化、类型推导与提升、表达式等价性证明、以及非确定性表达式的特殊处理。这些技术是现代化查询优化器在逻辑优化和物理优化之间进行精细转换的关键。

一、 复杂表达式规范化（Complex Expression Canonicalization）

问题描述： 用户编写的SQL表达式在语法上可能千变万化，但语义上可能等价。例如，a+0 和 a 是等价的，a*1 和 a 也是等价的。优化器需要将这些语法不同但语义相同的表达式转化为一种标准形式，以便于后续的简化、比较和优化规则匹配。

解题过程与原理：

  1. 建立规范化规则库：

    • 优化器内置一套数学和逻辑恒等规则。例如：
      • 加法/乘法恒等元：expr + 0 -> expr， expr * 1 -> expr。
      • 加法/乘法零元：expr * 0 -> 0 (但需注意expr是否可能为NULL，以及浮点数中的-0.0等情况)。
      • 双重否定：- (- expr) -> expr， NOT (NOT condition) -> condition。
      • 分配律与结合律应用：有时将表达式转换为更“规范”的形式。例如，将(a+b)+c规范为a+b+c（隐式结合）；或将a*b + a*c转换为a*(b+c)，这取决于哪种形式更有利于后续优化（如谓词下推）。
    • 这些规则被编码为模式匹配和替换规则。

  2. 递归应用与保证终止：

    • 规范化过程以自底向上的方式遍历表达式树。对于一个表达式节点，先递归规范化其所有子表达式，然后再尝试对当前节点应用规范化规则。
    • 必须确保规则应用不会导致无限循环。例如，规则x+0 -> x和x -> x+0如果同时存在就会导致循环。因此，规范化规则是单向的，总是导向一个唯一的“标准形式”。

  3. 实例解析：

    • 原始查询：SELECT * FROM t WHERE (salary * 1.0) > 100000 AND NOT (department_id != 10)。
    • 规范化过程：
      1. salary * 1.0 被规范化规则 expr * 1 -> expr 化简为 salary。
      2. NOT (department_id != 10) 首先处理内部条件：department_id != 10 是一个有效的比较，暂时不变。然后应用 NOT (a != b) -> a = b 规则，转换为 department_id = 10。
    • 规范化后表达式：WHERE salary > 100000 AND department_id = 10。这个形式更简洁，也更容易与索引匹配（例如，department_id上的索引可以高效使用）。

二、 类型推导与提升（Type Inference and Promotion）

问题描述： SQL是强类型语言，但支持隐式类型转换。表达式中的操作数和操作符需要类型兼容。优化器需要在预处理阶段确定每个子表达式的最终数据类型，并可能插入隐式类型转换（类型提升），以确保计算的正确性和效率。

解题过程与原理：

  1. 确定表达式类型：

    • 自底向上遍历表达式树。叶子节点（列引用、常量）的类型是已知的（从元数据或常量值推断）。
    • 对于操作符节点（如+, =, CASE），根据其子表达式的类型和SQL标准中关于操作符结果类型的定义，推导出该节点的结果类型。
    • 例如，INTEGER + DECIMAL(10,2)的结果类型通常为DECIMAL，精度和小数位数有特定规则。

  2. 处理隐式类型转换：

    • 当操作符期望的操作数类型与实际子表达式类型不匹配，但存在可转换关系时，优化器会决定是否及在何处插入一个隐式的CAST操作。
    • 关键决策：将哪个操作数转换为另一个操作数的类型。通常遵循“类型提升”规则，将“较窄”的类型转换为“较宽”的类型，以避免精度损失。例如，在比较int_column = float_literal时，通常将int_column提升为FLOAT进行比较。
    • 优化机会：有时，优化器可以“聪明地”决定转换方向。例如，对于谓词WHERE int_column = CAST('123' AS INTEGER)，优化器可能会尝试将常量提前计算（常量折叠），并生成WHERE int_column = 123，从而可能利用int_column上的索引。如果将int_column转换为字符串，则无法使用索引。

  3. 实例解析：

    • 原始查询：SELECT * FROM orders WHERE order_date = '2023-10-01'。假设order_date列为DATE类型，而'2023-10-01'是字符串字面量。
    • 类型推导与提升：
      1. order_date类型为DATE。
      2. '2023-10-01'是VARCHAR类型。
      3. 等值比较操作符=要求两边类型兼容。根据规则，字符串可以隐式转换为DATE。
      4. 优化器决定将常量转换为列的类型，生成内部表达式：WHERE order_date = CAST('2023-10-01' AS DATE)。
      5. 进一步的优化：常量折叠可以对CAST('2023-10-01' AS DATE)进行求值，得到一个内部的DATE常量。最终谓词可能被优化为WHERE order_date = DATE'2023-10-01'。这个形式对于索引查找是最优的。

三、 表达式等价性证明（Expression Equivalence Proof）

问题描述： 在查询重写、视图合并、谓词推导等高级优化中，优化器需要判断两个表达式是否在逻辑上等价。例如，判断column BETWEEN 10 AND 20是否等价于column >= 10 AND column <= 20。

解题过程与原理：

  1. 基于规范化形式的比较：

    • 最直接的方法是将两个表达式分别进行规范化（如上所述）。如果它们的规范化形式完全相同，则可以认为它们等价。
    • 例如，BETWEEN通常被规范化为一对>=和<=的组合。因此，a BETWEEN x AND y和a >= x AND a <= y在规范化后会变成相同的表达式树，从而证明等价。

  2. 应用已知的等价规则：

    • 优化器维护一组已知的等价规则，用于处理规范化后形式可能不同但依然等价的复杂情况。
    • 示例规则：
      • NOT (A AND B) <-> (NOT A) OR (NOT B) （德摩根定律）
      • A OR (A AND B) <-> A （吸收律）
      • (A = B) AND (B = C) -> 可推导出A = C （传递性，属于谓词传递闭包范畴，但也可用于证明A = C与已知条件集等价）
    • 优化器可以尝试对一个表达式应用这些等价变换，看是否能变形为另一个表达式。

  3. 利用约束信息：

    • 如果表上有约束（如主键、唯一键、CHECK约束），优化器可以利用这些信息证明等价。
    • 实例：假设有CHECK(status IN ('A', 'B', 'C'))约束。那么表达式status = 'A' OR status = 'B' 与 status != 'C' 在当前表的行集范围内是等价的。优化器可以利用这个信息进行重写。

四、 非确定性表达式的特殊处理（Handling Non-Deterministic Expressions）

问题描述： 某些表达式每次求值结果可能不同，如RAND()、CURRENT_TIMESTAMP、NEWID()。它们被称为非确定性（Non-Deterministic）或易变（Volatile）函数。在表达式预处理中，对它们的处理需要格外小心，因为很多优化（如公共子表达式消除、谓词下推）基于表达式在单次查询执行中多次求值结果相同的假设。

解题过程与原理：

  1. 标记与识别：

    • 优化器内部有一个函数属性表，标记每个内置函数是确定性的（Deterministic）还是非确定性的。
    • 用户自定义函数（UDF）通常需要由创建者声明其确定性属性。

  2. 限制优化应用：

    • 公共子表达式消除（CSE）： 对于SELECT RAND(), RAND() FROM t，不能将两个RAND()调用合并为一个，因为它们本应产生两个不同的随机数。优化器必须保留两个独立的调用。
    • 谓词移动/下推： 将包含非确定性函数的谓词下推到更早的执行阶段（如扫描时）可能会改变查询语义。例如，WHERE id > RAND() * 100，如果在连接（JOIN）前对单表求值RAND()，和在对连接结果求值RAND()，由于RAND()值不同，过滤的行数可能不同。高级优化器可能选择不移动这类谓词，或为其生成一个“物化”点（先求值一次，然后复用该值）。
    • 常量折叠： CURRENT_TIMESTAMP在一个SQL语句执行期间通常被认为是常量。优化器可能会在查询开始执行时对其求值一次，然后将该值作为常量传播到所有使用该函数的地方，以保证语句内部时间一致。但不同语句执行时值不同。

  3. 实例解析：

    • 查询：SELECT * FROM logs WHERE log_time > CURRENT_TIMESTAMP - INTERVAL '1' HOUR ORDER BY log_id LIMIT 100;
    • 优化：优化器会识别CURRENT_TIMESTAMP。为了保证WHERE条件中使用的“一小时前”是一个固定时间点（而不是每一行比较时都重新获取时间），优化器会在优化开始时（或查询执行开始时）将其物化为一个常量。假设执行开始时间是2023-10-27 10:00:00，那么整个谓词被转换为log_time > TIMESTAMP '2023-10-27 09:00:00'。这个转换是安全的，并且有利于在log_time列上使用索引进行范围扫描。

总结：
表达式预处理的进阶优化，是将基础的简化、合并、求值技术与类型系统、代数等价、约束信息和函数副作用等知识深度融合的过程。复杂表达式规范化为所有优化建立了统一、简洁的“语言”。类型推导与提升确保了表达式的语义正确性，并为基于类型的优化（如索引选择）铺平道路。表达式等价性证明是连接推导、谓词传递、视图合并等高级重写优化的基石。而对非确定性表达式的特殊处理，则体现了优化器在追求性能的同时，对SQL语义准确性的严格遵循。这些技术共同作用，使得现代数据库查询优化器能够处理极其复杂和多样的用户查询，并生成高效且正确的执行计划。

数据库查询优化中的表达式预处理优化原理解析（进阶篇） 在之前的“表达式预处理优化原理解析”基础篇中，我们讨论了常量折叠、常量传播、公共子表达式消除等基本技术。本篇（进阶篇）将深入探讨在更复杂场景下的表达式预处理高级优化技术，包括 复杂表达式规范化、类型推导与提升、表达式等价性证明、以及非确定性表达式的特殊处理 。这些技术是现代化查询优化器在逻辑优化和物理优化之间进行精细转换的关键。 一、 复杂表达式规范化（Complex Expression Canonicalization） 问题描述 ： 用户编写的SQL表达式在语法上可能千变万化，但语义上可能等价。例如， a+0 和 a 是等价的， a*1 和 a 也是等价的。优化器需要将这些语法不同但语义相同的表达式转化为一种标准形式，以便于后续的简化、比较和优化规则匹配。 解题过程与原理 ： 建立规范化规则库 ： 优化器内置一套数学和逻辑恒等规则。例如： 加法/乘法恒等元 ： expr + 0 -> expr ， expr * 1 -> expr 。 加法/乘法零元 ： expr * 0 -> 0 (但需注意 expr 是否可能为 NULL ，以及浮点数中的-0.0等情况)。 双重否定 ： - (- expr) -> expr ， NOT (NOT condition) -> condition 。 分配律与结合律应用 ：有时将表达式转换为更“规范”的形式。例如，将 (a+b)+c 规范为 a+b+c （隐式结合）；或将 a*b + a*c 转换为 a*(b+c) ，这取决于哪种形式更有利于后续优化（如谓词下推）。 这些规则被编码为模式匹配和替换规则。 递归应用与保证终止 ： 规范化过程以自底向上的方式遍历表达式树。对于一个表达式节点，先递归规范化其所有子表达式，然后再尝试对当前节点应用规范化规则。 必须确保规则应用不会导致无限循环。例如，规则 x+0 -> x 和 x -> x+0 如果同时存在就会导致循环。因此，规范化规则是单向的，总是导向一个唯一的“标准形式”。 实例解析 ： 原始查询 ： SELECT * FROM t WHERE (salary * 1.0) > 100000 AND NOT (department_id != 10) 。 规范化过程 ： salary * 1.0 被规范化规则 expr * 1 -> expr 化简为 salary 。 NOT (department_id != 10) 首先处理内部条件： department_id != 10 是一个有效的比较，暂时不变。然后应用 NOT (a != b) -> a = b 规则，转换为 department_id = 10 。 规范化后表达式 ： WHERE salary > 100000 AND department_id = 10 。这个形式更简洁，也更容易与索引匹配（例如， department_id 上的索引可以高效使用）。 二、 类型推导与提升（Type Inference and Promotion） 问题描述 ： SQL是强类型语言，但支持隐式类型转换。表达式中的操作数和操作符需要类型兼容。优化器需要在预处理阶段确定每个子表达式的最终数据类型，并可能插入隐式类型转换（类型提升），以确保计算的正确性和效率。 解题过程与原理 ： 确定表达式类型 ： 自底向上遍历表达式树。叶子节点（列引用、常量）的类型是已知的（从元数据或常量值推断）。 对于操作符节点（如 + , = , CASE ），根据其子表达式的类型和SQL标准中关于操作符结果类型的定义，推导出该节点的结果类型。 例如， INTEGER + DECIMAL(10,2) 的结果类型通常为 DECIMAL ，精度和小数位数有特定规则。 处理隐式类型转换 ： 当操作符期望的操作数类型与实际子表达式类型不匹配，但存在可转换关系时，优化器会决定是否及在何处插入一个隐式的 CAST 操作。 关键决策 ：将哪个操作数转换为另一个操作数的类型。通常遵循“类型提升”规则，将“较窄”的类型转换为“较宽”的类型，以避免精度损失。例如，在比较 int_column = float_literal 时，通常将 int_column 提升为 FLOAT 进行比较。 优化机会 ：有时，优化器可以“聪明地”决定转换方向。例如，对于谓词 WHERE int_column = CAST('123' AS INTEGER) ，优化器可能会尝试将常量提前计算（常量折叠），并生成 WHERE int_column = 123 ，从而可能利用 int_column 上的索引。如果将 int_column 转换为字符串，则无法使用索引。 实例解析 ： 原始查询 ： SELECT * FROM orders WHERE order_date = '2023-10-01' 。假设 order_date 列为 DATE 类型，而 '2023-10-01' 是字符串字面量。 类型推导与提升 ： order_date 类型为 DATE 。 '2023-10-01' 是 VARCHAR 类型。 等值比较操作符 = 要求两边类型兼容。根据规则，字符串可以隐式转换为 DATE 。 优化器决定将常量转换为列的类型，生成内部表达式： WHERE order_date = CAST('2023-10-01' AS DATE) 。 进一步的优化 ：常量折叠可以对 CAST('2023-10-01' AS DATE) 进行求值，得到一个内部的 DATE 常量。最终谓词可能被优化为 WHERE order_date = DATE'2023-10-01' 。这个形式对于索引查找是最优的。 三、 表达式等价性证明（Expression Equivalence Proof） 问题描述 ： 在查询重写、视图合并、谓词推导等高级优化中，优化器需要判断两个表达式是否在逻辑上等价。例如，判断 column BETWEEN 10 AND 20 是否等价于 column >= 10 AND column <= 20 。 解题过程与原理 ： 基于规范化形式的比较 ： 最直接的方法是将两个表达式分别进行 规范化 （如上所述）。如果它们的规范化形式完全相同，则可以认为它们等价。 例如， BETWEEN 通常被规范化为一对 >= 和 <= 的组合。因此， a BETWEEN x AND y 和 a >= x AND a <= y 在规范化后会变成相同的表达式树，从而证明等价。 应用已知的等价规则 ： 优化器维护一组已知的等价规则，用于处理规范化后形式可能不同但依然等价的复杂情况。 示例规则 ： NOT (A AND B) <-> (NOT A) OR (NOT B) （德摩根定律） A OR (A AND B) <-> A （吸收律） (A = B) AND (B = C) -> 可推导出 A = C （传递性，属于谓词传递闭包范畴，但也可用于证明 A = C 与已知条件集等价） 优化器可以尝试对一个表达式应用这些等价变换，看是否能变形为另一个表达式。 利用约束信息 ： 如果表上有约束（如主键、唯一键、 CHECK 约束），优化器可以利用这些信息证明等价。 实例 ：假设有 CHECK(status IN ('A', 'B', 'C')) 约束。那么表达式 status = 'A' OR status = 'B' 与 status != 'C' 在当前表的行集范围内是等价的。优化器可以利用这个信息进行重写。 四、 非确定性表达式的特殊处理（Handling Non-Deterministic Expressions） 问题描述 ： 某些表达式每次求值结果可能不同，如 RAND() 、 CURRENT_TIMESTAMP 、 NEWID() 。它们被称为非确定性（Non-Deterministic）或易变（Volatile）函数。在表达式预处理中，对它们的处理需要格外小心，因为很多优化（如公共子表达式消除、谓词下推）基于表达式在单次查询执行中多次求值结果相同的假设。 解题过程与原理 ： 标记与识别 ： 优化器内部有一个函数属性表，标记每个内置函数是确定性的（Deterministic）还是非确定性的。 用户自定义函数（UDF）通常需要由创建者声明其确定性属性。 限制优化应用 ： 公共子表达式消除（CSE） ： 对于 SELECT RAND(), RAND() FROM t ，不能将两个 RAND() 调用合并为一个，因为它们本应产生两个不同的随机数。优化器必须保留两个独立的调用。 谓词移动/下推 ： 将包含非确定性函数的谓词下推到更早的执行阶段（如扫描时）可能会改变查询语义。例如， WHERE id > RAND() * 100 ，如果在连接（JOIN）前对单表求值 RAND() ，和在对连接结果求值 RAND() ，由于 RAND() 值不同，过滤的行数可能不同。高级优化器可能选择不移动这类谓词，或为其生成一个“物化”点（先求值一次，然后复用该值）。 常量折叠 ： CURRENT_TIMESTAMP 在一个SQL语句执行期间通常被认为是常量。优化器可能会在查询开始执行时对其求值一次，然后将该值作为常量传播到所有使用该函数的地方，以保证语句内部时间一致。但不同语句执行时值不同。 实例解析 ： 查询 ： SELECT * FROM logs WHERE log_time > CURRENT_TIMESTAMP - INTERVAL '1' HOUR ORDER BY log_id LIMIT 100; 优化 ：优化器会识别 CURRENT_TIMESTAMP 。为了保证 WHERE 条件中使用的“一小时前”是一个固定时间点（而不是每一行比较时都重新获取时间），优化器会在优化开始时（或查询执行开始时）将其 物化为一个常量 。假设执行开始时间是 2023-10-27 10:00:00 ，那么整个谓词被转换为 log_time > TIMESTAMP '2023-10-27 09:00:00' 。这个转换是安全的，并且有利于在 log_time 列上使用索引进行范围扫描。 总结 ： 表达式预处理的进阶优化，是将基础的简化、合并、求值技术与类型系统、代数等价、约束信息和函数副作用等知识深度融合的过程。 复杂表达式规范化 为所有优化建立了统一、简洁的“语言”。 类型推导与提升 确保了表达式的语义正确性，并为基于类型的优化（如索引选择）铺平道路。 表达式等价性证明 是连接推导、谓词传递、视图合并等高级重写优化的基石。而对 非确定性表达式的特殊处理 ，则体现了优化器在追求性能的同时，对SQL语义准确性的严格遵循。这些技术共同作用，使得现代数据库查询优化器能够处理极其复杂和多样的用户查询，并生成高效且正确的执行计划。