写着简单跑得又快的数据库语言 SPL

朱雀 2023-09-30 19:11 7阅读 0赞

数据库语言的目标SQL为什么不行SPL为什么能行

### 数据库语言的目标 ###

要说清这个目标，先要理解数据库是做什么的。

数据库这个软件，名字中有个“库”字，会让人觉得它主要是为了存储的。其实不然，数据库实现的重要功能有两条：**计算**、**事务**！也就是我们常说的OLAP和OLTP，数据库的存储都是为这两件事服务的，单纯的存储并不是数据库的目标。

我们知道，SQL是目前数据库的主流语言。那么，用SQL做这两件事是不是很方便呢？

事务类功能主要解决数据在写入和读出时要保持的一致性，实现这件事的难度并不小，但对于应用程序的接口却非常简单，用于操纵数据库读写的代码也很简单。如果假定目前关系数据库的逻辑存储模式是合理的（也就是用数据表和记录来存储数据，其合理性与否是另一个复杂问题，不在这里展开了），那么SQL在描述事务类功能时没什么大问题，因为并不需要描述多复杂的动作，复杂性都在数据库内部解决了。

但计算类功能却不一样了。

这里说的计算是个更广泛的概念，并不只是简单的加加减减，查找、关联都可以看成是某种计算。

什么样的计算体系才算好呢？

还是两条：**写着简单**、**跑得快**。

写着简单，很好理解，就是让程序员很快能写出来代码来，这样单位时间内可以完成更多的工作；跑得快就更容易理解，我们当然希望更短时间内获得计算结果。

其实SQL中的Q就是查询的意思，发明它的初衷主要是为了做查询（也就是计算），这才是SQL的主要目标。然而，SQL在描述计算任务时，却很难说是很胜任的。

![01e5e5b095e14934a384e66e9f066d8d.png][]

### SQL为什么不行 ###

先看写着简单的问题。

SQL写出来很象英语，有些查询可以当英语来读和写（网上多得很，就不举例了），这应当算是满足写着简单这一条了吧。

且慢！我们在教科书上看到的SQL经常只有两三行，这些SQL确实算是写着简单的，但如果我们尝试一些稍复杂化的问题呢？

这是一个其实还不算很复杂的例子：计算一支股票最长连续上涨了多少天？用SQL写出来是这样的：

