速看projection(projection operator)

麻雀虽小 五脏俱全

 

中文名：顾仲贤现任Facebook资深架构师专注于数据库，分布式系统，数据密集型应用后端架构与开发拥有多年分布式数据库内核开发经验发表数十篇数据库最顶级期刊并申请获得多项专利对搜索，即时通讯系统有深刻理解。

爱设计爱架构，持续跟进互联网前沿技术个人经历: 2008年毕业于上海交大软件学院；12年，4年时间完成在美国加州大学戴维斯分校的学习并获得计算机硕士，博士学位；13-14年任Pivotal数据库核心研发团队资深工

程师，开发开源数据库优化器Orca;共发表4篇相关论文(总引用近100)并获得相关专利；15-16年追随原Pivotal总监一同参与创立Datometry，任首席工程师，负责全球首家数据库虚拟化平台开发；17年至今就职于Facebook任资深架构师，领导重构搜索相关后端服务及数据管道; 管理即时通讯软件WhatsApp数据平台负责数据收集，整理，并提供后续应用。

 欢迎阅读数据库内核杂谈的第一篇今天我们摒弃直接介绍数据库内核各个模块的思路，而是从应用开发者的角度出发，来看实现一个数据库需要哪些基本功能，然后把这些功能细分成最小的模块再手把手一起实现，帮你揭开数据库内核的神秘面纱。

希望能够减轻你对学习数据库内核的压力我们也可以从中体会到，九层之台，起于累土所有复杂的系统，都是通过模块化的架构和设计，以及工程阶段的精益求精，一步一步累计起来对与应用开发者而言，一个数据库需要哪些必要的功能呢？我觉得，下面这些是必不可少的：

1）创建数据库和数据表：create database，schema, table等2）存储数据：insert /update数据，或者从其他方式导入数据(比如csv文件)3）读取查询数据：通过SQL语句，对数据进行读取和查询，比如sort，aggregate，filter等

根据这三个功能，再回看标题，你可能产生疑问，一个小时就能实现上面这些功能，不会是标题党吧我承认，有一点小小得标题党了因为要和数据库交互，最必要的条件是有个客户端程序可以接受用户送来的指令但要实现一个功能齐全的Parser可得花不少精力。

既然是内核杂谈，请允许我偷个懒，假设Parser已经有实现，从而把精力都关注在数据库系统内部的实现抛开Parser，又该从哪开始呢？我的思路是跟着数据的流向，自下而上，依次从存储数据，读取数据和查询数据来看。

创建和存储数据当用户创建一个新的数据库，并导入数据时，数据库系统就需要存储这些数据说到存储，第一个想法就是文件系统（其实说到底数据库系统就是一个特殊的文件系统，区别与普通文件系统提供的的读写文件的接口，数据库只是提供了一个面向数据的接口：存储，读取和查询；整个系统为这些接口提供服务)。

以下图student表作为示例，要怎么把这张表存在文件中呢？

Student表最显而易见的就是用Comma-separated value(CSV)格式存:1,"Xiaoputao",3,"Hiking"2,"Zgu",3,"Running"3,"Xiaopang",2,"Walking"

