Skip to content
KEDBYTE
Site navigation
How Data Works
Chapter
43

Columnar Storage and Compression

Part G · From Records to Insight|3,861 words|about 17 min read|Volume G

43.0 What this chapter gives you#

  1. A report often needs a few fields from many records. Columnar storage arranges values so the engine can avoid reading unrelated fields and can exploit similarities among values of the same kind.
  2. You will work through row and column layouts, dictionary and run-length encodings, compression blocks, predicate pushdown and conservative skipping. Every saving will be tied to an explicit workload and representation.
  3. The companion byte-layout experiment is an original fixed-width format using Python’s standard library. It is not a Parquet writer, a database benchmark or evidence that columnar storage always outperforms row storage.

43.1 Rows versus columns#

43.1.1 PLAIN — in simple words#

  1. Row storage keeps the fields of one record close together. Column storage keeps values of one field close together across many records.
  2. A row-oriented layout can suit fetching most fields of one order. A column-oriented layout can suit adding one amount field across millions of orders.
  3. The benefit comes from avoiding unnecessary work, not from changing the answer. Both layouts must preserve the same record relationships and values.

43.1.2 PLAIN — a picture in your head#

  1. Mira can store complete order slips in a stack, or copy all quantities into one list and all amounts into another list with matching positions.
  2. To add amounts, the second arrangement lets her read only the amount list. To inspect one complete order, she must gather corresponding values from several lists.
  3. Where the comparison breaks: real columnar formats include row groups, metadata, null representation and nested structures. They are not simply separate text files with the same line numbers.

43.1.3 PLAIN — a worked example#

  1. Imagine 10 million records with 50 fixed-width fields of 8 bytes each. Ignoring all headers and compression, the data occupies 10,000,000 × 50 × 8 = 4,000,000,000 bytes, or 4 decimal GB.
  2. A query needing only two fields has 160,000,000 bytes of relevant field values. Ideal projection avoids 48 of 50 fields, or 96% of that raw field payload.
  3. That is an opportunity, not a promise of 25 times faster execution. Metadata reads, filtering, decompression, computation, result handling and storage access patterns still contribute to elapsed time.
  4. The local experiment uses 10,000 rows and four signed 64-bit fields. A complete row representation contains 320,000 raw bytes. The branch and amount columns together contain 160,000 bytes before metadata or compression.

43.1.4 PLAIN — what is really happening inside#

  1. A reader selects the fields required by the query and locates their chunks. Values from unneeded columns may remain unread.
  2. The engine combines corresponding positions to reconstruct selected records or compute aggregates. Preserving row alignment is essential; independently sorting columns would destroy the original relationships.
  3. Row groups divide a file into manageable horizontal pieces, within which columns are stored separately. This permits some parallelism and bounded reads without requiring one enormous chunk for each column.

43.1.5 TECHNICAL — the engineer’s version#

  1. Parquet’s file organization contains row groups and column chunks, with metadata describing their locations and interpretation. Projection can avoid unrelated column payloads when the reader and query support it. [S170]
  2. A column layout is not inherently a transaction or update policy. Point updates, deletes, snapshots and concurrency may be implemented by an engine or table layer above the file format.
  3. The laboratory counts bytes that its explicit access algorithm inspects and verifies equal query results across layouts. It does not measure operating-system read amplification, real storage-device traffic or a Parquet engine’s performance.

43.1.6 WORDS — remember these#

  1. Columnar storage: values grouped by field — a layout that can reduce irrelevant reads for analytical projections. Row group: a horizontal subset stored in column pieces — a unit connecting corresponding column chunks within a columnar file. Projection pruning: avoiding unneeded fields — selecting only the columns required to compute the query result.

43.2 Encodings#

43.2.1 PLAIN — in simple words#

  1. An encoding represents values in another form. It may save space by replacing repeated strings with short codes or by recording how values change rather than repeating their full representations.
  2. The decoder must recover the same intended values. A smaller representation that silently changes a price or loses missing-value information is not an equivalent storage improvement.
  3. Different patterns favour different encodings. Repeated values, small ranges and sorted sequences offer different opportunities; random-looking unique values may offer few.

43.2.2 PLAIN — a picture in your head#

  1. Instead of writing “north” five hundred times, Mira writes a small dictionary saying code 1 means north and then records the code on each relevant slip.
  2. For a long uninterrupted run of code 1, she might write “1 repeated 500 times.” That is another encoding layered on the repeated pattern.
  3. Where the comparison breaks: digital encodings require precise widths, byte order, length fields and error handling. A verbal shortcut is not a complete interoperable file specification.

