Back
+20 XP
Concept

Vectorized Filtering & Bitmask Selection

Row-by-row filtering causes catastrophic CPU branch mispredictions. Vectorized execution engines (ClickHouse, DuckDB) process arrays in contiguous chunks, producing compact selection bitmasks to filter data at native CPU register speed without branching 🏎️⚡.

python
def build_filter_bitmask(chunk, threshold):
    # Bit i is 1 if chunk[i] satisfies predicate:
    mask = 0
    for i, val in enumerate(chunk):
        if val > threshold:
            mask |= (1 << i)
    return mask

def filter_chunk(chunk, mask):
    return [val for i, val in enumerate(chunk) if (mask & (1 << i))]

prices = [10, 55, 20, 95, 12, 80]
mask = build_filter_bitmask(prices, 50)
print(f"Selection Mask: {bin(mask)}, Matches: {filter_chunk(prices, mask)} 🚀")

# 51. Vectorized Filtering & Bitmask Selection When iterating over 100,000,000 rows with a simple Python `if row['status'] == 'FAILED':`, your CPU spends massive amounts of time stalling on branch mispredictions whenever the condition flips between True and False 🛑. ```python # Scalar Volcano evaluation (Slow!): # for row in dataset: # if evaluate_predicate(row): # CPU branch predictor suffers! # yield row ``` ### The Vectorized Batch Invariant 1. **Chunks over Rows**: Instead of feeding 1 row at a time through an evaluation function, vectorized engines feed vectors of 1024 values at a time. 2. **Selection Bitmasks**: Evaluating `column > 50` on 1024 rows outputs an array of 16 unsigned 64-bit integers (1024 bits total), where each bit represents a True/False outcome ⚡. 3. **Hardware SIMD Alignment**: Bitwise operations (`AND`, `OR`, `NOT`) on bitmasks map directly onto single-cycle CPU SIMD instructions (AVX-512, NEON), evaluating hundreds of records per nanosecond 🏎️. --- ### Interactive Pop-Quiz 🧠 #### How does generating selection bitmasks improve query performance compared to branchy row-by-row if-conditions? - [ ] It eliminates CPU branch mispredictions and enables vectorized hardware SIMD bitwise parallel operations 🏎️ - [ ] It forces the query to compile to WebGL shaders on the GPU - [ ] It converts all column integers into ASCII floating point numbers - [ ] It prevents memory access violations by disabling kernel page tables --- ### Practical Challenge 🎯 Implement `create_selection_mask(arr, min_val, max_val)` that sets bit $i$ if `min_val <= arr[i] <= max_val`. Then implement `apply_mask(arr, mask)` to return the filtered items. Test with `arr = [5, 15, 25, 35, 45]`, range `[10, 40]`. Assert the filtered list is `[15, 25, 35]`, and print the filtered elements. <details> <summary>Solution</summary> ```python def create_selection_mask(arr, min_val, max_val): mask = 0 for i, v in enumerate(arr): if min_val <= v <= max_val: mask |= (1 << i) return mask def apply_mask(arr, mask): return [v for i, v in enumerate(arr) if (mask & (1 << i))] arr = [5, 15, 25, 35, 45] mask = create_selection_mask(arr, 10, 40) res = apply_mask(arr, mask) assert res == [15, 25, 35] print(res) ``` </details>

Checkpoint

How does generating selection bitmasks improve query performance compared to branchy row-by-row if-conditions? 🧠

Practice

Implement `create_selection_mask(arr, min_val, max_val)` that sets bit $i$ if `min_val <= arr[i] <= max_val`. Then implement `apply_mask(arr, mask)` to return the filtered items. Test with `arr = [5, 15, 25, 35, 45]`, range `[10, 40]`. Assert the filtered list is `[15, 25, 35]`, and print the filtered elements. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks