Back
+20 XP
Concept

Columnar Compression: Run-Length Encoding (RLE)

Sorted columnar data produces long streaks of duplicate values. Run-Length Encoding (RLE) collapses consecutive identical elements into `(count, value)` pairs, shrinking millions of repeated records into a few bytes with instantaneous sequential traversal 📦📉.

python
def rle_encode(column_data):
    if not column_data:
        return []
    runs = []
    current_val = column_data[0]
    run_length = 1

    for val in column_data[1:]:
        if val == current_val:
            run_length += 1
        else:
            runs.append((run_length, current_val))
            current_val = val
            run_length = 1
    runs.append((run_length, current_val))
    return runs

# 1,000 status codes compressed:
status_column = ["200"] * 800 + ["404"] * 150 + ["500"] * 50
compressed = rle_encode(status_column)
print(f"Compressed runs: {compressed} 🚀")

# 49. Columnar Compression: Run-Length Encoding (RLE) In analytics, tables often contain sorted columns like `country`, `order_date`, or `status`. Storing `"COMPLETED"` 10,000,000 times as raw strings wastes hundreds of megabytes of RAM and disk bandwidth 🛑. ```python # Raw Storage: # ["COMPLETED", "COMPLETED", ... (10M times)] -> ~100 MB # RLE Storage: # (10000000, "COMPLETED") -> 16 bytes! ``` ### RLE Mechanics in Parquet & DuckDB 1. **Contiguous Runs**: RLE requires identical items to be adjacent. This is why analytical tables are sorted on low-cardinality columns before writing to disk. 2. **Direct Predicate Pushdown**: An analytical engine doesn't need to decompress the run to evaluate queries. If the query asks for `status == "FAILED"` and the run is `(1000, "COMPLETED")`, the engine skips all 1,000 rows in a single CPU instruction ⚡. 3. **Hybrid RLE / Bit-Packed**: Modern file formats dynamically toggle between RLE (for repetitive runs) and bit-packing (for volatile sequences) 📉. --- ### Interactive Pop-Quiz 🧠 #### Under what specific data pattern does Run-Length Encoding (RLE) achieve maximum compression ratio? - [ ] When identical values appear consecutively in long, contiguous runs 📦 - [ ] When all values in the column are strictly unique and randomly ordered - [ ] When floating point numbers contain irrational square roots - [ ] When data is encrypted with AES-256 before compression --- ### Practical Challenge 🎯 Implement `rle_compress(data)` that turns a list of items into consecutive `(count, item)` tuples. Compress `['A', 'A', 'A', 'B', 'B', 'C', 'A']`. Verify the output matches `[(3, 'A'), (2, 'B'), (1, 'C'), (1, 'A')]`, and print the result. <details> <summary>Solution</summary> ```python def rle_compress(data): if not data: return [] runs = [] cur = data[0] cnt = 1 for x in data[1:]: if x == cur: cnt += 1 else: runs.append((cnt, cur)) cur = x cnt = 1 runs.append((cnt, cur)) return runs res = rle_compress(['A', 'A', 'A', 'B', 'B', 'C', 'A']) assert res == [(3, 'A'), (2, 'B'), (1, 'C'), (1, 'A')] print(res) ``` </details>

Checkpoint

Under what specific data pattern does Run-Length Encoding (RLE) achieve maximum compression ratio? 🧠

Practice

Implement `rle_compress(data)` that turns a list of items into consecutive `(count, item)` tuples. Compress `['A', 'A', 'A', 'B', 'B', 'C', 'A']`. Verify the output matches `[(3, 'A'), (2, 'B'), (1, 'C'), (1, 'A')]`, and print the result. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks