阿里：用户支付排名第 N 高的金额（LeetCode N 高薪水变体）。

考察要点

这道题是经典的 Top-K 问题变种，面试官想考察你对 SQL 排名和数据筛选能力的掌握程度。核心在于：

1. 排名能力：是否熟悉并能区分窗口函数 DENSE_RANK(), RANK(), ROW_NUMBER() 的语义差异，并选择最合适的 DENSE_RANK() 来处理金额相等的情况。
2. 多种解法：能否用不同 SQL 思路解决同一问题，例如现代的窗口函数、经典的子查询或 LIMIT 语法，并清晰地阐述其优劣。
3. 性能意识：是否理解不同写法的性能差异，尤其是在大数据量下，并能结合索引和执行计划进行分析。

核心概念

解决此问题的关键在于理解如何对金额进行排名，并处理金额相同的情况。

1. 窗口函数 (Window Functions)

窗口函数对一组与当前行相关的表行（称为窗口）执行计算。它们是解决排名、聚合等问题的现代标准。

• DENSE_RANK()：连续排名。相同值的行获得相同的排名，且后续排名没有间隙。这是本题的正确选择。
• RANK()：跳跃排名。相同值的行获得相同的排名，但后续排名会跳过相应数量的序号。
• ROW_NUMBER()：行号。为窗口中的每一行分配一个从 1 开始的唯一连续整数，不考虑值是否相同。

数据示例 假设 payments 表数据如下：

应用不同窗口函数的结果：

 1SELECT
 2    amount,
 3    ROW_NUMBER() OVER (ORDER BY amount DESC) AS row_num,
 4    RANK()       OVER (ORDER BY amount DESC) AS rnk,
 5    DENSE_RANK() OVER (ORDER BY amount DESC) AS dense_rnk
 6FROM payments;

如上表所示，要找第 2 高的金额（800），dense_rnk 为 2。若用 rnk，则找不到排名为 3 的记录。

2. LIMIT 与 OFFSET

• LIMIT count: 限制返回结果的行数。
• LIMIT offset, count 或 OFFSET offset LIMIT count (PostgreSQL/标准 SQL): 跳过 offset 行后，再返回 count 行。

这是 MySQL 中实现分页和取特定行记录的常用方法，但必须配合 ORDER BY 和 DISTINCT 才能正确解决本题。

3. 相关子查询 (Correlated Subquery)

子查询的执行依赖于外部查询的当前行。它会为外部查询的每一行都执行一次，通常性能较差。 例如，我们可以通过计算“有多少个不同的金额比当前行的金额更大”来实现排名。

多种解法

假设我们有一个 payments 表，需要找出支付排名第 N 高的金额。为了方便演示，我们设 N=2。

 1-- 表结构 DDL
 2CREATE TABLE payments (
 3    id INT PRIMARY KEY AUTO_INCREMENT,
 4    user_id INT,
 5    amount DECIMAL(10, 2),
 6    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
 7);
 8
 9-- 插入示例数据
10INSERT INTO payments (user_id, amount) VALUES
11(101, 1000.00), (102, 800.00), (103, 800.00), (104, 500.00), (105, 1200.00);

目标：找到第 2 高的金额，即 1000.00。

解法 1：使用窗口函数 DENSE_RANK (最优解)

这是最推荐、最清晰、性能也最好的现代解法。

• 版本：✅ MySQL 8.0+ / PostgreSQL / Oracle / SQL Server；❌ MySQL 5.7 及以下版本不支持。
• SQL (N=2)：
  sql

  ⧉⛶

   1WITH RankedPayments AS (
   2    SELECT
   3        amount,
   4        DENSE_RANK() OVER (ORDER BY amount DESC) AS rnk
   5    FROM
   6        payments
   7)
   8SELECT DISTINCT amount
   9FROM RankedPayments
  10WHERE rnk = 2;

  或者不使用 CTE，直接用子查询：
  sql

  ⧉⛶

   1SELECT DISTINCT amount
   2FROM (
   3    SELECT
   4        amount,
   5        DENSE_RANK() OVER (ORDER BY amount DESC) AS rnk
   6    FROM
   7        payments
   8) AS RankedPayments
   9WHERE rnk = 2;

