求出每个商品的销量中位数。(窗口函数 / 自连接)

考察要点

这道题面试官想看你是否懂 SQL 中位数的标准计算方法，以及能否熟练运用现代 SQL 的窗口函数（特别是 ROW_NUMBER 和 COUNT OVER）来解决复杂的统计问题。同时，也考察你是否了解在不支持窗口函数的老版本数据库中，如何使用自连接或相关子查询等经典但性能较低的方法作为替代方案，从而体现你的 SQL知识广度和深度。

核心概念

本题的核心是在分组（每个商品）内寻找排序后的中间值。

1. 中位数 (Median)：将一组数值按大小顺序排列，居于中间位置的数。

   • 奇数个：若有 N 个数（N 为奇数），中位数为第 (N+1)/2 个数。
   • 偶数个：若有 N 个数（N 为偶数），中位数通常定义为中间两个数（第 N/2 个和第 N/2 + 1 个）的平均值。面试中需要和面试官确认定义，若无特殊说明，按平均值计算是标准答案。

2. 窗口函数 (Window Functions)：在与当前行相关的行集（窗口）上执行计算，不改变原始行数。是解决此类排名、分位数问题的首选。

   • ROW_NUMBER() OVER (PARTITION BY col1 ORDER BY col2): 在 col1 定义的分区内，按 col2 排序，为每行分配一个从 1 开始的连续排名。这是计算中位数的关键，因为它能唯一标识每一行，即使 col2 的值相同。
   • COUNT(*) OVER (PARTITION BY col1): 在 col1 定义的分区内，计算总行数。这对于判断分区内元素是奇数还是偶数至关重要。

3. 数据示例 假设我们有 sales 表：

   sale_id	product_id	quantity
   1	P1	10
   2	P1	20
   3	P1	30
   4	P2	5
   5	P2	15
   6	P2	25
   7	P2	35

   期望输出：

   product_id	median_quantity
   P1	20.0
   P2	20.0

   • P1 有 3 条记录 (10, 20, 30)，中位数是第 (3+1)/2 = 2 个，即 20。
   • P2 有 4 条记录 (5, 15, 25, 35)，中位数是第 4/2=2 个和第 4/2+1=3 个的平均值，即 (15+25)/2 = 20。

多种解法

解法 1：窗口函数（推荐，最优解）

此方法思路清晰，性能优秀，是现代数据库（MySQL 8.0+ / PostgreSQL / SQL Server）的标准解法。

• 思路：

  1. 使用 CTE（公用表表达式）增加临时列。
  2. 在 CTE 内部，使用 ROW_NUMBER() 对每个商品 (product_id) 的销量 (quantity) 进行排序并编号 (rn)。
  3. 同时，使用 COUNT(*) OVER() 计算每个商品的总销量笔数 (total_cnt)。
  4. 在主查询中，筛选出 rn 位于中间位置的行。中间位置通过 total_cnt 判断：
     • 奇数：rn = (total_cnt + 1) / 2
     • 偶数：rn 在 total_cnt / 2 和 total_cnt / 2 + 1 之间。
     • 一个通用的筛选条件是 rn IN (FLOOR((total_cnt + 1) / 2), CEIL((total_cnt + 1) / 2))。
  5. 最后，按 product_id 分组，并使用 AVG(quantity) 计算最终中位数。对于奇数情况，这只会对一个值求平均，结果不变；对于偶数情况，则会对两个中间值求平均。

• 版本：✅ MySQL 8.0+ / PostgreSQL / Oracle / SQL Server

• SQL 实现：

  sql

  ⧉⛶

   1WITH RankedSales AS (
   2    SELECT
   3        product_id,
   4        quantity,
   5        -- 为每个商品内的销量排序并编号
   6        ROW_NUMBER() OVER (PARTITION BY product_id ORDER BY quantity) AS rn,
   7        -- 计算每个商品的总销量笔数
   8        COUNT(*) OVER (PARTITION BY product_id) AS total_cnt
   9    FROM
  10        sales
  11)
  12SELECT
  13    product_id,
  14    AVG(quantity) AS median_quantity
  15FROM
  16    RankedSales
  17WHERE
  18    -- 定位到中间的一个或两个位置
  19    rn BETWEEN FLOOR((total_cnt + 1) / 2.0) AND CEIL((total_cnt + 1) / 2.0)
  20GROUP BY
  21    product_id;

