SQL 实战编程题（GitHub 高频题） · 查找类

找出某列第 N 高的数据。(经典 LeetCode 题：第 N 高的薪水)

Find the Nth highest value in a column. (Classic LeetCode problem: N

答案语言

考察要点

这道题是 SQL 面试中考察频率最高的题目之一，面试官想看你是否扎实掌握了 SQL 的核心排序、去重和筛选能力。具体来说，考察点包括：

排名函数：是否熟悉并能区分 DENSE_RANK, RANK, ROW_NUMBER 的语义和适用场景。
分页查询：是否能熟练运用 LIMIT 和 OFFSET 来精确获取特定位置的数据。
子查询：是否理解如何通过子查询（尤其是派生表和标量子查询）来构建复杂的查询逻辑。

这道题能很好地筛选出候选人是对 SQL 仅有基础了解，还是具备了解决复杂数据问题的能力。

核心概念

解决此问题的核心在于如何对数据进行“排名”并筛选出特定位次的数据。

1. 窗口函数 (Window Functions)

窗口函数对一组与当前行相关的表行（称为窗口）执行计算。这是最现代、最标准的解法。

函数	描述	示例 (对薪水 `300, 200, 200, 100` 排序)
`DENSE_RANK()`	连续排名，相同值的排名相同，后续排名不跳跃。是本题“第 N 高”语义的最佳选择。	1, 2, 2, 3
`RANK()`	跳跃排名，相同值的排名相同，但后续排名会跳过并列的数量。	1, 2, 2, 4
`ROW_NUMBER()`	唯一排名，为窗口中的每一行分配一个从 1 开始的唯一整数。即使值相同，排名也不同。	1, 2, 3, 4

语法注意：窗口函数不能直接用在 WHERE 子句中，必须先在 SELECT 子句或 CTE (Common Table Expression) 中计算出排名，然后在外部查询中进行过滤。

sql

 1-- 错误用法
 2SELECT salary
 3FROM Employee
 4WHERE DENSE_RANK() OVER (ORDER BY salary DESC) = 2;
 5
 6-- 正确用法 (使用派生表)
 7SELECT salary FROM (
 8    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
 9    FROM Employee
10) AS ranked_salaries
11WHERE rnk = 2;

2. `LIMIT` 与 `OFFSET`

这是 MySQL 等数据库中实现分页的常用方法，也可以巧妙地用于解决本题。

ORDER BY col DESC: 按 col 列降序排序。
DISTINCT col: 去除 col 列的重复值。这是“第 N 高”的关键，因为我们关心的是不同的值。
LIMIT n: 返回最多 n 条记录。
OFFSET m: 跳过前 m 条记录。
LIMIT m, n (MySQL/MariaDB 特有语法): 等价于 LIMIT n OFFSET m，即跳过 m 条，取 n 条。

要找到第 N 高的数据，思路是：

对薪水去重并降序排序。
跳过前面的 N-1 个薪水。
取接下来的 1 个薪水。

所以组合起来就是 LIMIT N-1, 1。

3. 子查询 (Subquery)

通过子查询，尤其是关联子查询，也可以实现排名逻辑，但通常性能较差。

示例逻辑：找到一个薪水 s1，使得恰好有 N-1 个不同的薪水 s2 大于它。

sql

 1-- 查找第 2 高薪水的逻辑
 2SELECT salary FROM Employee e1
 3WHERE 1 = (SELECT COUNT(DISTINCT e2.salary) FROM Employee e2 WHERE e2.salary > e1.salary);

这个查询对外部查询的每一行，都会执行一次内部的 COUNT 查询，性能开销很大。

多种解法

假设我们有 Employee 表和需要实现的函数 getNthHighestSalary(N INT)。

示例数据 Employee 表:

id	salary
1	100
2	200
3	300
4	300

解法 1：窗口函数 `DENSE_RANK` (推荐，最标准)

这种方法逻辑清晰，可读性强，并且 легко 扩展到更复杂的排名场景（如按部门排名）。

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

SQL 实现：

sql

 1CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
 2BEGIN
 3  RETURN (
 4      # 使用派生表来过滤窗口函数的结果
 5      SELECT DISTINCT salary
 6      FROM (
 7          SELECT
 8              salary,
 9              DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
10          FROM
11              Employee
12      ) AS ranked_salaries
13      WHERE rnk = N
14      LIMIT 1 -- 确保当N无效时返回NULL，而不是空集
15  );
16END

时间/空间复杂度：主要开销在于排序，时间复杂度为 $O(K \log K)$ ，其中 K 是 Employee 表的行数。空间复杂度为 $O(K)$ ，需要存储排序的中间结果。
索引依赖：在 salary 列上建立索引可以加速 ORDER BY 操作，数据库可能利用索引进行排序，避免全表文件排序。

解法 2：`DISTINCT` + `LIMIT` + `OFFSET`

这种方法非常直观，性能在有索引的情况下通常是最好的，尤其是在 MySQL 中。

版本：✅ 所有 MySQL 版本 / PostgreSQL；语法略有不同。

SQL 实现 (MySQL)：

sql

 1CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
 2BEGIN
 3  # N-1 是因为 OFFSET 是从 0 开始的
 4  DECLARE M INT;
 5  SET M = N - 1;
 6  RETURN (
 7      SELECT DISTINCT salary
 8      FROM Employee
 9      ORDER BY salary DESC
10      LIMIT M, 1
11  );
12END

时间/空间复杂度：主要开销在于 ORDER BY。时间复杂度为 $O(K \log K)$ 。但如果 salary 列有索引，数据库可以利用索引顺序扫描，只需找到第 N 个唯一值，性能极高，接近 $O(\log K + N)$ 。
索引依赖：强烈依赖 (salary) 列上的索引。没有索引会导致全表扫描和文件排序，性能急剧下降。

解法 3：关联子查询

这种方法展示了对 SQL 查询执行模型的深刻理解，但在生产中几乎不使用，因为它通常性能最差。

版本：✅ 几乎所有 SQL 数据库都支持。

SQL 实现：

sql

 1CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
 2BEGIN
 3  RETURN (
 4      SELECT DISTINCT salary
 5      FROM Employee e1
 6      WHERE (N - 1) = (
 7          SELECT COUNT(DISTINCT e2.salary)
 8          FROM Employee e2
 9          WHERE e2.salary > e1.salary
10      )
11      LIMIT 1
12  );
13END

时间/空间复杂度：这是一个关联子查询，对于外表的每一行，都要执行一次子查询。在没有索引的情况下，复杂度可能高达 $O(K^2)$ 。即使 salary 有索引，子查询的 COUNT 操作也需要扫描部分索引，总复杂度仍然很高。
索引依赖：salary 列上的索引是必须的，否则查询无法在可接受的时间内完成。

常见低分回答

误用 RANK() 或 ROW_NUMBER()：
- ROW_NUMBER() 会给并列的值分配不同排名，导致结果错误。
- RANK() 会产生跳跃的排名，比如 1, 2, 2, 4，如果查询第 3 高，会找不到结果。
- 反例：... RANK() OVER (ORDER BY salary DESC) as rnk ... WHERE rnk = 3 在 {300, 200, 200, 100} 数据中会失败。
在 LIMIT 解法中忘记 DISTINCT：
- 如果不加 DISTINCT，查询的是第 N 行的薪水，而不是第 N 高的薪水。
- 反例：对于 {300, 300, 200}，SELECT salary FROM Employee ORDER BY salary DESC LIMIT 1, 1 会返回 300，而正确答案应该是 200。
LIMIT 的 OFFSET 计算错误：
- LIMIT N, 1 是一个常见的 off-by-one 错误，它会去查找第 N+1 高的薪水。正确的应该是 LIMIT N-1, 1。
直接在 WHERE 子句中使用窗口函数：
- 这是 SQL 的语法错误。SQL 的逻辑执行顺序是 FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY，窗口函数在 SELECT 阶段之后才计算，因此不能在 WHERE 中使用。
- 反例：SELECT salary FROM Employee WHERE DENSE_RANK() OVER (ORDER BY salary DESC) = N;
未处理 N 无效的情况：
- 如果 N 大于不同薪水的数量，查询应该返回 NULL 或空集。上述解法中的 LIMIT 1 或将整个 SELECT 语句作为函数返回值可以优雅地处理此问题，返回 NULL。如果直接查询，会返回空集。

工程实践与优化

索引是关键：对于此问题，salary 列上的 B+ 树索引是性能的决定性因素。对于解法 2 (LIMIT)，有索引的情况下，数据库可以直接在索引上向后遍历 N 个不同的键，无需对全表数据排序，性能极高。
执行计划分析 (EXPLAIN)：
- 解法 2 (LIMIT)：EXPLAIN 的 Extra 字段如果显示 Using index，表示实现了覆盖索引扫描，性能最佳。如果显示 Using filesort，说明索引未生效，需要优化。
- 解法 1 (窗口函数)：通常会看到 Using temporary; Using filesort，表示需要创建临时表并排序，开销较大。
- 解法 3 (关联子查询)：会看到 DEPENDENT SUBQUERY，这是严重的性能瓶颈信号。
数据量级影响：
- 小数据量 (万级)：任何解法都可以接受，窗口函数可读性最好。
- 大数据量 (亿级)：解法 2 (LIMIT + 索引) 是唯一可行的方案。解法 1 会因全表排序而耗尽内存或执行时间过长。解法 3 会直接导致数据库超时。
避免在函数中封装简单查询：虽然题目要求写成函数，但在真实生产中，如果一个查询只在单一场景使用，直接写 SQL 更易于维护和优化。只有当逻辑需要在多处复用时，才封装成存储过程或函数。

常见追问与延伸题目

追问：如果数据量增长到 10 亿，需要查找第 100 高的薪水，哪个方案最好？为什么？
- 回答要点：此时，解法 2 (LIMIT + OFFSET) 是唯一可行的选择。
  - 原因：salary 列上的索引是 B+ 树结构，数据本身有序。查询 ORDER BY salary DESC LIMIT 99, 1 时，数据库优化器会选择索引倒序扫描 (Index Backward Scan)。它只需要从索引的末尾开始，向后查找 100 个不同的值即可，完全不需要加载和排序 10 亿行数据。其性能与 N 的大小有关，但与表的总行数 K 无关，复杂度约等于 $O(\log K + N)$ 。
  - 对比：而窗口函数需要对 10 亿行数据进行排序，这会产生巨大的 I/O 和 CPU 开销，甚至可能导致磁盘空间或内存不足，查询基本无法完成。
追问：如果要查找每个部门内薪水第 N 高的员工信息，该怎么写？
- 回答要点：这个问题是考察 PARTITION BY，是窗口函数的典型应用场景。
  - 方案：必须使用窗口函数。LIMIT 或关联子查询的方案将变得极其复杂和低效。
  - SQL 示例：
    sql
```
 1WITH EmployeeRankedByDept AS (
 2    SELECT
 3        name,
 4        salary,
 5        departmentId,
 6        DENSE_RANK() OVER (PARTITION BY departmentId ORDER BY salary DESC) as rnk
 7    FROM Employee
 8)
 9SELECT name, salary, departmentId
10FROM EmployeeRankedByDept
11WHERE rnk = N; -- N 是你想找的排名
```
  - 解释：PARTITION BY departmentId 会将数据按部门分组，然后在每个部门内部独立进行 DENSE_RANK() 排名。这是解决“Top N per Group”问题的标准模式。
追问：如果换成 PostgreSQL 或 Oracle，答案有什么不同？
- 回答要点：核心逻辑不变，但语法细节有差异。
  - 窗口函数：解法 1 是标准 SQL，在 PostgreSQL, Oracle, SQL Server 中完全兼容，是首选方案。
  - LIMIT/OFFSET：
    - PostgreSQL：语法与 MySQL 相同，LIMIT n OFFSET m。
    - Oracle 12c+：使用 OFFSET m ROWS FETCH NEXT n ROWS ONLY。
    - SQL Server：使用 OFFSET m ROWS FETCH NEXT n ROWS ONLY。
    - 所以解法 2 的思想是通用的，但具体实现需要根据不同数据库的方言进行调整。
  - 函数定义：CREATE FUNCTION 的语法在不同数据库中有很大差异（如 PL/pgSQL, PL/SQL 等），需要单独学习。但核心的 SELECT 语句逻辑是相通的。