Why min/max and dictionary filtering fail on high-cardinality unsorted columns, and how bloom filters help

Three data-skipping mechanisms and their limitations.

• Min/max statistics – Record the smallest and largest value per block. Effective only when data is sorted so ranges are tight. Useless on high-cardinality unsorted columns where every block spans the full domain.
• Dictionary filtering – Checks if the filter value exists in the block's dictionary. Fails when the dictionary grows too large or Parquet drops dictionary encoding.
• Bloom filters – A compact fixed-size bitset per block built by hashing each value. Testing gives 'definitely not present' (safe skip) or 'probably present' (must read). Works for billions of distinct unsorted values.

Bloom filters are the purpose-built solution for high-cardinality equality lookups on unsorted columns.

Why do min/max statistics fail on unsorted columns?

Min/max statistics record the smallest and largest value in each Parquet row group. Their power comes from tight, non-overlapping ranges, which you only get when data is sorted on that column. For a high-cardinality unsorted column, each block receives a random sample of the whole value space.

Sorted by account_id:
  Block 1: min=ACC-0001, max=ACC-1000  → tight range
  Block 2: min=ACC-1001, max=ACC-2000  → tight range
  Query: WHERE account_id = 'ACC-1500' → skip Block 1 ✓

Unsorted (random distribution):
  Block 1: min=ACC-0003, max=ACC-9997  → spans everything
  Block 2: min=ACC-0001, max=ACC-9999  → spans everything
  Query: WHERE account_id = 'ACC-1500' → cannot skip any block ✗

# Demonstrate: min/max skipping on sorted vs unsorted data
txns_sorted = spark.read.parquet("/data/bank/transactions_sorted_by_txn_id")
txns_unsorted = spark.read.parquet("/data/bank/transactions")

# Sorted: Spark reads 1 row group (min/max skipping works)
txns_sorted.filter("transaction_id = 'TXN-500000'").explain()

# Unsorted: Spark reads ALL row groups (min/max useless)
txns_unsorted.filter("transaction_id = 'TXN-500000'").explain()

Why does dictionary filtering fail on high cardinality?

Dictionary filtering checks whether the filter value exists in a block's dictionary of distinct values. For a high-cardinality column, two things go wrong.

Low cardinality (branch_code, 50 values):
  Dictionary per block: [MUMBAI-01, DELHI-02, ..., KOLKATA-50]
  Size: ~2 KB
  Membership check: fast and selective ✓

High cardinality (transaction_id, 10M values):
  Dictionary per block: [TXN-000001, TXN-000002, ..., TXN-100000]
  Size: ~5 MB per block → exceeds Parquet threshold
  Parquet drops dictionary encoding → falls back to plain encoding
  No dictionary to check → filtering impossible ✗

# Check Parquet encoding for a column
import pyarrow.parquet as pq

parquet_file = pq.ParquetFile("/data/bank/transactions/part-00000.parquet")
for rg in range(parquet_file.metadata.num_row_groups):
    col_meta = parquet_file.metadata.row_group(rg).column(0)  # transaction_id
    print(f"Row group {rg}: encoding={col_meta.encodings}")
    # High cardinality: shows PLAIN instead of PLAIN_DICTIONARY

How do bloom filters work?

A bloom filter is a fixed-size array of bits. When writing, each value is hashed by several hash functions, and the corresponding bits are set. When reading, you hash the lookup value and check those bits.

Bloom filter for Block 1 (simplified, 16 bits):

Write 'TXN-1001':  hash1=3, hash2=7, hash3=12  → set bits 3, 7, 12
Write 'TXN-2045':  hash1=1, hash2=7, hash3=15  → set bits 1, 7, 15

Bitset: [0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,1]
         0 1 2 3 4 5 6 7 8 9 ...   12    15

Lookup 'TXN-5000': hash1=3, hash2=9, hash3=12
  Bit 3=1 ✓  Bit 9=0 ✗  → DEFINITELY NOT PRESENT → skip block

