有序分组

我们知道,SQL 延用了数学上的无序集合概念,所以 SQL 的分组并不关注待分组集合中成员的次序。我们前面讨论等值分组和非等值分组的时候,也都没有关注过这个问题,分组规则都是建立在成员取值本身上。但如果以有序集合作为运算对象时,那就必须考虑成员次序对分组的影响了,而且,现实业务中有大量的有序分组应用场景。

首先是序号分组。
一个简单的例子:将一个班的学生平均分成三份(假定人数能被 3 整除)。按我们所说的分组定义,这也可以看成是一种分组,但这个运算在 SQL 不能直接写出来,因为分组依据和成员取值没有关系。
如果 SPL 中 Lambda 语法的 #符号,这个问题就很容易解决了。

A.group( (#-1)*3\A.len() )		// 按序号分成前1/3,中1/3,后1/3
A.group( (#-1)%3 )			// 还可以按序号每三个中取一个构成分组子集

这也是个关注分组子集而不关注聚合值的运算。
用 SQL 实现这个运算会比较麻烦,需要先用子查询造出一个序号,然后再执行类似的动作。

这个例子中其实还没有真正关注成员的次序,只是说明了序号的作用,待分组集合的成员是其它次序时也可以得到可用的结果。
我们再看更多例子。
处理文本日志时,有些日志的基本单位不是 1 行,而可能是 3 行,即每个事件总是写出 3 行文本,这并不是多罕见的情况。对付这种日志时,就需要把文本每 3 行拆成一个分组子集,然后针对每个子集再进行详细的分析处理。这时就分组的正确性依赖于待分组集合中成员(文本日志的行)的次序了。

入学考试后,把学生按成绩排序来做蛇行分班,即名次 1,4,5,8,…在一个班,而 2,3,6,7,…在另一个班,这样能保证两个班的平均名次相同。这个分组运算用 SPL 利用序号很容易写出来:

A.sort@z(score).group(#%4<2)

这里用的分组键值不再是常见的普通数值,而是一个布尔量,相当于按“真“值和“假”值分成两个组,真值对应第一个班,假值对应另一个班。本质上讲,这还是个等值分组,只是用到的分组键值可以是任意泛型。
显然,这个分组的正确性也严重依赖于待分组集成的成员次序。
顺便说一句,这还是一个只关注分组子集而不关心聚合值的例子。

按序号分组在很多情况下就是用序号来计算出分组键值,然后就变成普通的等值分组了。那么有没有不能简单地转换成等值分组的情况呢?
值变化分组就是一种。
有一组婴儿出生记录,是按出生次序排序的,我们现在关心连续出生的同性别婴儿数量超过 5 的有多少批?
简单想,这就是先分组,把连续出生的性别相同的婴儿分到一组,然后计算每组计数值,再数出有几个大于 5 的。后两步很简单,问题是怎么分组?
直接按婴儿性别分组当然是不对的,必须考虑次序。依次扫描记录,当婴儿性别发生变化时则产生一个新组。这种分组显然没法直接用等值分组做出来了。
SPL 提供了有序分组方法,很容易实现这种分组运算,即当分组键值发生变化时就产生一个新的分组。

A.group@o(gender).count(~.len()>5)		// @o选项表示分组值变化时将产生新分组。

用 SQL 就麻烦很多,需要先造出中间标志来生成组的序号,大概是这样

SELECT COUNT(*) FROM
    (SELECT ChangeNumber FROM
        (SELECT SUM(ChangeFlag) OVER (ORDER BY birthday) ChangeNumber FROM
            (SELECT CASE WHEN gender=LAG(gender) OVER ( ORDER BY birthday) THEN 0 ELSE 1 END ChangeFlag FROM A))
    GROUP ChangeNumber HAVING COUNT(*)>5)

这样的 SQL,看懂都不是很容易的。而且必须借助 birthday 这种字段来形成次序,而前述的有序分组写法在原数据有序时根本用不着这个信息。

这种情况同样可能出现在文本分析中。每个用户事件的日志可能多行,而且行数不确定,但写日志时会在每个行开始处写上用户号。这样我们可以按这个用户号进行有序分组,它变化时就说明是另一个用户的事件了。
即使是普通的等值分组,如果事先知道原集合对分组键值有序,也可以使用这种方案来实施,这将获得更高的性能,比数据库常用的 HASH 分组方案要快得多,而且特别适合大数据遍历的情况。

还有条件变化分组。
我们经常用来举例的问题:一支股票最长连续上涨了多少天?
这个问题当然可以直接遍历去解决,不过我们现在用分组的思路来处理,至少在 SQL 体系下只能这么做(严格些说,这是目前找到的最简单可行的办法)。
将股票收盘价按日期排序,然后将连续上涨的日期分到同一组,这样只要考虑哪一组成员数最多即可。更明确地说,就是当某天上涨了,就把这一天和前一天分到一个组中,某天下跌了,则产生一个新组。
用 SQL 实现这个思路,同样需要用中间标志和变量来生成组序号:

SELECT MAX(ContinuousDays) FROM
    (SELECT COUNT(*) ContinuousDays FROM
        (SELECT SUM(RisingFlag) OVER (ORDER BY TradingDate ) NoRisingDays FROM
            (SELECT TradingDate,
                CASE WHEN ClosingPrice>LAG(ClosingPrice) OVER (ORDER BY TradingDate THEN 0 ELSE 1 END) RisingFlag
            FROM A))
        GROUP BY NoRisingDays)

SPL 有专门的有序分组方法以及相应的 Lambdba 语法,这个运算就很简单了:

A.sort(TradingDate).group@i(ClosingPrice<ClosingPrice[-1]).max(~.len())			//选项@i表示当条件成立时产生新分组

虽然实现思路和 SQL 完全一样,但写出来是分步的,而不是一个多层嵌套语句,书写和理解都要容易得多。

同样地,这种情况也会在文本分析中出现。不确定行数的日志中,有时会在事件开始时写一个标志串,当扫描到这个标志串的时候就产生一个新的分组,有序分组的条件可设定为当前扫描行和指定文字相同,这样就能保证同一事件的日志信息在同一个组中。

后两种有序分组的情况,理论上当然也可以转换成等值分组来处理(用 SQL 就要这么做,这也能从另一个侧面说明 SQL 运算体系的完备性),但确实是相当麻烦的,所以我们一般不把它再当成等值分组来处理了。