Why analytics favors columnar storage

Suppose you want the total price of all black products in a catalog. A straightforward plan is to visit the products one row at a time: compare each color with Black, and add the price when it matches.

SELECT SUM(price) AS total
FROM products
WHERE color = 'Black';

I used this small product table in my 2024 talk on columnar data processing. We can work through the entire query by hand:

Assume a full-table scan with no useful index. For these six non-null rows, the calculation looks like this:

total = 0
 
for row in products:
    if row.color == "Black":
        total = total + row.price

The loop makes six color comparisons and updates the total three times: 2000 + 1200 + 120 = 3320. The sample prices are integers in one consistent unit, and colors use exact, case-sensitive comparison. Example data.

The end of the batch section covers SQL's null and empty-result rules.

For six rows, this is easy. An analytical query might visit millions of records to produce a single total or a few grouped results. That broad-scan pattern is common in online analytical processing, or OLAP. The cost of getting values to the calculation can matter as much as the calculation itself.

The SQL asks for two fields, but a row-oriented scan encounters records containing four. The comparisons do not need the names or IDs, even when their bytes arrive on the same storage pages or cache lines. Can we arrange the data so less unrelated material travels along?

That question leads to columnar storage. We will keep the query and its answer fixed, then change which data gets read, how it is represented, and how it moves through the engine.

From row scans to column scans

A row-oriented layout places fields from the same record near each other. That is useful when a lookup needs most of one record: the product's name, color, and price arrive together.

In a column-oriented layout, values from one column occupy their own storage regions. A reader can request the two relevant columns without reading the payload of the other two. This is column pruning, also called projection pushdown. Metadata still has to be read, and physical I/O can include padding or read-ahead; the important separation is between required and unrelated column data. 1, 2

Within a shared row range, position preserves the relationship between columns. The third color and third price still belong to the same product. Filtering color can therefore produce a mask or a list of positions, leaving the color and price arrays in place.

The benefit depends on the access path. A row-store with a covering index on the needed fields may also avoid the base table. A query that needs nearly every column has much less projection work to eliminate. Comparing "rows versus columns" without specifying the query and its available indexes misses the reason for choosing either layout.

Encode the patterns within a column

Our color column repeats three strings across six rows. A numeric column may have many values packed into a narrow range. Those patterns give a storage engine opportunities to use fewer bits for the values a query needs. The payoff can be less disk or memory traffic; decoding has a cost too, so the smallest representation is not necessarily the fastest to read. 1

Dictionary encoding

There are three distinct colors in the example. A dictionary can assign them compact identifiers:

dictionary: 0 -> Black, 1 -> Blue, 2 -> Red
identifiers: [0, 1, 0, 0, 1, 2]

Three identifiers fit in 2 bits each. The six identifiers therefore need 12 bits of ideal packed payload, before the dictionary itself, lengths, headers, and padding.

For the equality predicate, an implementation that supports execution on encoded data can resolve Black to identifier 0 and compare identifiers. It need not repeatedly compare the same string bytes. A dictionary identifier is local to its dictionary, however. Another chunk could assign 0 -> Red, 1 -> Black, 2 -> Blue: a valid dictionary whose identifier order is different from string order. Equality uses that dictionary's mapping; a range predicate cannot assume the codes are sort keys. 1

