实现一个简单的推荐：基于共同购买（co-purchase）求最相似商品 Top 5。

考察要点

这道题面试官想看你是否掌握复杂查询的构建能力、窗口函数的使用以及SQL 性能优化的思维。具体来说，考察点包括：

1. 自连接（Self-Join）：通过将一张表与自身连接，来处理表内实体之间的关系，这是解决“共同”类问题的核心。
2. 分组聚合（GROUP BY）：用于计算共现次数（co-occurrence），即相似度得分。
3. 窗口函数（Window Functions）：特别是 ROW_NUMBER() 或 RANK()，用于在每个商品的分组内进行排序，并筛选出 Top N。
4. SQL 优化意识：能否意识到自连接在大数据量下的性能瓶颈，并提出索引、预计算等优化策略。

核心概念

本题的核心是计算商品之间的“相似度”，并按相似度对每个商品进行推荐。我们首先需要定义相似度。

1. 定义相似度：共购次数 最直观的相似度是“共同购买的用户数”。如果商品 A 和商品 B 同时被 100 个不同的用户购买过，我们就认为它们的相似度得分为 100。

2. 数据模型 假设我们有一张订单详情表 order_items。为了简化问题，我们只关心哪个用户购买了哪个商品，可以抽象为一张 purchases 表。

• purchases 表结构

  sql

  ⧉⛶

   1CREATE TABLE purchases (
   2    user_id INT,
   3    item_id VARCHAR(20),
   4    -- 为了简化，假设 user_id 和 item_id 组合唯一
   5    PRIMARY KEY (user_id, item_id)
   6);

• 示例数据 | user_id | item_id | | :------ | :------ | | 1 | A | | 1 | B | | 1 | C | | 2 | A | | 2 | C | | 3 | B | | 3 | D |

3. 核心思路：自连接 + 分组计数 要找出共同购买的商品对，需要对 purchases 表进行自连接。

 1graph TD
 2    subgraph user_id = 1
 3        A --- B
 4        A --- C
 5        B --- C
 6    end
 7    subgraph user_id = 2
 8        A --- C
 9    end
10    subgraph user_id = 3
11        B --- D
12    end

通过 ON p1.user_id = p2.user_id，我们可以找到同一用户购买的所有商品对。 例如，对于 user_id = 1，我们会得到 (A,B), (A,C), (B,C) 以及它们的翻转对和自身对。

关键过滤条件：p1.item_id < p2.item_id 这个条件非常重要，它有三个作用：

1. 去重：避免同时计算 (A, B) 和 (B, A)，使计算量减半。
2. 去自反：避免 (A, A) 这种无意义的对自己推荐。
3. 性能：减少了中间结果集的大小。

之后，通过 GROUP BY p1.item_id, p2.item_id 并使用 COUNT(DISTINCT p1.user_id) 即可计算出每对商品 (item1, item2) 的共购用户数。

4. 核心工具：窗口函数 ROW_NUMBER() 为了给每个商品找出 Top 5 相似商品，我们需要对相似度得分进行分组排名。 ROW_NUMBER() OVER (PARTITION BY item_id ORDER BY similarity DESC)

• PARTITION BY item_id：将数据按商品 ID 分成多个“窗口”，在每个窗口内独立排名。
• ORDER BY similarity DESC：在每个窗口内，按相似度得分从高到低排序。
• ROW_NUMBER()：为排好序的每一行分配一个从 1 开始的连续排名。

多种解法

假设有 purchases(user_id, item_id) 表。

解法 1：使用窗口函数（推荐，主流方案）

这种解法思路清晰，利用现代 SQL 特性，是目前最优雅、最高效的纯 SQL 解法。

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

• 思路：

  1. 自连接 purchases 表，使用 p1.item_id < p2.item_id 技巧找出无重复的商品对。
  2. 按商品对分组，计算共购用户数（similarity）。
  3. 由于步骤 1 的结果是不对称的（只有 (A,B) 没有 (B,A)），使用 UNION ALL 将其扩展为完整的相似度矩阵。
  4. 使用 ROW_NUMBER() 窗口函数对每个商品的相似商品进行排名。
  5. 筛选出排名前 5 的结果。

