进阶查询（窗口函数 / CTE / 递归 / 子查询） · 子查询与相关子查询

什么是相关子查询（correlated subquery）？性能为什么经常很差？如何改写为 JOIN？

What is a correlated subquery? Why is its performance often poor? How to rewrite it as a JOIN

答案语言

考察要点

这道题面试官想看你是否真正理解 SQL 查询的执行原理，而不仅仅是会写。核心考察点包括：

子查询的两种执行方式：能否清晰地区分独立子查询（只执行一次）和相关子查询（为外部查询的每一行都执行一次）的根本区别。
性能瓶颈分析能力：是否明白相关子查询“逐行执行”的模式是其性能瓶颈的关键，并能从复杂度层面（类似嵌套循环）进行分析。
SQL 优化与改写能力：是否具备将低效的相关子查询等价改写为高效的 JOIN 或窗口函数的能力，这是衡量 SQL 工程实践能力的重要标准。

核心概念

子查询（Subquery） 是嵌套在另一个 SQL 查询（如 SELECT, INSERT, UPDATE, DELETE）中的查询。根据其与外部查询的依赖关系，可分为两类：

非相关子查询（Non-correlated Subquery）
- 定义：子查询本身是一个独立的查询，可以独立执行，不依赖于外部查询的任何值。
- 执行过程：子查询先于外部查询执行，且只执行一次。其结果集被外部查询用作一个数据源或条件。
- 示例：查找所有薪资高于公司平均薪资的员工。
  sql
```
 1SELECT employee_name
 2FROM employees
 3WHERE salary > (SELECT AVG(salary) FROM employees);
```
  这里的 (SELECT AVG(salary) FROM employees) 只会计算一次，得到一个平均值，然后外部查询使用这个值进行比较。
相关子查询（Correlated Subquery）
- 定义：子查询的执行依赖于外部查询当前处理的行的值。它不能独立执行。
- 执行过程：对于外部查询的 每一行，相关子查询都会 执行一次。这类似于程序语言中的嵌套循环（Nested Loop）。
  text
```
 1For each row in outer_query:
 2    Execute inner_query(row.value)
```
- 性能瓶颈：如果外部查询返回 N 行，那么相关子查询就要执行 N 次。这导致查询的总时间复杂度急剧增加，通常为 $O(N \times M)$ （N 为外表行数，M 为内表操作复杂度），性能极差。

示例说明

假设有两张表：departments (部门表) 和 employees (员工表)。

departments 表

id	name
1	技术部
2	产品部

employees 表

id	name	dept_id	salary
101	张三	1	20000
102	李四	1	25000
103	王五	2	18000
104	赵六	2	18000

需求：查找每个部门中薪资最高的员工。

使用相关子查询的解法

sql

 1SELECT
 2    e1.name,
 3    e1.salary,
 4    e1.dept_id
 5FROM
 6    employees e1
 7WHERE
 8    e1.salary = (
 9        SELECT MAX(salary)
10        FROM employees e2
11        WHERE e2.dept_id = e1.dept_id -- 子查询依赖外部查询的 e1.dept_id
12    );

执行分析：

外部查询读取 employees 表的第一行（张三, 20000, 1）。
将 e1.dept_id 的值 1 传入子查询，执行 SELECT MAX(salary) FROM employees WHERE dept_id = 1，得到结果 25000。
外部查询 WHERE 条件变为 20000 = 25000，不成立。
外部查询读取第二行（李四, 25000, 1）。
将 e1.dept_id 的值 1 传入子查询，再次执行 SELECT MAX(salary) FROM employees WHERE dept_id = 1，得到 25000。
外部查询 WHERE 条件变为 25000 = 25000，成立，返回该行。
... 对 employees 表的每一行重复此过程。

如果 employees 表有 100 万行，这个子查询就会被执行 100 万次，造成巨大的性能开销。

多种解法（改写优化）

解法 1：使用 `JOIN` 和派生表（Derived Table）

这是最通用、最经典的优化方法，将“逐行计算”转变为“批量计算”。

思路：

