Column-Family and Column Stores

A row store (the classical relational layout) serializes each row's columns contiguously on disk: `(id₁, name₁, age₁, salary₁), (id₂, name₂, age₂, salary₂), …`. This is ideal for transactional workloads that fetch or modify entire records — an OLTP query like "give me all of employee 42's fields" reads one contiguous block. A column store instead serializes each column contiguously: all `id` values together, then all `name` values, then all `age` values, and so on. An analytical query like "average `salary` over all employees" then reads only the `salary` column's bytes, ignoring everything else. A column family, as introduced by Bigtable and adopted by HBase and Cassandra, is a middle ground from the NoSQL Data Models Overview. Data is still organized by row key, but the row's columns are partitioned into named groups called column families, and within a column family the data for many rows is stored together in per-family files (Bigtable calls these SSTables). Columns accessed together are placed in the same family, so a query touching one family avoids reading unrelated families — a coarse-grained columnar benefit layered on top of a row-keyed, sparse, schema-flexible data model. This distinguishes column families from pure column stores (Vertica, MonetDB, C-Store, and file formats like Parquet and ORC), which decompose the table into one physical stream per individual column, with no notion of row-based storage at all beneath the logical relation. The precision worth internalizing: column family stores are optimized for wide, sparse, semi-structured records accessed by key (a hybrid NoSQL model), while pure column stores are optimized for narrow, dense, strongly-typed analytical scans across billions of rows. Both exploit the same underlying physical principle — group data along the column dimension instead of the row dimension — but at different granularities and for different workloads.

Physical layout. In a pure column store, a table with columns $C_1, \ldots, C_k$ and $N$ rows is stored as $k$ separate arrays (or files), each of length $N$, in the same row order. A positional index (implicit, since row $i$ is simply the $i$-th entry of every array) reconstructs a full row by reading the $i$-th value from each column array. Column families store data per-family, keyed by (row key, column family), typically sorted by row key and then by column name within the family, so a scan over a family retrieves ranges of related columns efficiently.

Encoding. Because each column stores values of one type with often-repetitive or ordered patterns, specialized encodings apply:

• Run-length encoding (RLE): store `(value, count)` pairs for runs of identical adjacent values — devastating effective for low-cardinality sorted columns like `country` or `status`.
• Dictionary encoding: map each distinct value to a small integer code, store the codes (which pack into few bits) plus a lookup dictionary — effective for string columns with modest cardinality.
• Bit-packing / frame-of-reference: store integers as small deltas from a reference value using the minimum number of bits needed.
• Delta encoding: store successive differences, useful for sorted or monotonic columns like timestamps.

Query execution with late materialization. A columnar engine evaluates predicates column-by-column, producing intermediate position lists (row indices satisfying each predicate) rather than materializing full rows early. Only at the very end, when output columns are actually needed, does the engine "stitch" the surviving positions back into rows — this is late materialization, and it minimizes the amount of data ever assembled into row form. ```pseudocode function COLUMNAR_SCAN(table, predicates, output_columns):

# predicates: list of (column_name, operator, value)

# Start with the full set of row positions candidate_positions ← {0, 1, ..., table.num_rows - 1}

# Evaluate predicates one column at a time, narrowing positions for (col, op, val) in predicates: column_data ← LOAD_COLUMN(table, col) # read only this column's bytes column_data ← DECODE(column_data) # decompress / decode if needed matching ← ∅ for pos in candidate_positions: if APPLY_OP(column_data[pos], op, val): matching.add(pos) candidate_positions ← matching if candidate_positions is empty: return EMPTY_RESULT # short-circuit: nothing more to check

# Late materialization: only now fetch the columns the caller actually wants result ← [] for col in output_columns: column_data ← LOAD_COLUMN(table, col) column_data ← DECODE(column_data) result_column ← [column_data[pos] for pos in sorted(candidate_positions)] result.append(result_column) return ASSEMBLE_ROWS(result, candidate_positions) ``` ```pseudocode function RUN_LENGTH_DECODE(runs):

# runs: list of (value, count) pairs output ← [] for (value, count) in runs: append value repeated count times to output return output function DICTIONARY_DECODE(codes, dictionary):

# codes: array of small integers; dictionary: code -> actual value output ← [] for code in codes: output.append(dictionary[code]) return output ``` The order of predicate evaluation matters for efficiency: a good query optimizer applies the most selective, cheapest predicate first, since `candidate_positions` shrinks fastest that way and later, more expensive column scans touch far fewer positions (this is why the early-exit check after narrowing is included above).

I/O cost of a scan. Let a table have $N$ rows and $k$ columns, and suppose a query needs $m \le k$ columns with average on-disk byte-width $w$ per value (post-compression). A row store must read all $k$ columns' worth of bytes per row it touches, roughly

because rows are stored contiguously and cannot be split without random-access overhead per row. A column store reads only

where $\bar w$ is the average width among the needed columns. When $m \ll k$ (typical analytics: a handful of columns out of hundreds), this is a factor of roughly $k/m$ improvement, which is the core reason columnar scans dominate wide-table analytics.

Compression ratio. For a column with $d$ distinct values among $N$ rows, dictionary encoding needs $\lceil \log_2 d \rceil$ bits per value plus a dictionary of size $O(d \cdot \bar\ell)$ (where $\bar\ell$ is average string length), versus $O(\bar\ell)$ bytes per value uncompressed. When $d \ll N$ (e.g., a `country` column with 195 distinct values across a billion rows), the per-row cost collapses from tens of bytes to a handful of bits — this is only possible because columnar layout groups homogeneous values together, giving compressors long, self-similar streams to exploit; interleaved row-major storage destroys this locality.

