SQL,NoSQL 以及数据库的实质

在之前的一些博文里(比如这篇),我多次提到关系式数据库和 SQL 的缺陷。我觉得它们是制造了问题又自己来解决,而且没有解决好。现在有了点时间,我就把这里面的细节稍微说一下,希望有一定的启发作用。

描述性语言的局限性

当我指出 SQL 的问题时,总是避免不了有人反驳说:“SQL 是描述性的语言。你只告诉它 What,而不是告诉它 How。”我发现总是有人对一些我多年前就听腻了,看透了的“广告词”执迷不悟,而现在这同样的事又发生在 SQL 身上。他们没有发现,我不但能实现 SQL,而且已经实现过比 SQL 强大很多的语言(逻辑式语言),所以我其实早已看透了所有这些语言的实质,我知道那些广告词在很大程度上是误导。

现在我就来分析一下 SQL 与逻辑式语言之间的关系,并且找出这类“描述性语言”共同的弱点。

Prolog 与人工智能的没落

可以说,“只告诉它 What,而不是告诉它 How”,只是一个不切实际的妄想,而且它并不是 SQL 首创的口头禅。在 SQL 诞生两年以前,有人发明了 Prolog,著名的“逻辑式语言运动”的先锋。Prolog 使用了与 SQL 非常类似的广告词,声称自己能够一劳永逸的解决人工智能和自动编程的问题,这样人们不需要写程序,只需要告诉电脑“想要什么”,然后电脑就能自动生成算法,自动生成代码来解决这问题。

不需要理解数据结构和算法,直接告诉电脑需要什么,它就给你答案,这是多么美妙的事情。世界上总是有很多这种类似“减肥药”的东西,每一个都声称自己是“不需运动,不需节食,一个星期瘦 20 斤!”然而由于人类的智力和经验参差不齐,总会有人上当。Prolog 当年的风头之大,以至于它被日本政府采用并且大力推广,作为他们所谓的“第五代计算机”的编程语言。可惜的是,减肥药毕竟是减肥药,科学道理决定了 Prolog 必定失败,以及“人工智能冬天”(AI winter)的到来。

为什么 Prolog 会失败呢?这是因为 Prolog 虽然“终究”有可能自动解决某些问题,然而由于它的算法复杂度太高,所以没法在我们有生之年完成。说白了,Prolog 采用的“计算”方式就是“穷举法”。为了得到用户“描述”的问题的答案,而不需要用户指定具体的数据结构和算法,Prolog 必须对非常大的图状解空间进行完全的遍历(Prolog 采用深度优先搜索)。而这种解空间的“状态”数量往往是与程序运行时路过的分支数目成指数关系,这就决定了 Prolog 虽然“最终”可能找到问题的答案,却很有可能在地球毁灭之前都没法完成它的搜索。而且由于 Prolog 无法表达真正意义上的“逻辑否”操作,所以对于很多问题它永远无法得到正确的答案(这是一个非常深入的问题,30 多年的研究,仍然没有结果)。

过于具体的细节我不想在这里解释,你只需要明白的是我绝不是在信口开河。在 Indiana 的日子里,我重新实现,并且扩展了一种与 Prolog 类似的逻辑式语言,叫做 miniKanren。它也就是 Dan Friedman 的新书《The Reasoned Schemer》的主题。在两三个星期的时间内,我不但完全重写了 miniKanren 的代码(代码见这里),而且为它加入了一种技术叫做 constraint logic programming,并且在那之上实现了一个非常干净利落的“逻辑否”操作。经过这番动手操作,我对 miniKanren 和逻辑式语言的工作方式可以说是了如指掌。虽然 miniKanren 比起 Prolog 更加优雅,而且在搜索算法上有所改进(广度优先而非深度优先),它本质上采用的计算方式也是一样的:穷举法。所以在很多时候它的效率很低,用法不灵活。像 Prolog 一样,miniKanren 并不能用来解决很多实际的问题。有些很简单的 Scheme 代码,你却不能把它翻译成等价的 miniKanren。然而就是这样一种语言,比起 SQL 的表达能力,其实也是天上地下。所以在实现并且扩展了 miniKanren 这样的“智能语言”之后再来看 SQL,对于我来说就像是在解剖一只青蛙。

