Apache Drill的ValueVector数据结构说明

wslhs

原创，转载请注明出处。
关注很久的hadoop实时计算框架drill终于发布了他的里程碑的第一版本。
官网地址：
http://incubator.apache.org/drill/
目前开始慢慢学习，首先翻译一份官方文档，介绍Apache drill的数据结构ValueVector。
完成于2013年11月03日凌晨0：30

[size=medium]Value Vectors
本文档的作用是描述定义在Operator之间传递列式数据的时候所需要的数据结构。

Goals
Support Operators Written in Multiple Language（多语言支持）
ValueVector 需要支持使用C/C++/汇编语言的操作。这就需要底层的ByteBuffer在通过JNI传递的时候不需要被修改。ValueVector 一旦被创建之后就不可变。字节码的顺序也需要不用考虑。
Access
随机读取ValueVector元素的时间需要固定，需要解决这个问题， ValueVector中的元素通过在buffer开头中偏移量来进行识别。重复的数字，null值，变量的宽度的ValueVector利用额外固定的宽度value vector 来索引每一个元素。当ValueVector 被RecordBatch构建完成之后写操作是不被允许的。
Efficient Subsets of Value Vectors
当一个operator返回一个ValueVector中的子集的value的时候，他应该重用初始的ValueVector。这就需要一种间接层来跳过某些ValueVector中的值。这个间接层是一个偏移量序列，而这个序列引用了原ValueVector中一个偏移量，在子集中同样包含了数值的计数值。

Pool Allocation
ValueVector利用一个或者多个buffer。这些buffer可以从pool中提取出来，在record迭代过程中ValueVector会由于schema的改变而被created或者destroyed。

Homogenous Value Types
在一个ValueVector的每一个value都是相同的类型。RecordBatch的实现负责在schema出现变化的时候创建一个新的Value Vector。


定义

Data Types
权威的value 类型定义的说明文档参见
https://docs.google.com/spreadsheet/ccc?key=0AvUC_YMxQ9UkdE5kbHpfMzE1YlBSSkx0a0NrRnh1cFE#gid=0
其中分为两个Tab：Basic Data Types，Value Vectors

Operators
一个Operator的作用是转换field流。他可以操作Record Batches或者constant values。
Record Batch
一定范围记录的field value集。当每一个batch包含一个schema的时候，Batch可以由Value Vectors组成。
Value Vector
由一个或者多个连续的buffer组成，每一个Value Vector 保存了一些列的value，以及和Value Vetor对应的0个或者多个元数据信息。

Data Structure
ValueVector将数据保存在ByteBuffer中，ByteBuffer他是一段连续的内存。Additional levels of indirection被用来支持变量值的宽度（variable value widths），null值（nullable values），以及重复数据（repeated values）和selection vectors。 levels of indirection主要是一些lookup tables，这些表是由一个或者多个固定宽度的ValueVectors（这些ValueVectors可以合并，比如说存储了null值，或者variable width values）。一个固定宽度的ValueVector，存存储了非空值，非重复值的时候就不需要查询。ValueVector中的元素可以通过将position信息和Stride信息相乘来直接访问。

Fixed Width Values
Fixed width ValueVectors 仅仅包含一段value序列。通过ByteBuf[0] + Index * Stride公式可（index 从0开始）以随机访问Fixed width ValueVectors 的数据。比如INT4类型的数据结构如下图：




Nullable Values
Nullable Values由一个bit 值向量来表示。向量中每一个bit都对应了ValueVector的一个元素。如果某个bit咩有被设置，那么这个value就为null，否则value将会从下面的buffer中提取出来。
下图解释了一个INT4值2,3,6为空的时候NullableValueVector的对应关系：



Repeated Values
repeated ValueVector适用于包含多个值的元素（比如说JSON）。如下图中一个包含offset和count对table被用来指示ValueVector每一个重复的元素。Count等于0表示ValueVector中元素不包含值，注意offset没有被使用：



Variable Width Values
Variable width values保存在ByteBuffer中连续的位置，每一个元素都由一个fixed width ValueVector中的条目表示。一个条目的长度从其下方的数值中提取推算出来。




Repeated Map Vectors
repeated map vector包含一个或者多个map（类似于JSON中的对象数组），map的value会被保存在ByteBuffer中的连续的位置。如果要访问一条记录，就需要一个count-offset的可寻址表。lookup table指向每一个column中第一个重复的filed，而count表示这个column中包含了多少元素。




Selection Vectors
Selection Vectors代表了一个ValueVector的子集。他包含一个能识别ValueVector内部元素的offsets列表。对于一个fixed width ValueVector,，offsets代表了byteBuffer下面的元素的位置。



对于Nullable，repeated，variable width ValueVector，这些offsets指向了相应的lookup
Table。
下图解释了一个ValueVector（他是INT4类型，数值为1。。6）的SelectionVector包含了Int4值2,3,5