Row stores, column stores and compression

Row stores keep all the values of a row together, so one page read returns whole rows; column stores keep all the values of a column together, so a query reads only the columns it needs. Transactional work touches a few rows and most of their columns, which suits row stores. Analytical queries scan millions of rows but only a few of their columns, which suits column stores, and a column of similar values also takes compression far better than a row of mixed ones. Between the two sits PAX, which keeps rows on the same page but groups each page’s values by column. This lesson measures what each layout reads, names the encodings that compress a column, and shows how Parquet files lay out columns for analytics.

Three layouts of one table

The N-ary storage model (NSM) is the slotted page of the earlier lesson: each record holds every column of its row, one record after another. Ailamaki and colleagues, who proposed PAX in 2001, note that relational systems had long organised records this way, and that most queries use only a fraction of each record.

The decomposition storage model (DSM) splits a table into one sub-relation per column. The n-th value of each column file belongs to the n-th row, so a query that needs two columns reads two files, and a query that needs a whole row has to collect it from every file.

PAX (partition attributes across) stores the same rows on each page as NSM would, but inside the page it groups the values of each column into a minipage. Pages and I/O are unchanged; what improves is what reaches the processor’s cache, because a scan of one column now reads consecutive values of that column.

Which workload each layout serves

The program prices three requests against a table of 10 million rows and 20 columns of 8 bytes each, stored as rows and as columns:

"""What a row layout and a column layout read for three typical requests.

A sales table of 10 million rows and 20 columns of 8 bytes each, stored in 8 KB
pages. A row store keeps each row's 160 bytes together (NSM); a column store keeps
each column's values together (DSM), one file per column. Page headers, slots and
compression are left out, so the numbers show the layouts alone.
"""
from math import ceil

ROWS, COLUMNS, WIDTH, PAGE = 10_000_000, 20, 8, 8192
rows_per_page = PAGE // (COLUMNS * WIDTH)          # whole rows per row-store page
values_per_page = PAGE // WIDTH                    # values per column-store page
row_pages = ceil(ROWS / rows_per_page)
column_pages = ceil(ROWS / values_per_page)        # pages of one column

requests = [
    ("sum(amount) by region over all rows", row_pages, 2 * column_pages),
    ("read one order by its key", 1, COLUMNS),
    ("insert one order", 1, COLUMNS),
]
print(f"{ROWS:,} rows x {COLUMNS} columns: row store {row_pages:,} pages ({rows_per_page} rows each), "
      f"column store {column_pages:,} pages per column")
print(f"{'request':<38}{'row store':>12}{'column store':>15}   pages touched")
for name, row_store, column_store in requests:
    print(f"{name:<38}{row_store:>12,}{column_store:>15,}")
gb = lambda pages: pages * PAGE / 10**9
print(f"bytes read by the aggregate: {gb(row_pages):.2f} GB against {gb(2 * column_pages):.2f} GB")

10,000,000 rows x 20 columns: row store 196,079 pages (51 rows each), column store 9,766 pages per column
request                                  row store   column store   pages touched
sum(amount) by region over all rows        196,079         19,532
read one order by its key                        1             20
insert one order                                 1             20
bytes read by the aggregate: 1.61 GB against 0.16 GB

The aggregate reads 196,079 pages from the row store and 19,532 from the column store, 1.61 GB against 0.16 GB, because it needs only 2 of the 20 columns. The other two requests go the opposite way: reading or inserting one order touches one page of the row store and one page of each of the 20 column files. That is the whole trade-off, before compression changes the numbers again in favour of columns.

Compression, column by column

A column holds values of one type, and often only a few distinct ones, so it compresses far better than a row that mixes a name, a date and a price. The encodings that column stores and columnar files use most:

• Dictionary encoding replaces each value with a small integer code and stores each distinct value once.
• Run-length encoding stores a run of equal neighbouring values as the value and the length of the run.
• Bit-packing stores each integer in exactly as many bits as the largest value needs, instead of 32 or 64.
• Delta encoding stores the difference between neighbouring values, which is small when the column is sorted.
• Frame of reference stores each value minus the column’s minimum, so a narrow range needs few bits.

For example, the city column of the diagram, Pune, Kochi, Pune, Indore, has three distinct values: as a dictionary it becomes the codes 2, 1, 2, 0 of 2 bits each, one byte for all four rows, plus the three names once. Sort order decides how much each encoding saves, and the encodings can be combined: dictionary codes are themselves bit-packed or run-length encoded.

Files built for columns: Parquet

Parquet is a file format built on these ideas. Its documentation describes the hierarchy: a file holds one or more row groups; a row group, a horizontal slice of the rows, holds exactly one column chunk per column; and column chunks are divided into pages, the unit of encoding and compression. The metadata is written at the end of the file, after the data, and a reader reads it first to find the column chunks it needs. DuckDB, an analytical engine that needs no server and runs inside the process that uses it, reads and writes Parquet; its documentation says that it reads only the columns a query needs and can use the stored minimum and maximum values to skip parts of a file.

Encodings worked byte by byte, with sizes you can check Pro: opens with a Pro, Premium or Ultimate pass

Row groups, statistics and late materialisation, measured Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Row stores keep rows together and suit transactions; column stores keep columns together and suit analytics that read few columns of many rows; PAX groups a page’s values by column without changing the page.
• Dictionary, run-length, bit-packing, delta and frame-of-reference encodings shrink a column, and sort order decides which one works.
• Parquet files hold row groups of column chunks of pages, with the metadata at the end of the file.