• SQL 实现：

  sql

  ⧉⛶

   1WITH
   2-- 步骤1 & 2: 计算非对称的商品共购对及次数
   3CoPurchasePairs AS (
   4    SELECT
   5        p1.item_id AS item1,
   6        p2.item_id AS item2,
   7        COUNT(DISTINCT p1.user_id) AS similarity
   8    FROM
   9        purchases p1
  10    JOIN
  11        purchases p2 ON p1.user_id = p2.user_id AND p1.item_id < p2.item_id
  12    GROUP BY
  13        p1.item_id, p2.item_id
  14),
  15-- 步骤3: 构建完整的对称相似度矩阵
  16FullSimilarity AS (
  17    SELECT item1, item2, similarity FROM CoPurchasePairs
  18    UNION ALL
  19    SELECT item2 AS item1, item1 AS item2, similarity FROM CoPurchasePairs
  20),
  21-- 步骤4: 使用窗口函数进行分组排名
  22RankedSimilarity AS (
  23    SELECT
  24        item1,
  25        item2,
  26        similarity,
  27        ROW_NUMBER() OVER (PARTITION BY item1 ORDER BY similarity DESC, item2 ASC) as rnk -- item2 ASC 保证排序稳定性
  28    FROM
  29        FullSimilarity
  30)
  31-- 步骤5: 筛选出每个商品的 Top 5
  32SELECT
  33    item1 AS item_id,
  34    item2 AS similar_item_id,
  35    similarity
  36FROM
  37    RankedSimilarity
  38WHERE
  39    rnk <= 5
  40ORDER BY
  41    item_id, similarity DESC;

• 复杂度：

  • 时间复杂度：主要取决于自连接和分组聚合。如果 purchases 表有 N 行，每个用户平均购买 K 个商品，自连接产生的中间行数约为 $O(N \cdot K)$。后续排序复杂度为 $O(M \log M)$，其中 M 是商品对的数量。这是一个计算密集型操作。
  • 空间复杂度：需要存储 CTE 的中间结果，空间消耗较大。

• 索引依赖：在 purchases 表上建立 (user_id, item_id) 的复合索引至关重要，可以极大地加速 JOIN 操作。

解法 2：使用 LATERAL JOIN（更符合直觉的现代方案）

LATERAL JOIN (在 SQL Server 中称为 APPLY) 可以为外部查询的每一行执行一次子查询，非常适合 Top-N per group 的问题。

• 版本：✅ MySQL 8.0.14+ / PostgreSQL 9.3+；❌ MySQL 5.7 及早期版本不支持。

• 思路：

  1. 从 purchases 表中获取所有不重复的商品列表。
  2. 对于列表中的每一个商品 i，使用 LATERAL JOIN 执行一个子查询。
  3. 子查询计算商品 i 与其他所有商品的共购次数，并直接 ORDER BY ... LIMIT 5 取出前 5 名。

• SQL 实现：

  sql

  ⧉⛶

   1SELECT
   2    items.item_id,
   3    similar_items.similar_item_id,
   4    similar_items.similarity
   5FROM
   6    (SELECT DISTINCT item_id FROM purchases) AS items
   7CROSS JOIN LATERAL (
   8    SELECT
   9        p2.item_id AS similar_item_id,
  10        COUNT(DISTINCT p1.user_id) AS similarity
  11    FROM
  12        purchases p1
  13    JOIN
  14        purchases p2 ON p1.user_id = p2.user_id
  15    WHERE
  16        p1.item_id = items.item_id -- 关联外部查询的当前商品
  17        AND p2.item_id != items.item_id
  18    GROUP BY
  19        p2.item_id
  20    ORDER BY
  21        similarity DESC, p2.item_id ASC
  22    LIMIT 5
  23) AS similar_items
  24ORDER BY
  25    items.item_id, similar_items.similarity DESC;

• 复杂度：

  • 时间复杂度：对于 I 个独立商品，会执行 I 次子查询。如果数据库优化器不能有效处理，其总成本可能高于解法 1。但其逻辑清晰，且避免了 UNION ALL 和显式的窗口函数。
  • 空间复杂度：中间结果集较小，因为 LIMIT 5 在子查询内部就完成了筛选。

• 索引依赖：需要 (item_id, user_id) 和 (user_id, item_id) 两个方向的索引来优化内外两个表的连接。

解法 3：兼容老版本（MySQL 5.7）的模拟排名

在没有窗口函数的旧版本 MySQL 中，通常使用用户变量或自连接来模拟排名，但这些方法复杂、易错且性能较差。