读取CSV文件的逻辑也非常简单: 一行一行读取数据，然后根据";"把每个数据段取出除了CSV存储，另一种常见的方式就是json格式:[ {"id":1, "name":"Xiaoputao", "class":3, "hobby":"running}, ... ]。

聊聊CSV和JSON存储的优缺点两者都属于文本存储，优点一在于易于人类理解另一个优点就是直接兼容其他支持CSV和JSON的数据库缺点也很明显，存储效率不高，读取效率也会随之降低另一个问题在于，上述例子中存储的内容只有值，没有type和size(metadata)，这些信息在后续操作如校验中是很重要的。

当然，我们可以把metadata加入到存储中，比如，把json的每个val变成一个obj:{"colName":"id","colType":"int","colSize":4,"colVal":1}专业数据库肯定不会选择用CSV或JSON作为默认存储，但几乎都支持CSV和JSON数据作为external table。

如果要追求更高的性能，我们可以选择更高效的编码方式把数据以字节流的形式存储在文件中；只要数据库系统自身能够读取这些数据即可咱们既然时间有限，当然是一切从简，就选择CSV或者JSON的文件格式来存储我们的数据。

只要有一个文本编辑器，能够创建和编辑CSV或者JSON文件这其实这已经完成了创建数据表，输入，修改以及存储数据的功能读取数据基于上述用CSV或JSON的存储，读取数据非常简单(允许我们调用第三方支持CSV或者JSON的API)。

重点在于读取完存放在怎样一个数据结构中方便后续对数据进一步的查询操作根据数据的特性，结果集(RowSet)是由一序列的行数据(Row)组成，每一行又由多个单元(Cell)组成我们试着根据这个概念设计下面这些类：。

Cell, Row, RowSet Class简单梳理下，每个Cell存type，size，和value；Row存一整行cell；RowSet存一序列的Row具体在实现中还有很多细节需要注意，如typecheck, 确保每行列数相同，等等，这里也一并从简略过。

定义了存储方式和数据结构，具体数据读取代码如下

读取csvToRowSet和jsonToRowSet的实现只需要借助第三方CSV和JSON的类库就能实现，就不赘述代码了这一节里，我们定义了Cell, Row, RowSet的数据结构来存放从文件(CSV或JSON)中读取的数据，并给出了示例代码。

执行查询有了存储和读取，已经可以把数据从文件中读取到内存，接下来就要支持用户的查询语句了实现查询就是去实现SQL语句中的各个功能模块，比如排序(order by), 聚合(group by)，多表联合(join)等等。

执行器会对每个功能模块进行实现，甚至针对不同的数据分布，会有多种方式的实现来提高读取速度现在，我们一起来讨论一些常用的语言功能全表读取(SELECT *)其实，定义了RowSet的数据结构和实现了读取文件的接口，我们的数据库就已经支持全表读取的SQL语句，示例如下：

SELECT * FROM student;分页语句(LIMIT)一下子就能想到的分页语句，用来限制输出的数据行数：

Limit Operator一行代码，不解释了抬走！关系映射语句(PROJECTION)关系映射的本质是对于输入的RowSet的每一行(row), 通过各种标量计算，输出一个新的数据行，再由这些行组成新的RowSet。

见下图示例：SELECT id + 5, LEN(name) FROM student;对从student表读取的每一行数据，输出一个新的数据行包含 id + 5 和 LEN(name)的cellsProjection可以非常复杂，但有一条准则就是它不改变原有RowSet的基数(cardinality), 即新RowSet的行数和原来的相同。

因此，无论映射逻辑多复杂，输入一个Row，输出一个Row再复杂的计算，也是一比一步迭代产生比如上述示例可以分解成下面这些操作来完成：对于每一行input row, id值加5，对name取length，最后去掉class和hobby两列。

归根结底就是将复杂的运算拆分成原子操作然后一步一步地顺序执行我们可以定义如下两个基本operator：RowComputeOperator根据定义的computeCellVal对input row计算一个新cell，并把这个cell加到原row的末尾。

SelectionOperator根据给定的indexes，生成一个仅包含指定index的新rowPseudo code如下：

RowComputeOperator and SelectionOperatorRowComputeOperator里面有需要定义computeCellVal，输入是一个row,输出一个新的cell具体实现则根据具体语义来定。

定义一个computeCellVal需要2个参数：1）运算作用在哪些cell上，假设限制只能作用在1个或2个cell上(2个以上可以用多个Operator嵌套)；2）提供具体计算的操作，比如常见单元操作如len(), ceiling(), abs()或者常见的二元操作如+-*/等等。

有了这两个基本operator, 实现示例中的projection，我们定义3个operator即可：1）compute a new cell using "(id + 5)" 2) compute a new cell using "len(name)" 3) 用SelectionOperator选择最后两个新生成的cell。

实现整个projection的operator的pseudo code如下：

Projection Operator条件选择语句(WHERE)有了Projection，我们就可以实现下面的条件选择语句(WHERE)了：SELECT * FROM student WHERE class = 3;

实现想法很简单，首先用Projection operator计算出filter condition的值(bool)，然后filter by 这个cell即可。

