SQL 有序计算

什么是有序计算

       使用过 SQL 的朋友对计算字段都不会陌生，比如 firstname+lastname，year(birthday)，这些计算字段属于行内计算，不管表达式里用到的是单个字段，还是多个字段，使用的数据都在当前记录行内。有行内计算，对应的也就有跨行计算，如：第一名和第二名的差距；从 1 月到当前月份累计的销售额。按照成绩有序，才会有第一名、第二名的说法，累计操作同样基于有序数据，从第几个累加到第几个，这些基于有序集合的计算，就属于有序计算。行内计算关心的是每条数据自身的情况，而跨行的有序计算则关心有序数据的变化情况。

相邻记录引用

简单常见的有序计算是相邻记录引用，也就是在计算中要引用某种次序下的相邻记录。比如下面这些问题：

1、 股价每天的涨幅是多少（比上期）

按日期排序时，引用上一天的股价。

2、 前一天 + 当天 + 后一天的平均股价是多少（移动平均）

按日期排序时，引用前后两天的股价。

3、 多支股票数据，计算每支股票内的每日涨幅（分组内的比上期）

按股票分组，组内按日期排序，引用上一天股价。

接下来通过这几个例子研究下 SQL 如何实现这类有序计算。

早期 SQL 的解决方案

       早期的 SQL 没有窗口函数，引用相邻记录的方法是用 JOIN 把相邻记录拼到同一行。

       问题 1 写出来是这样的：

       SELECT day, curr.price/pre.price rate

       FROM (

              SELECT day, price, rownum row1

              FROM tbl ORDER BY day ASC) curr

       LEFT JOIN (

              SELECT day, price, rownum row2

              FROM tbl ORDER BY day ASC) pre

       ON curr.row1=pre.row2+1

       即将本表和本表做 JOIN，把前一天和当天作为连接条件，这样即可将前一天的股价和当天股价连接到同一行中，再用行内计算得到涨幅。一个很简单的问题必须使用子查询才能解决。

       再看问题 2，计算股价的移动平均，(前一天 + 当天 + 后一天)/3，同样是使用 JOIN 实现：

       SELECT day, (curr.price+pre.price+after.price)/3 movingAvg

       FROM (

              SELECT day, price, rownum row1

              FROM tbl ORDER BY day ASC) curr

       LEFT JOIN (

              SELECT day, price, rownum row2

              FROM tbl ORDER BY day ASC) pre

       ON curr.row1=pre.row2+1

       LEFT JOIN (

              SELECT day, price, rownum row3

              FROM tbl ORDER BY day ASC) after

       ON curr.row1=after.row3-1

       多取一天，就多 JOIN 一个子查询，试想，如果要计算前 10 天 ~ 后 10 天的移动平均，那需要写 20 个 JOIN，这种语句能写死人。

       再看更复杂一些的问题 3，股价表里有多支股票时，增加 code 字段区分不同的股票，那它的涨幅就要限定在某支股票的分组内：

       SELECT code, day ,currPrice/prePrice rate

       FROM(

              SELECT code, day, curr.price currPrice, pre.price prePrice

              FROM (

                     SELECT code, day, price, rownum row1

                     FROM tbl ORDER BY code, day ASC) curr

              LEFT JOIN (

                     SELECT code, day, price, rownum row2

                     FROM tbl ORDER BY code, day ASC) pre

              ON curr.row1=pre.row2+1 AND curr.code=pre.code

       )

       这里着重看两个地方：单表排序时，一定要增加股票代码，形成组合排序 code,day，code 还必须要在前面，这不难理解，先把一支股票的数据放在一起，然后这支股票组内数据再按照日期排序；数据排序好了还不算完，连接条件里也要加上股票代码相等，否则两个相邻的不同股票数据挨着，也会计算涨幅，但这是没意义的脏数据。

