【数据蒋堂】第 17 期:SQL 的困难源于关系代数

sjjt-17

在结构化数据处理领域,SQL 无疑是应用最广泛的工作语言,不仅被所有关系数据库采用,许多新进的大数据平台也将实现 SQL 作为目标。但是,SQL 真地好用吗?

人们写代码通常关心两个效率问题。一是运算的描述效率,二是运算的执行效率。这两个效率很容易理解,如果描述效率太低,就意味着开发成本太高,很难写出程序进行计算;而如果执行效率低,则需要运行很久才能得到结果,那实用价值也就大打折扣了。实际上,执行高效在本质上也是个描述问题,在软件层面不可能提高硬件性能,但可能设计出更高效的算法,那么这个语言不能限制我们写出高效算法。

对于简单问题,SQL 还是比较方便的,可以像英语一样读写,很容易理解。比如查询北京地区人员、按性别将计算人员的平均收入等,都很容易写。

但是,面对较复杂的数据运算,SQL 的表现就不如人意了,我们分别举两个并不复杂的例子说明:

1. 找出一支股票最长连续上涨了多少天

这个问题对于 Java 或 C++ 程序员来讲非常简单:做个初值为 0 的计数器,把数据按日期排序后遍历,发现上涨就将计数器加 1,下跌则清 0,最后看这个计数器出现过的最大值,这是个很自然的思路。但是用 SQL 实现就太困难了。SQL 中的记录没有次序,数据排序只在输出时有效,无法规定数据的遍历次序,也就很难实施上述的自然思路。要人为地制造出日期的序号后,再产生一个分组标志,把股价比前一天高的日期和前一天分成一组,下跌的日期分到另一组,然后计算最大的分组 COUNT() 值。即使这个思路,也很难在 SQL 中实现,要使用窗口函数,写成四层嵌套的子查询。有兴趣的同学可以自己试一下。

2. 从 10 亿条数据中找出最大的前 10 名

我们知道,这样的问题是不需要把 10 亿行数据全部排序的。先产生一个有 10 个成员的小集合,然后遍历数据,过程中始终保持这个小集合是当前已遍历过数据中最大的 10 个,这样整个 10 亿行数据只要遍历一次,内存占用很小,运算性能很好。但 SQL 没有显式的集合数据类型,无法描述这个算法。它描述出来的算法就是把 10 亿行数据大排序取出前 10 名后,剩下的已排序的数据没有用了。10 亿行大排序的成本很高,如果内存装不下则还会涉及多次外存数据倒换的问题,性能会严重下降。这就会发生明知有好的算法却无计可施的尴尬局面。这种情况常常就只能寄希望于数据库在工程上的优化,但情况复杂的 SQL 会超出数据库的优化能力(比如在分组中取每组的前 10 名)。

SQL 中类似的问题还很多,远远不象传说中的那么强悍。我们就不举更多的例子了,现实业务中这种事比比皆是。平常我们用来举例的那种三行五行的简单 SQL,只存在于教科书和培训班,现实中我们写 SQL 都是论 K 计的,稍复杂一些的运算就非常难写,而且很难调优。

看来,SQL 在两方面都并不够好用。

那么 SQL 的问题是什么原因造成的呢?表面上看,SQL 的问题主要在于不提倡也不擅长描述过程性运算,前面这两个例子都会涉及到过程式的运算,但这并不是最关键的问题,SQL 的根本困难实际上来源于其理论基础,即关系代数。

关系代数是一种代数体系。我们无法在本文的篇幅中严格定义代数体系这个概念,只能通俗地解释。人们为解决某种运算问题,定义了一些数据对象及针对这些数据对象的一套运算规则,确保这些运算的封闭性和自洽性,就可以称为一种代数体系了。比如说我们熟悉的有理数及其上的四则运算就是一种用于解决日常生活中数值计算需求的代数体系。封闭性是指计算结果必须仍然是定义过的数据对象,比如有理数的四则运算结果仍然是有理数。而自洽性指这些运算不能出现矛盾的结果,比如我们要约定不能除以 0,否则把某个数除以 0 规定成任何数都会推出逻辑矛盾来。

这里说的数据对象,和程序设计面向对象理论中数据对象不太一样。前者主要强调数据上的运算,而后者更多强调对象的封装性、继承性和重载能力。前者是为了更好的描述和实施数据运算,后者则主要是为了代码复用。

代数体系设计得好与不好,严重影响我们实施计算的方便度和效率!

举两个例子:

1. 我们从小学过的算术体系都采用阿拉伯数字,用来表示数值和做四则运算都很方便,但试想如果换成罗马数字会是个什么感觉?

2. 所有整数乘法都可以用加法表示,但如果我们在算术体系中引入了乘法来表示若干个相同数相加这种运算,就可以发明九九表来做而不必硬加,效率可显著提高。

要让计算机实施计算,还需要一套基于代数体系的形式化语言,用户把计算目标按约定的语法符号写成代码,就可以由计算机执行了。而用计算机解决问题的过程,也可以理解为把题目解法翻译成某种形式化语言的过程。如果代数体系及其形式化语言设计得不好,就可能发生翻译问题解法的难度大于解决问题本身的现象!用罗马数字来实施四则运算就是这个结果。

关系代数就是用来实现批量结构化数据计算的代数体系,而 SQL 则在这个理论上发展出来的形式语言。关系代数过于简单,没有足够的数据类型和运算,那么用 SQL 来描述问题的解法时,就要想办法绕路实现。比如股票上涨问题,因为关系代数延用了数学上的无序集合理论,没有给 SQL 造出序的概念,就把一个简单问题变成一个困难问题,即使绕路也很难写,于是就发生前面说过的翻译问题解法的难度大于解决问题本身的现象。取前 10 名问题也是,关系代数设计的聚合运算不包括 TOPN,它也没有集合数据类型,无法把这个运算设计成聚合运算,于是又只能描述成大排序了。

在运算简单的情况,并且性能要求不高时,用 SQL 还是比较方便的,毕竟掌握者众多,相关软件也很丰富。但现代应用中的数据需求越来越复杂,数据量也越来越大,继续采用 SQL 就会严重影响工作效率了。而且,SQL 的不适应并非实现层面的问题,而是其基础理论的问题,这不是在工程上进行优化就能解决的。面对当前的数据运算需求,关系代数显得过于简单了,需要从数学上进行彻底的革新。