• 时间/空间复杂度：主要开销在于排序，时间复杂度为 $O(N \log N)$，其中 N 是表中的总行数。空间复杂度为 $O(N)$ 用于存储排序过程中的数据。
• 索引依赖：在 amount 列上建立索引 (CREATE INDEX idx_amount ON payments(amount);) 可以极大地加速 ORDER BY 操作，数据库可以直接利用索引的有序性，避免全表扫描和额外的 filesort 操作。

解法 2：使用 DISTINCT 和 LIMIT OFFSET

这是一种巧妙且直观的解法，兼容性好，性能也不错。

• 版本：✅ MySQL / PostgreSQL 等主流数据库。
• SQL (N=2)：
  sql

  ⧉⛶

   1SELECT DISTINCT amount
   2FROM payments
   3ORDER BY amount DESC
   4LIMIT 1 OFFSET 1; -- OFFSET = N-1

• 时间/空间复杂度：需要先找出所有 DISTINCT 的金额，然后排序。复杂度同样为 $O(M \log M)$，其中 M 是去重后的金额数量。当 M 远小于 N 时，此方法可能比窗口函数更快。
• 索引依赖：在 amount 列上的索引同样能优化此查询。数据库可以利用索引进行 "Loose Index Scan" 来高效地获取 DISTINCT 值，并利用索引有序性来满足 ORDER BY 和 LIMIT，避免 filesort。

解法 3：使用相关子查询

这是一种经典的、符合 SQL 原始思想的解法，但在现代数据库中通常不被推荐，因为它性能很差。

• 版本：✅ 几乎所有 SQL 数据库，包括非常古老的版本。
• SQL (N=2)：
  sql

  ⧉⛶

   1SELECT DISTINCT p1.amount
   2FROM payments p1
   3WHERE (
   4    SELECT COUNT(DISTINCT p2.amount)
   5    FROM payments p2
   6    WHERE p2.amount > p1.amount
   7) = 1; -- COUNT = N-1

• 逻辑解释：对于 payments 表中的每一个金额 p1.amount，我们去计算在整个表中，有多少个不同的金额比它大。如果这个数量正好是 N-1，那么 p1.amount 就是我们要找的第 N 高的金额。
• 时间/空间复杂度：近似为 $O(M^2)$，其中 M 是表中的行数。因为对于外部查询的每一行，内部的相关子查询都要执行一次，导致性能急剧下降。
• 索引依赖：即使 amount 列上有索引，也无法从根本上改变其嵌套循环的执行模式。EXPLAIN 会显示 DEPENDENT SUBQUERY，这是性能的巨大隐患。

常见低分回答

1. 误用 RANK() 或 ROW_NUMBER()：
   • ROW_NUMBER() 会给相同的金额分配不同排名，导致结果错误。
   • RANK() 在金额相同时会产生排名空隙（如 1, 2, 2, 4），如果查询第 3 名，WHERE rnk = 3 会找不到结果。
2. LIMIT 未配合 DISTINCT：
   • SELECT amount FROM payments ORDER BY amount DESC LIMIT 1 OFFSET 1;
   • 对于数据 1200, 1000, 800, 800, 500，OFFSET 1 会跳过 1200，返回 1000，这是正确的第 2 高金额。但如果数据是 1200, 1200, 1000, ...，OFFSET 1 同样会跳过第一个 1200，返回第二个 1200，而不是 1000。
3. 忽略查询可能无结果的情况：如果 N 大于表中不同金额的数量，上述所有正确解法都会自然地返回一个空集，这是正确的行为。低分回答可能没有考虑到这一点，或者写出在某些边缘情况下会报错的 SQL。
4. 使用 MAX() 函数的复杂嵌套：有些候选人会尝试用 MAX() 函数来解决，例如 SELECT MAX(amount) FROM payments WHERE amount < (SELECT MAX(amount) FROM payments);。这种写法只能找到第 2 高的金额，无法泛化到第 N 高，缺乏扩展性。

工程实践与优化