引入窗口函数

       从 2003 年起，SQL 标准中引入了窗口函数，带来了序的概念。有序计算变得容易了许多。上面的三个例子写起来就简单多了。

       问题 1，比上期。为了看清楚，把窗口函数拆成多行缩进，方便理解：

       SELECT day, price /

              LAG(price,1)

                     OVER (

                            ORDER BY day ASC

                     ) rate

       FROM tbl

       LAG 函数实现引用前面的记录。函数里的参数表示找前面第 1 条的 price，OVER 是窗口函数 LAG 的子句（每个窗口函数都有 OVER 子句），它的作用是定义待分析的有序集合，这个例子很简单，待分析集合按照日期有序。

       问题 2，移动平均。可以用取前边函数 LAG+ 取后面函数 LEAD 实现，但这里用 AVG 函数更可取，它能支持一个范围内（比如前后十条）的平均，LAG/LEAD 每次只能取到一个值:

       SELECT price,

              AVG(price) OVER (

                     ORDER BY day ASC

                     RANGE BETWEEN 1 PRECEDING AND 1 FOLLOWING

              ) movingAvg

       FROM tbl;

       这样取前后 n 条也容易了，只要改变 RANGE BETWEEN 里的范围。

       问题 3，分组内的有序计算。每支股票的所有股价是一个分组，窗口函数对它也做了支持：

       SELECT code, day, price /

              LAG(price,1)

                     OVER (

                            PARTITION BY code

                            ORDER BY day ASC

                     ) rate

       FROM tbl

       OVER 下的 PARTITION BY 子句描述了怎么划分分组，LAG 操作会限定在每个组内。这比之前的 JOIN 做法好了很多，描述分组很直观。；而 JOIN 做法是对数据做组合排序，虽然实际上也是分组的效果，但不容易理解到位。

序号定位

有序集合里找相邻记录，属于相对位置定位，有时我们还会找绝对位置的记录，比如计算每天股价与第一天上市价的涨跌差距：

       SELECT day, price-FIRST_VALUE(price) OVER (ORDER BY day ASC) FROM tbl

       或者，已经知道第 10 天是最高股价，计算出每天和它的差距：

       SELECT day, price-NTH_VALUE(price,10)OVER (ORDER BY day ASC) FROM tbl

       再看复杂点的情况，要定位的序号事先未知，需要根据数据计算出来：

       4、 股票按照股价排序，取出中间位置的股价（中位数）

       先看简单的单支股票的解法，按照股价排序后，中间位置还不知道在哪，这时得根据实际股票数据的数量算出中间位置：

       SELECT *

       FROM

              SELECT day, price, ROW_NUMBER()OVER (ORDER BY day ASC) seq FROM tbl

       WHERE seq=(

              SELECT TRUNC((COUNT(*)+1)/2) middleSeq FROM tbl)

       FROM 里的子查询用 ROW_NUMBER() 给每行生成序号，WHERE 里的子查询计算出中间序号。这个 SQL 里有两个注意事项，一是不能直接针对第一个子查询内部过滤，因为 WHERE 里不能使用同级 SELECT 中的计算字段，这是 SQL 执行顺序导致的；二是 WHERE 里的子查询结果一定是一行一列的单个值，这时能直接把它看成单个值和 seq 做等值比较。

       计算多支股票中位数的 SQL 如下：

       SELECT *

       FROM

              (SELECT code, day, price,

                     ROW_NUMBER() OVER (PARTITION BY code ORDER BY day ASC)seq                    FROM tbl) t1

       WHERE seq=(

              SELECT TRUNC((COUNT(*)+1)/2) middleSeq

              FROM tbl t2

              WHERE t1.code=t2.code)

       除了增加窗口函数里的PARTITION BY，还要注意计算中间位置时，查询条件也要限定在一支股票内。

       5、 每支股票最高价格日与前一天相比涨幅是多少

       这个问题需要两种排序方式组合起来定位，还是先看单支股票：

       SELECT day, price, seq, rate

       FROM (

              SELECT day, price, seq,

                     price/LAG(price,1) OVER (ORDER BY day ASC) rate

              FROM (

                     SELECT day, price,

                            ROW_NUMBER ()OVER (ORDER BY price DESC) seq

                     FROM tbl)

              )

       WHERE seq=1

       连续两层子查询都通过窗口函数给原始数据增加有用信息，ROW_NUMBER 把价格从高到低标上序号，通过 LAG 计算出每天的涨幅，最后过滤出价格最高的一天就可以了（seq=1）。

注意过滤出最高价格不能先于涨幅的计算，最高价格的前一天还不知道在哪里，先过滤掉，后面就算不出来涨幅了。

       前面已经有几个针对分组做有序计算的例子了，这个题就不给出最终答案了，读者有兴趣可以自己尝试写写怎么得出多支股票最高价时的涨幅。

有序分组

       有序信息还可以用于分组。看这个例子：

       6、 一支股票最多连续上涨过几天。

       这个问题有点难想了。基本的思路是把按日期有序的股票记录分成若干组，连续上涨的记录分成同一组，也就是说，某天的股价比上一天是上涨的，则和上一天记录分到同一组，如果下跌了，则开始一个新组。最后看所有分组中最大的成员数量，也就是最多连续上涨的天数。