Lookup 'TXN-1001': hash1=3, hash2=7, hash3=12
  Bit 3=1 ✓  Bit 7=1 ✓  Bit 12=1 ✓  → PROBABLY PRESENT → read block

How do you enable bloom filters in Parquet?

Bloom filters are not built by default. You enable them per column at write time.

# Enable bloom filter on transaction_id column
txns.write \
    .option("parquet.bloom.filter.enabled#transaction_id", "true") \
    .option("parquet.bloom.filter.expected.ndv#transaction_id", "10000000") \
    .parquet("/data/bank/transactions_with_bloom")

-- Delta Lake: enable bloom filter index
CREATE BLOOMFILTER INDEX ON TABLE banking_prod.transactions
FOR COLUMNS (transaction_id OPTIONS (fpp = 0.01, numItems = 10000000));

What are the trade-offs?

Bloom filters add bytes to the file and are only useful for equality and IN predicates.

Pros:
  - Compact: a few bits per value regardless of value size
  - No false negatives: safe to skip
  - Works on billions of distinct unsorted values

Cons:
  - False positives: "probably present" may be wrong → reads unnecessary blocks
  - Storage overhead: typically 1-2% of column data size
  - Only equality and IN: hashing destroys order, so range queries get no help
  - Must be enabled per column at write time

# Bloom filters HELP:
txns.filter("transaction_id = 'TXN-500000'")  # equality ✓
txns.filter("transaction_id IN ('TXN-1', 'TXN-2', 'TXN-3')")  # IN ✓

# Bloom filters DO NOT HELP:
txns.filter("transaction_id > 'TXN-500000'")  # range ✗
txns.filter("transaction_id LIKE 'TXN-5%'")  # prefix ✗

When do you use each skipping mechanism?

| Mechanism | Best For | Fails When |
|---|---|---|
| Min/max | Sorted or low-cardinality columns | Unsorted high-cardinality |
| Dictionary | Low-cardinality equality filters | High cardinality (dictionary dropped) |
| Bloom filter | High-cardinality equality on unsorted columns | Range queries |
| ZORDER | Multi-column filter skipping | Too many ZORDER columns |

How do you combine all three mechanisms in a banking table?

At the National Bank of India, the transactions table uses all three skipping mechanisms together: sorting for date range queries, bloom filters for transaction ID point lookups, and dictionary filtering for low-cardinality branch codes.

# Combined strategy for the bank transactions table

# 1. Sort or ZORDER by txn_date (range filters use min/max)
# 2. Bloom filter on transaction_id (equality lookups)
# 3. Dictionary filtering on branch_code (low cardinality, automatic)

# Write with bloom filter on transaction_id
txns.write \
    .option("parquet.bloom.filter.enabled#transaction_id", "true") \
    .option("parquet.bloom.filter.expected.ndv#transaction_id", "10000000") \
    .format("delta") \
    .save("/data/bank/transactions")

# Then ZORDER for date range queries
spark.sql("OPTIMIZE banking_prod.transactions ZORDER BY (txn_date)")

# Result:
# WHERE txn_date = '2025-06-15'     → min/max skipping (ZORDER)
# WHERE transaction_id = 'TXN-5000' → bloom filter skipping
# WHERE branch_code = 'MUMBAI-01'   → dictionary filtering

What should a senior engineer know?

• Sort or ZORDER on the columns you range-filter on most; add bloom filters on the high-cardinality columns you equality-filter on.
• You cannot sort by many columns at once, so bloom filters cover the lookups sorting cannot.
• The false-positive rate is tunable: a larger filter means fewer false positives but more storage.
• At the National Bank of India, the transactions table was sorted by date (date filters used min/max), but point lookups by transaction_id skipped nothing until we added a bloom filter on that column.

# Combined strategy:
# 1. Sort or ZORDER by txn_date (range filters use min/max)
# 2. Bloom filter on transaction_id (equality lookups)
# 3. Dictionary filtering on branch_code (low cardinality, automatic)