Lecture Notes

These are textbook-style notes created from the slides and audio transcripts using AI tools (mostly Claude Code). They will be added to throughout the semester.

Note

I have not had a chance to carefully review all of these notes, which means there may be errors or hallucinations. They are also not guaranteed to be complete, and may be missing things that were covered in class.

Background for this course is CMSC 424 or an equivalent undergraduate database course; the CMSC 424 lecture notes cover that material in full.

Before You Start

  • Reading, Research, and Writing With AI Available — A note to graduate students, worth reading before the semester begins. Why the case against leaning on AI in a graduate course is different from the undergraduate one, what the evidence says about summaries, sycophancy, persistence, and writing, and specific suggestions for what to use these tools for and what to avoid.

Module 1 — Introduction and Overview

  • Motivation, Definitions, and a Brief History — Why databases remain an active research area, what actually distinguishes one database from another (the user-facing vs. implementation split), and a history of the field from 1960s hierarchical models through the relational paradigm shift, the 2000s shifts to columnar and in-memory processing, the cloud era, and today’s LLM-driven work.
  • Background: A Review of CMSC 424 — What this course assumes: the purpose of database systems, data models and schemas, data abstraction and independence, the relational and E/R models, query languages and relational algebra (including bag vs. set semantics and the join operators), normalization, constraints and triggers, storage and indexing, query processing, parallel architectures, and transactions.
  • Abstractions, Models, and Implementations — A framework for characterizing any data management system: five user-facing questions that define its type (data model, query language, transactions, performance and consistency guarantees) and five implementation questions that should not be visible to users. Includes a field guide to the usual wrong answers — what a graph, columnar, in-memory, NoSQL, vector, time-series, or distributed database “is” — and works through each question in turn, arguing that query plans, MapReduce jobs, ML pipelines, and visualization pipelines are all the same dataflow structure.

Module 4 — Query Processing and Optimization

  • Query Evaluation Techniques — Following Graefe’s 1993 survey: the query processing pipeline, logical vs. physical algebra, how operators pass tuples to each other (materialization, pipelining, and the iterator model), open/next/close, the exchange operator, plan shapes, external sorting and replacement selection, hash join and hybrid hash, and the unsettled sorting-versus-hashing question.
  • Parallel Execution and Skew — Parallel hash join and the shuffle, broadcast joins, parallel sort by range partitioning, which aggregates decompose, the four kinds of skew, and the 1992 skew paper’s techniques — subset-replicate, weighting, and virtual processors — one of which Spark reinvented in 2020.
  • Vectorized Execution — The computer-architecture background the next two chapters depend on: instruction pipelining, branch prediction, superscalar execution, SIMD, and registers. Why the iterator model is close to the worst case for modern hardware, the branch-free selection experiment, where MySQL’s cycles actually go on TPC-H Q1, MonetDB’s BATs and why full materialization made it memory-bandwidth bound, and MonetDB/X100’s synthesis — iterators carrying cache-sized vectors, selection vectors, and templatized primitives.
  • Compilation and Morsel-Driven Parallelism — HIQUE’s generated C++ and why specializing inside operators is not enough, HyPer’s data-centric code generation and the definition of a pipeline breaker, produce/consume as a purely logical interface, LLVM and the cost of compiling per query, the ten-year retrospective (adaptive compilation, 40–90 ms down to 1–2 ms with a hand-written x86-64 backend, one function per pipeline in Umbra), and morsel-driven parallelism on NUMA hardware.