• 复杂度：

  • 时间复杂度: $O(N \log N)$，主要开销在于窗口函数的排序操作。$N$ 是总行数。
  • 空间复杂度: $O(N)$，需要存储 CTE 的中间结果。

• 索引依赖：在 sales 表上创建复合索引 (product_id, quantity) 可以极大地优化性能，使数据库引擎能利用索引顺序，避免额外的排序（filesort）操作。

解法 2：自连接（兼容老版本，性能较差）

在不支持窗口函数的旧版 MySQL（如 5.7）中，可以使用自连接或相关子查询模拟排名，但性能会差很多。

• 思路： 对于 sales 表中的每一行 s1，我们通过自连接（或相关子查询）来计算：

  1. 有多少行的 quantity 小于等于 s1.quantity（leq_count）。
  2. 有多少行的 quantity 大于等于 s1.quantity（geq_count）。
  3. 该商品的总笔数 total_count。 如果一行 s1 满足 leq_count >= total_count / 2 且 geq_count >= total_count / 2，那么它就是中位数（或中位数之一）。最后对筛选出的行求平均值。

• 版本：✅ 所有 SQL 版本

• SQL 实现：

  sql

  ⧉⛶

   1SELECT
   2    s1.product_id,
   3    AVG(s1.quantity) AS median_quantity
   4FROM
   5    sales s1
   6JOIN
   7    sales s2 ON s1.product_id = s2.product_id
   8GROUP BY
   9    s1.product_id, s1.sale_id, s1.quantity
  10HAVING
  11    -- 小于等于当前值的数量 >= 总数的一半
  12    SUM(CASE WHEN s2.quantity <= s1.quantity THEN 1 ELSE 0 END) >= (COUNT(*) / 2.0)
  13    AND
  14    -- 大于等于当前值的数量 >= 总数的一半
  15    SUM(CASE WHEN s2.quantity >= s1.quantity THEN 1 ELSE 0 END) >= (COUNT(*) / 2.0)
  16GROUP BY
  17    s1.product_id;

  注意：上述 HAVING 子句的逻辑较为复杂，且在处理重复值时需要非常小心。这是一个更简洁但性能极差的变体，它对每个潜在的中位数行执行了两次子查询计数。

• 复杂度：

  • 时间复杂度: 近似 $O(N^2)$。对于每个商品分组，自连接的计算量是该组内行数的平方。
  • 空间复杂度: $O(N^2)$ 级别，取决于 JOIN 的中间结果集大小。

• 索引依赖： (product_id, quantity) 索引仍然有帮助，但无法从根本上改变其二次方级别的复杂度。

常见低分回答

1. 误用 AVG() 当作中位数：SELECT product_id, AVG(quantity) FROM sales GROUP BY product_id; 这是计算平均值，完全偏离题目。
2. 忘记处理分组：使用窗口函数但忘记 PARTITION BY product_id，导致计算的是全局中位数，而不是每个商品的中位数。
3. 使用 RANK() 或 DENSE_RANK()：当存在相同销量时，RANK() 会产生不连续的排名（如 1, 2, 2, 4），DENSE_RANK() 会产生重复的排名（如 1, 2, 2, 3）。这两种函数都会使基于行号定位中间位置的逻辑失效。ROW_NUMBER() (1, 2, 3, 4) 是唯一正确的选择。
4. 中位数定义处理不当：只考虑奇数情况（如 WHERE rn = (total_cnt + 1) / 2），在偶数情况下会得到错误或不精确的结果。
5. 在 WHERE 子句中使用窗口函数：SELECT ... FROM sales WHERE ROW_NUMBER() OVER (...) = 1; 这是非法的 SQL 语法。窗口函数只能在 SELECT 列表或 ORDER BY 子句中使用，必须通过 CTE 或子查询来对其结果进行过滤。

工程实践与优化

• 索引是性能的关键：对于解法 1，CREATE INDEX idx_prod_qty ON sales (product_id, quantity); 是最重要的优化。EXPLAIN 分析时，有此索引，Extra 字段应避免出现 Using filesort。
• 执行计划分析：
  • 优化的查询 (解法 1 + 索引)：EXPLAIN 会显示 type: index 或 range，key: idx_prod_qty。在 MySQL 8.0+ 中，Extra 字段会包含 Window func。
  • 未优化的查询 (解法 2)：EXPLAIN 会显示复杂的 JOIN 计划，rows 估算值会非常大，Extra 字段可能出现 Using temporary，表明性能瓶颈。