先用一个子查询（这里是派生表）计算出每个部门的最高薪资。这个子查询是非相关的，只会执行一次。
将原始员工表与这个派生表进行 JOIN，筛选出薪资等于该部门最高薪资的员工。

版本：所有 SQL 版本通用。

SQL 代码：

sql

 1SELECT
 2    e.name,
 3    e.salary,
 4    e.dept_id
 5FROM
 6    employees e
 7JOIN
 8    (SELECT dept_id, MAX(salary) AS max_salary FROM employees GROUP BY dept_id) AS dept_max_salary
 9ON
10    e.dept_id = dept_max_salary.dept_id AND e.salary = dept_max_salary.max_salary;

复杂度：
- 派生表计算： $O(N \log N)$ 或 $O(N)$ ，取决于 GROUP BY 的实现（排序或哈希）。
- JOIN 操作：通常是哈希连接（Hash Join） $O(N+M)$ 或带索引的嵌套循环连接（Index Nested-Loop Join） $O(N \log M)$ 。
- 总体性能远高于相关子查询。
索引依赖：employees 表的 (dept_id, salary) 复合索引能极大地加速 GROUP BY 和 JOIN 操作。

解法 2：使用窗口函数（Window Function）

这是更现代、更简洁的解法，尤其适合处理排名、分组 top-N 等问题。

思路：

使用 RANK() 或 DENSE_RANK() 窗口函数，按部门 (PARTITION BY dept_id) 对薪资进行降序排名 (ORDER BY salary DESC)。
在外层查询中，只选择排名为 1 的员工。

版本：✅ MySQL 8.0+ / PostgreSQL / Oracle / SQL Server；❌ MySQL 5.7 及更早版本不支持。

SQL 代码：

sql

 1WITH ranked_employees AS (
 2    SELECT
 3        name,
 4        salary,
 5        dept_id,
 6        RANK() OVER (PARTITION BY dept_id ORDER BY salary DESC) as rnk
 7    FROM
 8        employees
 9)
10SELECT
11    name,
12    salary,
13    dept_id
14FROM
15    ranked_employees
16WHERE
17    rnk = 1;

注意：如果最高薪有并列，RANK() 和 DENSE_RANK() 都会返回多条记录。ROW_NUMBER() 则会任选一条返回。根据业务需求选择。

复杂度：窗口函数的计算通常涉及排序，复杂度为 $O(N \log N)$ 。
索引依赖：在 (dept_id, salary) 上的索引可以帮助优化 PARTITION BY 和 ORDER BY 过程。

常见低分回答

混淆概念：回答“子查询性能都很差”，没有区分相关与非相关子查询。非相关子查询只要结果集不大，性能通常是可接受的。
解释不清原因：只说“相关子查询慢”，但无法解释其“逐行执行”的嵌套循环模型，也无法从复杂度层面进行对比。
滥用 IN 代替 =：写出类似 WHERE (dept_id, salary) IN (SELECT dept_id, MAX(salary) ...) 的代码。虽然在某些数据库中会被优化，但这在逻辑上和性能上都不如 JOIN 清晰和稳定。
盲目否定 EXISTS：EXISTS / NOT EXISTS 是典型的相关子查询用法，但它们通常比 IN / NOT IN 的相关子查询性能更好，因为 EXISTS 遵循“找到即停”（short-circuit）的逻辑，且对 NULL 的处理更符合直觉。一概而论地否定所有相关子查询是不准确的。
忽略优化器：声称相关子查询“一定”会逐行执行。虽然这是经典模型，但现代优化器（如 MySQL 8.0）可能会尝试将某些模式的相关子查询（如 IN）自动优化为 SEMI-JOIN，性能得到改善。不了解这一点会显得知识陈旧。

工程实践与优化