Filter Operator排序语句(ORDER BY)这里，我给一个非常低效但很容易理解的实现：创建一个hashmap来存，然后对要sort的cell排序，根据cell顺序取出原row组成新的rowSet输出：

Sort Operator有读者会问，如果排序语句是一个expression而不是单个column怎么办？比如下面的示例:SELECT * FROM student ORDER BY id + 5 ASEC;

还记得我们前面实现的projection吗？这里把(id + 5)作为一个新的projection加入到Row中即可一起实现了4个Operator，看看有没有什么规律可循？所有定义的操作都是基于一个原则：输入一个RowSet，然后输出一个RowSet。

并且，是一层一层循序渐进的迭代对于数据的查询操作，是从最初读取表中的原始数据开始，根据给定的Operator序列对数据逐一进行操作；这一个Operator的输出就是下一个operator的输入也就是说，给定一个SQL查询语句，我们生成一序列Operator的tree，再依次执行，就能得到最终结果。

现在来一起优化下代码，把Operator的接口抽象出来，然后把刚才实现的operator全当成子类来实现代码如下：

Unary Operator有读者会有疑问，基类为什么叫UnaryOperator呢？先卖个关子有了基类，我们可以根据SQL的语法功能实现相应的Operator聚合操作(AGGREGATION)接着一起来实现聚合操作。

Aggregation分为两大类，scalar-agg和multi-aggscalar-agg就是简单的sum, avg, min, max等的数据聚合操作，最终返回一个数据行的结果集，实现代码如下：

Scalar-agg每个AggOp接受一序列的cells，然后输出聚合结果的cell常见的AggOp如sum, max，min实现都很简单，这边就不赘述了multi-agg对应SQL中的GROUP By，如下图示例：。

SELECT class_room, COUNT(*) FROM student;比scalar-agg复杂的地方就是先要把有相同值的group by columns(示例中为class_rom)的row合并起来，然后对合并后的rows做Scala-agg即可。

代码我就不贴啦，当留个小作业给大家SQL Operator Tree有了实现基本语义的Operator，要实现一个完整的查询语句，我们要做的就是把operator一层一层的累加起来，形成一个Operator tree，然后根据这个operator tree, 依次执行每一个operator即可。

比如下面这个查询语句：select class, sum(id + len(name)) as c   from (    select * from student where hobby = hiking limit 10

    )   group by class;我们只要建立如下的Operator tree：

sql operator tree有没有觉得挺神奇的！即使再复杂的查询SQL都能这样用基本的operator像搭乐高一样搭建起来小结至此，我们简单的数据库也实现得差不多啦我看了下自己写的pseudo code仅仅200多行，一个小时写完也不算条件太苛刻。

虽然数据结构冗余，算法低效，但是麻雀虽小，五脏俱全！来解释前面卖的关子，为什么基类定义为UnaryOperator？因为我们还有BinaryOperator二元的操作是做什么的呢？答案就是为了表与表的联合(join)。

有了Binary Operator，Operator的叠加就真正变成了一颗树(二叉树)，这也是为什么前文我们称之为operator tree本文就先不详述如何实现Join Operator了，以后会有专门的章节来覆盖。

再讲下去，肯定超过一个小时，读者就更觉得我标题党了最后给大家总结一下：1）一个SQL的查询语句，即便逻辑再复杂，也可以拆分成一个一个原子operator的叠加2）把这些operator组建成一个operator tree，然后自底向上地依次执行，就能得到最终的查询结果

3) 你可能觉得真正的数据库和我们在这捣鼓的很不一样如果有条件，可以在Mysql或者Postgres中运行"EXPLAIN SQL_STMT"来打印它们生成的operator tree，你会发现和我们生成的树挺相似的。

4) 相信大家都非常熟悉用SQL做各种数据查询，但可能从没去想过底层是怎样实现的希望这篇博客对你有所帮助正所谓，知其然，知其所以然！下一篇，咱们深入聊聊存储!--- END ---文章来源丨简书作者丨Dr_GU。

整理：CTOA-吴贝贝

免责声明：本站所有信息均搜集自互联网，并不代表本站观点，本站不对其真实合法性负责。如有信息侵犯了您的权益，请告知，本站将立刻处理。联系QQ：1640731186