Parquet stores a dictionary page per dictionary-encoded column chunk (one column's values for a range of rows) and encodes references to it in data pages. A writer can fall back to plain encoding if the dictionary grows too large. Consequently, an optimization based on the dictionary must account for whether the relevant data pages actually use it. 3

Frame-of-reference encoding

The magnitude of a number is sometimes less important than its distance from nearby numbers. Consider another example from the talk:

An unsigned representation of the original values needs 15 bits per value: 30000 fits below 2^15, but not below 2^14. The largest offset is 2000, which fits in 11 bits because 2000 < 2^11. The 12-bit label in my slides was one bit too wide.

The ideal packed payload changes from 6 * 15 = 90 bits to 6 * 11 = 66 bits. The decoder must also know the base, 28000, and the bit width. For six values, metadata and byte padding can erase the payload saving.

This is a simple frame of reference: store a base and offsets, then recover each value with base + offset. It is not the exact Parquet DELTA_BINARY_PACKED byte stream. That encoding first takes differences between consecutive values and packs adjusted deltas in blocks. A block is split into miniblocks, small groups whose values all use the same bit width. 1, 3

The distinction matters for these very numbers. Consecutive differences are 500, 400, 850, 250, -1250. Subtracting the minimum delta, -1250, gives 1750, 1650, 2100, 1500, 0. Encoding these six values together puts the five deltas in one partial miniblock; its largest adjusted value, 2100, needs 12 bits.

The final backward step widened the range. Real files add headers and padding on top of that. The encoding choice depends on the pattern in the data, not just the magnitude of the original numbers. 3

Runs and row order

Dictionary encoding benefits from few distinct values. Run-length encoding benefits from adjacent repetitions.

The original identifier sequence contains five runs:

[0, 1, 0, 0, 1, 2]
 
(value, count):
(0, 1), (1, 1), (0, 2), (1, 1), (2, 1)

If the rows are clustered by color, the same six identifiers become three runs:

[0, 0, 0, 1, 1, 2]
 
(0, 3), (1, 2), (2, 1)

The pairs show the runs conceptually. Real formats have headers and may combine runs with bit-packing. A column with few distinct values can still have short runs if those values alternate.

The other columns must follow the same row permutation. After clustering, the product IDs are 1, 3, 4, 2, 5, 6, and the prices move with them. Sorting only the color array would attach colors to the wrong products. The query result remains 3320.

On disk, in memory, inside the engine

Before skipping parts of a file, we need to distinguish its layout from the memory representation and the engine using it. Parquet, Arrow, and VertiPaq illustrate those three roles.

Parquet defines the persistent file. Rows are divided into row groups; within each group, each column has a column chunk, divided into pages. Metadata near the file's end tells a reader where the chunks are, so it can locate the needed columns. 2

Arrow defines in-memory columnar layouts, including value buffers and validity information. A reader can turn Parquet data into Arrow arrays or use its engine's own representation. Arrow does not choose the SQL execution plan. 6

VertiPaq is a storage-engine implementation used by Power BI Import models. Microsoft's guidance describes value encoding for numeric data and hash encoding for text: assigning an identifier to each distinct value, as in our color dictionary. 7

There is a further distinction inside the file: encoding versus compression. Parquet pages may contain dictionary IDs or another encoding, then be compressed with a codec such as Snappy or Zstandard. The reader first decompresses the needed payload. A compatible operator can then compare IDs or consume runs without reconstructing every original value. 3, 8

Reject groups that cannot match

Clustering by color gave us longer runs. It can also help the reader reject entire regions of storage. Column pruning asks which fields are needed; predicate pruning asks which regions could contain a qualifying row.

For an equality predicate and trustworthy minimum/maximum bounds, a group can be excluded when the target is outside its range:

target < min -> skip
target > max -> skip
otherwise    -> candidate

For this example, use bytewise ordering of the exact ASCII labels: Black < Blue < Red. Divide the six products into two illustrative row groups of three rows each.

In arrival order, the first group contains Black, Blue, Black; the second contains Black, Blue, Red. Both ranges include Black, so neither group can be excluded by these bounds.

After clustering all columns together by color, the first group contains only Black, while the second contains Blue, Blue, Red. The second group's minimum is now Blue. It cannot contain Black, so its column data can be skipped for this query.

An overlapping range usually establishes only that a match is possible. The arrival-order group spanning Black to Red does not, for example, contain every string between those bounds. A candidate still needs row-level evaluation unless stronger information justifies a shortcut.

Try color = 'Brown'. Using only min/max bounds, the first arrival-order group can be excluded, but the second remains a candidate. Neither contains Brown, so the aggregate returns NULL. Metadata can retain a region that ultimately contributes nothing.

Parquet carries column-chunk statistics in metadata and can also provide an optional page index. A ColumnIndex supplies per-page bounds, while an OffsetIndex helps map qualifying row ranges to pages in other columns. A reader must support and choose to use these structures; their existence in the format is not a guarantee that a particular query will skip pages. 4

The bounds must be safe for the predicate's semantics. Missing or unusable min/max values cannot justify this range test. Other metadata may still help: a trustworthy all-null indicator excludes a page for equality to a non-null literal. Bytewise string bounds cannot simply be reused for a different collation without establishing that the comparison is sound. Parquet page-index bounds may also be conservative, truncated values rather than values actually present in the page. Wider safe bounds reduce pruning power, but must not exclude a possible match. 4

Clustering has costs of its own. Sorting and maintaining a useful order take work, and an order that helps one predicate may help another much less. This is a physical-design decision tied to the workload, not an instruction to sort every table by its lowest-cardinality column.

Three matches can still touch every page

Return to the original row order and the selected positions 1, 3, 4.

For this illustration, put all six rows in one row group whose price chunk has two pages: positions 1-3 in the first, and 4-6 in the second. Both pages contain a needed price. The reader may have to fetch and decompress both pages even though only three prices contribute to the aggregate.

This is why "read only matching rows" needs a precise meaning. It may mean avoiding row reconstruction, avoiding expression evaluation, avoiding some value decoding, or avoiding physical I/O. Those are different savings.

A reader can evaluate color first, then use the price column's OffsetIndex to find pages covering the selected positions. An entirely unneeded price page could then be skipped. When every page is needed, the selection still saves work later in the pipeline. Page boundaries need not align across columns, so readers must relate row positions to each column's own layout. 4

Give the CPU a batch of work

The query still has the same jobs: check colors and add the matching prices. Now let the engine do those jobs for a small group of rows at a time. That group is a batch.

Keep the original row order and use two-row batches for illustration. Matches lists original row positions passed on by the filter; each batch contributes to the same running total:

The last batch has no matches, so it leaves the total alone. Notice that rows 3 and 4 share a batch but occupied different price pages in Figure 4. A batch is an execution choice; it does not have to follow the file's page boundaries.

Less setup per value

The opening loop showed the logical calculation. To see the setup saving, imagine a row-at-a-time operator pipeline that calls the filter once per row: six calls. With two-row batches, it calls the filter three times, while still checking six colors.

This batch-at-a-time style is called vectorized execution. Each filtering call handles its group in a tight loop, sharing the per-call setup across values. MonetDB/X100 is an influential example. 5

The group has to be sized sensibly. Too few values and the engine keeps paying setup costs. Too many and temporary arrays, including matching-position lists, may outgrow the smaller, faster CPU caches. Moving those intermediates through main memory can then become the bottleneck. Batches balance those costs; processing an entire column at once can lose the benefit. 5

Some loops also use SIMD, where one CPU instruction operates on several values. Batching can reduce overhead even when that hardware technique is not used. 1, 5, 6

Carry the matches forward

The first batch's position 1 identifies price 2000; positions 3 and 4 in the second identify 1200 and 120. The sum can read these entries from the existing price arrays. Passing a mask or selected positions avoids copying the qualifying values into a new array, a technique used by X100. 5

Delaying the assembly of row-shaped records from the required columns is called late materialization. Our sum never needs to assemble color/price pairs. But when many columns are needed and few rows are filtered out, tracking positions and collecting values can cost more than assembling those records earlier. 1

SQL's rules still apply across the batches: null colors do not satisfy this predicate, and SUM ignores null prices. If no qualifying non-null price appears anywhere, the result is NULL. A batch with no matches does not reset an existing total, and the running total must use the aggregate's numeric type and overflow rules.

Where the trade-off changes

For a scan over many rows and a few columns, the opportunities reinforce one another: pruning avoids unrelated payload, encoding shrinks what remains, metadata excludes regions, and batched execution limits overhead and temporary objects.

Other access patterns change that balance:

Column-oriented databases can support writes through additional structures and maintenance strategies. 1 Parquet alone supplies neither transaction management nor concurrency control; those responsibilities belong to the systems using the files. A workload comparison has to account for that surrounding machinery. 2

For a wider map of storage designs and access patterns, see Designing Data-Intensive Applications, first edition, chapter 3, "Storage and Retrieval." 9 Its author-maintained bibliography also leads to the column-store survey and X100 paper used here.

What I would measure

For a slow columnar query, I would first separate four questions:

1. Which column payloads were actually read?
2. Which row groups and pages were rejected, and how many compressed bytes were fetched?
3. How much time went into decompression, decoding, and the query operators?
4. Which intermediate values were materialized or copied?

Then I would compare the same query and data under stated conditions: cache state, data order, group/page sizes, codecs, reader version, and available indexes. A smaller file and a faster query can have different explanations. A result obtained by changing all those variables at once cannot tell us which mechanism supplied the gain.

The six-row example does not predict a speedup. It gives us a way to account for work: two required columns, three qualifying positions, different opportunities to skip groups, and possibly two price pages to read. That accounting is what I want before trusting a claim that a columnar system is fast.

References

1. Daniel Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreos, and Samuel Madden, The Design and Implementation of Modern Column-Oriented Database Systems, especially sections 2.3, 4.1-4.4, and 4.7.
2. Apache Parquet, File Format.
3. Apache Parquet, Encodings.
4. Apache Parquet, Page Index.
5. Peter Boncz, Marcin Zukowski, and Niels Nes, MonetDB/X100: Hyper-Pipelining Query Execution, CIDR 2005, especially sections 3.2 and 4.
6. Apache Arrow, Arrow Columnar Format.
7. Microsoft, Data reduction techniques for Import modeling, especially "Optimize column data types."
8. Apache Parquet, Compression.
9. Martin Kleppmann, Designing Data-Intensive Applications, first edition, chapter 3, "Storage and Retrieval"; author-maintained chapter references.