PageStorage: compression of the fields offset in PageEntry

Enhancement

https://github.com/pingcap/tiflash/blob/2d578951911fc5fe720d28e1b768cd8ab982341d/dbms/src/Storages/Page/V3/WAL/serialize.cpp#L46-L52

PageStorage supports setting fields on Page, which correspond to different columns inside a row group. And we store the beginning offset of each field in PageEntry. Now we store the field offset and checksum as size_t(8 bytes). When storing page for wide tables that contains over 100 columns, the serialized size of all fields offset is relatively big.

Assume we have a table with 1024 columns, and there are 100,000 pages stored in PageStorage. Then the WAL files is about 787 MB. More than 99% of data (781 MB) is to store the offsets. Using compression on offset usually can reach a compression ratio around 6, meaning that we can compress it to be about 136 MB.

As the fields offset must be 0 or positive numbers sorted by increasing, we can find a suitable compression algorithm to get optimized compressed data.

First, we can calculate the difference between two adjacent integers, this can make the number to be smaller and have more prefix-zero in the binary representation. For example, offset [0, 1024, 9182, 19000, 22000, 23022] => [0, 1024, 8158, 9818, 3000, 1022].

After that, one simple way is that we can use "VarInt" (https://en.wikipedia.org/wiki/Variable-length_quantity) to store each offset. https://github.com/pingcap/tiflash/blob/2d578951911fc5fe720d28e1b768cd8ab982341d/dbms/src/Storages/Transaction/DatumCodec.cpp#L449-L452
Another way is that we can use "Elias gamma coding" (https://en.wikipedia.org/wiki/Elias_gamma_coding) to get a more compacted result. "Elias gamma coding" is the most compacted representation for small integer AFAIK. But compared to "VarInt", the output of "Elias gamma coding" is not fixed size of bytes, which may bring some performance regression while encoding/decoding on integreters.

As the two encoding methods are not complex, we can implement both "VarInt" and "Elias gamma coding", and get a performance benchmark result of both.

And there maybe more suitable compression algorithm for "positive increasing integers", we can do some investigation for that.

Start by inspecting the field-offset serialization in dbms/src/Storages/Page/V3/WAL/serialize.cpp and the VarInt implementation referenced in dbms/src/Storages/Transaction/DatumCodec.cpp. Compare VarInt and Elias gamma coding, investigate alternatives for positive increasing integers, and benchmark the encoders and decoders; done means selecting and implementing a suitable compression approach with measured results.