ARTICLE · INTELLIGENCE

战地情报 · 详情页

来自尧图项目组的一线实战观察与深度解析

连续出现三次,不是总共出现三次:修正一道SQL题里的错误分组

连续出现三次,不是总共出现三次:修正一道SQL题里的错误分组

旧草稿里有一道“连续数字”的SQL题:从Logs中找出连续出现至少三次的值。

先看这两串记录,按id从小到大排:

1、1、1 找到1 1、2、1、2、1 找不到1

两边的1都出现了三次,但第二串每次都被2隔开。所以只写GROUP BY num,再判断COUNT(*)>=3,数到的是总次数,还不知道三次是不是挨着。

LeetCode 180题面里,id是从1开始自增的主键,num是varchar。本文按唯一id升序看相邻记录,数字1、2表示字符串值;另外用id有缺口的样例说明“记录相邻”的扩展,不把编号相差1当成必要条件。业务若要求时间间隔或同一用户内连续,需要另定规则。

先试一下旧稿里的式子

原草稿用的是num减去这个值内部的行号:

这里先把“值内行号”理解成:这是这个值第几次出现。SQL的窗口函数写法稍后再解释,先用三行数据看看这个减法能不能把一段放在一起。

SELECT DISTINCT num AS ConsecutiveNums FROM ( SELECT num, num - ROW_NUMBER() OVER (PARTITION BY num ORDER BY id) AS grp FROM Logs ) AS numbered GROUP BY num, grp HAVING COUNT(*) >= 3;

它到底会把哪些行分到一起?不用大样例,只放三行1,就能算出来。

num: 1 1 1 值内行号: 1 2 3 相减: 0 -1 -2

三个结果不同,GROUP BY num, grp把它们拆成三个只有一行的组,当然找不到三连。

这里不是少了DISTINCT。连续段里,行号每次增加,num却不动,差值也就每次改变。我们希望同一段贴上同一个标记,这个式子没做到。而且num是字符串,直接拿它做减法,还多了一次不需要的数值转换。

我们想留下的,究竟是哪一段?

看这七行:

位置: 1 2 3 4 5 6 7 值: 1 1 1 2 1 1 1

前面的三个1是一段,后面的三个1是另一段。希望前一段三行有共同标记,后一段三行也有共同标记,但两段别混在一起。

我们能看到两段,是因为眼睛扫过了中间那个2。想让查询也区分出来,就得把“中间夹了其他值”这件事留下来。

先不想SQL。我拿两个数记一下已经读过的记录:一个数所有记录,来什么都加1;另一个只数值为1的记录,看到1才加1。不是数连续的1有几个,而是从开头到现在总共见过几个1,遇到2也不清零。

读完前三行,两个数都是3。图里上面保留原记录,下面只把其中值为1的记录挑出来数,右边没读到的还不算。

再读第四行,是2。所有记录的数量变成4,值为1的仍只有三条。为什么第二个数没加?不是算法规定它暂停,而是我们又没读到一个1。

接着读第五行,是1。这是整张表的第五条记录,却是我们见到的第四个1;前面的三个1还算数,不因为中间来了2就忘掉。

现在只看值为1的行,把两个数记在一起:

全表位置: 1 2 3 5 6 7 1的次序: 1 2 3 4 5 6 两者相减: 0 0 0 1 1 1

相减到底数到了什么?读完前三条,3条全是1,所以3-3=0,没有夹进其他值。到了第五条,总共读了5条,其中4条是1,5-4=1,剩下的那一条就是刚才的2。

这就给两段1留下了不同标记。继续往后读两个1,两个数都会增加,但中间那条2仍只有一条,差值还是1。

前三个1每向后走一行,全表位置加1,1的出现次数也加1,相减还是0。

不只对1有效。换成别的值,也可以数“到现在一共读过多少条”和“其中多少条等于这个值”。同一个值连续来,两边一起加,差不变;隔了一条别的值后再来,差就增加。这才是我们拿这个差来分段的理由。

把两种编号写出来

刚才是我们手动数。ROW_NUMBER可以替我们按顺序给每行写上编号:不分区,按id排,就是“整张表第几条”,代码里叫global_pos;按num分区,分别在各个值内部按id排,就是“这个值第几次出现”,代码里叫value_pos。MySQL的ROW_NUMBER说明

“按num分区”是各个值分别编号,不是把同一值的多行压成一行。所以七条原记录都还在,只是每条旁边多了两个数:

idnum全局号值内号差值
11110
21220
31330
42413
51541
61651
71761

第四行的值2是它自己第一次出现,值内号从1开始。第五行又遇到1,它的值内号接着前面三个1继续到4,不是因为换了一段就重置为1。

