ORC索引的位置信息

ORC索引的位置信息

ORC是Hadoop生态圈里一种流行的列式存储格式，自带schema和索引。索引是用来加速查找数据的，当查询条件能用上索引时，就跳转到文件对应位置来读取，跳过无关的数据。因此文件里的索引是要记录一个位置信息的，这样才能跳转。最近在debug时发现索引记录的位置信息不太好理解，这里记一下笔记。

一个ORC文件按行横向切分成多个Stripe，每个Stripe里分成三部分，分别是索引、数据（Raw Data）和Stripe Footer。索引和Raw Data部分都按列来存储：

（图片复制于https://orc.apache.org/specification/ORCv1/）

ORC的索引分为Row Group Index和Bloom Filter Index。这里的Row Group不是Parquet里的Row Group，而是指默认每10,000行（可调）。ORC里的Row Group是用来生成索引的，数据并没有按Row Group来切分。也就是默认每一万行生成一个索引（Row Group Index），在文件中跳转（seek）时，步长就是一万行。

Bloom Filter Index是可选的，在Hive中生成ORC文件时，需要在表属性里用orc.bloom.filter.columns 配置为哪些列生成Bloom Filter Index。其粒度也是Row Group，即每个Row Group配一个Bloom Filter Index。所以Bloom Filter Index里就没有记录需要跳转的位置信息了，直接使用对应Row Group Index里的就行了。

它们的protobuf定义如下：

message RowIndexEntry {
  repeated uint64 positions = 1 [packed=true];
  optional ColumnStatistics statistics = 2;
}

message RowIndex {
  repeated RowIndexEntry entry = 1;
}

message BloomFilter {
  optional uint32 numHashFunctions = 1;
  repeated fixed64 bitset = 2;
  optional bytes utf8bitset = 3;
}

message BloomFilterIndex {
  repeated BloomFilter bloomFilter = 1;
}

可以看到RowIndex由多个（repeated）RowIndexEntry组成，每个RowIndexEntry由多个64位整数和一个可选的统计信息组成。BloomFilter部分没有位置信息，这里就不展开了。

位置信息是多个64位整数，一开始我以为是多列的位置信息，但后来发现索引是按列存储的，第一个列的索引写完才写第二个列的索引。因此每个RowIndexEntry实际上对应的是某一列属于某个RowGroup的数据，记录的也是那个列的起始位置信息。即然是一列，为什么不是用一个position表示文件里的offset就行呢？

ORC文件里的每一种列的类型，都是由多个stream来存储的。比如说int类型，就是用一个bool的stream和一个int stream表示的。前者标记某行数据是否为null，后者保存所有非null数据。读的时候是同时读这两个stream的数据进行解析，那跳转的时候就需要记录这两个stream的位置了，因此至少需要2个位置信息。每种类型的列都有一个present stream和一些保存真实数据的streams，因此索引都至少要记录两个位置信息。

这还没完，stream会被编码和压缩，记录stream里的位置可不是一个offset这么简单。

先说编码，stream里的原始数据会被切分成段然后用Run Length Encoding算法进行编码。每一段称为一个Run，解码时也需要先读这个Run的header，才知道如何解码（编码类型、Run的长度）。因此在这样的编码流里记录位置，就需要记录所在Run的header起始位置和在Run里是第几个数。

再说压缩，ORC可以配不同的压缩算法对stream进行压缩，默认是使用zlib，压缩比大。不过要权衡性能和压缩比的话，还是建议用Snappy等其它的算法。为了让stream可以被分段读取，压缩也是分段进行的，每一段称为一个chunk，默认大小是256KB。压缩完如果发现空间变大了，就会使用未压缩的chunk。所以每个chunk需要有个header记录压缩后的长度，以及是否有使用压缩。如图

（图片复制于https://orc.apache.org/specification/ORCv1/）

每个chunk使用3个字节作为header，后面接压缩或者未压缩的数据。因此在一个压缩的stream里定位，就需要先定位其所在chunk的header，再定位其在解压后的chunk里的位置。这样我们就能定位到前面说的一个Run的header的位置。

总结一下，在一个带压缩的stream里定位需要提供3个位置信息，先定位Run的header，需要提供chunk header在stream中的位置和对应解压后的chunk里的位置，然后定位在Run里的位置，再需要一个offset。不带压缩的stream比较简单，直接就能定位Run的header，因此能少用一个位置信息。

最后回到一个列对应的RowGroupIndex，里面的positions就是各个stream里的positions拼接起来的。

更细节的内容可以看原版spec: https://orc.apache.org/specification/ORCv1/