Metainfo of the inverted index may overflow, causing the index to become unavailable

[zhongzc]

What type of bug is this?

Unexpected error

What subsystems are affected?

Storage Engine

Problem Report

Below is the definition of InvertedIndexMeta: https://github.com/GreptimeTeam/greptime-proto/blob/a11db14b8502f55ca5348917fd18e6fcf140f55e/proto/greptime/v1/index/inverted_index.proto#L41-L68

As can be seen, both relative_fst_offset and fst_size are defined as uint32.

    // The byte offset of the Finite State Transducer (FST) data relative to the `base_offset`.
    uint32 relative_fst_offset = 4;

    // The size in bytes of the FST data.
    uint32 fst_size = 5;

According to the layout of the inverted index:

null_bitmap bitmap₀ bitmap₁ bitmap₂ ... bitmapₙ fst

This implies that if the total size of the bitmaps exceeds 4.3GB, the relative_fst_offset will overflow, causing the FST to be located at an incorrect position when read.

Let's examine the possibility that the total bitmap size exceeds 4.3GB:

1. Suppose there are 100k distinct values in the column, each occupying an average of 43KB of bitmap size.
2. Since the bitmap is implemented with the simplest bitvec, 43KB actually represents a maximum of 344k segments, which is 352 million rows.

This is achievable, so this issue urgently needs to be addressed.

Some possible solutions are:

1. Optimize bitmap implementation, compress the bitmap, or adopt a roaring bitmap.
2. Introduce additional levels of indexing, SST -> Row Group -> Segment, to control the number of indexing targets.

Note: Simply adjusting relative_fst_offset to uint64 is insufficient because the Value that the FST maps to represents the position and size of the bitmap, which also uses u32. Therefore, the positioning of the bitmap will also be affected by the total size of the bitmap.