注意上面的图一直在数1,所以在第四行只数1的结果仍为3;SQL表第四行的num是2,它写的是“2第几次出现”,所以value_pos是1。这两处回答的问题不同,不能把图中数1的3直接填到值2那一行。

但现在还有一个问题:这个差值能不能单独拿来分组?

不同值,可能算出同一个差

换成1、2、1、1。最长也只有两个1,没有任何三连。

num全局号值内号差值
1110
2211
1321
1431

后面三行的差都是1,但里面有一个2和两个1。只按差分组,就把不同值拼在一起,误数出了长度3。

所以分组要带上num。对于固定的num,差值能区分前后两段;再加num,才能防止别的值混进来。同一组必须同时满足“值相同”和“属于这个值的同一连续段”。

到这里再写完整查询

WITH numbered AS ( SELECT id, num, ROW_NUMBER() OVER (ORDER BY id) AS global_pos, ROW_NUMBER() OVER (PARTITION BY num ORDER BY id) AS value_pos FROM Logs ) SELECT DISTINCT num AS ConsecutiveNums FROM numbered GROUP BY num, global_pos - value_pos HAVING COUNT(*) >= 3;

WITH里的numbered先给每条记录加上两种行号。外层按num和差分组,COUNT数每段多长,HAVING留下至少三行的段。

最后还要DISTINCT:七行样例里,前后的两段1都合格,分组会给出两份1。但题目要的是符合条件的值,不是每个段分别报一次,所以最终只留一份1。

这用到MySQL 8.0的窗口函数,不能原样拿去MySQL 5.7执行。是否比自连接快,要看执行计划和数据;这里先把结果做对,没有比较性能。

自己放七行进去看看

在练习数据库的同一个会话中执行下面的完整SQL。它建临时表blog_runs_lab,不替换你已有的Logs。num明确为非NULL,采用二进制排序规则,便于让实验中的字符串相等含义固定下来。

CREATE TEMPORARY TABLE blog_runs_lab ( id INT PRIMARY KEY, num VARCHAR(16) CHARACTER SET utf8mb4 COLLATE utf8mb4_bin NOT NULL ); INSERT INTO blog_runs_lab VALUES (1,'1'),(2,'1'),(3,'1'),(4,'2'),(5,'1'),(6,'1'),(7,'1'); WITH numbered AS ( SELECT id, num, ROW_NUMBER() OVER (ORDER BY id) AS global_pos, ROW_NUMBER() OVER (PARTITION BY num ORDER BY id) AS value_pos FROM blog_runs_lab ) SELECT DISTINCT num AS ConsecutiveNums FROM numbered GROUP BY num, global_pos - value_pos HAVING COUNT(*) >= 3;

结果只有一行字符串1。可以把输入改成前面的1、2、1、1,再看结果是否为空。

如果id换成10、20、40,值仍是三个1,按记录顺序它们仍然相邻。全局行号是1、2、3,差仍为0;直接拿id减值内行号,差却变成9、18、37,又会拆开。这也是为什么这里写ROW_NUMBER,而不是觉得id看起来像行号就直接用它。

业务若允许NULL、大小写等价等不同字符串比较规则,分区和分组要按实际语义核对;下面的程序用精确字符串相等,不能代表任意排序规则。唯一id让本例的先后顺序明确,换成会并列的时间列时还要补确定顺序的键。

下面保留验证设计。正确查询、错误旧式和两个改错分组的对照都在隔离MySQL中检查过;这是本地验证,没有提交LeetCode。

附录:如何验证这份答案?

验证器没有再用另一份窗口SQL生成“标准答案”,而是用普通程序按id排序后逐行扫描:相同值延长当前段,值改变就重新计数,长度达到3时加入答案集合。

先检查空表、长度2和3、四连、分散重复、两个合格值、同值多段、id有缺口。再穷举长度0到5、值只取1与2的所有序列。这些不是随机碰运气,包含63种完整序列;连同8个固定样例,共71次输入验证。

固定样例和穷举集有重叠;71是运行次数,不是71种互不相同的输入,也不是对所有字符串和任意长度的证明。

每次把SQL返回值当作集合与扫描结果比较,不依赖输出顺序。旧错误查询在三连样例被检出;额外把global_pos换成id,在缺口样例也会得到错误结果。这证明我们的用例同时检查了“减错值”和“把记录顺序偷换成编号连续”两类错误。

另外对1、2、1、1故意只按差值分组,用MIN(num)取一个合法聚合输出,避免SQL语法检查先挡住它。错误查询返回1,正确答案为空;这检查的是“混合了不同值”的结果错误,不是把语法报错算作反例通过。

运行环境是新建临时目录里的隔离MySQL实例,只使用本机Unix socket,不碰现有数据库。结果与日志留在本地;服务进程结束后也要核对已退出。

RELATED READING

延伸阅读

更多一线实战笔记与深度复盘,助您持续精进