Querying RLE Columns with Predicates

1. The Core Idea: Bypassing Decompression

Imagine a billion-row table where a country column is RLE-compressed. If we want to run a query like SELECT ... WHERE country = 'Canada', the naive approach would be to decompress the entire billion-value column into memory and then scan it. This would be incredibly slow and memory-intensive.

The key insight of "operating on compressed data" is that we can satisfy this query by scanning the much smaller RLE structure itself. Instead of checking a billion values, we might only need to check a few hundred RLE triplets.

Let's see how this works.

2. The Algorithm for Executing a Selection

To execute a selection query, we iterate through our RLE triplets and check the value of each run against the predicate.

Let's assume we have a status column with the following values:
['A', 'A', 'A', 'B', 'B', 'A', 'C', 'C', 'C', 'C']

In the last lesson, you learned how to compress this into a structure of (value, start_pos, run_length) triplets. This would yield:
[ ('A', 0, 3), ('B', 3, 2), ('A', 5, 1), ('C', 6, 4) ]

Now, let's execute the query WHERE status = 'A'.

The algorithm is as follows:

1. Initialize an empty list of matching row positions.
2. Iterate through each RLE triplet (v, pos, len):
   • Compare v with the predicate value ('A').
   • If v matches: We've found a run of len matching rows starting at logical position pos. We don't need to generate these rows; we just record the range of matching offsets. In this case, we'd record the range [pos, pos + len - 1].
   • If v does not match: We simply skip this entire run and move to the next triplet.
3. The result is a list of logical row offsets or ranges that can be passed to the next operator in the query plan.

**Applying this to our example for WHERE status = 'A': **

• Triplet 1: ('A', 0, 3). The value 'A' matches. We've found 3 matches at logical positions 0, 1, and 2.
• Triplet 2: ('B', 3, 2). The value 'B' does not match. We skip 2 rows instantly.
• Triplet 3: ('A', 5, 1). The value 'A' matches. We've found 1 match at logical position 5.
• Triplet 4: ('C', 6, 4). The value 'C' does not match. We skip 4 rows instantly.

The final result of this selection operator is the set of matching logical positions: {0, 1, 2, 5}. The database can now use these positions to fetch data from other columns (e.g., price, timestamp) only for the rows that matter.

The following presentation slide beautifully illustrates this exact process.

The slide shows that by using the RLE metadata, the system can jump directly to the relevant data blocks, completely avoiding reads for Q1, Q3, and Q4. This is the source of the massive performance gain.

3. A Practical Implementation View

Since you have a strong background in C++, let's look at how this logic translates into code. The following research paper provides pseudocode for a search function that operates on RLE data.

The pseudocode in the paper captures the essential logic. Here is a slightly cleaner, more abstract version of that search algorithm that returns the positions of all matching runs:

// A struct to represent one run in our RLE-compressed column
struct RLE_Triplet {
    ValueType value;
    uint32_t start_pos;
    uint32_t run_length;
};

// A struct to represent a matching run
struct Match {
    uint32_t start_pos;
    uint32_t run_length;
};

// Function to find all runs that match a predicate value
std::vector<Match> find_matches(const std::vector<RLE_Triplet>& rle_column, const ValueType& predicate_value) {
    std::vector<Match> results;

    for (const auto& triplet : rle_column) {
        if (triplet.value == predicate_value) {
            // Found a matching run. Add its position and length to the results.
            results.push_back({triplet.start_pos, triplet.run_length});
        }
    }

    return results;
}

This function directly implements the logic we discussed: it iterates through the compressed triplets and collects the position and length of every run whose value matches the predicate. This is significantly faster than decompressing and then scanning.

4. A System-Level Abstraction: The Block API

In a real database system, the query execution engine shouldn't have to contain if/else logic for every possible compression scheme (if RLE do X, if Dictionary do Y...). A cleaner, more extensible design uses an abstraction, much like an interface or virtual class in C++.

This is often called a Block API. The query engine's Scan operator interacts with a generic DataBlock interface. Each type of compressed block (RLE, Dictionary, etc.) provides its own implementation of that interface.

The LINK slide deck hints at this on slide 60, showing a "Block API" with methods like:

• getValueAtPosition(pos): Gets the value at a specific logical position. An RLE block would find the right run and return its value.
• find_matches(predicate): A high-performance method like the one we wrote above.
• decompressIntoArray(): A fallback for when an operator absolutely needs the raw data.

This design is powerful because it separates the query logic from the compression details. The Scan operator can be written once, and you can add new compression schemes just by providing a new DataBlock implementation.

Conclusion

You've now seen how to complete the lifecycle of RLE compression: from encoding the data to efficiently executing queries on it. This principle of operating directly on compressed data is fundamental to the performance of modern analytical databases.

Key Takeaways:

• Selection queries can be performed on RLE data by scanning the small list of RLE triplets instead of the massive raw data column.
• The algorithm involves checking the value of each run and, upon a match, using the start_pos and run_length to identify all matching rows at once.
• This process avoids the massive I/O and CPU cost of full decompression, dramatically speeding up queries.
• A Block API provides an elegant abstraction that allows the query engine to work with different compression schemes without being coupled to their specific implementations.

Preview of the Next Lesson

RLE is fantastic for data with long, identical runs. But what about a column of small integer values that don't repeat consecutively, like an age column? In our next lesson, we will explore another technique perfect for this scenario: Bit-Packed Encoding. You will learn how to implement bit-packed encoding for compressing columns with small integer values, a technique that stores numbers using just enough bits to represent them, further shrinking the data footprint.