select max (consecutive_day)
    from (select count(*) (consecutive_day
          from (select sum(rise_mark) over(order by trade_date) days_no_gain
                from (select trade_date,
                             case when closing_price>lag(closing_price) over(order by trade_date)
                                  then 0 else 1 END rise_mark
                      from stock_price ) )
          group by days_no_gain)

这个语句的工作原理就不解释了，反正有点绕，同学们可以自己尝试一下。

这是润乾公司的招聘考题，通过率不足20%；因为太难，后来被改成另一种方式：把SQL语句写出来让应聘者解释它在算什么，通过率依然不高。

这说明什么？说明情况稍有复杂，SQL就变得即难懂又难写！

再看跑得快的问题，还是一个经常拿出来的简单例子：1亿条数据中取前10名。这个任务用SQL写出来并不复杂：

SELECT TOP 10 x FROM T ORDER BY x DESC

但是，这个语句对应的执行逻辑是先对所有数据进行大排序，然后再取出前10个，后面的不要了。大家知道，排序是一个很慢的动作，会多次遍历数据，如果数据量大到内存装不下，那还需要外存做缓存，性能还会进一步急剧下降。如果严格按这句SQL体现的逻辑去执行，这个运算无论如何是跑不快的。然而，很多程序员都知道这个运算并不需要大排序，也用不着外存缓存，一次遍历用一点点内存就可以完成，也就是存在更高性能的算法。可惜的是，用SQL却写不出这样的算法，只能寄希望于数据库的优化器足够聪明，能把这句SQL转换成高性能算法执行，但情况复杂时数据库的优化器也未必靠谱。

看样子，SQL在这两方面做得都不够好。这两个并不复杂的问题都是这样，现实中数千行的SQL代码中，这种难写且跑不快的情况比比皆是。

为什么SQL不行呢？

要回答这个问题，我们要分析一下用程序代码实现计算到底是在干什么。

本质上讲，编写程序的过程，就是**把解决问题的思路翻译成计算机可执行的精确化形式语言的过程**。举例来说，就象小学生解应用题，分析问题想出解法之后，还要列出四则运算表达式。用程序计算也是一样，不仅要想出解决问题的方法，还要把解法翻译成计算机能理解执行的动作才算完成。

用于描述计算方法的形式语言，其核心在于所采用的代数体系。所谓代数体系，简单说就是一些数据类型和其上的运算规则，比如小学学到的算术，就是整数和加减乘除运算。有了这套东西，我们就能把想做的运算用这个代数体系约定的符号写出来，也就是代码，然后计算机就可以执行了。

如果这个代数体系设计时考虑不周到，提供的数据类型和运算不方便，那就会导致描述算法非常困难。这时候会发生一个怪现象：**翻译解法到代码的难度远远超过解决问题本身**。

举个例子，我们从小学习用阿拉伯数字做日常计算，做加减乘除都很方便，所有人都天经地义认为数值运算就该是这样的。其实未必！估计很多人都知道还有一种叫做罗马数字的东西，你知道用罗马数字该怎么做加减乘除吗？古罗马人又是如何上街买菜的？

**代码难写很大程度是代数的问题**。

再看跑不快的原因。

软件没办法改变硬件的性能，CPU和硬盘该多快就是多快。不过，我们可以设计出低复杂度的算法，也就是计算量更小的算法，这样计算机执行的动作变少，自然也就会快了。但是，光想出算法还不够，还要把这个算法用某种形式语言写得出来才行，否则计算机不会执行。而且，写起来还要比较简单，都要写很长很麻烦，也没有人会去用。所以呢，对于程序来讲，**跑得快和写着简单其实是同一个问题**，背后还是这个形式语言采用的代数的问题。如果这个代数不好，就会导致高性能算法很难实现甚至实现不了，也就没办法跑得快了。就象上面说的，用SQL写不出我们期望的小内存单次遍历算法，能不能跑得快就只能寄希望于优化器。

我们再做个类比：

上过小学的同学大概都知道高斯计算1+2+3+...+100的小故事。普通人就是一步步地硬加100次，高斯小朋友很聪明，发现1+100=101、2+99=101、...、50+51=101，结果是50乘101，很快算完回家午饭了。

听过这个故事，我们都会感慨高斯很聪明，能想到这么巧妙的办法，即简单又迅速。这没有错，但是，大家容易忽略一点：在高斯的时代，人类的算术体系（也是一个代数）中已经有了**乘法**！象前面所说，我们从小学习四则运算，会觉得乘法是理所当然的，然而并不是！乘法是后于加法被发明出来的。如果高斯的年代还没有乘法，即使有聪明的高斯，也没办法快速解决这个问题。

目前主流数据库是关系数据库，之所以这么叫，是因为它的数学基础被称为**关系代数**，SQL也就是关系代数理论上发展出来的形式语言。

现在我们能回答，为什么SQL在期望的两个方面做得不够好？**问题出在关系代数上**，关系代数就像一个只有加法还没发明乘法的算术体系，很多事做不好是必然的。

关系代数已经发明五十年了，五十年前的应用需求以及硬件环境，和今天比的差异是很巨大了，继续延用五十年前的理论来解决今天的问题，听着就感觉太陈旧了？然而现实就是这样，由于存量用户太多，而且也还没有成熟的新技术出现，基于关系代数的SQL，今天仍然是最重要的数据库语言。虽然这几十年来也有一些改进完善，但根子并没有变，面对当代的复杂需求和硬件环境，SQL不胜任也是情理之中的事。

而且，不幸的是，这个问题是理论上的，在工程上无论如何优化也无济于事，只能有限改善，不能根除。不过，绝大部分的数据库开发者并不会想到这一层，或者说为了照顾存量用户的兼容性，也没打算想到这一层。于是，主流数据库界一直在这个圈圈里打转转。

### SPL为什么能行 ###

那么该怎样让计算写着更简单、跑得更快呢？

**发明新的代数**！有“乘法”的代数。在其基础上再设计新的语言。

这就是SPL的由来。它的理论基础不再是关系代数，称为**离散数据集**。基于这个新代数设计的形式语言，起名为**SPL**（Structured Process Language)。