使用 EXPLAIN 诊断：识别相关子查询最直接的方法是查看执行计划。在 MySQL 中，如果 select_type 列出现 DEPENDENT SUBQUERY，就明确表示这是一个相关子查询，需要立即进行优化。
优化首选 JOIN：将相关子查询改写为 JOIN 是最普适、最有效的优化手段。
善用 CTE 和窗口函数：对于支持的数据库版本（如 MySQL 8.0+），使用 WITH 子句（CTE）和窗口函数通常能写出更易读、更高效的 SQL。
EXISTS 的适用场景：当只关心“是否存在”满足条件的关联行，而不需要关联行的数据时，EXISTS 是一个非常高效的选择。例如，“查询所有有员工的部门”。
sql
```
 1-- 高效的 EXISTS
 2SELECT d.name
 3FROM departments d
 4WHERE EXISTS (SELECT 1 FROM employees e WHERE e.dept_id = d.id);
 5
 6-- 低效的 COUNT(*)
 7SELECT d.name
 8FROM departments d
 9WHERE (SELECT COUNT(*) FROM employees e WHERE e.dept_id = d.id) > 0;
```
EXISTS 在找到第一个匹配的员工后就会立即返回 true，而 COUNT(*) 必须统计完所有员工。

常见追问与延伸题目

追问：EXISTS、IN 和 JOIN 在用于改写时，有什么区别和优劣？
- 回答要点 1 (语义)：JOIN 用于合并两个表的数据，返回组合后的行。IN 用于判断一个值是否存在于一个集合中。EXISTS 用于判断一个子查询是否返回任何行。
- 回答要点 2 (性能)：
  - JOIN 通常最高效，特别是当优化器选择哈希连接时。
  - EXISTS 性能也很好，因为它“找到即停”，且子查询中的 SELECT * 或 SELECT 1 没有区别。优化器通常会将其转换为 SEMI-JOIN。
  - IN 的性能波动较大。如果 IN 的列表是常量，性能很好。如果 IN 的内容来自非相关子查询，优化器可能会物化子查询结果并使用哈希查找。如果来自相关子查询，则可能退化为逐行匹配，性能差（尽管新版 MySQL 会尝试优化）。
- 回答要点 3 (NULL 处理)：NOT IN 子查询如果返回任何 NULL 值，整个外部查询的结果将是空集，这是一个巨大的坑。NOT EXISTS 则没有这个问题，行为更符合逻辑。因此，在做“不存在”判断时，强烈推荐使用 NOT EXISTS。
追问：你刚才提到 MySQL 8.0 的优化器会改写相关子查询，能具体讲讲吗？
- 回答要点 1 (Semi-Join)：对于 IN 或 EXISTS 引导的相关子查询，优化器会尝试将其转换为半连接（Semi-Join）。它不会像普通 JOIN 那样产生笛卡尔积，而是对于左表的每一行，在右表中找到第一条匹配的行后就停止，并返回左表的行。这避免了相关子查询的“逐行执行”开销。
- 回答要点 2 (Subquery Unnesting)：优化器会尝试“解嵌套”，将子查询的表直接提升到外部查询的 FROM 子句中，并将其转换为一个普通的 JOIN。这是最理想的优化。
- 回答要点 3 (Materialization)：对于非相关子查询，优化器可能会选择“物化”策略，即先执行子查询，将其结果存入一个临时表，并为临时表创建哈希索引，然后再与外部查询进行连接。
追问：如果外部查询的表非常小，比如只有 10 行，而内部表非常大，使用相关子查询性能会很差吗？
- 回答要点 1 (具体情况具体分析)：在这种场景下，相关子查询的性能可能不是瓶颈，甚至可能是可接受的。因为子查询只会执行 10 次。
- 回答要点 2 (索引是关键)：如果这 10 次子查询都能高效地利用内部大表的索引（例如，WHERE e2.dept_id = e1.dept_id 中的 dept_id 列有索引），那么每次执行的成本非常低（如 log(M) 级别）。总成本就是 10 * log(M)，可能比一个复杂的 JOIN（可能涉及全表扫描和排序）更快。
- 回答要点 3 (结论)：这表明没有绝对的“银弹”。虽然理论上相关子查询模型更糟，但在特定数据分布下（外表小、内表大且有索引），其性能可能尚可。但作为一种开发习惯，优先选择 JOIN 或窗口函数是更稳妥、更具扩展性的做法，因为表的规模是会变化的。