---
title: "Columnar Formats"
book: "Research, Data and Risk Platforms"
subject: quant
language: en
chapter: 3
exercises: 8
source: https://one-course.com/books/quant/15/en/chapter/3-columnar-formats
---

# Chapter 3 — Columnar Formats

A researcher asks for one symbol’s quotes over one hour of one day, from a month of quotes for fifty symbols stored in one file of 19.5 MB. The query reads 17.0 MB of it. The same quotes written in time order, or sorted by symbol and then time, in [row groups](#def-pl-columnar-formats-rowgroup) of 8 192 rows, answer the same query by reading 0.39 or 0.36 MB. Nothing about the data changed, only where its bytes sit and what the file says about them. This chapter explains the two open columnar formats that most of the industry’s research data now passes through — one for memory, one for disk — well enough to predict such numbers, builds a small columnar file format from scratch (`firm.colfile`) to see every byte, and measures what layout a market-data file should have.

## 3.1 Rows against columns

**Definition 3.1 (Row-oriented and columnar layout).**

In a *row-oriented layout* the fields of each record are stored next to each other, record after record. In a *columnar layout* the values of each field are stored next to each other, field after field, so that the $i$-th record is the $i$-th value of every column.

The normalised records of chapter 2 are row-oriented: 56 bytes a message, each message whole. A [columnar layout](#def-pl-columnar-formats-layouts) is the structure of arrays of One Quant Book 13, chapter 14, applied to storage: one array per field. [Figure 3.1](#fig-pl-columnar-formats-layouts) shows the same four quotes both ways.

![The same four quotes in a row-oriented layout (top: each record whole) and a columnar layout (bottom: each field whole). A query that needs one field of every record reads a contiguous run in the columnar layout and every record in the row layout.](https://one-course.com/images/onecourse/chapters/quant-15/pl-columnar-formats/fig-bd9816a1aba0.svg)

***Figure 3.1.** The same four quotes in a [row-oriented layout](#def-pl-columnar-formats-layouts) (top: each record whole) and a [columnar layout](#def-pl-columnar-formats-layouts) (bottom: each field whole). A query that needs one field of every record reads a contiguous run in the [columnar layout](#def-pl-columnar-formats-layouts) and every record in the row layout.*

**Proposition 3.2 (What a scan reads).**

A query that needs $k$ of the $m$ fixed-width fields of every record, of widths $w_1,\dots,w_m$, reads $n\sum_{i=1}^m w_i$ bytes from a [row-oriented layout](#def-pl-columnar-formats-layouts) and $n\sum_{i\in K} w_i$ from a columnar one, where $K$ is the set of fields it needs.

**Proof.** In the row layout the needed fields are interleaved with the others at every record, and storage is read in blocks far larger than a field, so every byte is read. In the [columnar layout](#def-pl-columnar-formats-layouts) the needed columns are contiguous and the others are never touched. ∎

Two more advantages come from the same place. A column holds values of one type and often of one kind — a timestamp that increases, a symbol that repeats, a price that moves by a tick — so it compresses far better than a row of mixed fields (chapter 2 measured it). And an array of one type is what vector instructions (One Quant Book 13, chapter 14) and array programming (chapter 8) want. The price is paid on writes and on reads of whole records: appending one record touches every column, which is why the intraday store of chapter 4 appends rows and the historical store holds columns.

## 3.2 The in-memory columnar standard: buffers, validity, dictionaries

The open in-memory columnar standard (Apache Arrow) fixes how a column sits in memory, so that two libraries, or two processes, can share it without converting it: the zero-copy exchanges of chapters 4 and 9 rely on it. A column (an *array*) is a few contiguous buffers, recommended to be aligned and padded to 64 bytes.

**Definition 3.3 (Validity bitmap).**

The *validity bitmap* of a column is a buffer holding one bit per value, set when the value is present and clear when it is null, numbered from the least significant bit of each byte; a column with no null may omit it.

A fixed-width column is its [validity bitmap](#def-pl-columnar-formats-validity) and one buffer of values. A string column adds an offsets buffer of $n+1$ integers: value $i$ is the bytes between offsets $i$ and $i+1$ of a data buffer. A dictionary-encoded column is an integer column of indices into a separate column of distinct values. [Figure 3.2](#fig-pl-columnar-formats-buffers) lists the buffers of the first 1 000 rows of three columns of the chapter’s quotes.

![Buffers of the first 1 000 rows of three columns of the chapter’s quotes in the in-memory columnar format: an integer column with no null needs no validity bitmap; a nullable string column has a bitmap, n+1 offsets and a data buffer holding only the 49 characters of its 49 present values; a dictionary column holds 4-byte indices into 50 distinct symbols. Data: pl_colfmt.arrow_buffers.](https://one-course.com/images/onecourse/chapters/quant-15/pl-columnar-formats/fig-0c4887241cc3.svg)

***Figure 3.2.** Buffers of the first 1 000 rows of three columns of the chapter’s quotes in the in-memory columnar format: an integer column with no null needs no [validity bitmap](#def-pl-columnar-formats-validity); a nullable string column has a bitmap, $n+1$ offsets and a data buffer holding only the 49 characters of its 49 present values; a dictionary column holds 4-byte indices into 50 distinct symbols. Data: `pl_colfmt.arrow_buffers`.*

Nulls cost one bit each, not a sentinel value and not a byte: the condition code, null on 95% of the rows, costs 125 bytes of bitmap for its 1 000 rows plus the offsets. Market data needs nulls constantly: a quote with no bid, a trade with no condition, a field a venue added last year.

## 3.3 The on-disk columnar standard: row groups, pages, encodings

The open on-disk columnar standard (Apache Parquet) adds what memory does not need: compression, statistics, and the ability to read part of a file. Its layout ([Figure 3.3](#fig-pl-columnar-formats-anatomy)) is three levels deep.

**Definition 3.4 (Row group, column chunk, data page).**

A *row group* is a horizontal slice of a columnar file’s rows, stored as one *column chunk* per column, each contiguous in the file. A column chunk is divided into *data pages*, the unit of encoding and compression. The file’s metadata (its schema, and the position, size, encoding and statistics of every chunk) is written in a footer after the data, so that the file can be written in one pass and read from its end.

![Anatomy of a file in the on-disk columnar format: row groups of column chunks, each chunk a sequence of data pages, and a footer after the data that says where every chunk is and what range of values it holds.](https://one-course.com/images/onecourse/chapters/quant-15/pl-columnar-formats/fig-c326d5153b05.svg)

***Figure 3.3.** Anatomy of a file in the on-disk columnar format: [row groups](#def-pl-columnar-formats-rowgroup) of [column chunks](#def-pl-columnar-formats-rowgroup), each chunk a sequence of [data pages](#def-pl-columnar-formats-rowgroup), and a footer after the data that says where every chunk is and what range of values it holds.*

Inside a page, values are encoded before they are compressed. Four encodings do most of the work on market data, and `firm.colfile` implements the four in numpy ([Listing 3.1](#lst-pl-columnar-formats-encode)).

**Definition 3.5 (Dictionary, run-length, delta encoding; bit packing).**

*Dictionary encoding* stores a column’s distinct values once and each value as an index into them. *Run-length encoding* stores each run of equal consecutive values as the value and the run’s length. *Delta encoding* stores the first value and then each value’s difference from the previous one, usually as the excess over the smallest difference in a block. *Bit packing* stores small non-negative integers in the fewest bits that hold the largest of them, with no byte boundaries between values.

```python
def encode(values: np.ndarray, encoding: str) -> bytes:
    n = len(values)
    if encoding == "plain":
        return _plain(values)
    if encoding == "dict":
        uniq, idx = np.unique(values, return_inverse=True)
        w = _width(idx)
        head = _plain(uniq)
        return struct.pack("<IIB", len(uniq), len(head), w) + head + bitpack(idx, w)
    if encoding == "rle":
        change = np.r_[True, values[1:] != values[:-1]] if n else np.zeros(0, dtype=bool)
        starts = np.flatnonzero(change)
        runs = np.diff(np.r_[starts, n]).astype(np.uint64)
        head = _plain(values[starts])
        w = _width(runs)
        return struct.pack("<IIB", len(starts), len(head), w) + head + bitpack(runs, w)
    if encoding == "delta":
        if values.dtype.kind not in "iu":
            raise ValueError("delta encoding needs integers")
        v = values.astype(np.int64)
        d = np.diff(v) if n > 1 else np.zeros(0, dtype=np.int64)
        out = [struct.pack("<q", int(v[0]) if n else 0)]
        for b in range(0, len(d), BLOCK):     # per block: its minimum delta, then the excess
            blk = d[b:b + BLOCK]
            lo = int(blk.min())
            x = (blk - lo).astype(np.uint64)
            w = _width(x)
            out.append(struct.pack("<qB", lo, w) + bitpack(x, w))
        return b"".join(out)
    raise ValueError(encoding)
```

***Listing 3.1.** The four encodings of `firm.colfile`: plain values, a dictionary with bit-packed indices, runs with bit-packed lengths, and deltas over a per-block minimum, bit-packed at the block’s own width. code/firm/colfile/firm_colfile.py*

**As of September 2026 — The encodings of the open on-disk format.**

The specification of the open on-disk columnar format (consulted September 2026) lists as encodings plain, dictionary (plain or run-length dictionary), a run-length and bit-packing hybrid, three [delta encodings](#def-pl-columnar-formats-encodings) (binary-packed integers, byte-array lengths, and byte-array prefixes), byte-stream split for floating point, and ALP (adaptive lossless floating point). Its [delta encoding](#def-pl-columnar-formats-encodings) bit-packs miniblocks of deltas, each at its own bit width, after subtracting a minimum delta.

[Table 3.1](#tab-pl-columnar-formats-encodings) encodes one day of the chapter’s quotes (50 000 rows) column by column. Each column has a clear winner, and it is not the same one: the date, one value all day, is 13 bytes as a dictionary; the symbol, 50 values repeated, is 37.9 kB as a dictionary in capture order and 480 bytes as runs once the day is sorted by symbol; the timestamp, increasing, halves as deltas; the bid, a few hundred distinct prices, is best as a dictionary; the venue, four values, takes two bits a row.

| column (50 000 rows) | plain | dictionary | run-length | delta | best |
| --- | --- | --- | --- | --- | --- |
| date | 200 000 | 13 | 15 | 449 | dictionary |
| symbol, capture order | 400 008 | 37 917 | 404 432 | – | dictionary |
| symbol, sorted by symbol | 400 008 | 37 917 | 480 | – | run-length |
| timestamp | 400 000 | 500 009 | 406 259 | 201 085 | delta |
| bid | 400 000 | 99 097 | 410 505 | 137 947 | dictionary |
| bid size | 200 000 | 37 705 | 208 072 | 87 948 | dictionary |
| venue | 400 008 | 12 549 | 318 436 | – | dictionary |

***Table 3.1.** Bytes of each column of one day of quotes under each of `firm.colfile`’s encodings, before any compression; strings are stored plain as offsets and bytes, and [delta encoding](#def-pl-columnar-formats-encodings) applies to integers only. Data: `pl_colfmt.encodings_by_column`.*

## 3.4 Statistics and pushdown

The footer’s statistics are what let a reader skip data it has not read.

**Definition 3.6 (Zone map, predicate pushdown, projection pushdown).**

A *zone map* is the minimum and maximum of a column within a unit of storage (a [row group](#def-pl-columnar-formats-rowgroup), a page). *Predicate pushdown* evaluates a query’s filter against zone maps before reading, and skips every unit whose range cannot satisfy it. *Projection pushdown* reads only the columns a query names, in its output or its filter.

**Proposition 3.7 (Pruning by zone maps).**

[Predicate pushdown](#def-pl-columnar-formats-pushdown) never skips a matching row, and it skips a [row group](#def-pl-columnar-formats-rowgroup) exactly when some condition of the filter is false for every value in the group’s range. A filter on a column therefore prunes in proportion to how narrow that column’s ranges are in each [row group](#def-pl-columnar-formats-rowgroup): well on a column the file is sorted by, hardly at all on a column whose values are spread across every group.

**Proof.** A row that matches has, in its [row group](#def-pl-columnar-formats-rowgroup), a value inside the filter’s range for every filtered column, so the group’s $[\min,\max]$ intersects that range and the group is read. Conversely a group is skipped only if some condition fails on its whole range. If a column’s values are sorted, each group’s range is a narrow interval and only the groups overlapping the filter survive; if every group contains nearly all values, every range contains the filter’s. ∎

```python
    def _may_match(self, rg, where) -> bool:
        """Zone-map pruning: False only if a condition can hold for no row of the group."""
        for col, op, val in where:
            lo, hi = rg["chunks"][col]["min"], rg["chunks"][col]["max"]
            if (op == "==" and not lo <= val <= hi) \
                    or (op in ("<", "<=") and not OPS[op](lo, val)) \
                    or (op in (">", ">=") and not OPS[op](hi, val)):
                return False
        return True

    def read(self, columns=None, where=()):
        columns = list(columns or self.footer["schema"])
        need = list(dict.fromkeys(columns + [c for c, _, _ in where]))
        out = {c: [] for c in columns}
        stats = {"row_groups": len(self.footer["row_groups"]), "row_groups_read": 0,
                 "bytes_read": self.footer_bytes, "file_bytes": self.file_bytes}
        with open(self.path, "rb") as f:
            for rg in self.footer["row_groups"]:
                if not self._may_match(rg, where):
                    continue
                stats["row_groups_read"] += 1
                vals = {}
                for c in need:
                    ch = rg["chunks"][c]
                    f.seek(ch["offset"])
                    data = f.read(ch["length"])
                    stats["bytes_read"] += ch["length"]
                    kind = self.footer["schema"][c]
                    vals[c] = decode(data, ch["encoding"], kind, rg["rows"])
                mask = np.ones(rg["rows"], dtype=bool)
                for col, op, val in where:
                    mask &= OPS[op](vals[col], val)
                for c in columns:
                    out[c].append(vals[c][mask])
        dt = self.footer["schema"]
        cols = {c: np.concatenate(out[c]) if out[c] else np.zeros(0, dtype=dt[c])
                for c in columns}
        return cols, stats
```

***Listing 3.2.** Pruning and reading in `firm.colfile`: a row group is skipped when a condition fails on its zone map; the chunks of the needed columns of the others are read, decoded and filtered. code/firm/colfile/firm_colfile.py*

The proposition is the whole of layout design. The chapter’s month of quotes, written three ways into the on-disk format with zstd compression, answers three query shapes through a file object that counts every byte pyarrow reads ([Table 3.2](#tab-pl-columnar-formats-queries)). Shuffled, the file offers no narrow range to any filter, and every query reads most of it: [projection pushdown](#def-pl-columnar-formats-pushdown) alone saves the columns not named. In capture order the timestamp is sorted, so the one-hour queries read 3% of the file; the one-symbol month still reads 28%, the projected columns of every group. Sorted by symbol and then time, the one-symbol queries read 1–3% and the one-hour cross-section 86%.

| query | shuffled | time order | symbol, then time |
| --- | --- | --- | --- |
| one symbol, one hour | 86.0% | 3.30% | 3.30% |
| one symbol, one month | 34.1% | 28.2% | 1.07% |
| all symbols, one hour | 81.7% | 3.13% | 86.1% |

***Table 3.2.** Share of the file read by three queries (projecting bid and ask) from a month of quotes for fifty symbols in the on-disk columnar format, in three row orders, with [row groups](#def-pl-columnar-formats-rowgroup) of 32 768 rows. Counted by a file object wrapped around the file. Data: `pl_colfmt.study`.*

![Bytes read by the one-symbol, one-hour query against the size of the row groups, for the three row orders. Sorted, the curve is U-shaped: large groups make zone maps coarse, small ones lengthen the footer every query reads; its minimum here is at 8 192 rows (0.39 MB in time order, 0.36 MB sorted by symbol). Shuffled, only projection helps. Data: pl_colfmt.study.](https://one-course.com/images/onecourse/chapters/quant-15/pl-columnar-formats/fig-a944d42731a5.svg)

***Figure 3.4.** Bytes read by the one-symbol, one-hour query against the size of the [row groups](#def-pl-columnar-formats-rowgroup), for the three row orders. Sorted, the curve is U-shaped: large groups make [zone maps](#def-pl-columnar-formats-pushdown) coarse, small ones lengthen the footer every query reads; its minimum here is at 8 192 rows (0.39 MB in time order, 0.36 MB sorted by symbol). Shuffled, only projection helps. Data: `pl_colfmt.study`.*

The row-group size is the other dial ([Figure 3.4](#fig-pl-columnar-formats-rowgroups)). Large groups make each [zone map](#def-pl-columnar-formats-pushdown) cover a long stretch of time, so the one-hour query reads 5.5 to 6.0 MB at half a million rows a group. Small groups sharpen the [zone maps](#def-pl-columnar-formats-pushdown) but lengthen the footer that every query reads first, one entry per column per group: at 2 048 rows (489 groups) the time-ordered file’s footer is 444 kB against 115 kB at 8 192 rows, and the query reads 0.57 to 0.64 MB. The minimum is where the two costs balance.

## 3.5 Choosing a layout for market data

No single order serves every query: time order is right for cross-sections of an hour, symbol order for the history of one name, and each is wrong for the other. The industry’s answers combine three tools.

**Method 3.8 (Laying out a market-data file).**

(1) Partition by the coarsest filter every query uses, almost always the date (chapter 2), so that no file mixes days. (2) Inside a partition, sort by the filter that queries use most after the date (the symbol, for research on names), then by time, so that both [zone maps](#def-pl-columnar-formats-pushdown) are narrow. (3) Choose the row-group size from a measurement like [Figure 3.4](#fig-pl-columnar-formats-rowgroups) on real queries, and let the writer pick each column’s encoding. (4) If a second query shape matters as much as the first, keep a second copy in the other order: storage is cheaper than a full scan repeated every day.

**Remark 3.9 (Nested data, and where the design comes from).**

The on-disk format stores nested records (an order with a list of fills) by the record shredding and assembly algorithm published for Google’s Dremel system in 2010; the in-memory format mirrors the same nested types. Flat market-data tables use none of it, but order and trade records from order-management systems often arrive nested.

## 3.6 Tutorial: the same quotes, three layouts

**Goal.** See every buffer of a column in memory and every chunk of a file on disk, then measure what layout and row-group size do to a query. **End state:** Figures [3.2](#fig-pl-columnar-formats-buffers) and [3.4](#fig-pl-columnar-formats-rowgroups) and Tables [3.1](#tab-pl-columnar-formats-encodings) and [3.2](#tab-pl-columnar-formats-queries).

1. **Generate** `pl_colfmt.quotes()` : a million rows, fifty symbols, twenty days, in capture order.
2. **Buffers.** `arrow_buffers()` lists the buffers of an integer, a nullable string and a dictionary column.
3. **Encodings.** `encodings_by_column()` , in capture order and sorted, with `firm.colfile` ’s four encodings ( [Listing 3.1](#lst-pl-columnar-formats-encode) ).
4. **Layouts.** `study()` writes the month in three orders and five row-group sizes and counts the bytes each query reads with `CountingFile` .
5. **Your own file.** Write the month with `firm_colfile.write` , query it with `ColFile.read` ( [Listing 3.2](#lst-pl-columnar-formats-read) ), and compare the answer and the bytes read with pyarrow’s.

**What to change next.** Partition the month by date and sort each day by symbol, then rerun the three queries; add a page-level [zone map](#def-pl-columnar-formats-pushdown) to `firm.colfile` and measure what it saves on large [row groups](#def-pl-columnar-formats-rowgroup).

## 3.7 Build: a columnar file from scratch

**Purpose.** A columnar format small enough to read in full: the reference against which the chapter’s claims about encodings, [zone maps](#def-pl-columnar-formats-pushdown) and pushdown are checked, and the model for the flat formats of chapter 4.

**Interface.** `ENCODINGS`; `bitpack(values, width)`, `bitunpack(data, width, n)`; `encode(values, encoding)`, `decode(data, encoding, dtype, n)`, `best_encoding(values)`; `write(path, columns, row_group_size, encodings)` returning the footer; `ColFile(path).read(columns, where) -> (columns, stats)` with `row_groups`, `row_groups_read`, `bytes_read`, `file_bytes`.

**Rules.** Magic number at both ends and a footer of chunk positions, encodings and [zone maps](#def-pl-columnar-formats-pushdown); a chunk is decoded only if its [row group](#def-pl-columnar-formats-rowgroup) may match; a filter never loses a matching row; the reader’s answer equals a full scan’s.

**Acceptance tests.** `code/firm/colfile/tests/`: [bit packing](#def-pl-columnar-formats-encodings) at widths 0 to 64; every encoding round-trips every column type, and delta refuses non-integers; the obvious encoding chosen for a run, a progression and a small alphabet; a filtered read equal to pyarrow’s, reading one [row group](#def-pl-columnar-formats-rowgroup) of twenty; a projection that reads only its chunks.

**Stretch.** Page-level [zone maps](#def-pl-columnar-formats-pushdown); compression of each chunk after encoding; nullable columns with a [validity bitmap](#def-pl-columnar-formats-validity); dictionary pages shared by the [row groups](#def-pl-columnar-formats-rowgroup) of a column.

Sources and further reading

- Apache Arrow, *Arrow Columnar Format* (specification); Apache Parquet, *File Format* , *Concepts* and *Encodings* (specification).
- D. J. Abadi, S. R. Madden and N. Hachem, “Column-stores vs. row-stores: how different are they really?”, *SIGMOD* , 2008.
- S. Melnik et al., “Dremel: interactive analysis of web-scale datasets”, *Proceedings of the VLDB Endowment* 3(1), 2010.

## 3.8 Exercises

**Exercise 3.1 ★.**

A table has five 8-byte fields and a million rows. How many bytes does a scan of one field read in a row-oriented and in a [columnar layout](#def-pl-columnar-formats-layouts), before compression?

**Solution of Exercise 3.1.**

Row-oriented: every row is read whole, $5 \times 8 \times 10^6 = 40$ MB. Columnar: one column, $8 \times 10^6 = 8$ MB.

**Exercise 3.2 ★.**

A nullable string column of 1 000 rows has 49 present values of one character each. Count the bytes of its [validity bitmap](#def-pl-columnar-formats-validity), its 32-bit offsets and its data.

**Solution of Exercise 3.2.**

Bitmap: 1 000 bits, 125 bytes. Offsets: $1\,001 \times 4 = 4\,004$ bytes. Data: 49 bytes. In all 4 178 bytes; the nulls cost their bit and an offset each, no data.

**Exercise 3.3 ★.**

The venue column takes four values over 50 000 rows. How many bits a value, and how many bytes, does [dictionary encoding](#def-pl-columnar-formats-encodings) with bit-packed indices need, and why does [Table 3.1](#tab-pl-columnar-formats-encodings) show 12 549?

**Solution of Exercise 3.3.**

Four values need 2 bits each: $50\,000 \times 2 / 8 = 12\,500$ bytes of indices. `firm.colfile` adds a 9-byte header (count, dictionary size, bit width) and the dictionary itself stored plain, 40 bytes (a count, five 4-byte offsets and 16 characters): 12 549.

**Exercise 3.4 ★★.**

Why does the timestamp column compress to about 32 bits a value under [delta encoding](#def-pl-columnar-formats-encodings) in capture order, and why worse once the day is sorted by symbol?

**Solution of Exercise 3.4.**

In capture order consecutive quotes of all fifty symbols are about half a second apart, $4.7\times10^8$ ns, so each delta needs about 29 bits and each block’s width is set by its largest delta: 32.2 bits a value measured. Sorted by symbol, consecutive rows are quotes of one symbol, about 23 seconds apart, and each symbol’s run starts with a jump back in time: 44.9 bits a value. [Delta encoding](#def-pl-columnar-formats-encodings) pays for the size of the steps, and sorting by another key makes the time steps larger.

**Exercise 3.5 ★★.**

In time order, why does the one-symbol, one-month query still read 28% of the file, although it returns 2% of the rows?

**Solution of Exercise 3.5.**

Every [row group](#def-pl-columnar-formats-rowgroup) of a time-ordered file holds quotes of all fifty symbols, so its symbol [zone map](#def-pl-columnar-formats-pushdown) is S000 to S049 and no group can be skipped. The reader still applies projection: it reads only the symbol column (to filter) and the bid and ask, 28% of the file, to return 2% of the rows.

**Exercise 3.6 ★★.**

Explain the U shape of [Figure 3.4](#fig-pl-columnar-formats-rowgroups): what grows on each side of the minimum?

**Solution of Exercise 3.6.**

To the right, large groups make each [zone map](#def-pl-columnar-formats-pushdown) cover a long stretch of time, so more of each read group is outside the hour (6.00 MB at 524 288 rows in time order). To the left, the footer, which every query reads before anything else, grows with the number of groups and columns: 444 kB at 2 048 rows against 115 kB at 8 192. The minimum is where coarse [zone maps](#def-pl-columnar-formats-pushdown) stop costing more than metadata.

**Exercise 3.7 ★★★.**

*Coding.* Write the month with `firm_colfile.write` sorted by symbol and then time, in [row groups](#def-pl-columnar-formats-rowgroup) of 8 192 rows, and read the one-symbol, one-hour query with `ColFile.read`. How many of the [row groups](#def-pl-columnar-formats-rowgroup) does it read, and does the answer equal pyarrow’s?

**Solution of Exercise 3.7.**

The file has 123 [row groups](#def-pl-columnar-formats-rowgroup); the [zone maps](#def-pl-columnar-formats-pushdown) on the symbol and the timestamp leave two that may match, and the reader decodes only those two groups’ chunks of the four columns. It returns 153 rows, equal to pyarrow’s answer on the same data.

**Exercise 3.8 ★★★.**

*Find the flaw.* “Our quotes file is sorted by time and has statistics on every column, so any filter is pushed down and a query for one symbol reads only that symbol’s data.”

**Solution of Exercise 3.8.**

Statistics on a column prune only if its values are narrow within each [row group](#def-pl-columnar-formats-rowgroup). In a time-sorted file every group contains every symbol, so the symbol’s [zone maps](#def-pl-columnar-formats-pushdown) cover everything and a one-symbol query reads the projected columns of every group (28% of the chapter’s file for a query returning 2% of the rows). Sort by symbol inside each date partition, or keep a second copy.

## 3.9 Problem: Most of the File for One Hour

**Problem 3.1.**

Weekend problem — laying out a month of quotes

The chapter’s month of quotes (fifty symbols, twenty days, a million rows), its three row orders and five row-group sizes.

**Part I — Rows and columns.**

1. What share of a row-oriented table of nine fields does a query on two fields read, if all fields have equal width?
2. Which buffers does a nullable string column have in the in-memory format?
3. Why does a null cost one bit?
4. Which encoding wins for the date, the symbol in capture order, the timestamp and the bid?
5. Why does sorting by symbol make [run-length encoding](#def-pl-columnar-formats-encodings) of the symbol shrink from 404 432 to 480 bytes?

**Part II — Pushdown.**

6. What does a [zone map](#def-pl-columnar-formats-pushdown) hold, and when does it let a reader skip a [row group](#def-pl-columnar-formats-rowgroup) ?
7. Can [predicate pushdown](#def-pl-columnar-formats-pushdown) return a wrong answer? Why not?
8. In the shuffled file, what share does the one-symbol, one-hour query read, and what saves it anything at all?
9. In time order, what share do the two one-hour queries read at 32 768 rows a group?
10. Sorted by symbol, what share does the all-symbols hour read, and why?

**Part III — [Row groups](#def-pl-columnar-formats-rowgroup).**

11. How many megabytes does the one-symbol, one-hour query read at 524 288 rows a group in time order?
12. And at 8 192?
13. Why is the query more expensive again at 2 048 rows?
14. How much larger is the time-ordered file’s footer at 2 048 rows than at 8 192?
15. Which row-group size would you choose, and on what evidence?

**Part IV — The verdict.**

16. State the *named result* : the share of the file read by the one-symbol, one-hour query in each order, and the best row-group size.
17. Which order serves which query shape, and which serves neither?
18. What layout do you give a month of quotes that serves both one-symbol and one-hour queries?
19. What would you have to measure before trusting these numbers on real data?
20. In one sentence: what decides how many bytes a query reads from a columnar file?

**Solution of Problem 3.1.**

1. All of it, since every row is read whole; a [columnar layout](#def-pl-columnar-formats-layouts) would read $2/9 = 22\%$ .
2. A [validity bitmap](#def-pl-columnar-formats-validity) , an offsets buffer of $n+1$ integers and a data buffer.
3. It is one bit of the [validity bitmap](#def-pl-columnar-formats-validity) ; the value itself takes no space in the data buffer.
4. Dictionary (13 bytes), dictionary (37 917), delta (201 085), dictionary (99 097).
5. Sorted, the day’s 50 000 symbols are 50 runs, stored as 50 values and 50 lengths.
6. The minimum and maximum of a column in the group; it allows the reader to skip the group when some condition of the filter is false for every value in that range.
7. No: a matching row lies inside its group’s range for every filtered column, so its group is never skipped.
8. 86.0% at 32 768 rows a group; only projection saves anything, by leaving out the columns the query does not name.
9. 3.30% for one symbol and 3.13% for all symbols.
10. 86.1%: each group holds a few symbols over the whole month, so every group’s time range contains the hour.
11. 6.00 MB.
12. 0.39 MB.
13. The footer, read first, lists every chunk of 489 groups.
14. 3.9 times (444 against 115 kB).
15. 8 192 on this data, from the measurement; on real data the same measurement with the real query mix.
16. **Named result.** With 8 192-row groups, the one-symbol, one-hour query reads 87.2% of the shuffled file (17.0 of 19.5 MB), 2.65% in time order (0.39 MB) and 2.79% sorted by symbol then time (0.36 MB); smaller and larger groups both cost more (0.64 MB at 2 048 rows, 6.00 MB at 524 288 in time order).
17. Time order serves the one-hour queries, symbol order the one-symbol queries; a shuffled file serves neither.
18. Partition by date, sort each day by symbol then time, choose the row-group size by measurement; keep a time-ordered copy if cross-sections matter as much.
19. The real query mix, the real distribution of symbols and quote rates (a few symbols dominate), and the bytes read, not the wall time alone.
20. How narrow the [zone maps](#def-pl-columnar-formats-pushdown) of its filter columns are in the file’s order, and how many columns it projects.

## 3.10 Interview questions

**Interview question 3.1 ★ developer, researcher.**

Why are columnar formats used for market data research, and when is a row format better?

**Solution of Interview question 3.1.**

Research reads a few fields of many records, and columns of one type compress well and vectorise; a columnar file reads only the fields and [row groups](#def-pl-columnar-formats-rowgroup) needed. A row format is better for writing records as they arrive and for reading whole records one at a time: the intraday capture, the order state of one order.

*What the interviewer is looking for: Reads of few fields over many rows; appends and point reads favour rows.*

**Interview question 3.2 ★★ developer.**

What is [predicate pushdown](#def-pl-columnar-formats-pushdown), and what does the layout of the file have to do with it?

**Solution of Interview question 3.2.**

Evaluating the filter against each [row group](#def-pl-columnar-formats-rowgroup)’s (or page’s) minimum and maximum before reading, and skipping those that cannot match. It only helps if the file is sorted (or partitioned) so that the filtered columns have narrow ranges per group.

*What the interviewer is looking for: [Zone maps](#def-pl-columnar-formats-pushdown); sort order decides.*

**Interview question 3.3 ★★ developer.**

Which encodings would you expect for a timestamp, a symbol and a price column, and why?

**Solution of Interview question 3.3.**

Timestamp: [delta encoding](#def-pl-columnar-formats-encodings), since it increases in small steps. Symbol: dictionary (few distinct values), or run-length once sorted by symbol. Price: dictionary if few distinct prices in a chunk, otherwise deltas, since prices move by ticks.

*What the interviewer is looking for: Encoding matched to the column’s structure, and dependence on sort order.*

**Interview question 3.4 ★★ developer.**

How are nulls represented in the in-memory columnar standard, and what does a null cost?

**Solution of Interview question 3.4.**

A [validity bitmap](#def-pl-columnar-formats-validity) with one bit a value, set when present; a column without nulls may omit it. A null costs one bit (and, for variable-width columns, an offset), never a sentinel.

*What the interviewer is looking for: Bitmap, not sentinel; bit order LSB-first as a detail.*

**Interview question 3.5 ★★★ developer, researcher.**

Research queries on your quotes store are slow. How do you find out whether the layout is the problem, and what do you change?

**Solution of Interview question 3.5.**

Measure bytes read, [row groups](#def-pl-columnar-formats-rowgroup) read and columns read per query (a counting file, the reader’s statistics), against rows returned. If the reads are far above the result, check the sort order against the filters, the row-group size, and whether statistics are written. Then change the layout (partition by date, sort by the main filter, tune the group size) and re-measure.

*What the interviewer is looking for: Bytes read against rows returned, then layout, measured again.*

**Interview question 3.6 ★★★ developer.**

Design the file layout for five years of US equity trades that researchers query by symbol over long periods and by time across all symbols.

**Solution of Interview question 3.6.**

Partition by date; within each day sort by symbol then time, with [row groups](#def-pl-columnar-formats-rowgroup) sized by measurement (thousands of rows) and statistics on symbol and time; dictionary-encode symbols and conditions, delta-encode timestamps. Long single-symbol histories read one small range per day; cross-sections of a time window read the day’s partition, projected. If cross-sections are frequent and large, add a time-sorted copy.

*What the interviewer is looking for: [Partitioning](https://one-course.com/books/quant/15/en/chapter/2-capturing-and-storing-tick-data#def-pl-capturing-and-storing-tick-data-partition) plus sort order plus the admission that one order cannot serve both.*