如何看待王垠对数据库的理解？

肤浅至极，给大家展示什么叫隔行如隔山。

作为一个研究数据库系统的人，明确告诉大家SQL的这层“非指令式”是现代数据库大多数性能提升的来源。所谓NoSQL快，只是在特定情况下而已。 比如把数据库当成一个不会丢失的hash table来用，那么K-V store显然会比支持ACID transactions和各种分析性事务的RDBMS要来的高效。

该文的一堆“就是C的struct， 就是指针, 为什么不能RPC”等等错误言论，本周放假无聊，逐条批驳。

讲到数据库系统， 首先要明确的是为什么需要用到数据库系统。 王垠开篇便开始详尽叙述数据结构和数据库的相同之处，如何“一个表本质上是一个数组”等等。 这是典型的本末倒置。 研究一个系统的时候，首先需要明确的是这个系统解决什么样的问题，给使用者提供了什么样的假设和便利，来把原来复杂的问题简单化，然后才研究以什么样的API或者编程范式来展现给使用者。后者的选择受到前者的限制。那么为什么需要一个数据库系统呢？现代计算机的存储技术很大程度上分为快速但可丢失的内存储（寄存器，多层缓存，DRAM）和缓慢但断电不丢失的硬盘，SSD等。数据库系统存储设计的本质是简化以及优化程序和外存储的互动。

数据库系统设计的根本问题是，内存储快但是断电会丢失数据，外存储虽然相对可靠但是比内存储慢了一个数量级，不可能所有操作都直接读写硬盘（DRAM读写速度大约10-20倍于SSD， 对于HDD更加明显， 硬盘延迟是80倍左右）。而且由于现代计算机存储架构的原因，CPU不能直接操作硬盘，需要把硬盘数据先读入内存，然后进入缓存，然后读取到CPU寄存器上。同一份数据，在读写过程中自然地有多份copy，而且他们之间不自动同步。数据库系统的职责就是， 在这样的硬件环境下，保证性能并且保证不会丢失数据。

解决这个问题的方式，是由单独的数据库系统进程来管理其他程序与硬盘的互动。因为硬盘读写十分缓慢，数据库系统可以集中几次操作的量，一起写出，来保证速度。打一个比方就是一群人需要去图书馆借书（读数据）还书（写数据），但是从住处到图书馆的车程要十个小时，而且路窄易堵车。与其每个人不停开车来回全部堵死在路上，更有效地办法是指定一个人定期收集大家要借的书单和要还的书，定期往返。 数据库系统就扮演了这样一个角色。

那说到这里很多人就要问了，这活操作系统不就能做了吗，费那功夫干什么？

答案是操作系统只是一个开车的文盲司机，而数据库系统是一个会开车的图书管理员。车的后备箱里容量是有限的，与其一车一车地运，数据库系统知道，如果顾客要借一本新华字典，肯定不是为了闲着没事翻翻玩的，而是要查字典用。所以，如果顾客事先说，“我需要一本新华字典，查找“颰”字的读音”， 或者"我需要一本新华字典，数一下一共多少字是木字旁的"， 数据库系统不需要借两本新华字典，只需要找到一本，并且算出答案，写在小纸条上给他们就好了。

同样在还书的问题上，因为操作系统是一个文盲，顾客只能让其“把这本书放到左边第二个书架的第三个空格上去”。顾客自己必须脑海里有一套图书管理体系，并且和其他顾客商量好。但是数据库系统是图书管理员出身，所以只要把书给他，他就可以自己把书放到正确的地方，方便下次查找。

那么接下来说数据丢失的问题。首先，停电，系统崩溃这种事情不是人能控制的。灾难可以在任何时候发生。就算我们的数据库系统根本不在乎性能，每次读写都直接走硬盘，依然会出现如下的问题：

操作：

1. 找到写了“别人什么都不懂”的硬盘区域
2. 覆盖写入“老王什么都懂”

写入的操作并不是一次完成的，字要一个个写。这个时候，在写入“老王”的时候，突然有人踢到了电源线，断电了。于是，硬盘上的数据是这样的：