• 版本：✅ MySQL 5.7 (不推荐)
• 思路：使用用户变量。先将所有相似度计算出来并排序，然后在扫描过程中用变量来模拟 ROW_NUMBER() 的分区和计数。
• SQL 实现：
  sql

  ⧉⛶

   1-- 步骤1和2与解法1相同，先创建完整的相似度矩阵（这里用临时表）
   2CREATE TEMPORARY TABLE FullSimilarity AS
   3SELECT item1, item2, similarity FROM (
   4    SELECT p1.item_id AS item1, p2.item_id AS item2, COUNT(DISTINCT p1.user_id) AS similarity
   5    FROM purchases p1 JOIN purchases p2 ON p1.user_id = p2.user_id AND p1.item_id < p2.item_id
   6    GROUP BY p1.item_id, p2.item_id
   7) AS CoPurchasePairs
   8UNION ALL
   9SELECT item2, item1, similarity FROM (
  10    SELECT p1.item_id AS item1, p2.item_id AS item2, COUNT(DISTINCT p1.user_id) AS similarity
  11    FROM purchases p1 JOIN purchases p2 ON p1.user_id = p2.user_id AND p1.item_id < p2.item_id
  12    GROUP BY p1.item_id, p2.item_id
  13) AS CoPurchasePairs2;
  14
  15-- 步骤3: 使用用户变量模拟 ROW_NUMBER()
  16SELECT
  17    item_id,
  18    similar_item_id,
  19    similarity
  20FROM (
  21    SELECT
  22        item1 AS item_id,
  23        item2 AS similar_item_id,
  24        similarity,
  25        @rn := IF(@current_item = item1, @rn + 1, 1) AS rnk,
  26        @current_item := item1
  27    FROM
  28        (SELECT @rn := 0, @current_item := '') AS init,
  29        FullSimilarity
  30    ORDER BY
  31        item1, similarity DESC, item2 ASC
  32) AS ranked
  33WHERE
  34    rnk <= 5;

• 注意：这种用户变量的用法在 MySQL 8.0 中已被官方声明为不推荐，其执行顺序无法保证，可能在未来版本失效。面试中可以提及此法作为历史方案，但强调其风险和局限性。

常见低分回答

1. 忘记排除自身和重复对：JOIN purchases p2 ON p1.user_id = p2.user_id。这会导致一个商品与自身匹配，并且 (A,B) 和 (B,A) 被重复计算，结果不准且效率低下。
2. 全局 Top 5 而非分组 Top 5：在计算完所有商品对的相似度后，直接 ORDER BY similarity DESC LIMIT 5。这只会返回全局最相似的 5 对商品，而不是“为每个商品”推荐。
3. 错误使用 COUNT：使用 COUNT(*) 而不是 COUNT(DISTINCT user_id)。如果一个用户在一次会话中多次购买同一商品（例如，purchases 表记录的是订单行项目），COUNT(*) 会夸大共购关系。COUNT(DISTINCT user_id) 才准确反映了共购的用户基数。
4. 在 WHERE 子句中使用 HAVING 的逻辑：写出 ... GROUP BY item1, item2 HAVING rnk <= 5。这是错误的，因为 HAVING 在窗口函数执行之前进行过滤，rnk 此时还不存在。必须在子查询或 CTE 中生成排名列，然后在外部查询的 WHERE 子句中过滤。
5. 对 NULL 的处理不当：如果 user_id 或 item_id 可能为 NULL，JOIN 和 GROUP BY 的行为会受影响。虽然本题场景下通常不为 NULL，但在其他问题中忽略 NULL 是常见错误。

工程实践与优化

• 性能瓶颈：核心瓶颈在于 purchases 表的自连接。如果 purchases 表有数十亿行，这个 SQL 查询在生产数据库上是不可行的，它会消耗大量 CPU 和 IO，甚至锁住表，导致数据库崩溃。
• 解决方案：离线计算 + 服务化
  1. 批处理系统：这种计算密集型任务应使用离线大数据处理框架（如 Spark、Flink 或 Hive）来完成。这是一个经典的 MapReduce 问题（WordCount 的变种：ItemPairCount）。计算逻辑与 SQL 类似，但可以水平扩展到上百台机器。
  2. 预计算与物化：每天或每小时运行一次批处理任务，将计算出的 Top 5 相似商品结果存储到一个专门的结果表（物化视图）中，例如 item_similarity(item_id, similar_item_id, rank, score)。
  3. 在线服务：线上推荐服务直接查询这个预计算好的结果表，查询非常简单快速：SELECT similar_item_id, score FROM item_similarity WHERE item_id = ? ORDER BY rank。这能做到毫秒级响应。
• 执行计划分析 (EXPLAIN)
  • 对于解法 1，关注 EXPLAIN 的输出。JOIN 的 type 应该是 ref（使用索引），key 应该指向 (user_id, item_id) 索引。Extra 字段如果出现 Using temporary; Using filesort，说明中间结果集很大，需要磁盘临时表和文件排序，是严重的性能问题。
• 索引策略
  • 必须在 purchases(user_id, item_id) 上创建复合索引。user_id 在前，因为它是 JOIN 的条件，可以快速定位到同一用户的所有购买记录。