这里只举一个例子,说明我所看到的所谓“描述性语言”的局限,看不懂的人可以暂时跳过。在 IU 的时候总有一些人喜欢用 miniKanren 来实现 Haskell 和 OCaml 的 Hindley-Milner 类型系统(HM 系统)。HM 那种最基本的基于 unification 的类型推导,miniKanren 确实能做到,因为 miniKanren,Prolog 和 HM 系统一样,都是基于 Robinson unification 算法。这种算法虽然精巧,表达能力却是非常有限的。如果遇到一些必要的扩展,比如 HM 系统所需要的 let-polymorphism,你就需要对 miniKanren 语言本身进行扩展。也就是说,你不再是用 miniKanren 实现你的算法,而是用一种过程式或者函数式语言(比如 Scheme)把你的算法加到 miniKanren 里面作为“语言特性”,然后再利用这个你刚实现的新特性来“实现”你的算法。于是你就发现,其实 miniKanren 本身并没有足够的表达力表示完整的 HM 类型推导算法。如果 miniKanren 必须经过 Scheme 扩展才能表达 HM 算法,那么比起直接的 Scheme 实现,miniKanren 并没有任何优势。一个新的语言特性要有价值,它必须能够在很多地方使用。然而这些 miniKanren 的扩展,每一个只能用到一个地方。所以它们其实完全失去了作为语言特性的价值,还不如直接写一段 Scheme 代码。

这也就是为什么虽然我很感谢 miniKanren 教会了我逻辑编程的原理,然而我实现过的所有强大的类型系统(有些的能力大大超过 HM 系统),全都是用最普通的过程式或者函数式语言。“描述性语言”声称的好处,其实在这种关键时刻总是微乎其微,还不如调用普通语言的库代码。

从 Prolog 到 SQL

扯了这么多 Prolog 和 miniKanren 的事情,这跟关系式数据库和 SQL 的讨论到底有何关系呢?其实,这些东西是有非常深层次的内在联系的。一个有趣的事情是,miniKanren 里面的“Kanren”一词并不是一个英语国家的人名,而是日语“関连”(かんれん,读作 kanren)。而“逻辑式语言”的另一个名字,其实叫做“关系式语言”(relational language)。

在数学上,“关系”(relation)意味着“没有方向”,意味着“可逆”。然而具有讽刺意味的是,所谓的“关系式数据库”并不具有这种可逆计算的能力。Prolog 和 miniKanren 其实是比 SQL 强大很多的语言,是真正的“关系式语言”,它们能够在比较大的程度上完成可逆计算。比如在 miniKanren 里面,你可以使用这样“查询操作”:如果 x+y 等于 10,y 等于 2,那么 x 等于几?很多 Prolog 和 miniKanren 可以表达的查询,SQL 没法表示。SQL 其实只能用于非常简单的,有“明确方向”的查询操作,基本上就像 Lisp 的 filter 函数。由于这些局限性,再加上很多其他的设计失误(比如语法像英语,组合能力弱),它只适合会计等人员使用,一旦遇到程序员需要的,稍微复杂一点的数据结构,它就没法表达了,而且会像 Prolog 一样引起诸多的性能问题。

由于 SQL 比起逻辑式语言有更多的限制,表达力弱很多,再加上 SQL 对于基本的数据结构进行了“索引”,逻辑式语言的性能问题在 SQL 里面得到了局部的缓解。比如,对于基本的算数操作 x < 10,SQL 能够通过对索引(B树)的查找来进行“优化”,从而避免了对 x 所有可能的值(一个非常大的空间)进行完全的遍历。然而这种索引的能力是非常有限的,它几乎没有扩展能力,而且很难自动生成。所以一旦遇到更加复杂的情况,数据库自带的索引就没法满足需要了。除了极其简单的情况,SQL 的编译器无法自动生成高效的索引。

