ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
###  “神秘”的r和d **单从数据结构来看的话**,我们可以这样解释r和d的含义。r代表着当前字段与前一字段的关系,是在哪一层合并的,即公共的父结点在哪?举例来说,假如我们重建到了Code='en',通过r=2可以知道是在Language那一层发生了重复。 ![](https://box.kancloud.cn/2016-08-31_57c6b136ae7a5.jpg) 为了保持原纪录的结构,我们会保存一些NULL数据,而d就是用于重建NULL字段。通过d的值,就能知道NULL的结构。例如下图,通过r=1知道应该合并到Name那一层。而通过d=1则知道路径上只有一个字段,即不仅仅是Code字段不存在,Language也不存在。这样就把NULL正确地重建出来了,那么接下来的Code='en-gb'的层级也就不会乱了。 ![](https://box.kancloud.cn/2016-08-31_57c6b136c83d4.jpg) 然而这只是从静态的数据结构来解释,而r和d的深层次含义还是要看FSM是如何执行的。**真正的因果关系是FSM的执行方式决定了数据结构的设计**。 ### 3 记录查询 ### 3.1 从FSM角度看r和d 先看一下前面例子的完整FSM的样子。如果把Protocol Buffer中对数据格式定义的schema看作是编译原理中的语法定义的话,那么一般可以使用工具如antlr, yacc自动生成自动机,手写的话是相当恐怖的吧。 ![](https://box.kancloud.cn/2016-08-31_57c6b13696f5e.jpg) 对列数据的完整遍历就是这个样子的: ![](https://box.kancloud.cn/2016-08-31_57c6b136f1874.jpg) 在讨论查询如何执行之前,先继续刚才未完成的题目,r和d的本质,这次通过动态的FSM的角度来分析,而不是静态的数据结构了: Ø  **FSM状态机只是定义了状态的变更,即处理流程应当如何在各个列的存储表之间跳转,而实际数据还是在表中保存**。有点像数据库索引,遍历时是根据FSM进行跳转,然后对某一列的表进行table scan。但索引是靠字段值的顺序组织,因为数据库表之间没什么嵌套关系,而Dremel的FSM则是靠字段之间的嵌套关系来组织。 ![](https://box.kancloud.cn/2016-08-31_57c6b1371fafc.jpg) Ø  状态机中线条上的数字表示什么?回忆一下,数字表示的是:字段的数据表中当前行的下一行的r值。通过检测下一个r值来决定跳转。因为**r=0,则说明下一行与当前行所表示的字段一定不在同一路径,否则必然会在某一Level上有共同的字段(路径的部分重叠)**。注意这是由于Protocol Buffer的schema不是树,没有共同的根所导致,否则所有字段必然都会在根重复,上面对r的解释也就没意义了。以repeated的Forward为例,检查到下一行r=1说明40、60都是接在20字段下面的。Code字段也是同样道理。 ![](https://box.kancloud.cn/2016-08-31_57c6b137347b4.jpg) Ø  Name.Language.Code到Name.Language.Country之间的线上为什么是0,1,2?因为Name.Language.Code是required不是repeated,读取后不管下一行的r值是多少都要去读Name.Language.Country。同理Name.Language.Country也是读完不管怎样都跳到下一字段。 Ø  最复杂的要属Name.Url了,因为它是schema里定义的最后一个字段。在Name.Url这要决定到底是继续下一文档如r2的处理,还是跳回到本文档的其他字段继续处理。具体分析一下:**r=0说明当前文档中没有Name字段了**。为什么这么说?因为如果文档后面真有Name字段,假如下面有Url,则当前表中的下一条应该是r=1;**假如下面没有Url,则当前表的下一条应该是r=0的NULL。这里NULL又发挥用处了!所以中间部分的NULL能保持结构无损,而后面部分的NULL能提示文档是否结束**。 ### 3.2 查询引擎 至此,我们已经彻底摸清Dremel数据模型以及FSM的基本运行方式了。现在终于可以分析Dremel是如何解析和执行类SQL查询的了。查询语言类似SQL,输出也是个嵌套式的记录,以及schema定义。 ![](https://box.kancloud.cn/2016-08-31_57c6b1374f185.jpg) 那么查询引擎如何执行呢?首先为查询语句中涉及到的每个字段都打开一个Reader来读取数据,然后就是根据WHERE中的条件过滤以及根据SELECT中的条件投影并聚合了。难点在于:**重建出层次关系,再进行过滤和聚合**。例如,过滤掉DocId=20很容易,但其实文档r2的所有记录都应被过滤。因为WHERE中两个条件是AND关系,同时DocId又是最底层的字段,所以相当于r2这一整棵树都被裁剪掉了。Code=en-gb也是由于所在的Name字段下没有满足http开头的Url字段,而被间接的过滤掉了。 聚合也是同样道理,有了层次关系,才能正确的聚合。例如Code=en-us,en和Url=http://A是同一个Name下的,COUNT和字符串拼接时会一起处理。而Url=http://B则是另一个Name下的,要分开处理。 ![](https://box.kancloud.cn/2016-08-31_57c6b137631b9.jpg) ### 参考资料 1 Dremel: Interactive Analysis of Web-Scale DataSets