写着简单和跑得快是一回事,SQL 为什么不可能跑得快?

我们讨论过代码编写的难和繁的原理问题,现在关注性能问题,运行速度当然是非常重要的事情。
我们知道,软件不能改变硬件的性能,CPU 和硬盘该多快就多快。不过,我们可以设计出低复杂度的算法,也就是计算量更小的算法,计算机执行的动作变少,自然也就会快了。本来要做 1 亿次运算,如果有个好算法能把计算量降低到 100 万次,那快出 100 倍就不奇怪了。但是,光想出算法还不够,还要把这个算法实实在在地用某种程序语言写出来,否则计算机不会执行。
然而,如果采用的程序语言不给力,就有可能真地写不出来,这时候就干瞪眼忍受低速度。

SQL 就会经常发生这种事。我们用这个简单例子来说明:从 1 亿条数据中取出前 10 名,用 SQL 写出来并不复杂:

SELECT TOP 10 * FROM Orders ORDER BY Amount DESC

这个语句里有个 ORDER BY 的字样,对应的执行逻辑就是要对 1 亿条数据做大排序。我们知道,排序是个非常慢的动作,要把数据遍历多次(具体复杂度是 N*logN 次 ),如果数据量大到内存装不下,那还需要外存做缓存,性能还会急剧下降。如果严格按这句 SQL 描述的逻辑去执行,这个运算无论如何是跑不快的。
其实,我们知道,只是取前 10 名并不需要将所有数据做大排序,只要在遍历时始终保持一个前 10 名的小集合,遍历过程中不断地修正这个小集合,一次遍历可以了,复杂度是 N*log10,和 log1 亿相比差了 8 倍左右,也就是计算量能小 8 倍,而且这种算法完全不需要外存做缓存。
遗憾的是,用 SQL 无法描述这样的计算过程,只能写成上面那个样子,然后指望数据库去优化。所幸,几乎所有数据库都会优化这个句子,没有傻到去做大排序了,所以也能跑得比较快。

但是,情况再复杂一些会怎样呢?比如我们把需求改成计算分组内的前 10 名,SQL 写出来是这样的:

SELECT * FROM (
    SELECT *, ROW_NUMBER() OVER (PARTITION BY Area ORDER BY Amount DESC) rn
    FROM Orders )
 WHERE rn<=10

这和刚才针对全集取前 10 名的写法相差就很大了,这是我们之前说的缺失离散性导致的。要先借助窗口函数造一个组内序号出来,再用子查询过滤出符合条件的记录,也就是有点“绕”了。
无论如何,这里还是有 ORDER BY 字样,其中的运算逻辑还是要排序。我们实际测试发现,在 Oracle 中,同样的数据量,计算这种分组前 10 名要比上面那个全集前 10 名慢出几十倍,按说多个分组应该只慢一点点才对。Oracle 有很大可能性真地去做了排序甚至是外存排序(当然我们没读过 Oracle 的源代码并不能确定),数据库优化引擎在这种稍复杂的情况下就晕掉了,只能老老实实按 SQL 写的逻辑去执行,性能就会陡降。

当然,也许哪天数据库又进化了,碰到这种情况也会优化了(事实上确实有了)。但总有更复杂的情况,而数据库优化引擎的进化速度是非常慢的。
比如这么一个更复杂的需求,做电商系统中的漏斗分析,计算每一步动作后的用户流失率。下面是一个实际业务中发生的三步漏斗计算,SQL 会写成这样:

WITH e1 AS (
    SELECT userid, visittime AS step1_time, MIN(sessionid) AS sessionid, 1 AS step1
    FROM defined_events e1 JOIN eventgroup ON eventgroup.id = e1.eventgroup
    WHERE visittime >= DATE_ADD(arg_date,INTERVAL -14 day) AND visittime < arg_date AND eventgroup.name='SiteVisit'
    GROUP BY userid,visittime
), e2 AS (
    SELECT e2.userid, MIN(e2.sessionid) AS sessionid, 1 AS step2, MIN(visittime) AS step2_time, MIN(e1.step1_time) AS step1_time
    FROM defined_events e2 JOIN e1 ON e1.sessionid = e2.sessionid AND visittime > step1_time JOIN eventgroup ON eventgroup.id = e2.eventgroup
    WHERE visittime < DATE_ADD(step1_time ,INTERVAL +1 day) AND eventgroup.name = 'ProductDetailPage'
    GROUP BY e2.userid
), e3 AS (
    SELECT e3.userid, MIN(e3.sessionid) AS sessionid, 1 AS step3, MIN(visittime) AS step3_time, MIN(e2.step1_time) AS step1_time
    FROM defined_events e3 JOIN e2 ON e2.sessionid = e3.sessionid AND visittime > step2_time
    JOIN eventgroup ON eventgroup.id = e3.eventgroup
    WHERE visittime < DATE_ADD(step1_time ,INTERVAL +1 day) AND (eventgroup.name = 'OrderConfirmationType1')
    GROUP BY  e3.userid
)
SELECT s.devicetype AS devicetype,
    COUNT(DISTINCT CASE WHEN funnel_conversions.step1 IS NOT NULL THEN funnel_conversions.step1_userid  ELSE NULL END) AS step1_count,
    COUNT(DISTINCT CASE WHEN funnel_conversions.step2 IS NOT NULL THEN funnel_conversions.step2_userid  ELSE NULL END) AS step2_count,
    COUNT(DISTINCT CASE WHEN funnel_conversions.step3 IS NOT NULL THEN funnel_conversions.step3_userid  ELSE NULL END) AS step3_count,
    COUNT(DISTINCT CASE WHEN funnel_conversions.step3 IS NOT NULL THEN funnel_conversions.step3_userid  ELSE NULL END) 
		/ COUNT(DISTINCT CASE WHEN funnel_conversions.step1 IS NOT NULL THEN funnel_conversions.step1_userid  ELSE NULL END) AS step3_rate