这种分组比较特殊，和记录的次序有关，而 SQL 里只支持等值分组，就需要把这种有序分组转换成常规的等值分组来实现。过程是这样：

       1) 按日期排序，用窗口函数取出每天的前一天股价；

       2）对比，如果上涨了的标记为 0，下跌的标记为 1；

       3）累加当前行以前的标记，累加的结果类似 0,0,1,1,1,1,2,2,3,3,3…，这些就是我们需要的组号了；

       4）现在可以用 SQL 常规的等值分组了。

       完整的 SQL 写出来是这样：

       SELECT MAX(ContinuousDays)

       FROM (

              SELECT COUNT(*) ContinuousDays

              FROM (

                     SELECT SUM(RisingFlag) OVER (ORDER BY day) NoRisingDays

                     FROM (

                            SELECT day, CASE WHEN price>

                                   LAG(price) OVER (ORDER BY day) THEN 0 ELSE 1 END RisingFlag                           FROM tbl

                     )

              ) GROUP BY NoRisingDays

       )

       这个题已经不简单了，嵌套了四层的子查询。细追究下解题思路，就得说 SQL 语言与 JAVA/C 语言的不同特点，SQL 是集合化语言，提供的计算直接针对集合，没有显式可精细控制的循环操作，更没有过程中的临时变量可利用，这导致解决问题的思路和人的自然思路差异比较大，得变换思路，通过几个规整的集合计算实现出等价效果；用非集合化的语言 JAVA 或 C，比较贴合自然思路，循环处理每个数据，过程中产生新组或加入旧组很直观。当然 JAVA 等语言基本上没有提供集合运算，也是各有特长。

       合理的查询需求在复杂程度上不会止步：

       7、 连续上涨超过三天的股票有哪些？

       这个问题题是有序分组 + 分组子集，最后再加个常规的分组、聚合值过滤（HAVING）。通过上个查询的思路得到每支股票的所有上涨组，最外面套上分组运算得出每支股票的最大上涨天数，并用聚合后的条件运算 HAVING 过滤出上涨大于三天的：

       SELECT code, MAX(ContinuousDays)

       FROM (

              SELECT code, NoRisingDays, COUNT(*) ContinuousDays

              FROM (

                     SELECT code,

                     SUM(RisingFlag) OVER (PARTITION BY code ORDER BY day) NoRisingDays

                     FROM (

                            SELECT code, day,

                                   CASE WHEN price>

                                          LAG(price) OVER (PARTITION BY code ORDER BY day)

                                   THEN 0 ELSE 1 END RisingFlag

                            FROM tbl

                     )

              ) GROUP BY NoRisingDays

       )

       GROUP BY code

       HAVING MAX(ContinuousDays)>=3

       这个 SQL 已经很难看懂了。

总结

       从上面的讨论可以看出。没有窗口函数 SQL 对有序运算极端不适应（目前还有些数据库不支持窗口函数），理论上可以写，但实际的麻烦程度基本上等同于不能用。在引入窗口函数后，有序计算得到了很好的改善，不过对于稍复杂情况还是相当麻烦。

       这个原因在于 SQL 的理论基础，也就是关系代数，是以无序集合作为基础的，仅靠窗口函数这种打补丁的办法并不能从根本上解决问题。

       其实，计算机语言中的数组（即集合）是天然有序的（有序号），在 Java/C++ 这些高级语言的思路下很容易理解和实现有序计算，但是这类语言的集合计算能力又比较弱，实现上面这些问题的代码也不短（虽然有序计算的解题思路难度并不大）。

       esProc 的 SPL 可以很好地解决这一问题。esProc 是专业的数据计算引擎，基于有序集合设计，同时提供了完善的集合运算，相当于 Java 和 SQL 优势的结合。在 SPL 的支持下，有序集合计算会非常容易，比如上面的问题用 SPL 写出来是这样：

1、 T.sort(day).derive(price/price[-1]:rate)

2、 T.sort(day).derive(avg(price[-1:1]):movingAvg)

3、 T.sort(day).group(code).(~.derive(price/price[-1]:rate)).conj()

4、 T.sort(price).group(code).(~((~.len()+1)\2))

5、 T.sort(day).group(code).((p=~.pmax(price),~.calc(p,price/price[-1])))

6、 T.sort(day)[email protected](price >price[-1]).max(~.len()))

7、 T.sort(day).group(code).select([email protected](price>price[-1]).max(~.len())>3).(code)

       SPL 中提供了跨行引用的语法，也支持有序分组等运算，有了这些后，上面那些问题只要按自然思维去组织计算逻辑，一行代码就能优雅地写出来。