Run-Length Encoding for Data Compression

1. The Core Idea of Run-Length Encoding

Run-Length Encoding is a straightforward and intuitive lossless compression technique. The main idea is to replace consecutive sequences (or "runs") of identical values with a single pair representing the value and the length of the run.

For example, a sequence of characters like: WWWWAAXXXXX

Can be compressed into a shorter representation like: (W, 4), (A, 2), (X, 5)

This simple transformation can lead to significant space savings when long runs are present.

Now, let's watch a short video that explains this concept within the context of columnar databases and highlights a crucial prerequisite for RLE to be effective.

As the video clearly demonstrated, RLE's performance is highly dependent on the data's layout.

• For unsorted data with alternating values (e.g., M, F, M, F, M, F...), RLE can actually increase the data size because each "run" has a length of one.
• For sorted data (e.g., F, F, ..., M, M, ...), RLE achieves a massive compression ratio by collapsing all identical values into a small number of run-length pairs.

This is why RLE is a perfect fit for columns that are either explicitly sorted (like a primary key or a sort key in a data warehouse) or have very low cardinality (e.g., a "status" column with values like 'PENDING', 'COMPLETE', 'FAILED'), as even unsorted low-cardinality data tends to have natural runs.

2. Implementing the RLE Algorithm

Now that you understand the "what" and "why," let's focus on the "how." Given your proficiency in C++, we can look at a direct, practical implementation.

The core logic of an RLE encoder involves iterating through the input data, keeping track of the current value and a counter. When the value changes (or the data ends), the encoder writes the previous value and its count to the output and resets the counter for the new value.

The following resource provides a simple C-style pseudocode for an RLE_Encode function that compresses a character string.

Let's break down the logic from the paper's pseudocode. It's a bit condensed, so let's analyze a cleaner version of the same algorithm:

void RLE_Encode(char* input_str, char* output_str) {
    int input_idx = 0;
    int output_idx = 0;

    while (input_str[input_idx] != '\0') {
        char current_value = input_str[input_idx];
        int run_length = 1;

        // Inner loop: count the length of the run
        while (input_str[input_idx + 1] == current_value) {
            run_length++;
            input_idx++;
        }

        // Write the value and its count to the output
        output_str[output_idx++] = current_value;
        // This converts the integer count to a character, e.g., 3 -> '3'
        output_str[output_idx++] = (char)(((int)'0') + run_length);

        // Move to the next character in the input
        input_idx++;
    }
    output_str[output_idx] = '\0'; // Terminate the output string
}

This implementation encodes a string like "AAABBC" into "A3B2C1". The outer loop picks a character, and the inner loop consumes all subsequent identical characters while incrementing a counter.

3. Data Structures for RLE Output

The simple string format ("A3B2C1") is just one way to store the RLE output. In real database systems, a more structured approach is common, especially when dealing with data types other than single characters.

A prevalent design is to store the output in two separate arrays:

1. A values array containing the sequence of unique values that start each run.
2. A run_lengths array containing the corresponding length of each run.

For an input column [5.5, 5.5, 5.5, 9.0, 9.0, 5.5], this would produce:

• values: [5.5, 9.0, 5.5] (array of doubles)
• run_lengths: [3, 2, 1] (array of integers)

This approach has several advantages in a systems context:

• Type Safety: The values array can be strongly typed (e.g., int32_t, double, string_view), which is cleaner than mixing data and counts in a byte stream.
• Further Compression: The values and run_lengths arrays can themselves be compressed! For example, if the run_lengths array contains many identical values (e.g., [2, 2, 2, 2, 2]), it could also be run-length encoded. This concept is called cascading compression.
• Efficient Decompression: As we will see, vectorized hardware instructions (SIMD) can be used to rapidly decompress these two arrays back into the original data.

The following paper describes a system that uses this two-array approach and even discusses vectorized decompression.

This look into a real system shows that RLE is not just a textbook algorithm but a practical tool with sophisticated implementations designed for modern hardware.

Conclusion

Today you've explored Run-Length Encoding, a simple yet powerful compression technique that is highly effective in columnar databases. You've gone from the high-level concept to a concrete implementation and seen how it's used in real-world systems.

Key Takeaways:

• Run-Length Encoding (RLE) compresses data by replacing consecutive runs of identical values with a (value, count) pair.
• RLE's effectiveness is maximized on sorted data or columns with low cardinality, as these conditions create the long runs that RLE can exploit.
• The core implementation involves a simple loop that iterates through the data, counts consecutive values, and writes the resulting pairs.
• While a simple string can represent the output, a more robust system design uses two separate arrays for values and run_lengths, enabling type safety and further optimizations.

Preview of the Next Lesson

Having an RLE-compressed column is the first step. The next is to use it. In our next lesson, we will address the learning outcome: Execute a selection query with a predicate on a run-length encoded (RLE) column. You will learn how to find all rows matching a predicate like WHERE status = 'COMPLETE' without having to decompress the entire column first, further building on the theme of "late materialization".