• 索引是关键：对于 amount 列，必须建立 B+ 树索引。这使得 ORDER BY 和 DISTINCT 操作可以利用索引的有序性，从 $O(N \log N)$ 的 filesort 优化为 $O(N)$ 的索引扫描，甚至更快。
• 执行计划分析：
  • 解法 1 (窗口函数)：EXPLAIN 的 Extra 字段会显示 Window: dense_rank...。如果有索引，type 可能是 index，避免了 Using filesort。
  • 解法 2 (LIMIT)：EXPLAIN 的 Extra 字段在有索引时可能是 Using index for group-by (对于 DISTINCT)，表示高效地利用了索引。无索引则是 Using temporary; Using filesort。
  • 解法 3 (相关子查询)：EXPLAIN 会明确指出 DEPENDENT SUBQUERY，这是必须避免的性能杀手。
• 大数据量下的实践：在用户行为分析等场景，支付表可能有数十亿甚至上万亿行。
  • 禁止在线查询：这种全表聚合排序类的查询绝对不能在生产环境的 OLTP 数据库上实时执行，它会消耗大量 CPU 和 IO，可能导致服务抖动甚至锁表。
  • 离线预计算：正确的做法是，通过离线计算任务（如 Spark, Flink, Hive）每天或每小时对数据进行预处理，将用户的支付排名、Top-N 金额等指标计算好，存入结果表或分析型数据库（如 ClickHouse, Doris, StarRocks）中，供线上业务查询。

常见追问与延伸题目

1. 追问：如果需要找出支付了第 N 高金额的 所有用户，SQL 该怎么写？

   • 回答要点：这正是窗口函数的优势所在。在计算出排名的 CTE 中，不要 DISTINCT amount，而是直接保留 user_id 和 amount 列进行筛选。
   • SQL 示例：
     sql

     ⧉⛶

      1WITH RankedPayments AS (
      2    SELECT
      3        user_id,
      4        amount,
      5        DENSE_RANK() OVER (ORDER BY amount DESC) AS rnk
      6    FROM
      7        payments
      8)
      9SELECT user_id, amount
     10FROM RankedPayments
     11WHERE rnk = 2; -- 假设 N=2

2. 追问：如果数据量增长 100 倍（达到百亿级别），这条 SQL 性能会怎样？怎么优化？

   • 回答要点 1 (性能瓶颈)：LIMIT 解法和窗口函数解法的性能都会急剧下降。排序百亿行数据需要巨大的内存和磁盘 I/O，单机 MySQL 根本无法完成。相关子查询的解法会直接超时，完全不可用。
   • 回答要点 2 (架构级优化)：必须放弃在单机关系型数据库中实时计算的想法。
     • 方案 A (离线计算)：使用分布式计算框架如 Spark 或 Flink，在 HDFS/S3 上的数据进行分布式排序和排名计算。将最终的 Top-N 结果存入一个高性能的 KV 存储（如 Redis）或分析型数据库（如 ClickHouse）中，供业务方快速查询。
     • 方案 B (近似算法)：如果业务可以接受近似结果（例如，找到近似第 N 高的金额），可以使用一些大数据近似算法，如 t-digest 或 KLL sketch，它们可以在流式处理或单次遍历中以很小的内存占用估算出分位数，速度极快。

3. 追问：如果换成 PostgreSQL 或 Oracle，答案有什么不同？

   • 回答要点：核心思想和最优解（窗口函数）是完全一致的，因为窗口函数是 SQL 标准的一部分。
     • 语法差异：LIMIT...OFFSET... 在 Oracle 中需要用 OFFSET ... ROWS FETCH NEXT ... ROWS ONLY 语法，但功能相同。PostgreSQL 的语法与 MySQL 兼容。
     • 优化器差异：不同数据库的查询优化器实现细节不同，可能会对相同的 SQL 生成略有差异的执行计划，但对于索引的使用、排序的代价等基本原则是相通的。在 PostgreSQL 中，EXPLAIN ANALYZE 提供了更详尽的执行信息，包括实际执行时间和行数，比 MySQL 的 EXPLAIN 更利于诊断。