Cover

CMU Database Group · 1:28:00 · https://www.youtube.com/watch?v=nhlpwmOBEiE

Summary

The final lecture of CMU 15-445/645's storage-layer sequence, contrasting how a DBMS can physically lay out tuples and what that costs. Andy Pavlo first separates OLTP from OLAP workloads, then walks the same Wikipedia-derived query through the N-ary Storage Model (row store), the Decomposition Storage Model (column store), and the PAX hybrid used by Parquet, ORC and Arrow — showing why analytical scans waste most of their I/O in a row store. The second half covers compression: why block-level compression with Snappy/Zstd is an opaque box the engine cannot reason about, and how DBMS-owned columnar schemes (RLE, bit packing with patching, bitmap, delta, and above all dictionary encoding) let queries run directly on compressed data. The lecture closes with a guest talk from Sean of StarTree on Apache Pinot, a real-time OLAP system serving user-facing analytics at ~10,000 QPS with sub-100 ms p99 latency.

Classification: university lecture (educational) + an appended industry conference talk.

flowchart TD
    W["Workloads: OLTP / OLAP / HTAP"] --> S["Storage models"]
    S --> NSM["NSM — row store<br/>fast writes, wasteful analytical I/O"]
    S --> DSM["DSM — column store<br/>minimal I/O, slow writes"]
    S --> PAX["PAX — hybrid<br/>row groups + column chunks"]
    PAX --> C["Compression"]
    DSM --> C
    C --> BLK["Block level<br/>(opaque, poor ratio)"]
    C --> COL["Column level<br/>(DBMS-owned, query on compressed data)"]
    COL --> P["Apache Pinot / StarTree<br/>real-time OLAP in production"]
    PAX --> P

Topics

  1. Lecture scope and logistics — where this lecture sits in the storage sequence, and the agenda (0:27)
  2. Database workloads: OLTP, OLAP, HTAP — the quadrant chart and the origin of the term "OLAP" (4:44)
  3. Running example: the Wikipedia schema — the tables and the two query shapes used throughout (10:56)
  4. N-ary Storage Model (row store) — layout, query walkthroughs, and the useless-I/O problem (15:10)
  5. Decomposition Storage Model (column store) — offsets, variable-length data, write penalty, mitigations (22:12)
  6. PAX: the hybrid storage model — row groups, column chunks, Parquet/ORC footers and sizes (36:14)
  7. Why compress, and at what granularity — the three goals and the four granularity levels (40:52)
  8. Naive block-level compression — MySQL's compressed pages and mod log, and why it falls short (47:28)
  9. Columnar compression schemes — RLE, bit packing, patching, bitmap, delta, dictionary (55:28)
  10. Guest talk: Apache Pinot / StarTree — real-time OLAP, architecture, and the star-tree index (1:12:17)

Key takeaways

  • On the lecture's 6-page toy database, the same analytical query read all 6 pages as a row store but only 2 pages as a column store — and at cloud scale that is also a direct bill reduction, since S3 charges per lookup (26:02, 26:23).
  • Column stores identify tuples by fixed-length offsets, not embedded tuple IDs; variable-length types are forced fixed-length via dictionary encoding first (27:51, 29:45).
  • Nearly every production "column store" — Parquet, ORC, Arrow — is really PAX: 128 MB row groups in Parquet, a fixed 1 million tuples per row group in ORC, ~1 MB pages, metadata in the footer because the files are immutable (37:17, 38:03, 39:09).
  • Off-the-shelf block compression (Snappy, Zstd, LZ4) is rejected for analytics on three grounds: it breaks fixed-length offsets, it blocks late materialization, and the compressed bytes are an opaque box the engine cannot interpret (43:03, 52:41, 53:33).
  • Bitmap encoding is only viable at low cardinality: 10 million zip codes cost 40 MB raw but 53 GB as 43,000 uncompressed bitmaps — hence roaring bitmaps in real systems, including Pinot (1:03:17, 1:04:27).
  • Sorting is the multiplier for RLE: an unsorted 8-tuple boolean column produced triplets larger than the original data, while sorting collapsed it to 2 triplets (57:59, 58:20).
  • Order-preserving dictionary encoding is the most important scheme: LIKE 'And%' rewrites into BETWEEN 10 AND 20, so a billion-tuple table with ~100 codes is answered from the dictionary without reading the column at all (1:08:01, 1:08:49).
  • Contorting a row store into a column store is a documented failure mode: Microsoft paid ~$200 million for DATAllegro and discarded the code within three months (28:51, 1:10:57).
  • Apache Pinot's star-tree index turns the materialized-view choice into a tunable latency/storage curve; LinkedIn's "who viewed my profile" went from ~1,000 machines serving 1,000 QPS on a key-value materialized view to 5,000 QPS on ~75 machines (1:23:18, 1:24:39).
  • Pinot's production envelope for user-facing analytics: ~10,000 QPS at p99 < 100 ms, fresh enough to query live while a profile page loads (1:14:11, 1:14:29).