43.2.3 PLAIN — a worked example#

  1. A column contains 500 instances of north, 300 of south and 200 of west. The raw UTF-8 character payload is 500 × 5 + 300 × 5 + 200 × 4 = 4,800 bytes.
  2. A dictionary’s three strings need 14 character bytes, and 1,000 one-byte codes need 1,000 bytes. The combined 1,014 bytes exclude lengths, counts and other framing; they are not a claimed complete file size.
  3. If the codes appear in three runs, a toy run-length format using one byte for the code and four for its count needs 3 × 5 = 15 run bytes. Alternating codes 1 and 2 for 1,000 values instead needs 5,000 run bytes, worse than the uncompressed codes.
  4. A delta example stores 1,000 once, then changes +2, +2 and +3 to represent 1,000, 1,002, 1,004 and 1,007. The benefit depends on how those deltas and their metadata are actually encoded.

43.2.4 PLAIN — what is really happening inside#

  1. Dictionary encoding separates distinct values from their occurrences. Its usefulness decreases when most values are unique or when dictionary lookup and storage costs dominate.
  2. Run-length encoding records consecutive repetitions. Sorting or clustering can improve runs, but changing record order must preserve the relationship among all fields.
  3. Delta and bit-packing schemes exploit small differences or bounded ranges. The decoder needs the appropriate base, bit width and signedness rules; these are part of the format contract.

43.2.5 TECHNICAL — the engineer’s version#

  1. Parquet specifies several encodings, including plain values, dictionary codes, run-length/bit-packing hybrids and delta representations. Their actual bitstream rules must be read from the specification, not inferred from the teaching examples. [S171]
  2. The toy run codec validates code range and positive bounded counts before decoding. Resource limits matter: a tiny encoded input claiming billions of repetitions should not allocate unbounded memory.
  3. Encoding and general-purpose compression are distinct stages. An encoding may reduce size directly or rearrange bytes so that a later compressor finds more repetition. Neither should be credited with the other’s effect without measuring the pipeline.

43.2.6 WORDS — remember these#

  1. Dictionary encoding: replacing values with reusable codes — a representation containing a distinct-value dictionary and an occurrence-code sequence. Run-length encoding: storing repetitions as a value and count — an encoding effective when identical values are consecutive. Delta encoding: storing changes from earlier values — a representation whose savings depend on the size and regularity of differences.

43.3 Compression blocks#

43.3.1 PLAIN — in simple words#

  1. Compression reduces a byte sequence using patterns that a decoder can reconstruct. Lossless compression must return the original bytes exactly.
  2. Compression usually works within blocks or pages. To read one value, the reader may need to fetch and decompress a larger block containing it.
  3. Larger blocks can provide more repeated context and fewer headers, but can also increase the minimum work for a small read. Block size is therefore a trade-off, not a universal “bigger is better” setting.

43.3.2 PLAIN — a picture in your head#

  1. Mira packs many slips into a tightly sealed bundle. The bundle occupies less shelf space, but extracting one slip may require opening and unpacking the whole bundle.
  2. Several smaller bundles can make selective access easier, at the cost of more wrapping and sometimes less efficient packing.
  3. Where the comparison breaks: software compression uses mathematical representations, not physical squeezing. Its CPU cost, memory use and exact framing depend on the codec and implementation.

43.3.3 PLAIN — a worked example#

  1. Suppose a raw 1 MB block compresses to 250 kB. Reading and decoding that block to obtain one 8-byte value may still require 250 kB of input and roughly 1 MB of decompressed output handling.
  2. If a query needs every value in the block, that overhead may be worthwhile because three quarters of the stored payload was avoided. If it needs one scattered value from each of many blocks, the trade-off is different.
  3. In the companion experiment, the same generated records are packed in row-major and column-major byte order, then compressed with the same standard-library zlib settings.
  4. The output records actual encoded lengths and verifies exact decompression equality. It does not assume in advance which layout has the better compression ratio, and it does not infer application throughput from file size alone.

43.3.4 PLAIN — what is really happening inside#

  1. The compressor encodes patterns in a bounded input unit. The decoder reconstructs that unit before or while the reader interprets the values inside it.
  2. Compressed length, uncompressed length and integrity metadata serve different purposes. A length field helps frame data but must not be trusted as permission for unlimited memory allocation.
  3. A reader may decompress only selected pages when metadata allows it. Efficient access depends on the arrangement of blocks, the query and which metadata the writer actually supplied.

43.3.5 TECHNICAL — the engineer’s version#

  1. Keep the stages explicit: logical values, value encoding, compression and file/container framing. Distinguish stored bytes, bytes read, bytes decompressed and values examined in a measurement.
  2. A codec benchmark should state implementation, level, block size, data distribution and whether encoding/decoding time is included. Comparing different data or unequal settings confounds the result.
  3. Parquet pages are the units whose encoded payloads may be compressed under the file’s codec settings. The teaching zlib blob has no Parquet page headers, dictionary-page rules or compatible reader contract. [S170] [S171]

43.3.6 WORDS — remember these#

  1. Lossless compression: a smaller representation with exact recovery — byte encoding whose decoder reproduces the original input. Compression block: a unit compressed and decoded together — a boundary affecting storage efficiency and selective-read cost. Read amplification: reading more bytes than the requested logical data — additional work caused by layout, blocks, metadata or access patterns.

43.4 Predicate pushdown#

43.4.1 PLAIN — in simple words#

  1. A predicate is a condition such as “branch equals 1” or “amount is at least 5,000.” Pushdown means applying useful parts of that condition closer to the stored data.
  2. This can avoid returning or decoding data that the rest of the query would immediately discard. It is helpful only when the lower layer understands the condition with compatible semantics.
  3. Not every expression can be pushed down safely. A custom function, different text comparison or missing-value rule can change which rows qualify.

43.4.2 PLAIN — a picture in your head#

  1. Dev asks the storeroom clerk for only the boxes belonging to branch 1 rather than carrying every box to the office and sorting them there.
  2. The clerk must use the same branch definition and labels. A convenient approximation can send the wrong boxes or omit needed ones.
  3. Where the comparison breaks: engines may combine metadata pruning, value filtering and later verification. “Pushed down” does not necessarily mean the storage layer proves the entire query condition without reading values.

43.4.3 PLAIN — a worked example#

  1. The toy file contains four 8-byte fields per row: sequence, branch, quantity and amount. A query asks for the sum of amount where branch is 1.
  2. A full-row scan examines 32 bytes per row, or 320,000 bytes for 10,000 rows. A column-oriented scan can inspect the branch and amount columns, totalling 160,000 raw bytes in this simple implementation.
  3. A more selective implementation could first inspect branch values, then fetch amount values only for matching positions. Whether that reduces physical reads depends on block layout and the access API, so the simple lab does not claim it automatically.
  4. Both query paths must return exactly the same sum for the same generated records. A smaller byte count with a different result is a correctness failure, not an optimization.

43.4.4 PLAIN — what is really happening inside#

  1. The query planner determines which conditions the storage reader can evaluate. The reader uses partition information, statistics or decoded values to reduce candidates.
  2. Conditions left unresolved continue through the execution plan and are evaluated later. Correctness requires retaining all possible qualifying rows until the relevant condition is decided.
  3. Filtering also changes downstream work. Fewer candidate rows can reduce joins, aggregation memory and network transfer, even when the initial file read saves little.

43.4.5 TECHNICAL — the engineer’s version#

  1. Pushdown requires semantic compatibility across layers, including data types, null handling, collation and supported operators. A functionally similar expression is not necessarily equivalent for every input.
  2. Distinguish partition pruning, row-group/page pruning and row-level filtering. They remove work at different granularities and rely on different metadata or decoded values. [S172]
  3. Validate optimized output against a simpler reference query, including boundary values, missing fields and unusual distributions. An execution-plan label indicates a selected mechanism, not its correctness for an undocumented data contract.

43.4.6 WORDS — remember these#

  1. Predicate: a condition used to select records — an expression whose truth determines query eligibility under the relevant semantics. Predicate pushdown: evaluating selection closer to storage — moving supported filtering work earlier to reduce later processing. Candidate row: a record not yet ruled out — input retained until the necessary conditions can be evaluated correctly.

43.5 Statistics and skipping#

43.5.1 PLAIN — in simple words#

  1. A block may carry a summary such as its smallest and largest value. A query can skip the block when that summary proves that no value can match.
  2. The word “proves” matters. If the summary merely suggests that matching values are unlikely, skipping could lose valid results.
  3. Statistics can be missing or imprecise. A safe reader then reads more data rather than inventing a stronger exclusion claim than the metadata supports.

43.5.2 PLAIN — a picture in your head#

  1. A box labelled “order numbers 100 through 199” cannot contain order 250 when the label is reliable and uses the same numbering system.
  2. A box labelled “mostly old orders” does not justify skipping it while looking for a recent order. One exception would invalidate that shortcut.
  3. Where the comparison breaks: binary formats have type-specific comparison and null rules. A text prefix bound, a floating-point special value or a missing statistic needs more care than a simple integer label.

43.5.3 PLAIN — a worked example#

  1. Three toy blocks have integer ranges [0, 9], [10, 19] and [20, 29]. A query selects values from 12 through 16 inclusive.
  2. The first block can be skipped because its maximum 9 is below 12. The third can be skipped because its minimum 20 is above 16. The middle remains a candidate and its actual values must be checked.
  3. A range of [10, 19] does not prove that 12, 13, 14, 15 or 16 actually occurs. It only fails to rule them out. Candidate selection and confirmed matches are different stages.
  4. If the middle block has no statistics, read it. If its bounds are corrupt, treating them as authoritative can lose rows; metadata integrity and validation remain part of the storage system’s responsibility.

43.5.4 PLAIN — what is really happening inside#

  1. Writers compute summaries while creating files or pages. Readers compare the query bounds with those summaries before fetching unnecessary payloads.
  2. Clustering similar values can make block ranges narrower and improve skipping. Randomly mixing every date into every block may leave each block spanning the whole report interval.
  3. Null counts, bloom filters and additional indexes can support other decisions, but each has a defined scope. A bloom filter’s possible match still requires verification; absence is useful only when the filter is valid and correctly interpreted.

43.5.5 TECHNICAL — the engineer’s version#

  1. Parquet’s optional page index separates value-bound information from page offsets so readers can skip suitable pages without first reading every page header. The index is not a general secondary B-tree index. [S172]
  2. Conservative interval exclusion for an inclusive query [low, high] is block_max < low or block_min > high, assuming trustworthy comparable integer bounds. Equality at a boundary must not be excluded.
  3. The lab tests boundary, missing-statistic and overlapping-range cases against direct value filtering. It does not validate every Parquet logical type, truncated string bound, NaN convention or encrypted-file metadata path.

43.5.6 WORDS — remember these#

  1. Zone map: summary bounds for a data region — metadata such as minimum and maximum used for conservative elimination. Conservative pruning: skipping only what cannot match — a rule that may retain extra candidates but must not discard valid results. Data clustering: placing similar values near one another — a layout choice that can tighten summaries and improve selective access.

43.6 CPU, memory and input-output trade-offs#

43.6.1 PLAIN — in simple words#

  1. Saving storage reads may require more CPU work to decode values. Saving disk space may increase memory needed for dictionaries or decompressed blocks.
  2. The best balance depends on what is scarce and what the query actually does. A CPU-bound report and a slow-storage scan can favour different settings.
  3. Measure the entire question under a stated environment. A compression ratio, a byte count and a latency figure describe different aspects of the system.

43.6.2 PLAIN — a picture in your head#

  1. Mira can carry fewer tightly packed bundles from the storeroom, but Dev may spend longer unpacking them at his desk.
  2. If walking is the slow part, tight packing helps. If unpacking already keeps Dev busy while the storeroom is next door, another packing method might be preferable.
  3. Where the comparison breaks: real engines can overlap I/O and computation, use vectorized decoding and cache data. Adding isolated stage times does not always predict end-to-end elapsed time.

43.6.3 PLAIN — a worked example#

  1. Suppose reading raw input takes an assumed 8 seconds and processing takes 2 seconds without overlap. A compressed alternative takes 2 seconds to read and 5 seconds to decompress and process.
  2. Under this deliberately serial model, the first path takes 10 seconds and the second 7. Compression saves time despite increasing CPU work.
  3. Change only the raw-read time to 1 second on a much faster storage path. The uncompressed model now totals 3 seconds; the compressed path is not automatically preferable. Real measurements would need updated compressed-read time and overlap behaviour too.
  4. The companion report therefore records generated row count, exact layout lengths, compressed lengths, round-trip checks and equal query results separately. It does not convert these into a production capacity claim.

43.6.4 PLAIN — what is really happening inside#

  1. Execution can process batches of values efficiently, reducing per-value dispatch and improving locality. The benefit depends on operators, representation and available hardware.
  2. Large dictionaries, many concurrent scans and decompressed buffers can consume substantial memory. A query that fits alone may spill or slow under concurrent load.
  3. Updates and small writes introduce another cost. An analytical file arrangement may require writing replacement files, maintaining delete information or compacting many small files before queries remain efficient.

43.6.5 TECHNICAL — the engineer’s version#

  1. Report workload and measurement scope: cold or warm data, projected columns, selected fraction, ordering, compression settings, concurrency and result consumption. Avoid comparing an in-memory decoded array with a disk-backed compressed file as though layout were the only variable.
  2. Distinguish logical payload, encoded size, compressed size, bytes transferred and CPU/memory use. A query can save one of these while increasing another.
  3. The file-format and encoding specifications explain available mechanisms; they do not guarantee a workload-specific speedup. Verify correctness first, then measure the selected implementation under representative conditions. [S170] [S171] [S102]

43.6.6 WORDS — remember these#

  1. Vectorized execution: processing batches of values together — an implementation approach reducing overhead and exploiting suitable data layout. Decode cost: work to reconstruct usable values — CPU and memory effort introduced by an encoding or compression layer. End-to-end measurement: timing the complete defined operation — evidence that includes all stages required to produce and consume the intended result.

43.97 Practice and worked answers#

  1. Question: How much raw field payload is needed for two of fifty 8-byte columns across ten million rows? Answer: 160,000,000 bytes, excluding metadata and compression.
  2. Question: Why must columns preserve row alignment? Answer: A quantity and price at corresponding positions must still belong to the same record. Independently sorting columns destroys that relationship.
  3. Question: When does the toy run-length encoding become larger? Answer: Alternating codes produce one five-byte run per value, so 1,000 values become 5,000 run bytes instead of 1,000 one-byte codes.
  4. Question: Does a 250 kB compressed block allow an 8-byte physical read for one value? Answer: Not generally. The reader may need the whole compressed block and substantial decoded data.
  5. Question: Can a block with bounds 10 through 19 be skipped for a query 12 through 16? Answer: No. The bounds overlap the query, even though they do not prove an actual match.
  6. Question: What should a safe reader do when useful statistics are absent? Answer: Retain the block as a candidate and inspect it rather than inventing an exclusion.
  7. Question: Is a smaller compressed file necessarily faster to query? Answer: No. Decoding, memory, access granularity and the workload affect the outcome.
  8. Question: What does the companion format establish about Parquet interoperability? Answer: Nothing. It is a labelled original byte-layout exercise, not a Parquet implementation.

43.98 Common wrong ideas#

  1. Wrong: Columnar storage changes the logical rows. Right: It changes representation while preserving their relationships.
  2. Wrong: Projection savings directly predict equal latency savings. Right: Other stages still contribute to time.
  3. Wrong: Dictionary encoding always compresses data. Right: High cardinality and metadata can reduce or reverse its benefit.
  4. Wrong: More compression is always better. Right: Decode and access costs can dominate.
  5. Wrong: Pushdown means the whole predicate was decided without reading values. Right: Some conditions only reduce candidates.
  6. Wrong: An overlapping min/max range proves a match. Right: It only prevents safe exclusion.
  7. Wrong: Missing statistics justify guessing. Right: Safe pruning becomes less aggressive.
  8. Wrong: A toy byte experiment is a production engine benchmark. Right: Its evidence applies only to the stated representation and operations.

43.99 Chapter summary in 20 lines#

  1. Row layouts group a record’s fields together.
  2. Column layouts group values of one field together.
  3. Analytical projections can avoid unrelated columns.
  4. Row alignment must survive every representation change.
  5. Row groups bound columnar processing units.
  6. Encodings exploit repeated or predictable value patterns.
  7. Dictionary codes need their dictionary and framing.
  8. Run-length encoding benefits consecutive repetitions.
  9. Delta encoding benefits suitable differences between values.
  10. Compression must be evaluated separately from value encoding.
  11. Blocks determine the minimum decoding work for some reads.
  12. Pushdown moves supported filtering closer to storage.
  13. Semantics must agree across execution layers.
  14. Metadata can rule out blocks conservatively.
  15. Overlapping bounds identify candidates, not confirmed matches.
  16. Missing statistics should reduce pruning, not correctness.
  17. Clustering can improve the usefulness of block summaries.
  18. CPU, memory and I/O costs can move in opposite directions.
  19. Compare equal results under equal workload assumptions.
  20. A format specification supplies mechanisms, not guaranteed speedups.

Return to contents