字典编码简介

字典编码是指将某一列数据的值替换成一些编码后的值，在进行存储和处理时转而使用这些编码值，同时额外维护一个从编码值到原始值的映射。理想情况下，字典编码应该能够进行快速编解码，并且能够提升数据处理的速度。

在实现字典编码时，有几个值得考虑的问题：

• 编码值的长度：
  • 固定长度
  • 根据要编码值的值域大小动态变化
• 字典的构建时机：
  • 一次性构建：对于一批数据，对其构建字典后该字典不再改变，后续的新数据必须构建新的字典
  • 增量构建：将新的数据合并到原始字典中
• 字典的粒度：
  • 块级：对一个表的一部分维持字典
  • 表级：对一张表维持字典
  • 多表级：对多张表或整个库维持字典
• 偏序关系：码字的偏序关系是否需要和原始值的偏序关系一致
• 编码和解码的时机：在数据从导入到内存到进行处理的流程当中的什么时候进行编码/解码操作

Apache Doris中字典编码的相关存储结构

在存储文件中的位置

我们首先来看字典编码相关数据结构在存储文件中的位置。目前doris使用segment_v2结构存储数据，一个Segment主要包括数据区，索引区和Footer三部分，其中Footer部分负责存储该segment的一些元数据，其结构由SegmentFooterPB.proto所描述。在SegmentFooterPB中有一个类型为ColumnMetaPB的Columns字段用于存储table schema。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

message ColumnMetaPB {
    // column id in table schema
    optional uint32 column_id = 1;
    // unique column id
    optional uint32 unique_id = 2;
    // this field is FieldType's value
    optional int32 type = 3;
    // var length for string type
    optional int32 length = 4;
    optional EncodingTypePB encoding = 5;
    // compress type for column
    optional CompressionTypePB compression = 6;
    // if this column can be nullable
    optional bool is_nullable = 7;
    // metadata about all the column indexes
    repeated ColumnIndexMetaPB indexes = 8;
    // pointer to dictionary page when using DICT_ENCODING
    optional PagePointerPB dict_page = 9;
    repeated ColumnMetaPB children_columns = 10;
    // required by array/struct/map reader to create child reader.
    optional uint64 num_rows = 11;
    repeated string children_column_names = 12;
}

可以看到ColumnMetaPB中有一个类型为EncodingTypePB的字段encoding，有一个类型为PagePointerPB的字段dict_page存储字典页的指针。encoding用于存储当前segment的编码类型，继续看EncodingTypePB的定义我们可以看到目前doris支持的编码种类，和字典编码相关的有DICT_ENCODING和PLAIN_ENCODING。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

enum EncodingTypePB {
    UNKNOWN_ENCODING = 0;
    DEFAULT_ENCODING = 1;
    PLAIN_ENCODING = 2;
    PREFIX_ENCODING = 3;
    RLE = 4;
    DICT_ENCODING = 5;
    BIT_SHUFFLE = 6;
    FOR_ENCODING = 7; // Frame-Of-Reference
}

字典编码存储结构

在Apache Doris中，使用字典编码的数据页的存储会用到两种模式

• PLAIN_ENCODING模式：页面布局为header+embedded BinaryPlainPage，即将数据项在页头依次顺序排放，各个数据的offsets从页末尾开始依次逆序排放。
• DICT_ENCODING模式：布局为header+embedded codeword page，即数据页中存放(压缩后的)码字。此时编码信息存放在dict_page中，目前dict_page只支持按BinaryPlainPage格式存放。

这里字典编码的编码信息最多只会存放在一个页中，当编码信息页的大小超过一个阈值后，之后添加的数据页会自动从DICT_ENCODING模式fall back到PLAIN_ENCODING模式，且之前已经编码过的数据页不受影响。这个字典信息页大小的阈值由PageBuilderOptions中的dict_page_size字段所决定，目前其值为固定的大小1024 * 1024即1M。

Doris所有类型支持的编码方式在EncodingInfoResolver进行了注册，我可以看到其中可以使用字典编码的类型有OLAP_FIELD_TYPE_CHAR, OLAP_FIELD_TYPE_VARCHAR, OLAP_FIELD_TYPE_STRING, OLAP_FIELD_TYPE_JSONB。并且在不开启optimize_value_seek选项的情况下，这些类型的字段默认使用字典编码进行存储。

编码流程

写路径

我们从DeltaWriter开始，通过考察一个WriteRequest的写路径来看在什么地方会应用字典编码的编码过程。

• 对每个WriteRequest(一个WriteRequest会写入到一个Tablet，一个Tablet就是一个表的物理储存结构)会创建一个对应的DeltaWriter完成写入
• 通过调用DeltaWriter的append()/write()方法不断写入增量数据，完成一个Tablet的写入。
• DeltaWriter首先先写入到内存中的MemTable(使用SkipList存储数据)中，写满后，则提交一个MemtableFlushTask异步任务到线程池，这个异步任务负责将Memtable写入成为磁盘上的当前数据变更对应的Rowset中的一个Segment，然后重置当前的MemTable处理后续的写入。