SPL针对SQL的不足（更确切地说法是，离散数据集针对关系代数的各种缺陷）进行了革新。SPL重新定义了并扩展许多结构化数据中的运算，增加了离散性、强化了有序计算、实现了彻底的集合化、支持对象引用、提倡分步运算。

把前面的问题用SPL重写一遍有个直接感受。

一支股票最长连续上涨多少天：

stock_price.sort(trade_date).group@i(closing_price<closing_price[-1]).max(~.len())

计算思路和前面的SQL相同，但因为引入了有序性后，表达起来容易多了，不再绕了。

1亿条数据中取前10名：

T.groups(;top(-10,x))

SPL有更丰富的集合数据类型，容易描述单次遍历上实施简单聚合的高效算法，不涉及大排序动作。

限于篇幅，这里不能介绍SPL（离散数据集）的全貌。我们在这里列举SPL（离散数据集）针对SQL（关系代数）的部分差异化改进：

**游离记录**

离散数据集中的记录是一种基本数据类型，它可以不依赖于数据表而独立存在。数据表是记录构成的集合，而构成某个数据表的记录还可以用于构成其它数据表。比如过滤运算就是用原数据表中满足条件的记录构成新数据表，这样，无论空间占用还是运算性能都更有优势。

关系代数没有可运算的数据类型来表示记录，单记录实际上是只有一行的数据表，不同数据表中的记录也不能共享。比如，过滤运算时会复制出新记录来构成新数据表，空间和时间成本都变大。

特别地，因为有游离记录，离散数据集允许记录的字段取值是某个记录，这样可以更方便地实现外键连接。

**有序性**

关系代数是基于无序集合设计的，集合成员没有序号的概念，也没有提供定位计算以及相邻引用的机制。SQL实践时在工程上做了一些局部完善，使得现代SQL能方便地进行一部分有序运算。

离散数据集中的集合是有序的，集合成员都有序号的概念，可以用序号访问成员，并定义了定位运算以返回成员在集合中的序号。离散数据集提供了符号以在集合运算中实现相邻引用，并支持针对集合中某个序号位置进行计算。

有序运算很常见，却一直是SQL的困难问题，即使在有了窗口函数后仍然很繁琐。SPL则大大改善了这个局面，前面那个股票上涨的例子就能说明问题。

**离散性与集合化**

关系代数中定义了丰富的集合运算，即能将集合作为整体参加运算，比如聚合、分组等。这是SQL比Java等高级语言更为方便的地方。

但关系代数的离散性非常差，没有游离记录。而Java等高级语言在这方面则没有问题。

离散数据集则相当于将离散性和集合化结合起来了，既有集合数据类型及相关的运算，也有集合成员游离在集合之外单独运算或再组成其它集合。可以说SPL集中了SQL和Java两者的优势。

有序运算是典型的离散性与集合化的结合场景。次序的概念只有在集合中才有意义，单个成员无所谓次序，这里体现了集合化；而有序计算又需要针对某个成员及其相邻成员进行计算，需要离散性。

在离散性的支持下才能获得更彻底的集合化，才能解决诸如有序计算类型的问题。

离散数据集是即有离散性又有集合化的代数体系，关系代数只有集合化。

**分组理解**

分组运算的本意是将一个大集合按某种规则拆成若干个子集合，关系代数中没有数据类型能够表示集合的集合，于是强迫在分组后做聚合运算。

离散数据集中允许集合的集合，可以表示合理的分组运算结果，分组和分组后的聚合被拆分成相互独立的两步运算，这样可以针对分组子集再进行更复杂的运算。

关系代数中只有一种等值分组，即按分组键值划分集合，等值分组是个完全划分。

离散数据集认为任何拆分大集合的方法都是分组运算，除了常规的等值分组外，还提供了与有序性结合的有序分组，以及可能得到不完全划分结果的对位分组。

**聚合理解**

关系代数中没有显式的集合数据类型，聚合计算的结果都是单值，分组后的聚合运算也是这样，只有SUM、COUNT、MAX、MIN等几种。特别地，关系代数无法把TOPN运算看成是聚合，针对全集的TOPN只能在输出结果集时排序后取前N条，而针对分组子集则很难做到TOPN，需要转变思路拼出序号才能完成。

离散数据集提倡普遍集合，聚合运算的结果不一定是单值，仍然可能是个集合。在离散数据集中，TOPN运算和SUM、COUNT这些是地位等同的，即可以针对全集也可以针对分组子集。