Point-lookup cost. Retrieving one full row in a column store requires $k$ separate positional lookups (one per column file) plus assembly, an $O(k)$ operation with $k$ potentially expensive random I/Os, versus $O(1)$ contiguous I/O in a row store. This is the honest trade-off: column stores are asymptotically worse for point lookups and small-row transactional access, which is precisely why OLTP systems remain row-oriented while OLAP systems go columnar — a distinction elaborated further in OLAP vs OLTP Workloads.

Correctness of late materialization. The invariant maintained by `COLUMNAR_SCAN` is: after processing predicates $1, \ldots, i$, `candidate_positions` equals exactly the set of row indices satisfying all of predicates $1$ through $i$. This holds by induction — the base case is the full position set (satisfying the empty conjunction vacuously), and each iteration intersects the current set with positions satisfying the new predicate, which is exactly conjunction. Because AND is commutative and associative, the final set after all predicates is independent of evaluation order, so reordering predicates for efficiency (cheapest/most-selective first) cannot change the result, only the cost. The early-exit on an empty set is also safe: once the conjunction is unsatisfiable, no further predicate can add rows back (intersection with anything remains empty), so returning immediately preserves correctness while saving work.

Compression is lossless and order-preserving, which matters for correctness: RLE and dictionary encoding are invertible transforms — `DICTIONARY_DECODE(DICTIONARY_ENCODE(x)) = x` for every value $x$ — so predicate evaluation on decoded values is equivalent to evaluation on the original data, and some engines even push predicates into the encoded representation (e.g., comparing dictionary codes directly) as a further optimization, valid precisely because the encoding is a monotonic bijection when the dictionary is built by sorted value order.

Consider a table `Sales(txn_id, region, product, amount)` with 8 rows, and the query: ```sql SELECT AVG(amount) FROM Sales WHERE region = 'West'; ``` Row-major storage (8 rows × 4 columns, assume 8 bytes/value ⇒ 32 bytes/row):

Row store execution: must read all 8 rows fully — 8 × 32 = 256 bytes of I/O, even though only `region` and `amount` (2 of 4 columns) are relevant.

Column store execution, tracing `COLUMNAR_SCAN`: 1. `candidate_positions ← {0,1,2,3,4,5,6,7}` (0-indexed). 2. Predicate `(region = 'West')`: load only the `region` column array `[East, West, East, West, South, West, East, West]` — 8 bytes if dictionary-coded to 1 byte/value (dictionary: East=0, West=1, South=2). Scanning gives `matching = {1, 3, 5, 7}`. Update `candidate_positions ← {1,3,5,7}`. 3. No more predicates. Not empty, so proceed to materialization. 4. Output column requested: `amount`. Load only the `amount` array (8 values × 8 bytes = 64 bytes), decode, and gather positions `{1,3,5,7}`: values `[340, 260, 410, 300]`. 5. `ASSEMBLE_ROWS` and compute average: $(340+260+410+300)/4 = 1310/4 = 327.5$.

I/O comparison: column store read the `region` array (dictionary-coded, ~8 bytes) plus the `amount` array (64 bytes) ≈ 72 bytes, versus 256 bytes for the row store — a 3.5× reduction even on this tiny toy table; on real tables with 50+ columns the ratio grows proportionally to $k/m$, exactly as the complexity analysis predicts.

Compression trace on `region`: sorted-and-RLE'd, the column `[East, East, East, South, West, West, West, West]` (if physically re-sorted by region, as some column stores do via a sort key) becomes runs `(East,3), (South,1), (West,4)` — 3 run-pairs instead of 8 raw values, each pair needing only a few bytes, versus 8 separate string values in a row store where `region` is interleaved with unrelated bytes from `product` and `amount` and cannot be run-length encoded at all.

The columnar idea traces back to statistical and scientific databases of the 1970s, but its modern form crystallized through two parallel lineages: academic column-store research (C-Store, MonetDB) and Google's Bigtable, which popularized the column-family hybrid for web-scale NoSQL systems.

Pure column stores power analytical databases such as Vertica, Amazon Redshift, Snowflake, ClickHouse, and Google BigQuery, all of which scan billions of rows for reporting and business intelligence with only a handful of columns touched per query. Columnar file formats — Apache Parquet and ORC — are the default storage layer for data lakes queried by Spark, Presto/Trino, and Hive, letting engines skip entire column chunks and even entire files via min/max statistics stored in file footers. Column-family stores — Bigtable, HBase, Cassandra — remain the backbone of large-scale operational systems (Google's web index metadata, time-series and IoT telemetry, messaging systems) where sparse, wide, semi-structured records must be written and read efficiently by key, building on the sharding and replication techniques from Data Partitioning and Sharding. In-memory analytical engines (Apache Arrow, DuckDB) go further, keeping columnar batches in cache-friendly vectorized form so that CPU SIMD instructions process thousands of values per instruction — the same locality principle that motivates disk-level column storage, now applied to CPU cache lines. This entire lineage feeds directly into Data Warehousing Foundations and clarifies why the OLAP side of OLAP vs OLTP Workloads is built on fundamentally different physical storage than the OLTP side.

Ask the tutor: How would you decide, for a specific workload, whether to store a table row-oriented, column-family, or pure columnar?