更要命的是,这种问题的来源是根本性的,不可解决的,而不只是因为某些数据库的 SQL 编译器不够“智能”。很多人不理解这一点,总是辩论说“我们为何需要 Java 而不是写汇编,也就是我们为何需要 SQL。”然而,把 Java 编译成高效的汇编,和把 SQL 编译成高效的汇编,是两种本质上不同的问题。前者可以比较容易的解决,而后者是不可能的(除了非常个别的情况)。如果你理解“编译器优化”的本质就会发现,这里面有一个拓扑学上的质的飞跃。把 Java 编译成高效的汇编,是一个非常简单的,线性的优化。这个过程就像改进一个已经连接好的电路,把里面太长的电线缩短一点,这样时延和电阻可以小一些。而把 SQL 优化成高效的汇编,是一个非线性的优化。这个过程不只是缩短电线那么简单的问题,它需要解开一些错综复杂的“结”。这种优化不但非常难以实现,需要大量的“潜在数学知识”,而且有可能花费比执行代码还多的时间。

我只举一个例子来说明这个问题。如果你需要迅速地在地图上找到一个点附近的城市,SQL 无法自动在平面点集上建造像 KD-tree 那样的数据结构。这是很显然的,因为 SQL 根本就不知道你的数据所表示的是平面上的点集,也不理解平面几何的公理和定理。跟 B-tree 类似,知道什么时候需要这种特殊的索引结构,需要非常多的潜在数学知识(比如高等平面几何),所以你肯定需要手动的建立这种数据结构。你发现了吗,你其实已经失去了所谓的“描述性”语言带来的好处,因为你完全可以用最普通的语言,加上一些构造 B-tree, KD-tree 的“库代码”,来实现你所需要的所有复杂查询操作。你的 SQL 代码并不会比直接的过程式代码更加清晰和简洁。再加上 SQL 本身的很多设计失误,你就发现使用 SQL 数据库其实比自己手工实现这些数据结构还要痛苦。你学会 SQL 是为了避免编程,结果你不得不做比编程还要苦逼的工作,还美其名曰“performance tuning”。

到这里也许有人仍然会说,这只是因为现在的 SQL 编译器不够智能,总有一天我们能够制造出能够“自动发明”像 B-tree, KD-tree 这样索引结构的“优化算法”。我对此持非常不乐观的态度。首先你要意识到,哪怕最基本的数学知识,也是经过了人类几千年的实践,研究和顿悟才得到的。计算机虽然越来越快,它却缺乏对于世界最直接的观察和探索能力,所以在相当长的时间内,计算机是根本不可能自动“想到”这些数学和算法问题的,就不要谈解决它们。其次,即使计算机有一天长了脚可以走路,有了眼睛可以看见东西,有了“自由意志”,可以自己去观察世界,它却不一定能够发现并且解决“人类关心的数学问题”,因为它根本不知道人类需要什么。最后,我们需要在有生之年解决这些迫切的问题,我们无法等待几十年几百年,就为了让计算机自己想出像 KD-tree 一类众所皆知的数据结构。

计算机不可能猜到人类到底想要什么,这就是为什么你几乎总是需要手动指定索引的原因,而且这种索引需要数据库“内部支持”。你一次又一次的希望 SQL 能够自动为你生成高效的索引和算法,却一次又一次的失望,也就是这个原因。当然,你永远可以使用所谓的 stored procedure 来扩展你的数据库,然而这就像是我的 IU 同学们用 miniKanren 来实现 HM 类型系统的方式——他们总是先使用一种过程式语言(Scheme)来添加这种描述性语言的“相关特性”,然后欢呼:“哇,miniKanren 解决了这个问题!”而其实呢,还不如直接使用过程式语言来得直接和容易。

这种总是需要扩展的显现也出现在数据库的语言里面。经验告诉我,如果想数据库处理大量数据时达到可以接受的性能,你几乎总是需要使用普通语言对手头的数据库进行所谓的“扩展”,然后从 SQL 等查询语言“调用”它们。这种扩展代码往往是一次性的,只能用在一个地方,从而使得这些查询语言失去了存在的意义。因为如果经常如此,我们为何不直接发送这种过程语言到数据库里面执行,从而完全取代 SQL?

另外有一种数据库查询语言叫 Datalog,它结合了 SQL 和 Prolog 的特点。然而以上对于 SQL 和 Prolog 的分析,同样也适用于 Datalog。

关系模型的实质

每当我批评 SQL,就有人说我其实不理解关系模型,说关系模型本身并没有问题,所以现在我就来分析一下什么是关系模型的实质。其实关系模型比起逻辑式语言,基本就是个衍生产物,算不上什么发明。关系代数其实对应逻辑式语言里面的一个很小的部分——它的数据结构及其基本操作,只不过关系模型有更大的局限性而已。所以学会了逻辑式语言的设计之后,你直接就可以把关系模型这种东西想出来。

每当谈到关系模型,总是有人很古板的追究它与 SQL,Datalog 等“查询语言”的区别。然而如果你看透了逻辑式语言的本质就会发现,其实“语言”和“模型”这两者并没有本质区别和明确界限。人们总是喜欢制造这些概念上的壁垒,用以防止自己的理论受到攻击。追究语言和模型的差别,把过错推到 SQL 和 IBM 身上,是关系式数据库领域常见的托词,用以掩盖其本质上的空洞和设计上的失误。所以在下面的讨论里为了方便,我仍然会使用少量 SQL 来表示关系模型里面对应的概念,但这并不削弱我对关系模型的批评。

关系模型与逻辑式语言

我们先来具体探讨一下关系模型与逻辑式语言的强弱关系。之前我们已经提到了,关系式数据库所谓的“关系”,比起逻辑式语言来说,其实是小巫见大巫。关系式数据库的表达能力,绝对不会超过逻辑式语言。关系式代数里面的“=”,join 等构造都是没有方向的。然而与逻辑式语言不同,这些“可逆操作符”在关系代数里的用法受到非常大的限制。比如,这些可逆操作都不能跨过程,而且关系模型并不包含递归函数。所以你并不能真正利用这种“无方向的代码”来完成比“有方向代码”更加强大的功能,大部分时候它们本质上只是普通程序语言里面最普通的一些表达式,只不过换了一种更“炫”的写法而已。

总是有人声称限制语言的表达力可以让语言更加容易优化,然而如果一个语言弱得不能用,优化做得再好又有什么用。关系模型的核心,其实是普通程序语言里面最简单的部分:表达式。如果缺乏控制结构和递归,这些表达式的能力只相当于最简单的计算器。经验告诉我,就算表达力这么弱的语言,很多数据库的编译器也不能把优化做好,所以这不过是为它的弱表达力找个借口。另外由于这种无方向的表达式让你在阅读的时候很难看清楚数据的“流向”,所以你很难理解这里面包含的算法。这种问题也存在于逻辑式语言,但因为逻辑式语言的表达力在某些方面强于过程式语言,所以感觉还不算白费劲。然而,关系模型有着逻辑式语言的各种缺点,却不能提供逻辑式语言最基本的长处,所以比起过程式语言来说其实是一无是处。

关系模型与数据结构

我们再来探讨一下关系模型与数据结构的关系。很多人认为关系式数据库比起数据结构是一个进步,然而经过仔细的思考之后我发现,它其实不但是一个退步,而且是故弄玄虚,是狗皮膏药。在 IU 的时候,我做过好几个学期数据库理论课程的助教。当时我的感受就是,很多计算机系学生上了“数据结构”课程之后,再来上“数据库理论”课程,却像是被洗脑了一样,仿佛根本没有理解数据结构。经过一段时间的接触之后,我发现其实他们大部分人只是被数据库领域的诸多所谓“理论”,“模型”或者“哲学”给迷惑了。本来是已经理解的数据结构和算法,却被数据库理论给换成了等价却又吓人的新名词,所以他们忽然搞不明白了。我是很负责的老师,所以我努力地思索,想让他们找回自我,最后我成功了。经过我如下的分析,他们大多数后来都茅塞顿开,对关系式数据库应用自如,最后取得了优异的成绩。

其实,关系模型的每一个“关系”或者“行”(row),表示的不过是一个普通语言里的“结构”(就像 C 的 struct)。一个表(table),其实不过是一个装着结构的数组。举个例子,以下 SQL 语句构造的数据库表:

CREATE TABLE Students ( sid CHAR(20),
name CHAR(20),
login CHAR(20),
age INTEGER,
gpa REAL )
其实相当于以下 C 代码构造的结构的数组:

struct student {
char sid;
char
name;
char* login;
int age;
double gpa;
}
每一个 join,本质上就是沿着行里的“指针”(foreign key)进行“寻址”,找到它所指向的东西。在实现上,join 跟指针引用有一定区别,因为 join 需要查软件哈希表,所以比指针引用要慢。指针引用本质上是在查硬件哈希表,所以快很多。当然,这些操作都是基于“集合”的,但其实普通语言也可以表示集合操作。

所谓的查询(query),其实就是普通的函数式语言里面的 filter, map 等抽象操作,只不过具体的数据结构有所不同。关系式代数更加笨拙一些,组合能力弱一些。比如,以下的 SQL 语句

SELECT Book.title
FROM Book
WHERE price > 100
本质其实相当于以下的 Lisp 代码(但不使用链表,执行机制有所不同而已):

(map book-title
(filter (lambda (b) (> (book-price b) 100)) Book)
所以关系模型所能表达的东西,其实不会超过普通过程式(函数式)语言所用的数据结构,然而关系模型却有过程式数据结构所不具有的局限性。由于经典的关系“行”只能有固定的宽度,所以导致了你没法在结构里面放进任何“变长”的东西。比如,如果你有一个变长的数组需要放进结构,你就需要把它单独拿出来,旋转 90 度,做成另外一个表,然后在原来的表里用一个“key”指向它们。在这个“中间表”的每一行,这个 key 都要被重复一次,产生大量冗余。这种做法通常被叫做 normalization。这种方法虽然可行,然而我不得不说这是一个“变通”。它的存在是为了绕过关系模型里面的无须有的限制,终究导致了关系式数据库使用的繁琐。说白了,normalization 就是让你手动做一些比 C 语言的“手动内存管理”还要低级的工作,因为连 C 这么低级的语言都允许你在结构里面嵌套数组!然而,很多人宝贵的时间,就是在构造,释放,调试这些“中间表格”的工作中消磨掉了。

这些就是关系模型所有的秘密。如果你深刻的理解了数据结构的用法,那么通过反复推敲,深入理解以上这番“补充知识”,你就能把已知的数据结构常识应用到所谓的“关系模型”上面,从而对关系式数据库应用自如,甚至可以使用 SQL 写出非常复杂和高效的算法。

另外有一些人(比如这篇文章)通过关系模型与其它数据模型(比如网状模型之类)的对比,以支持关系模型存在的必要性,然而如果你理解了这小节的所有细节就会发现,使用基本的数据结构,其实可以完全的表示关系模型以及被它所“超越”的那些数据模型。说实话,我觉得这些所谓“数据模型”全都是故弄玄虚,无中生有。数据模型可以完全被普通的数据结构所表示,然而它们却不可能表达数据结构带有的所有信息。这些模型之所以流行,是因为它们让人误以为知道了所谓的“一对一”,“一对多”等肤浅的概念就可以取代设计数据结构所需要的技能。所以我认为它们其实也属于技术上的“减肥药”。

NoSQL 的“革命”

SQL 和关系模型所引起的这一系列无须有的问题,终究引发了所谓 NoSQL 的诞生。很多人认为 NoSQL 是划时代的革命,然而在我看来它很难被称为是一次“革命”,最多可以被称为“不再愚蠢”。而且大多数 NoSQL 数据库的设计者们并没有看到以上所述的问题,所以他们的设计并没有完全摆脱关系模型以及 SQL 带来的思维枷锁。

最早试图冲破关系模型和 SQL 限制的一种数据库叫做“列模式数据库”(column-based database),其代表包括 Vertica, HBase 等产品。这种数据库其实就是针对了我刚刚提到的,关系模型无法保存可变长度数组的问题。它们所谓的“列压缩”,其实不过是在“行结构”里面增加了对“数组”的表示和实现。很显然,每一个数组需要一个字段来表示它的长度,剩下的空间用来依次保存每一个元素。所以在这种数据库里,你大部分时候不再需要进行 normalization,也不需要重复存储很多 key。这种对数组的表示,是一开始就应该有的,却被关系模型排除在外。然而,很多列模式数据库并没有看到这一实质。它们经常设定一些无端的限制,比如你的变长数组只能有非常有限的嵌套层数之类,所以它们其实没能完全逃脱关系式数据库带来的思想枷锁。让我很惊讶的是,如此明显的事情,数据库专家们最开头恁是看不到。到后来改来改去改得六成对,还美其名曰“优化”和“压缩”。

最新的一些 NoSQL 数据库,比如 Neo4j, MongoDB 等,部分的针对了 SQL 的表达力问题。Neo4j 设计了个古怪又不中用的查询语言叫 Cypher,MongoDB 使用冗长繁琐的 JSON 来直接表示对数据的查询,就像是在手写编译器里的 AST 数据结构。Neo4j 的 Cypher 语言不但语法古怪,表达力弱,而且效率非常低,以至于几乎任何有用的操作你都必须使用 Java 写扩展来完成(参考这篇博文)。所以到现在看来,数据库的主要问题已经转移到了语言设计的问题,而且它们会在很长一段时间之内处于混沌之中。

其实数据库的问题哪有那么困难。只要你有一个好的程序语言,你就可以发送这种语言的代码到“数据库服务器”,这个服务器可以远程执行你的代码,调用服务器上的“库代码”对数据进行索引,查询和重构,然后返回代码指定的结果。如果你看清了 SQL 的实质,就会发现这样的“过程式设计”其实并不会损失 SQL 的“描述性语言”的表达能力。反而由于过程式语言使用的简单性,直接性和普遍性,会使得开发效率大大提高。NoSQL 数据库比起 SQL 和关系式数据库存在一些优势,也就是因为它们在朦胧中朝着这个方向发展。

然而,NoSQL 并不总是朝着正确的方向发展。因为设计它们的人往往没有专业的修习过程序语言的设计,缺乏对历史教训的认识,所以他们经常犯下不应有的设计错误。我经历过好些 NoSQL 数据库之后发现,它们的查询语言设计几乎完全没有章法。而且由于具体的实现质量以及商业动机,这些数据库往往有各种各样恼人的问题。这是必然的现象,因为这些数据库公司靠的就是咨询和服务作为收入,如果他们把这些数据库高质量又开源的实现,没有烦人的问题,谁会给他们付费呢?

所以,这些 NoSQL 数据库问题的存在,也许并不是因为人们都很笨,而是因为世界的经济体制仍然是资本主义,大家都需要骗钱糊口,大家都舍不得给“小费”。有人说我这是“阴谋论”,可惜总有一天你会意识到,这的确是一个阴谋。如果你想知道跟 NoSQL 数据库公司打交道是什么感觉,可以参考一下我这篇博文里面关于 Neo4j 的部分。

总结

说了这么多,其实主要的只有几点:

关系模型是一个无需有的东西。它严重束缚了人们的思想,其本质并不如普通的数据结构简单和高效。它比起逻辑式语言的理论来说是非常肤浅的。
SQL,Datalog,Prolog 等所谓“描述性语言”的价值被大大的高估了。使用它们的人往往有“避免编程”的心理,结果不得不做比编程还要痛苦的工作:数据库查询优化。
数据库完全可以使用普通的程序语言(Java,Scheme 等)的“远程执行”来进行查询,而不需要专门的查询语言。这在某种程度上就是 NoSQL 数据库的实质和终极发展方向。
对数据库的问题有更多兴趣的人,可以参考我的一篇相关的英文博客,以及这篇《一种新的操作系统的设计》里面的相关部分。

习题

有人评论说我其实不懂 SQL,现在我就来考考你的 SQL 编程能力,看看到底是谁理解 SQL 多一些 :)

题目:请用 SQL 实现 Dijkstra 的最短路径算法。

为了加深对数据库的认识,每个人都应该用 SQL 来实现这样稍微复杂的算法,而不只是写一些高中生都会的基础程序。如果你仍然相信“What,not How”的广告,反对使用 SQL 来写这样的过程式算法,那么就请你更进一步,使用你所谓的“What 查询方式”来高效的解决最短路径问题。