• 近似计算：在数据仓库或大数据场景（如 Hive, Spark SQL, ClickHouse），数据量可能达到 TB/PB 级别，计算精确中位数非常昂贵。此时可以采用近似计算函数，如 APPROX_PERCENTILE(quantity, 0.5)，它能以极高的性能提供一个误差可控的近似中位数。在面试中提及此点，能体现你对工程实践中性能与精度权衡的理解。
• 避免大事务：此查询是只读操作，通常不涉及事务问题。但在某些系统中，如果查询触发了大量 I/O 和 CPU，可能会长时间持有元数据锁，影响其他 DDL 操作。

常见追问与延伸题目

1. 追问：如果数据量增长 100 倍，你的窗口函数解法性能会怎样？如何进一步优化？

   • 回答要点 1 (性能瓶颈)：窗口函数解法的时间复杂度是 $O(N \log N)$，主要瓶颈在于排序。如果单个 product_id 的数据量变得极其巨大（例如，一个商品有数十亿条销售记录），那么即使有索引，对这个巨大分区的排序也会消耗大量内存和 CPU，甚至可能因为内存不足而使用磁盘临时文件（filesort），导致性能急剧下降。
   • 回答要点 2 (优化策略)：
     • 垂直分区/分表：如果业务允许，可以将超大 product_id 的数据拆分到独立的表中。
     • 预计算/物化视图：对于报表类需求，可以定期（如每天凌晨）运行此查询，将结果存储在一个汇总表中。这样实时查询时只需访问这个小得多的结果表。
     • 引入大数据方案：当单机 MySQL 无法承载时，应考虑将数据迁移到如 Spark、Presto、ClickHouse 等分布式计算平台。这些平台能将排序和聚合任务并行化到多台机器上，横向扩展计算能力。并可使用 approx_percentile 等近似函数获得秒级响应。

2. 追问：如果换成 PostgreSQL 或 Oracle，这道题有更简单的写法吗？

   • 回答要点：是的，PostgreSQL 和 Oracle 提供了更直接的内置函数来计算中位数，这体现了它们在统计分析功能上的强大支持。
     • PostgreSQL: 使用 percentile_cont 有序集聚合函数。cont 代表连续型，它会进行线性插值，完全符合中位数的标准定义。
     sql

     ⧉⛶

      1SELECT
      2    product_id,
      3    percentile_cont(0.5) WITHIN GROUP (ORDER BY quantity) AS median_quantity
      4FROM sales
      5GROUP BY product_id;

     • Oracle: 直接提供了 MEDIAN 聚合函数，语法最为简洁。
     sql

     ⧉⛶

      1SELECT product_id, MEDIAN(quantity) AS median_quantity
      2FROM sales
      3GROUP BY product_id;

     • 提及这些能展示你的数据库知识广度，知道不同系统的优劣势。

3. 追问：如果要求计算每个商品的“众数”（mode）而不是中位数，该如何实现？

   • 回答要点：众数是出现次数最多的数值。SQL 实现比中位数更直接，但同样适合用窗口函数。
   • 思路：
     1. 第一层 CTE：按 product_id 和 quantity 分组，用 COUNT(*) 计算每个销量的出现次数 freq。
     2. 第二层 CTE：使用窗口函数 RANK() OVER (PARTITION BY product_id ORDER BY freq DESC) 对频率进行排名。使用 RANK() 是因为可能存在多个众数（频率相同）。
     3. 主查询：筛选出排名为 1 的所有 quantity。
   • SQL 示例：
   sql

   ⧉⛶

    1WITH FreqCounts AS (
    2    SELECT product_id, quantity, COUNT(*) AS freq
    3    FROM sales
    4    GROUP BY product_id, quantity
    5),
    6RankedFreq AS (
    7    SELECT product_id, quantity, freq,
    8           RANK() OVER (PARTITION BY product_id ORDER BY freq DESC) as rk
    9    FROM FreqCounts
   10)
   11SELECT product_id, quantity AS mode_quantity
   12FROM RankedFreq
   13WHERE rk = 1;