“老王什么都不懂“

更不要说数据散落在内存和硬盘两地的状况了。数据库系统的职责就是，在系统恢复的时候，记住原来的操作，意识到现在的数据是不对的，并且在别人重新开始读取之前把数据改对了，要么改回“别人什么都不懂”，要么改成“老王什么都懂”。并且关系型数据库的能力不仅可以做到这个，还可以保证随意大小的操作，只有发生过和没有发生过两种结果，在任何时间点绝对不会出现发生了一半的状况。

具体的实现比较复杂（论文在此https://cs.stanford.edu/people/chrismre/cs345/rl/aries.pdf），在此不复赘述。

明确了数据库的根本目的之后， 一条一条批驳这篇文章的无知观点

可以说，“只告诉它 What，而不是告诉它 How”，只是一个不切实际的妄想，而且它并不是 SQL 首创的想法

从一个高级语言编译到低级语言，确实不是首创的想法，因为所有现代语言都是这样的。我写C的时候只告诉电脑要一个变量”int a“，不告诉它要存在内存的哪里，还是放在寄存器里，也不告诉它整数是什么，存几个字节，真是一个不切实际的妄想啊。

Prolog （miniKanren）的性能问题在 SQL 里面得到了部分的缓解，这是因为 SQL 对于基本的数据结构进行了“索引”

不，索引是要人去建的，SQL只是有一个优化器而已。

然而 SQL 的表达力也受到比 Prolog 更大的限制。很多 Prolog 可以表达的问题，SQL 没法表示。所以后来你就发现，SQL 其实只能用于非常简单的，适合会计等人员使用的查询操作。一旦遇到程序员需要的，稍微复杂一点的数据结构，它就会引起诸多的性能问题。

对于一个设计出来给会计等人员用的简单的查询操作的语言，听起来没什么不对的？

更要命的是，这种性能问题的来源是根本性的，不可解决的，而不只是因为某些数据库的 SQL 编译器不够“智能”。很多人不理解这一点，总是辩论说“我们为何需要 Java 而不是写汇编，也就是我们为何需要 SQL。”然而，把 Java 编译成高效的汇编，和把 SQL 编译成高效的汇编，是两种本质上不同的问题。前者可以比较容易的解决，而后者是不可能的（除了非常个别的情况）。

请多读论文少胡思乱想，这年头你的数据库不把SQL编译成汇编都不好意思出去和人打招呼。

我只举一个例子来说明这个问题。如果你需要迅速地在地图上找到一个点附近的城市，SQL 无法自动在平面点集上建造像 KD-tree 那样的数据结构。这是很显然的，因为 SQL 根本就不知道你的数据所表示的是平面上的点集，也不理解平面几何的公理和定理。跟 B-tree 类似，知道什么时候需要这种特殊的索引结构，需要非常多的潜在数学知识（比如高等平面几何），所以你肯定需要手动的建立这种数据结构

没有错，从来都是手动建的。SQL从来没有说过要帮你建。

你发现了吗，你其实已经失去了所谓的“描述性”语言带来的好处

没发现，毕竟建好的index用哪个，怎么用，是SQL优化器选的，依然不需要人来选。

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

如果手动建一个index你都懒得建，你会去直接用过程式语言写上万行代码来保证ACID？

而其实，数据结构的理论，可以很容易的解释所有关系式数据库里面的操作

首先，废话，大家都是图灵完备的。其次，数据库的操作在加上transaction以后自带了对于断电等情况的应对，需要相对应加强代码的理论模型（https://pdos.csail.mit.edu/papers/fscq:sosp15.pdf）来应对这样的语义。

每一个“foreign key”，其实就是一个指针

foreign key更接近于一个”reference“，而不是C语言里的pointer。有人可能要问这俩有啥区别，pointer本质上是一个东西的物理位置（内存地址0xdeadbeef开始的10个字节），而reference只是泛指找到某个东西的办法，可以通过物理位置，也可以通过别的方式。数据库里的foreign key不是pointer。数据库经常需要把数据更换位置来解决存储碎片化的问题，不可能用pointer来实现这个。

每一个join操作，本质上就是对指针的“访问”，找到它所指向的对象

看好了上面有多少种基础的join。（分布式数据库等会有更多种类）Join有没有foreign key都可以执行。这位老兄怕是只写过equi-join。

在实现上，join跟指针引用有一定差别，因为 join需要查“索引”（index），所以它比指针引用要慢。

如何实现一个Join是由数据库查询优化器（Query Optimizer）来决定的，基础的算法就有nested-loop join, sort-merge join, hash-join等好几种，也会有用索引和不用索引，甚至半用索引的区别。优化器会根据对于数据分布的理解挑选合理的join顺序和算法来实现每一个join。

至于用指针来实现join，你有种写一个给我看看。

所谓的查询（query），本质上就是函数式语言里面的filter, map等操作。只不过关系式代数更加笨拙，组合能力很弱。

SQL操作的data model是relational bag algebra (有别于Codd本来的relational algebra，基于集合)， 和函数式编程可以转换，但是没有可比性，只能说各有优劣。你用functional给我写几个join看看，是不是还觉得SQL笨拙。

由于“行”只能有固定的宽度，所以导致了你没法在里面放进任何“变长”的对象

打脸啪啪响，现代数据库系统不是严格基于Codd的Relational Algebra的。那些1-NF， 2-NF, BCNF 的东西基本没有人理睬。

比如，如果你有一个数组，那你是不能把它放在一个行里的。

当然可以，刚刚贴的doc。

你需要把数组拿出来，旋转90度，做成另一个表B。从原来的表A，用一个“foreign key”指向B。这样在表B的每一行，这个key都要被重复一次，产生大量冗余。

如果是嵌套式的，那么不止A的foreign key，A的整个行都要重复好几次嵌套到B里去。更加不要说update一次A的值需要把所有持有A的B的值一起update的问题了。normalization在很多情况下更高效（多个B的值指向同一个A, A表加一列等等）。

使用基本的数据结构，其实可以完全的表示关系模型以及被它所“超越”的那些数据模型

之所以用数据模型，是因为需要实现ACID数据库的数据结构一点都不基本。您用C写完了自己的数据结构以后请加上一个buffer pool，WAL，disk-backed B Tree，并且写上所有高并发的优化来解决transaction的问题。

数据模型可以完全被普通的数据结构所表示，然而它们却不可能表达数据结构带有的所有信息

这句话大体是正确的，但是用数据模型的原因不就是因为你不需要在乎数据结构的信息吗？你写个webapp在乎Bw-Tree是怎么实现lock-free的吗？明明是好处，却被当作了问题。

最早试图冲破关系模型和SQL限制的一种技术，叫做“列模式数据库”（column-based database），比如Vertica, HBase等。

Vertica是使用SQL的RDBMS。Column-Store诞生是为了更有效地解决大数据分析的问题（OLAP workloads），节省硬盘I/O（就是所谓列压缩），运用SIMD等等。不知道这和逃脱SQL有什么关系。

很显然，每一个数组需要一个字段来表示它的长度N，剩下的空间用来依次保存每一个元素，这样你只需要一个key就可以找到数组里所有的元素，而不需要把key重复N遍。

这是什么压缩算法？把字典压缩理解错了？把run-length压缩理解错了？这怎么解决变长问题?

其实数据库的问题哪有那么困难，它其实跟“远过程调用”（RPC）没什么两样

RPC最著名的问题就是怎么在保证性能的情况下靠近"Exactly Once"的semantics。数据库相反，一定要”Exactly Once“，然后再来看性能能提升多少。完全不一样啊。

只要你有一个程序语言，你就可以发送这语言的代码，到一个“数据服务器”。服务器接受并执行这代码，对数据进行索引，查询和重构，最后返回结果给客户端

恭喜您发明了Spark。但是这怎么解决写入的问题？

如果你看清了SQL的实质，就会发现这样的“过程式设计”，其实并不会损失SQL的“描述”能力

牺牲的不是”expressiveness“，是”guarantee“。还记得那个只知道往左边第二个书架的第三个空格上放书的文盲司机吗？