FROM (
    SELECT e1.step1_time AS step1_time, e1.userid AS userid, e1.userid AS step1_userid, e2.userid AS step2_userid,e3.userid AS step3_userid,
           e1.sessionid AS step1_sessionid, step1, step2, step3
    FROM e1 LEFT JOIN e2 ON e1.userid=e2.userid LEFT JOIN e3 ON e2.userid=e3.userid ) funnel_conversions
LEFT JOIN sessions s ON funnel_conversions.step1_sessionid = s.id 
GROUP BY s.devicetype

这个 SQL“绕”得很严重了,看懂非常费劲,摆在这里就是感受一下。这还只是三步,想再多算几步还得写更多子查询,那就摆不出来了。这种复杂的 SQL,真想不出这能怎么做优化。结果,这句 SQL 在 Snwoflake 的 Medium 集群上(4 节点)跑了 3 分钟没出来,用户只能放弃。

所以,不能也不要指望数据库优化,还是要自己写出高性能算法出来。
那么,什么样的程序语言才能写出刚才说的这些算法呢?
很多,C++,Java 这些都可以。理论上用 SQL 写的存储过程也可以,但工程实现的结果还是会太慢,这还是因为缺失离散性。比如 TopN 问题,在 SQL 中要保存那 10 个成员的小集合也得用临时表,很难写也很慢。
那就不用 SQL,用 C++,Java 这些去写好了。

这又回到我们之前说的集合化特性了,这些语言缺乏集合化,写出来很繁琐。像分组 TopN,如果要考虑各种数据类型、多个分组键、还可能带着计算式,几千行也未必写得出来。而漏斗分析这种复杂运算,还要考虑大数据存储问题,写个几万行也很正常。开发成本极高,以后维护时也累死人。
这样,在现实中就没有可操作性了。
所以,代码能写着简单就变得非常有意义了。一方面是短小,这意味着工作量少,另一方面还要容易,这意味着更多的程序员可以写。从这个角度上看,写着简单和跑得快是一回事。想跑得快,就是要有一种程序语言能让高性能算法写着简单,这才有可操作性。

这样的标准,可能只有 esProc SPL 适合了,它同时拥有集合化和离散性两种特性,又提供相当多固有的高性能算法库函数,这才能写着简单,从而跑得快。
前面的前 10 名问题用 SPL 写出来是这样的:

Orders.groups(;top(10;-Amount)
Orders.groups(Area;top(10;-Amount))

SPL 把 TopN 理解为聚合计算,这个语句中没有排序的字样,也就不会做大排序,而采用刚才说的快速算法了。而且,这里分组前 10 名和全集前 10 名的写法基本一样,只是多了分组键。这也是在集合化的基础上支持了离散性的结果。

漏斗分析用 SPL 写出来是这样:


A

1

=now()

2

=eventgroup=file("eventgroup.btx").import@b()

3

=devicetype=file("devicetype.btx").import@b()

4

=long(elapse(arg_date,-14))

5

=long(arg_date)

6

=long(arg_date+1)

7

=A2.(case(NAME,"SiteVisit":1,"ProductDetailPage":2,"OrderConfirmationType1":3;null))

8

=file("defined_events.ctx").open()

9

=A8.cursor@m(USERID,SESSIONID,VISITTIME,EVENTGROUPNO;VISITTIME>=A4 && VISITTIME<A6,EVENTGROUPNO:A7:#)

10

=sessions=file("sessions.ctx").open().cursor@m(USERID,ID,DEVICETYPENO;;A9)

11

=A9.joinx@m(USERID:SESSIONID,A10:USERID:ID,DEVICETYPENO)

12

=A11.group(USERID)

13

=A12.new(~.align@a(3,EVENTGROUPNO):e,e(1).select(VISITTIME<A5).group@u1(VISITTIME):e1,e(2).group@o(SESSIONID):e2,e(3):e3)

14

=A13.run(e=join@m(e1:e1,SESSIONID;e2:e2,SESSIONID).select(e2=e2.select(VISITTIME>e1.VISITTIME && VISITTIME<e1.VISITTIME+86400000).min(VISITTIME) ) )

15

=A14.run(e0=e1.id(DEVICETYPENO),e1=e.min(e1.VISITTIME),e2=e.min(e2),e=e.min(e1.SESSIONID),e3=e3.select(SESSIONID==e && VISITTIME>e2 && VISITTIME<e1+86400000).min(VISITTIME),e=e0)

16

=A15.news(e;~:DEVICETYPE,e2,e3)

17

=A16.groups(DEVICETYPE;count(1):STEP1_COUNT,count(e2):STEP2_COUNT,count(e3):STEP3_COUNT,null:STEP3_RATE)

18

=A17.run(DEVICETYPE=devicetype.m(DEVICETYPE).DEVICETYPE,STEP3_RATE=STEP3_COUNT/STEP1_COUNT)

19

=interval@s(A1,now())

这个代码要比前面的 SQL 更短,而且更灵活,再增加几步也还是这段代码。实测的结果,这段代码用单台服务器 10 秒就跑完了。
有了集合化和离散性的 SPL,才能做到写着简单又跑得快。