找出每个班级成绩前 20% 的学生。

考察要点

这道题的核心是考察候选人对 窗口函数（Window Functions） 的理解和熟练运用，特别是分组排名和分位数计算的能力。面试官想看你是否懂：

1. 分组处理能力：能否正确使用 PARTITION BY 将数据划分为独立的班级进行计算。
2. 排名与分位数函数：是否了解 NTILE, RANK, PERCENT_RANK 等函数的精确语义和适用场景。
3. 复杂查询构建：能否通过 CTE（Common Table Expressions）或子查询，将复杂问题分解为清晰的步骤。

核心概念

解决本题，需要精准理解以下几个核心概念：

1. 窗口函数 (Window Functions)

窗口函数对一组与当前行相关的表行（这个组称为“窗口”）执行计算。与聚合函数（如 GROUP BY）不同，它不会将多行压缩为一行，而是在保留原始行数的基础上，为每一行添加一个计算列。

基本语法：

 1<window_function>() OVER (
 2    [PARTITION BY col1, col2...]
 3    [ORDER BY col3, col4...]
 4    [<window_frame_clause>]
 5)

• PARTITION BY: 将数据行分成多个分区（“组”），窗口函数在每个分区内独立计算。对于本题，就是 PARTITION BY class_id。
• ORDER BY: 定义分区内行的顺序。对于本题，需要按成绩倒序排列，即 ORDER BY score DESC。

2. 关键的分位数/排名函数

示例数据

假设有 scores 表：

 1CREATE TABLE scores (
 2    student_id INT,
 3    class_id INT,
 4    student_name VARCHAR(50),
 5    score DECIMAL(5, 2)
 6);
 7INSERT INTO scores VALUES
 8(1, 1, 'Alice', 95.0), (2, 1, 'Bob', 90.0), (3, 1, 'Carol', 85.0), (4, 1, 'David', 80.0), (5, 1, 'Eve', 75.0),
 9(6, 2, 'Frank', 100.0), (7, 2, 'Grace', 100.0), (8, 2, 'Heidi', 90.0), (9, 2, 'Ivan', 80.0), (10, 2, 'Judy', 70.0),
10(11, 2, 'Mallory', 60.0), (12, 2, 'Niaj', 50.0), (13, 2, 'Olivia', 40.0), (14, 2, 'Peggy', 30.0), (15, 2, 'Trent', 20.0);

• 班级 1：5 个学生，Top 20% 是第 1 名。
• 班级 2：10 个学生，Top 20% 是第 1、2 名。

多种解法

解法 1：使用 NTILE() 窗口函数（最直观）

这种方法直接将问题 "前 20%" 翻译为 "五分位数的第一分位"。

• 版本：✅ MySQL 8.0+ / PostgreSQL / Oracle / SQL Server；❌ MySQL 5.7 不支持窗口函数。
• SQL 代码：

 1WITH student_tiles AS (
 2    SELECT
 3        student_id,
 4        class_id,
 5        student_name,
 6        score,
 7        NTILE(5) OVER (PARTITION BY class_id ORDER BY score DESC) AS score_tile
 8    FROM
 9        scores
10)
11SELECT
12    student_id,
13    class_id,
14    student_name,
15    score
16FROM
17    student_tiles
18WHERE
19    score_tile = 1;

• 时间/空间复杂度：时间复杂度为 $O(N \log N)$，主要是因为 PARTITION BY 后的排序操作。空间复杂度为 $O(N)$，用于存储中间结果。
• 索引依赖：在 (class_id, score DESC) 上建立复合索引可以极大地提升性能，数据库可以利用索引顺序直接计算窗口，避免额外的排序（filesort）。

解法 2：使用 RANK() 和 COUNT() 窗口函数（更灵活）

这种方法先计算出每个学生在班级内的排名，再计算出每个班级的总人数，最后筛选出排名在前 20% 的学生。这种方法在处理非整除百分比（如 Top 17%）时更灵活。

• 版本：✅ MySQL 8.0+ / PostgreSQL / Oracle / SQL Server；❌ MySQL 5.7。
• SQL 代码：

 1WITH student_ranks AS (
 2    SELECT
 3        student_id,
 4        class_id,
 5        student_name,
 6        score,
 7        RANK() OVER (PARTITION BY class_id ORDER BY score DESC) AS rk,
 8        COUNT(*) OVER (PARTITION BY class_id) AS total_students
 9    FROM
10        scores
11)
12SELECT
13    student_id,
14    class_id,
15    student_name,
16    score
17FROM
18    student_ranks
19WHERE
20    rk <= total_students * 0.2;

注意：RANK() 在处理并列名次时，可能会让选出的人数超过严格的 20%。例如，一个班 10 人，第 2 名和第 3 名并列，rk <= 10 * 0.2 (即 rk <= 2) 会把第 2、3 名都选出来。这通常是符合业务预期的（并列算入）。如果要求严格不多于 20%，应使用 ROW_NUMBER()，但这会随机破坏并列关系。

• 时间/空间复杂度：同解法 1，为 $O(N \log N)$。
• 索引依赖：同解法 1， (class_id, score DESC) 上的复合索引是性能关键。

解法 3：使用相关子查询（兼容老版本，性能较差）

在不支持窗口函数的旧版 MySQL（如 5.7）中，可以通过相关子查询模拟排名。

• 版本：✅ 所有版本；但性能极差，不推荐在生产中使用。
• SQL 代码：

 1SELECT
 2    s1.student_id,
 3    s1.class_id,
 4    s1.student_name,
 5    s1.score
 6FROM
 7    scores s1
 8WHERE
 9    (
10        SELECT COUNT(*)
11        FROM scores s2
12        WHERE s2.class_id = s1.class_id AND s2.score >= s1.score
13    ) <= (
14        SELECT COUNT(*)
15        FROM scores s3
16        WHERE s3.class_id = s1.class_id
17    ) * 0.2;

• 复杂度：对于 scores 表中的每一行，都要执行两次子查询。这导致时间复杂度近似为 $O(N^2)$，其中 N 是表行数。数据量稍大就会导致查询超时。
• 索引依赖：即使在 (class_id, score) 上有索引，子查询的重复执行开销依然巨大。

常见低分回答

1. 误用 LIMIT：SELECT ... FROM scores GROUP BY class_id LIMIT ... 这种写法完全错误，LIMIT 在 GROUP BY 之后执行，且无法实现分组取 Top N。
2. 忘记 PARTITION BY：RANK() OVER (ORDER BY score DESC)，导致对全体学生进行排名，而不是在每个班级内排名，完全曲解了题目意图。
3. 混淆 RANK(), DENSE_RANK(), ROW_NUMBER()：不解释为何选择特定排名函数，或在需要处理并列时错误地使用 ROW_NUMBER()，导致并列的学生被随机舍弃一个。
4. 用 WHERE 子句过滤窗口函数：写出 SELECT ..., RANK() ... AS rk FROM scores WHERE rk <= 5 这样的代码。这是语法错误，因为 WHERE 子句在窗口函数计算之前执行，必须使用 CTE 或子查询。
5. 对 NTILE 的误解：NTILE 会尽量均匀分配，但如果分区内的行数不能被 N 整除，那么前面的桶会比后面的桶多一个元素。例如 NTILE(5) 作用于 12 行，前 2 个桶会有 3 行，后 3 个桶会有 2 行。不了解这个细节可能导致边界判断错误。

工程实践与优化

• 索引是关键：对于此类查询，PARTITION BY 和 ORDER BY 的列 (class_id, score DESC) 建立复合索引是性能优化的第一步，也是最重要的一步。使用 EXPLAIN 查看执行计划，确保索引被有效利用，避免 Extra 字段出现 Using filesort。
• 执行计划分析：一个好的执行计划中，type 应该是 index 或 range，key 应该是我们创建的复合索引。Extra 字段如果显示 Using index，则表示实现了覆盖索引，性能最佳。
• 数据倾斜：如果某个班级的学生数量远超其他班级（例如，一个班有 100 万学生，其他班级只有几十个），PARTITION BY 会导致内存和计算资源向这个超大分区倾斜，可能引发单点瓶颈或内存溢出。在 OLAP 场景下，这需要用更专业的分布式计算框架（如 Spark）处理，或在数据建模时就考虑拆分超大班级。
• 处理并列的业务沟通：当 Top 20% 的边界上出现大量并列分数时，是全部取（可能超过 20%），还是截断（可能不公平）？这是一个业务决策。
  • 全部取：使用 RANK() 或 DENSE_RANK()，如解法 2。
  • 严格截断：使用 ROW_NUMBER()，但要明确告知业务方，并列者会被随机选择。
  • NTILE(5) 的行为是，如果并列的行跨越了桶的边界，它们会被分配到不同的桶中，可能导致部分并列者被舍弃。在面试中能指出这一点是加分项。

常见追问与延伸题目

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

   • 回答要点 1 (DB 内优化)：在亿级别数据下，即使有索引，实时计算窗口函数也可能非常慢，消耗大量 CPU 和内存。必须确保 (class_id, score DESC) 索引存在。可以考虑使用 EXPLAIN ANALYZE (MySQL 8.0+) 来查看实际执行时间和行数，定位瓶颈。
   • 回答要点 2 (架构级优化)：最好的方法是预计算。通过离线任务（如每日或每小时的 Spark/Flink 作业）计算好每个班级的排名，并将结果存储在一个专门的结果表或宽表中。线上查询直接读取这个预计算好的结果，实现 $O(1)$ 级别的查询速度。这体现了从 OLTP（在线事务处理）到 OLAP（在线分析处理）的思维转变。

2. 追问：在解法 2 中，如果要求严格保证选出的人数不超过班级总人数的 20%，如何修改 SQL？

   • 回答要点：这说明业务要求即使有并列，也不能超过名额。这时 RANK 就不合适了。
     • 方案一（随机选择）：将 RANK() 替换为 ROW_NUMBER()。ROW_NUMBER() OVER (PARTITION BY class_id ORDER BY score DESC) 会为并列的行分配不同的序号，从而严格控制数量。需要向面试官说明，这种方式对于并列的学生是不公平的，因为它会随机选择一个。
     • 方案二（保留并列但截断）：可以先用 DENSE_RANK() 得到排名，再用 ROW_NUMBER() 在同名次内再编号，实现一个稳定的、可复现的截断。但最符合该要求的还是直接用 ROW_NUMBER()。

3. 追问：如果换成 ClickHouse 或者 TiDB 这样的分布式数据库，这个查询有什么不同？

   • 回答要点 1 (通用性)：SQL 语法层面基本一致。NTILE, RANK 等标准窗口函数在这些现代分析型或分布式数据库中都有很好的支持。
   • 回答要点 2 (分布式执行)：关键区别在于数据分布和计算下推。
     • TiDB/OceanBase (分布式关系型数据库)：查询会被拆分。PARTITION BY class_id 会触发数据混洗（Shuffle），TiDB 会根据 class_id 将数据发送到不同的计算节点进行局部排名，最后汇总。如果 class_id 是表的分片键（SHARDING KEY），则可以避免 Shuffle，性能会好很多。
     • ClickHouse (列式分析型数据库)：ClickHouse 对窗口函数的性能极高。它的分布式执行引擎也会做类似的数据 Shuffle。关键在于其列式存储和向量化执行，使得排序和计算都非常快。在 ClickHouse 中，这样的查询通常能以亚秒级的速度在海量数据上完成。能提到“列存”、“向量化执行”、“Shuffle”这些词，会展示你对不同数据库架构的理解深度。