SQL 的困难源于关系代数

在结构化数据计算领域,SQL 现在还是应用最广泛的工作语言,不仅被所有关系数据库采用,许多新进的大数据平台也将实现 SQL 作为目标。
对于某种计算技术,人们通常会关心两个效率。一是运算的描述效率,二是运算的执行效率。这容易理解,描述效率太低就意味着开发成本太高,很难写出程序进行计算;而执行效率低则需要运行很久才能得到结果,那实用价值也就大打折扣了。通俗地说,就是要写着简单且跑得快。
但是,我们之前分析了一些结构化数据的计算场景,对于写着简单和跑得快这两方面,SQL 其实做得都不好,情况稍一复杂就难以胜任,结果经常导致数千行嵌套 N 层的代码以及几十 G 就要跑几个小时的运算。比较典型的两个例子就是计算股票连涨的天数和大集合中做全集和分组的 TopN,细节这里不再重复了,有兴趣的可以看之前的帖子。

一支股票最长连续上涨多少天:本来很简单的任务,因为缺乏有序计算能力,需要写成多层嵌套的形式,难写又难懂
select max(ContinuousDays) from (
    select count(*) ContinuousDays from (
        select sum(UpDownTag) over (order by TradeDate) NoRisingDays from (
            select TradeDate,case when Price>lag(price) over ( order by TradeDate) then 0 else 1 end UpDownTag from Stock ))
    group by NoRisingDays )

一亿条数据中取前10名,分组后每组取前10名,写法相差很大,且都有ORDER BY,意味着要执行高复杂度的大排序,只能指望数据库优化器找到低复杂度算法。
SELECT TOP 10 * FROM Orders ORDER BY Amount DESC
SELECT * FROM (
    SELECT *, ROW_NUMBER() OVER (PARTITION BY Area ORDER BY Amount DESC) rn FROM Orders )
WHERE rn<=10

原因我们也分析过了,SQL 缺乏离散性,导致集合化不彻底,有序运算很困难,也导致高性能算法难以描述,….。
但是,这背后还有更深层次的原因,SQL 的根本困难实际上来源于其理论基础,即关系代数。
要解释这个说法,我们需要分析一下用程序实现计算到底是在干什么。
本质上讲,编写程序的过程,就是把解决问题的思路翻译成计算机可执行的精确化形式语言的过程。举例来说,就象小学生解应用题,分析问题想出解法之后,还要列出四则运算表达式。用程序计算也是一样,不仅要想出解决问题的方法,还要把解法翻译成计算机能理解执行的动作才可以实现计算。
用于描述计算方法的形式语言,其核心在于所采用的代数体系。我们无法在这里严格定义代数体系这个概念,只能通俗地解释。人们为解决某种运算问题,定义了一些数据类型及针对这些数据类型的一套运算规则,确保这些运算的封闭性和自洽性,就可以称为一种代数体系了。比如说我们熟悉的有理数及其上的四则运算就是一种用于解决日常生活中数值计算需求的代数体系。封闭性是指计算结果必须仍然是定义过的数据对象,比如有理数的四则运算结果仍然是有理数。而自洽性指这些运算不能出现矛盾的结果,比如我们要约定不能除以 0,否则把某个数除以 0 规定成任何数都会推出逻辑矛盾来。

如果这个代数体系设计时考虑不周到,提供的数据类型和运算不方便,那就会导致描述算法非常困难。这时候会发生一个怪现象:翻译解法到代码的难度远远超过解决问题本身
举个例子,我们从小学习用阿拉伯数字做日常计算,实施加减乘除都很方便,所有人都天经地义认为数值运算就该是这样的。其实未必!我想大多数人都知道还有一种叫做罗马数字的东西,我不知道罗马数字体系是不是还有我们熟悉的加减乘除运算(它那个数字体系无法象阿拉伯数字这样方便地实施这些运算,很可能运算定义也不同了),我也一直很困惑古罗马人是如何上街买菜的

这样,我们知道了,程序能不能写着简单,其实是程序语言背后的代数的问题。
而我们之前也说过了,跑得快本质上和写着简单的是一回事,也就是能让高性能算法容易写。这么一来,跑得快也还是个代数的问题。

我们再做个类比:
在国内上过小学的同学大概都知道高斯计算 1+2+3+…+100 的小故事。普通人就是一步步地硬加 100 次,高斯小朋友很聪明,发现 1+100=101、2+99=101、…、50+51=101,结果是 50 乘 101,很快算完回家午饭了。
听过这个故事,我们都会感慨高斯很聪明,能想到这么巧妙的办法,即简单又迅速。这没有错,但是,大家容易忽略一点:在高斯的时代,人类的算术体系(也是一个代数)中已经有了乘法!象前面所说,我们从小学习四则运算,会觉得乘法是理所当然的,其实并不是,乘法是后于加法被发明出来的。乘法虽然是被加法定义的,但可以利用它的特点使用九九表来算,效率就提高很多。如果高斯的年代还没有乘法,即使有聪明的高斯,也没办法快速解决这个问题。

SQL 的数学基础就是关系代数,是用来实现批量结构化数据计算的代数体系,这也是采用 SQL 的数据库又被叫做关系数据库的原因。
关系代数已经发明五十年了,五十年前的应用需求以及硬件环境,和今天比的差异是很巨大了。由于存量用户太多,而且也还没有成熟的新技术出现,基于关系代数设计的 SQL,今天仍然是最重要的数据库开发语言。虽然这几十年来也有一些改进完善,但根子并没有变,面对当代的复杂需求和硬件环境,关系数据库并没有那么得心应手了。
关系代数过于简单,缺乏足够的数据类型和运算,那么用 SQL 来描述问题的解法时,就要想办法绕路实现。比如股票上涨问题,因为关系代数延用了数学上的无序集合理论,没有给 SQL 造出序的概念,结果就把一个简单问题变成一个困难问题,即使绕路也很难写,于是就发生前面说过的翻译问题解法的难度大于解决问题本身的现象。取前 10 名问题也是,关系代数设计的聚合运算不包括 TOPN,它也没有集合数据类型,无法把这个运算设计成聚合运算,于是又只能描述成大排序了。
关系代数就象只有加法还没发明乘法的算术体系,很多事做不好是必然的。

在运算简单的情况,或者性能要求不高时,用 SQL 还是比较方便的,毕竟掌握者众多,相关软件也很丰富。但现代应用中的数据需求越来越复杂,数据量也越来越大,继续采用 SQL 就会严重影响工作效率了。而且,不幸的是,这个问题是理论层面的,在工程上无论如何优化也无济于事,只能有限改善,不能根除。不过,绝大部分的数据库开发者并不会想到这一层,或者说为了照顾存量用户的兼容性,也没打算想到这一层。于是,主流数据库界一直在这个圈圈里打转转。

那么该怎么办呢?也就是如何让计算写着更简单、跑得更快呢?
发明新的代数!有“乘法”的代数。这就是 esProc SPL 的不同之处。我们给 SPL 的代数基础起了个数学味道的名字:离散数据集。SPL 就是这个代数的形式语言。前面的内容中已经多次讲过 SPL 的优势。在新代数的支持下,我们就真地能做到写着简单又跑得快了。