SPL把TOPN理解成聚合运算后，在工程实现时还可以避免全量数据的排序，从而获得高性能。而SQL的TOPN总是伴随ORDER BY动作，理论上需要大排序才能实现，需要寄希望于数据库在工程实现时做优化。

**有序支持的高性能**

离散数据集特别强调有序集合，利用有序的特征可以实施很多高性能算法。这是基于无序集合的关系代数无能为力的，只能寄希望于工程上的优化。

下面是部分利用有序特征后可以实施的低复杂度运算：

1)数据表对主键有序，相当于天然有一个索引。对键字段的过滤经常可以快速定位，以减少外存遍历量。随机按键值取数时也可以用二分法定位，在同时针对多个键值取数时还能重复利用索引信息。

2)通常的分组运算是用HASH算法实现的，如果我们确定地知道数据对分组键值有序，则可以只做相邻对比，避免计算HASH值，也不会有HASH冲突的问题，而且非常容易并行。

3)数据表对键有序，两个大表之间对位连接可以执行更高性能的归并算法，只要对数据遍历一次，不必缓存，对内存占用很小；而传统的HASH值分堆方法不仅比较复杂度高，需要较大内存并做外部缓存，还可能因HASH函数不当而造成二次HASH再缓存。

4)大表作为外键表的连接。事实表小时，可以利用外键表有序，快速从中取出关联键值对应的数据实现连接，不需要做HASH分堆动作。事实表也很大时，可以将外键表用分位点分成多个逻辑段，再将事实表按逻辑段进行分堆，这样只需要对一个表做分堆，而且分堆过程中不会出现HASH分堆时的可能出现的二次分堆，计算复杂度能大幅下降。

其中3和4利用了离散数据集对连接运算的改造，如果仍然延用关系代数的定义（可能产生多对多），则很难实现这种低复杂的算法。

除了理论上的差异， SPL还有许多工程层面的优势，比如更易于编写并行代码、大内存预关联提高外键连接性能等、特有的列存机制以支持随意分段并行等。

这里还有更多SPL代码以体现其思路及大数据算法：

*  [性能优化技巧：遍历复用提速多次分组][Link 1]
 *  [性能优化技巧：TopN][TopN]
 *  [性能优化技巧：预关联][Link 2]
 *  [性能优化技巧：部分预关联][Link 3]
 *  [性能优化技巧：外键序号化][Link 4]
 *  [性能优化技巧：维表过滤或计算时的关联][Link 5]
 *  [性能优化技巧：有序归并][Link 6]
 *  [性能优化技巧：有序定位关联提速主子关联后的过滤][Link 7]
 *  [性能优化技巧：附表][Link 8]
 *  [性能优化技巧：小事实表与大维表关联][Link 9]
 *  [性能优化技巧：大事实表与大维表关联][Link 10]
 *  [性能优化技巧：有序分组][Link 11]
 *  [性能优化技巧：后半有序分组][Link 12]
 *  [性能优化技巧：前半有序时的排序][Link 13]

[01e5e5b095e14934a384e66e9f066d8d.png]: https://img-blog.csdnimg.cn/01e5e5b095e14934a384e66e9f066d8d.png
[Link 1]: http://c.raqsoft.com.cn/article/1568960169923
[TopN]: http://c.raqsoft.com.cn/article/1568974653153
[Link 2]: http://c.raqsoft.com.cn/article/1574142747764
[Link 3]: http://c.raqsoft.com.cn/article/1574667872162
[Link 4]: http://c.raqsoft.com.cn/article/1575263621672
[Link 5]: http://c.raqsoft.com.cn/article/1575946624827
[Link 6]: http://c.raqsoft.com.cn/article/1577153335610
[Link 7]: http://c.raqsoft.com.cn/article/1578967693907
[Link 8]: http://c.raqsoft.com.cn/article/1582862688002
[Link 9]: http://c.raqsoft.com.cn/article/1583209591047
[Link 10]: http://c.raqsoft.com.cn/article/1583667643978
[Link 11]: http://c.raqsoft.com.cn/article/1585814654188
[Link 12]: http://c.raqsoft.com.cn/article/1586773745830
[Link 13]: http://c.raqsoft.com.cn/article/1586936086188