SPL：一种易于编写且运行快速的数据库语言

数据库语言的目标

要弄清楚这个目标，我们首先需要了解数据库的作用。

提起数据库，人们总是会想到它主要是用于存储，因为它的名字里有个“库”（base）。但事实上并非如此，数据库可以实现两个重要的功能：计算和事务，这也就是我们常说的OLAP和OLTP。数据库的存储是为了服务于这两个功能，而仅仅作为存储角色并非数据库的终极目标。

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

事务功能主要是为了解决读写过程中的数据一致性问题。尽管实现起来并不容易，但它对应用程序的接口却非常简单，操作数据库读写数据的代码也很简单。如果假设当前关系数据库的逻辑存储模式是合理的（即以数据表和记录来存储数据。至于是否合理是另一个复杂的问题，这里不详述），那么SQL描述事务功能不会有问题，因为不需要描述复杂的操作，复杂性已经由数据库解决了。

然而，在计算功能方面，情况则不同。

这里所说的计算，是一个更广泛的概念。它不仅仅是简单的加减乘除，搜索和关联都可以看作是某种计算。

那么问题来了，什么样的计算系统是好的呢？

需要两个特点：易于编写，运行快速。

易于编写顾名思义，就是让程序员能够快速地写出代码，从而在单位时间内完成更多的工作；而运行快速，则更容易理解，因为我们肯定希望在更短的时间内得到计算结果。

事实上，SQL中的Q代表query（查询）。SQL的发明初衷就是为了查询（即计算），这是SQL的主要目标。然而，在描述计算任务方面，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)

这里不再解释这条语句的工作原理，反正有点令人费解。有兴趣的可以自己试试。

这是某公司（Raqsoft）的一道招聘试题，通过率不到20%；因为太难，后来改为另一种测试方式：要求应聘者解释所写的SQL语句的意思，但遗憾的是，通过率仍然不高。

这说明了什么？说明情况稍微复杂一点，SQL就变得难以理解和编写！

我们再来看看运行快速的问题，就拿一个经常被用作例子来说的简单任务：从一亿条数据中取出前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相同，但由于引入了排序特性，表达起来要容易得多，不再令人费解。

从一亿条数据中取出前10条

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

SPL具有更丰富的集合数据类型，可以轻松表达实现单次遍历简单聚合的高效算法，而不涉及大规模排序操作。

限于篇幅，这里不全面介绍SPL（离散数据集），列出SPL（离散数据集）相比于SQL（关系代数）的一些差别性改进。

离散记录

离散数据集中的记录是一种基本数据类型，可以独立于数据表而存在。数据表是由记录构成的集合，而构成某个数据表的记录也可以用来构成其他数据表。例如，过滤操作就是用原数据表中满足条件的记录构成一个新的数据表，这样在空间占用和操作性能上都更有优势。

关系代数没有可计算的数据类型来表示记录。单个记录实际上就是一个只有一行的数据表，并且不同数据表中的记录不能相同。例如，在过滤操作中，会复制新的记录来构成新的数据表，这就会导致空间和时间成本的增加。

特别是，由于离散记录的存在，离散数据集允许记录的字段值是某个记录，这使得实现外键连接更加容易。

排序特性

关系代数基于无序集合设计，集合成员没有序号的概念，并且不提供定位计算和相邻引用的机制。在实践中，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. 数据表按键排序，在两个大表之间的对齐连接（alignment join）时，可以使用性能更高的合并算法。这样，我们只需要遍历一次数据，无需缓冲数据，从而减少内存占用。而传统的HASH值分区方法不仅相对复杂，需要更多的内存和数据缓冲，而且由于哈希函数不当，还可能出现二次哈希和重新缓冲。
4. 大表作为外键表进行连接。当事实表较小时，可以使用外键表进行排序，从中快速取出与关联键值对应的数据实现连接，无需进行HASH分区。当事实表也较大时，我们可以将外键表按分位数分成多个逻辑段，然后按逻辑段对事实表进行分区。这样，只需要对一张表进行分区，并且在分区过程中不会出现HASH分区可能出现的二次分区，从而大大降低了计算复杂度。

上述第3)和第4)项利用了离散数据集中连接操作的改进。如果继续使用关系代数的定义（可能产生多对多），则很难实现这种低复杂度的算法。

除了理论差异之外，SPL还有许多工程级优势，例如：更易于编写并行计算代码、内存预关联以提高外键连接性能、独特的列存储机制以支持任意分段和并行计算等。