Columnar storage usually compresses far better than row storage. Explain why, describe run-length encoding and dictionary encoding, and say how compression affects query execution beyond saving disk space.
answer
- One type, one domain per block = low entropy
- RLE = value + run length; needs clustering
- Dictionary = small codes + value table
- Delta/frame-of-reference + bit-packing for sorted numerics
- Late materialization: filter on codes, decode survivors
basics
~20 sA column block holds one data type with similar, often repeating values, so it compresses far better than a row block that interleaves types. Run-length encoding stores value plus repeat count; dictionary encoding replaces values with small codes into a value table. Beyond disk savings, scans read fewer bytes and engines can filter and aggregate on encoded data without decompressing.
solid answer
~60 sCompression works on redundancy. In a column block every value is the same type and usually drawn from a narrow domain - a handful of statuses, near-identical timestamps, a bounded set of prices - so local entropy is low. A row block interleaves an integer, a string, a timestamp and a decimal, which breaks that regularity. Typical encodings: - **Run-length encoding (RLE):** store `('PAID', 8000)` instead of 8000 copies. Excellent for low-cardinality columns, and dramatically better if the data is sorted or clustered on that column. - **Dictionary encoding:** build a table of distinct values and store small integer codes. Turns wide strings into 1-2 byte codes and makes equality comparison integer comparison. - **Delta / frame-of-reference plus bit-packing:** store differences from a base and use only the bits needed - ideal for sorted keys, timestamps, sequences. The execution payoff matters more than the disk saving: scans are usually I/O-bound, so 10x compression is close to 10x less to read. Better, engines run **late materialization** - filtering, joining and grouping on dictionary codes or RLE runs directly, decoding only the surviving values, and counting a run in one step instead of 8000 comparisons.
code
text · 4 linesraw: PAID PAID PAID PAID NEW NEW PAID PAID
RLE: (PAID,4) (NEW,2) (PAID,2)
dictionary: dict{0:PAID, 1:NEW} codes: 0 0 0 0 1 1 0 0
predicate status='PAID' -> compare codes to 0go deeper
Know that columns compress well because neighbouring values are the same type and often repeat, and be able to describe run-length and dictionary encoding in one sentence each.
Explain which encoding suits which column shape, and that less I/O is the point; mention that sort order drives the ratio.
Discuss operating on encoded data, late materialization and zone-map skipping, plus the update cost of compressed blocks and the CPU/IO tradeoff between codecs.
Reason about clustering and segment design as a capacity lever - what to sort by, block sizing, and when decompression CPU becomes the new bottleneck.
## Why layout drives compressibility Compression exploits repetition and predictability within a block of bytes. Grouping values by column concentrates both. A columnar block of the `status` column might be thousands of copies of a dozen strings. A block of `event_time` is a near-monotonic sequence where consecutive values differ by seconds. A block of `price` is a few thousand distinct decimals. Every block is one type, one width, one domain. The same rows in a row store produce a block where an int is followed by a string, a timestamp, a decimal, then the next row's int. General-purpose compressors still find some redundancy, but the fine-grained, type-aware encodings below cannot be applied at all, because they need a homogeneous sequence. ## The main encodings **Run-length encoding (RLE).** Replace a run of identical values with the value and a count: 8000 rows of `'PAID'` become one pair. Effectiveness depends entirely on clustering - if the table is stored sorted (or partitioned) by that column, runs are long. RLE also compresses the *work*: an aggregate can add 8000 to a counter in one step instead of iterating. **Dictionary encoding.** Collect distinct values into a dictionary and store per-row codes. A `country` column of 200 distinct 12-byte strings becomes 1-byte codes plus a small dictionary - a >10x win, plus equality predicates become integer comparisons against a single looked-up code. Grouping can use the code as the hash key. Dictionaries are usually per-block or per-segment so they stay small and bounded. **Delta and frame-of-reference encoding with bit-packing.** For sorted or slowly-changing numerics, store the difference from the previous value or from a block minimum, then pack the residual into the minimum number of bits. IDs and timestamps in insertion order often collapse to a handful of bits per value. **Bitmap encoding.** For very low cardinality, keep one bitmap per distinct value; predicates become bitwise AND/OR over compressed bitmaps. Engines usually pick an encoding per block by sampling, then optionally apply a general byte compressor (LZ4, Zstd) on top - fast codecs are preferred because CPU time spent decompressing must stay cheaper than the I/O it saves. ## Why this changes execution, not just storage size **Less I/O.** Analytical scans are usually bandwidth-bound. Reading a 10x-compressed column is roughly 10x faster, and it also stretches the buffer cache: more of the working set fits in RAM. **Operating on encoded data (late materialization).** The big win is deferring decode. Filtering `status = 'PAID'` becomes: look up the code once, compare integers. `count(*)` over an RLE run reads one pair. A GROUP BY can aggregate on dictionary codes and translate only the final groups. Values are materialized as real strings or decimals only for rows that survive, and only for columns actually output. **Better vectorization.** Fixed-width packed codes sit in dense arrays, so comparisons run over batches with SIMD instructions, branch-free. **Zone maps.** Per-block min/max metadata, stored alongside encoded blocks, lets the scan skip blocks that cannot satisfy a predicate without touching them at all. ## Costs and limits - Compression quality depends on **physical clustering**. Randomly ordered data destroys RLE and delta encoding; that is why columnar engines care so much about sort/cluster keys during load. - **Updates fight compression.** Changing one value inside a compressed, packed block means rewriting the block, which is why writes land in an uncompressed row-shaped delta area first and are compacted later. - **High-cardinality columns** (free text, UUIDs) compress poorly; dictionaries grow toward the data size and lose their advantage. - CPU is not free: heavyweight codecs can turn an I/O-bound scan into a CPU-bound one.
- Why does the physical sort order of a table matter so much for columnar compression?Run-length, delta and frame-of-reference encodings all exploit locality between neighbouring values. If rows are clustered by a low-cardinality column, that column collapses into a few long runs and correlated columns compress better too. Randomly ordered data yields runs of length one, so RLE can even inflate storage, and zone maps become useless because every block's min/max spans the whole domain.
saying these in an interview costs you the question
- Treating compression as purely a disk-space saving and missing that it cuts scan I/O and CPU work
- Claiming compressed data must always be fully decompressed before predicates can be applied
- Assuming compression ratios are a property of the engine rather than of cardinality and sort order
- Suggesting the heaviest codec is always best, ignoring that decompression CPU can become the bottleneck
- Believing compression applies equally well to high-cardinality columns like UUIDs or free text