其中MemtableFlushTask异步任务的调用链如下：

• MemtableFlushTask::run()->FlushToken::_flush_memtable()->Memtable::flush()->MemTable::_do_flush()：通过MemTable::_collect_vskiplist_results()将跳表中的数据收集到_output_mutable_block中再转为Block(包含了一次磁盘写入的数据和元数据)以供后续写入
• ->BetaRowsetWriter::flush_single_memtable()：创建SegmentWriter，并添加刚刚构造的Block。SegmentWriter继续分别通过ShortKeyIndexBuilder, PrimaryKeyIndexBuilder构造并写入对应的索引数据, 通过ColumnWriter写入列数据
• 不同类型的ColumnWriter(ScalarColumnWriter/StructColumnWriter/ArrayColumnWriter/MapColumnWriter)通过各种Builder生成并写入列数据和对应的各类索引数据(BloomFilterIndex/BitMapIndex/ZoneMapIndex/InvertedIndex/OrdinalIndex)
• 上述各类xxxBuilder最终通过PageIO::write_page()/compress_and_write_page()->FileWriter::appendv()将数据写入到不同类型的存储介质(local file/s3/hdfs等)上

我们所关心的字典编码会在ScalarColumnWriter下的BinaryDictPageBuilder进行处理。

ScalarColumnWriter

在ScalarColumnWriter::init()函数中会获取使用的压缩算法和使用的编码类型，并通过编码类型获取相应的xxxPageBuilder进行数据页的构建。当使用DICT_ENCODING编码类型时，这会获取到BinaryDictPageBuilder。

由于各种索引(BloomFilterIndex/BitMapIndex/ZoneMapIndex/InvertedIndex/OrdinalIndex)的目的是根据查询来缩小最终进行scan的范围，所以这些索引当中依然存储的是关于原始值的相关信息。

上游通过ScalarColumnWriter::append_data()向ScalarColumnWriter输入数据，ScalarColumnWriter会将上游输入的数据组织成ScalarColumnWriter::Page构成的链表最后再一次性地写入。其中，一个Page包括数据部分和footer部分。其中数据可能部分有以下三种情况：

• 包含一个OwnedSlice且数据页已压缩
• 包含一个OwnedSlice，数据页未压缩且没有nullmap
• 包含一个OwnedSlice，数据页未压缩且包含一个nullmap页

在ScalarColumnWriter::append_data()->ScalarColumnWriter::append_data_in_current_page()中会将写入继续下发到下游的xxxPageBuilder中，这其中就包括BinaryDictPageBuilder。而当某个数据页写满后(_page_builder->is_page_full())，会取出对应的数据页更新ZoneMap和BloomFilter的信息，并构造相应的nullmap页(如果该列nullable)，然后构造一个新的Page同时设置其footer部分，然后尝试对其进行压缩，最终将该Page加入到链表中。

上游最终通过调用ScalarColumnWriter::write_data()中将上述Page链表中的数据全部写入到存储介质。对于需要字典编码的，会通过_page_builder->get_dictionary_page()获取到字典编码信息页，设置其footer部分后压缩并写入到存储介质，最后更新其ColomnMetaPB的dict_page字段。

BinaryDictPageBuilder

BinaryDictPageBuilder通过内存中的phmap::flat_hash_map来维持字典值到字典id的映射，并通过下游的_data_page_builder和_dict_builder来构建和输出数据页和字典编码信息页。

• _data_page_builder: 类型为BitshufflePageBuilder，负责构建和输出由数据编码后的编码值组成的页，其会对存储的编码值使用压缩算法进一步压缩。
• _dict_builder: 类型为BinaryPlainPageBuilder，负责构建和输出保存字典应映射信息的页，即ColumnMetaPB中dict_page字段所指向的页。

BinaryDictPageBuilder的编码方式为将任意长度的字节序列映射为一个uint32_t，编码值从0开始依次递增，0表示空串的编码，1是第一个有效编码值。

字典编码的实际编码过程发生在ScalarColumnWriter::append_data_in_current_page()->BinaryDictPageBuilder::add()中，对于每个输入的数据块，若为空，则返回_empty_code；否则如果该值存储在与哈希表中则直接返回相应的编码值；否则，将该值加入到哈希表中并赋予新的编码值，同时将该新的编码映射加入到_dict_builder中。最后通过_data_page_builder将编码值写入到数据页中。

解码流程

读初始化

• NewOlapScanner::init()->Tablet::capture_rs_readers()->BetaRowset::create_reader(): NewOlapScanner初始化Tablet对象，之后根据需要的版本信息找到对应的Rowset并创建RowsetReader，然后初始化TabletReader的读参数，包括查询条件，遍历范围等。
• NewOlapScanner::open()->BlockReader::init()/VerticalBlockReader::init():
  • 根据读参数初始化初始化查询条件，各种filters等
  • 初始化RowsetReader并添加到VCollectIterator中
  • 根据数据表数据模型的不同(Aggregate/Unique/Duplicate)设置数据读取函数(_direct_next_block/_unique_key_next_block/_agg_key_next_block)
• BetaRowsetReader::init():
  • ->BetaRowsetReader::get_segment_iterators():
    • 初始化key_ranges，delete_handler等
    • ->SegmentLoader::load_segment(): 将Rowset下的Segment导入到内存中并创建对应的迭代器SegmentIterator
  • 将多个SegmentIterator合并为一个new_merge_iterator/new_union_iterator并对其进行初始化

读路径

接下来我们来看和字典解码相关的读路径。

• BlockReader/next_block_with_aggregation::next_block_with_aggregation(): 调用实际注册的读取函数，都通过VCollectIterator::next()读一行数据，然后根据数据模型不同进行处理
• VCollectIterator::next(): 从其管理的RowsetIterator中读出一行
• BetaRowsetReader::next_block()->RowwiseIterator::next_batch()->SegmentIterator::next_batch()->SegmentIterator::_next_batch_internal():
  • ->SegmentIterator::_init(): 初始化BitmapIndexIterator/InvertedIndexIterator等
  • ->SegmentIterator::_read_columns_by_index():
    • 通过BitmapRangeIterator::next_range()得出当前读取的行号范围
    • 先读出有predict的列的上述范围的数据，然后再进行精确过滤。再读取无条件的列中的数据。
• 上述过程中SegmentIterator会通过SegmentIterator::_seek_columns()移动指针，通过SegmentIterator::next_batch()获取数据，而这些方法会调用对应类型ColumnIterator的_read_data_page()方法取读取页数据
• ColumnIterator::_read_data_page()->ColumnReader::read_page()->PageIO::read_and_decompress_page(): 最终完从存储介质上的读取并Parse出对应的页数据

FileColumnIterator

字典信息页的读取发生在FileColumnIterator::_read_data_page()中，为了优化内存使用，字典信息页会在第一次被使用时才被读取到内存中。

上层对FileColumnIterator的各种seek_xxx()/next_batch()/read()读调用都需要通过FileColumnIterator::_read_data_page()进行页的读取，它继而使用对应的ColumnReader读取页数据并Parse到内存中。对于字典编码的页面，如果此时字典信息页还没有读入到内存中，则会读取字典信息页然后使用BinaryPlainPageDecoder对其进行解码，并将字典的值存放到一个StringRef数组中用于后续解码，由于字典码值从0开始且依次递增，所以直接通过数组下标访问就可以得到码值对应的原始值。之后它通过BinaryDictPageDecoder::set_dict_decoder()将该数组传递到该页的BinaryDictPageDecoder中。

BinaryDictPageDecoder

BinaryDictPageDecoder负责对编码类型为DICT_ENCODING和PLAIN_ENCODING的数据页进行解码。

• 对于编码类型为DICT_ENCODING的数据页，使用BitShufflePageDecoder对页数据进行解压缩，通过BinaryPlainPageDecoder对字典信息页进行解码
• 对于编码类型为PLAIN_ENCODING的数据页，使用BinaryPlainPageDecoder根据页尾的offsets取出页中的数据。

上层读取数据时，BinaryDictPageDecoder通过_data_page_decoder从数据页中读取数据，并通过Column::insert_many_dict_data()将数据与字典dict提供给上层，不同的类型的Column再根据需要特化实际的处理过程。

查询执行过程中的处理

上面说到BinaryDictPageDecoder值负责提供码值和字典，上层会根据需要进行特化。例如对于ColumnString来说，其会在ColumnString::insert_many_dict_data()中完成解码的过程，即根据每个位置的码字拷贝出对应的字符串并修改offsets数组。显然，这种方式并充分发挥字典编码的优势，特别是对于string类型的列而言，其在一个查询中主要是作为聚合键的一部分，或者在条件中进行等值比较，在这种情况下，使用直接码值进行处理显然要比直接处理原值更高效。所以Doris针对低基数的string列使用了ColumnDictioinary来进行优化。它会在ColumnDictionary::insert_many_dict_data()中直接拷贝码值并保存字典。之后，对于等值比较，它将等值比较中的常量转化为字典中对应的码值。对于range类型的条件过滤，它会首先将字典的码值变换为可以反应原始值偏序关系的码值，然后在应用range predicate时就可以直接比较对应的码值。对于不完全使用字典编码的，即含有plain encoding编码类型的页的，ColumnDictionary会转化成PredicateColumn继续后续的处理。

参考资料

• Data Compression
• 【Doris】Doris存储层设计介绍1——存储结构设计解析
• 【Doris】存储层设计介绍2——写入流程、删除流程分析
• 【Doris】存储层设计介绍3——读取流程、Compaction流程分析
• Apache Doris 学习笔记: 字符串编码与解码
• [Segment V2] Support lazy materialization read
• [bugfix](low cardinality) cached code is wrong will result wrong query result when many null pages