如何在非O(n²)复杂度下添加COUNT()计算列并判定点击有效性？

我来帮你逐个拆解这两个数据库问题，都是日常开发里常见的性能优化和业务逻辑需求：

首先得说清楚：如果你用关联子查询（比如SELECT *, (SELECT COUNT(*) FROM table t2 WHERE t2.group_col = t1.group_col) FROM table t1），这种写法会对原表的每一行都执行一次子查询，数据量大的时候直接就变成O(n²)的时间复杂度，慢到离谱。

推荐两种高效方案，时间复杂度都能控制在O(n log n)级别，完全避开n²的陷阱：

方案1：用窗口函数（最推荐，代码简洁性能优） #

窗口函数可以在一次扫描中完成分组统计，不需要额外的关联操作。比如你要给每行添加同一分组下的记录数，直接用COUNT() OVER (PARTITION BY 分组列)就行：

SELECT 
    *,
    COUNT(*) OVER (PARTITION BY group_column) AS group_count
FROM your_table;

• 原理：数据库会按group_column把数据分组，一次性算出每个分组的总数，再把结果匹配到对应的行，全程只需要一次全表（或索引）扫描，性能甩子查询几条街。

方案2：先聚合再关联（兼容老版本数据库） #

如果你的数据库不支持窗口函数（比如MySQL 5.7及以前），可以先通过GROUP BY预计算每个分组的总数，再用LEFT JOIN关联回原表：

SELECT 
    t1.*,
    t2.group_count
FROM your_table t1
LEFT JOIN (
    SELECT group_column, COUNT(*) AS group_count
    FROM your_table
    GROUP BY group_column
) t2 ON t1.group_column = t2.group_column;

• 原理：先花一次聚合查询拿到分组统计结果（O(n)或O(n log n)），再通过关联匹配到原表，整体效率远高于O(n²)的子查询写法。

先明确核心逻辑：我们需要先从LinkId里提取域名，然后统计每个用户（Email）对同一域名的点击次数——如果该域名下的点击≥2次，那这些点击都算无效；如果只有1次，就是有效。

下面以MySQL为例给出实现，其他数据库可以调整域名提取的函数适配：

SELECT 
    Email,
    LinkId,
    ClickTime,
    -- 提取域名：假设LinkId是完整URL，取协议后的主机部分
    SUBSTRING_INDEX(SUBSTRING_INDEX(LinkId, '/', 3), '://', -1) AS domain,
    -- 标记有效性：同一用户同一域名点击数≥2则无效
    CASE 
        WHEN COUNT(*) OVER (PARTITION BY Email, SUBSTRING_INDEX(SUBSTRING_INDEX(LinkId, '/', 3), '://', -1)) >= 2 
        THEN '无效' 
        ELSE '有效' 
    END AS is_valid
FROM clicks;

几个细节补充： #

1. 域名提取适配：如果你的LinkId直接存的是域名（比如example.com），那直接用LinkId作为分组列就行，不用提取；如果URL格式复杂，比如带端口号，可以用正则函数（比如MySQL的REGEXP_SUBSTR）来精准提取。
2. 不同业务逻辑的调整：如果你的需求是「第一次点击有效，后续同域名点击无效」，而不是所有同域名点击都无效，可以用行号函数来实现：

SELECT 
    Email,
    LinkId,
    ClickTime,
    SUBSTRING_INDEX(SUBSTRING_INDEX(LinkId, '/', 3), '://', -1) AS domain,
    CASE 
        WHEN ROW_NUMBER() OVER (PARTITION BY Email, domain ORDER BY ClickTime) > 1 
        THEN '无效' 
        ELSE '有效' 
    END AS is_valid
FROM clicks;

这里用ROW_NUMBER()按点击时间排序，给每个用户的同域名点击编序号，序号>1的就是后续点击，标记为无效。

内容的提问来源于stack exchange，提问作者James Stott