• 增量计算
  • 对于超大规模数据，每次都全量计算成本高昂。可以考虑增量计算：只计算新产生的购买数据带来的相似度变化，并更新到全量结果中。这需要更复杂的算法和架构。

常见追问与延伸题目

1. 追问：如果 purchases 表数据量增长 100 倍，达到百亿级别，这条 SQL 会怎么样？你如何设计架构来解决这个问题？

   • 回答要点 1 (SQL 的末日)：直接表明这条 SQL 将无法在任何单机关系型数据库上执行。它会因为巨大的中间结果集（百亿 x 百亿级别）耗尽内存、磁盘空间和 CPU 时间，并可能导致数据库长时间无响应。
   • 回答要点 2 (架构设计)：
     • 数据流：将用户行为日志（购买记录）实时采集到消息队列（如 Kafka）。
     • 离线计算：使用分布式计算框架（如 Spark）消费 Kafka 数据。编写 Spark 作业实现相同的自连接、分组、排序逻辑。Spark 的分布式内存计算和数据分区能力可以轻松处理百亿级数据。
     • 结果存储：将计算出的 Top-N 相似度结果存储在高性能的 KV 存储（如 Redis）或列式存储（如 HBase/Cassandra）中，键为 item_id，值为一个包含 Top-N 相似商品列表的 JSON 或 protobuf 对象。
     • 在线查询：推荐服务通过 API 查询 Redis/HBase，根据 item_id 在 $O(1)$ 时间内获取推荐列表，实现低延迟响应。
     • 调度：整个离线计算流程由 Airflow 或 Azkaban 等工作流调度系统按天或按小时调度执行。

2. 追问：除了共购次数，还有哪些更高级的相似度度量？如何用 SQL 实现？

   • 回答要点 1 (Jaccard 相似度)：Jaccard 相似度 = (A和B的交集) / (A和B的并集)。在我们的场景里，即 COUNT(同时购买A和B的用户) / COUNT(购买过A或购买过B的用户)。它能惩罚热门商品，因为热门商品的 并集 分母会很大。
   • 回答要点 2 (SQL 实现 Jaccard)：需要额外计算每个商品的总购买用户数。
     sql

     ⧉⛶

      1-- 步骤1: 计算每个商品被多少独立用户购买
      2WITH ItemUserCounts AS (
      3    SELECT item_id, COUNT(DISTINCT user_id) AS user_count
      4    FROM purchases
      5    GROUP BY item_id
      6),
      7-- 步骤2: 计算共购次数 (同解法1)
      8CoPurchasePairs AS (
      9    SELECT p1.item_id AS item1, p2.item_id AS item2, COUNT(DISTINCT p1.user_id) AS intersection_count
     10    FROM purchases p1 JOIN purchases p2 ON p1.user_id = p2.user_id AND p1.item_id < p2.item_id
     11    GROUP BY p1.item_id, p2.item_id
     12)
     13-- 步骤3: 合并计算 Jaccard
     14SELECT
     15    cp.item1,
     16    cp.item2,
     17    cp.intersection_count / (iuc1.user_count + iuc2.user_count - cp.intersection_count) AS jaccard_similarity
     18FROM CoPurchasePairs cp
     19JOIN ItemUserCounts iuc1 ON cp.item1 = iuc1.item_id
     20JOIN ItemUserCounts iuc2 ON cp.item2 = iuc2.item_id;
     21-- 后续的排序和筛选逻辑与之前类似

   • 回答要点 3 (余弦相似度)：可以提及更复杂的余弦相似度，将用户向量化，但这通常很难用纯 SQL 高效实现，更适合在 Spark 中使用 MLlib 等库来计算。

3. 追问：如果我把 p1.item_id < p2.item_id 改成 p1.item_id != p2.item_id，会对查询有什么影响？

   • 回答要点 1 (结果正确性)：结果在逻辑上仍然可以做对，但计算过程会变得低效。!= 会同时产生 (A, B) 和 (B, A) 两个组合。
   • 回答要点 2 (性能影响)：
     • 计算量加倍：GROUP BY 需要处理的商品对数量会翻倍，导致聚合计算的开销增大。
     • 需要额外处理：在后续步骤中，你得到的相似度矩阵已经是对等的，无需再做 UNION ALL。但前期的计算浪费是实实在在的。
     • 最终结论：p1.item_id < p2.item_id 是一个非常关键的优化，它利用对称性将计算量减半，是衡量候选人是否细心和具备优化思维的重要标志。而 != 虽然直观，但不是最优实践。