Columnar Compression: Bit-Packing & Dictionary Encoding
Repeating identical strings wastes memory. Dictionary encoding maps distinct values to small integer IDs ($0, 1, \dots, K-1$). Bit-packing squeezes those IDs into the exact theoretical minimum bit width $\lceil \log_2 K \rceil$, slashing storage by over 80% 🗜️⚡.
import math
def dict_encode(column):
dictionary = []
lookup = {}
ids = []
for val in column:
if val not in lookup:
lookup[val] = len(dictionary)
dictionary.append(val)
ids.append(lookup[val])
# Required bit-width per integer:
bits = math.ceil(math.log2(len(dictionary))) if len(dictionary) > 1 else 1
return ids, bits, dictionary
os_col = ["Linux", "Darwin", "Linux", "Windows", "Linux"]
ids, bits, dictionary = dict_encode(os_col)
print(f"Packed {len(dictionary)} unique values into {bits} bits per row 🚀")
# 50. Columnar Compression: Bit-Packing & Dictionary Encoding If your users table has 50,000,000 rows with a `subscription_tier` column containing only `"FREE"`, `"PRO"`, and `"ENTERPRISE"`, storing them as UTF-8 strings consumes roughly 500 megabytes of disk space and CPU cache 🛑. ```python # Uncompressed: # 50,000,000 strings * ~10 bytes = ~500 MB # Dictionary Encoded + Bit-Packed: # 3 unique strings -> requires only 2 bits per row! # 50,000,000 * 2 bits = 12.5 MB (97.5% memory reduction!) ``` ### The Compression Pipeline 1. **Dictionary Construction**: Scan the block, identify unique values, and build an ordered dictionary lookup table: `[0: "FREE", 1: "PRO", 2: "ENTERPRISE"]`. 2. **Integer Substitution**: Replace string instances with their respective dictionary index. 3. **Bit-Packing**: Standard integers take 32 or 64 bits. Bit-packing masks and shifts bits to store four 2-bit values inside a single 8-bit byte (`0b00_01_10_00`), maximizing cache density and vectorized instruction throughput 🗜️⚡. --- ### Interactive Pop-Quiz 🧠 #### If a database column contains exactly 4 distinct categorical values, how many bits per row are required when bit-packed? - [ ] 2 bits per row (since $2^2 = 4$) 🗜️ - [ ] 4 bytes per row - [ ] 16 bits per row - [ ] 64 bits per row --- ### Practical Challenge 🎯 Implement `dict_encode(values)` that maps distinct elements to zero-indexed IDs and returns `(encoded_ids, dictionary)`. Encode `['GOLD', 'SILVER', 'BRONZE', 'GOLD', 'PLATINUM']`. Verify that `'GOLD'` maps to ID 0 in both occurrences and that the dictionary has 4 unique entries. Print `len(dictionary)`. <details> <summary>Solution</summary> ```python def dict_encode(values): dict_table = [] lookup = {} ids = [] for v in values: if v not in lookup: lookup[v] = len(dict_table) dict_table.append(v) ids.append(lookup[v]) return ids, dict_table raw = ['GOLD', 'SILVER', 'BRONZE', 'GOLD', 'PLATINUM'] ids, d = dict_encode(raw) assert ids[0] == 0 and ids[3] == 0 assert len(d) == 4 print(len(d)) ``` </details>