Doris Storage File Format Optimization

    1. doris segment

    Documents include:

    • The file starts with an 8-byte magic code to identify the file format and version
    • Data Region: Used to store data information for each column, where the data is loaded on demand by pages.
    • Index Region: Doris stores the index data of each column in Index Region, where the data is loaded according to column granularity, so the data information of the following column is stored separately.
    • Footer信息
      • FileFooterPB: Metadata Information for Definition Files
      • Chesum of 4 bytes of footer Pb content
      • The 8 byte MAGIC CODE is stored in the last bit to facilitate the identification of file types in different scenarios.

    The data in the file is organized in the form of page, which is the basic unit of coding and compression. Current page types include the following:

    Data Page is divided into two types: nullable and non-nullable data pages.

    Nullable’s data page includes:

    non -zero data page32467;- 26500;- 229140;-

    • value count
      • Represents the number of rows in a page
    • First row id
      • Line number of the first line in page
    • bitmap length
      • Represents the number of bytes in the next bitmap
    • null bitmap
      • bitmap representing null information
    • Data
      • Store data after encoding and compress
      • You need to write in the header information of the data: is_compressed
      • Various kinds of data encoded by different codes need to write some field information in the header information in order to achieve data parsing.
      • TODO: Add header information for various encodings
    • Checksum
      • Store page granularity checksum, including page header and subsequent actual data

    Bloom Filter Pages

    For each bloom filter column, a page of the bloom filter is generated corresponding to the granularity of the page and saved in the bloom filter pages area.

    For each column, a sparse index of row numbers is established according to page granularity. The content is a pointer to the block (including offset and length) for the line number of the start line of the page

    Short Key Index page

    We generate a sparse index of short key every N rows (configurable) with the contents of short key - > line number (ordinal)

    The format design supports the subsequent expansion of other index information, such as bitmap index, spatial index, etc. It only needs to write the required data to the existing column data, and add the corresponding metadata fields to FileFooterPB.

    Metadata Definition

    FileFooterPB is defined as:

    The general writing process is as follows:

    1. Write magic
    2. Generate corresponding Column Writer according to schema information. Each Column Writer obtains corresponding encoding information (configurable) according to different types, and generates corresponding encoder according to encoding.
    3. Call encoder - > add (value) for data writing. Each K line generates a short key index entry, and if the current page satisfies certain conditions (the size exceeds 1M or the number of rows is K), a new page is generated and cached in memory.
    4. Generate FileFooterPB information and write it to the file.

    • How does the index of short key be generated?

      • Now we still generate a short key sparse index according to how many rows are sparse, and keep a short sparse index generated every 1024 rows. The specific content is: short key - > ordinal

    • What should be stored in the ordinal index?

      • Store the first ordinal to page pointer mapping information for pages

    • What are stored in pages of different encoding types?

      • Dictionary Compression
      • plain
      • rle
      • bshuf

    Read

    1. Read the magic of the file and judge the type and version of the file.
    2. Read FileFooterPB and check sum
    3. Read short key index and data ordinal index information of corresponding columns according to required columns
    4. Use start key and end key, locate the row number to be read through short key index, then determine the row ranges to be read through ordinal index, and filter the row ranges to be read through statistics, bitmap index and so on.
    5. Then read row data through ordinal index according to row ranges

    Relevant issues:

    1. How to quickly locate a row within the page?

      The data inside the page is encoding, so it can not locate the row-level data quickly. Different encoding methods have different schemes for fast line number positioning in-house, which need to be analyzed concretely:

      • If it is rle-coded, skip is performed by resolving the head of RLE until the RLE block containing the row is reached, and then the reverse solution is performed.
      • binary plain encoding: offset information will be stored in the page, and offset information will be specified in the page header. When reading, offset information will be parsed into the array first, so that you can quickly locate the data of a row of block through offset data information of each row.
    2. How to achieve efficient block reading? Consider merging adjacent blocks while they are being read, one-time reading? This requires judging whether the block is continuous at the time of reading, and if it is continuous, reading it once.

    It implements a scalable compression framework, supports a variety of compression algorithms, facilitates the subsequent addition of new compression algorithms, and plans to introduce zstd compression.

    1. How to optimize the downstream bitmap and column statistics statistics caused by ScanRange splitting?