Cover

CMU Database Group · 1:23:43 · Watch on YouTube

Summary

Lecture 7 of CMU 15-445/645 (Fall 2024) opens the access methods stretch of the course: with disk management and the buffer pool already built, Andy Pavlo turns to the data structures the execution engine will use, starting with the unordered one — the hash table. The lecture decomposes a hash table into two independent design decisions, the hash function (pick XXHash, don't write your own) and the hashing scheme (how collisions are resolved), then walks through five schemes in increasing sophistication: linear probe and cuckoo hashing for static tables, and chained, extendible and linear hashing for dynamic ones — each with its worked example, failure mode, and real-system sightings (ClickHouse, PostgreSQL, IBM DB2 BLU, Berkeley DB). It closes by explaining why, despite O(1) lookups, CREATE INDEX almost never gives you a hash table, and hands the last ten minutes to Nico from RelationalAI, who argues for data-centric architectures where the system derives implications from inputs by reasoning, and shows how query classes from database theory keep their optimizer tractable.

flowchart TD
    A["Hash table = 2 design decisions"] --> B["Hash function<br/>speed vs. collision rate"]
    A --> C["Hashing scheme<br/>storage vs. compute"]
    C --> D["Static — fixed size"]
    C --> E["Dynamic — grows incrementally"]
    D --> D1["Linear probe hashing"]
    D --> D2["Cuckoo hashing"]
    E --> E1["Chained hashing"]
    E --> E2["Extendible hashing"]
    E --> E3["Linear hashing"]
    A --> F["Verdict: B+ Tree wins for indexes"]

Topics

  1. Course logistics and roadmap — administrivia, and where access methods sit in the bottom-up build of the system.
  2. Hash table fundamentals and design goals — where DBMSs use data structures, complexity, and why the naive giant array fails.
  3. Hash functions — speed over cryptography, XXHash, and the SMHasher benchmark.
  4. Linear probe hashing — probing, load factors, tombstones, non-unique keys, and ClickHouse optimizations.
  5. Cuckoo hashing — multiple hash functions, eviction, and trading insert cost for O(1) lookups.
  6. Chained hashing — bucket chains, Bloom filters in front, and the skew problem.
  7. Extendible hashing — global/local depth bits and localized bucket splits.
  8. Linear hashing — the split pointer, two hash functions, and PostgreSQL's dynahash.
  9. Wrap-up: hash indexes in practice — no range queries, no partial keys, plus a comparison table of all five schemes.
  10. Guest talk: RelationalAI — the tarpit of software complexity, data-centric architecture, and query classes.

Key takeaways

  • A hash table is not one design but two orthogonal ones: a hash function trading speed against collision rate, and a hashing scheme trading storage against compute 19:01 20:17.
  • Do not write your own hash function. Use XXHash (state of the art, from the Zstandard author); PostgreSQL rolling its own is a historical accident, not a model. SMHasher ranks the alternatives — RabbitHash fastest, XXH3 second 22:35 23:36 24:19.
  • Cryptographic hashes (SHA-1/SHA-256) are explicitly the wrong choice internally: too slow, and there is nothing to protect since the DBMS already owns the user's data 21:51 22:18.
  • Deleting from a linear probe table must use tombstones, not entry movement — rehashing-and-sliding is so expensive that no known system implements it 37:35 38:11.
  • Simplicity beats cleverness in probing: Robin Hood hashing keeps keys nearer their ideal slot yet is often slower than plain linear probing 33:28.
  • ClickHouse ships ~20 specialized hash table implementations versus roughly two in PostgreSQL, including a version-counter trick that logically clears a table without rewriting memory 44:54 45:39.
  • Cuckoo hashing buys guaranteed O(1) lookups and deletes at the price of eviction-cascading inserts; it is rare in practice (IBM DB2 BLU), and the best open-source implementation came out of CMU and is used inside Google 46:20 47:02.
  • Extendible and linear hashing both amortize resizing across queries by splitting one bucket at a time; linear hashing counterintuitively splits whatever its split pointer targets, not the bucket that overflowed, and still balances out over time — this is what PostgreSQL's dynahash does, inherited from the same author's Berkeley DB 1:01:54 1:03:23 1:02:28.
  • Hash tables are the wrong choice for table indexes: no range queries and no partial-key lookups, so CREATE INDEX yields a B+ Tree ~99% of the time (PostgreSQL's USING HASH being the opt-out) 1:08:49 1:09:31.
  • RelationalAI's position: software complexity grows with state, control logic and code volume, so their system keeps only inputs as state and derives everything else by reasoning over declarative Rel code — compiled down to what is essentially Datalog, written in Julia, deployed inside Snowflake Container Services because data has gravity 1:12:25 1:14:30 1:15:25 1:22:16.
  • Their concrete theory-to-practice win: classify every query, decompose it into prefix joins connected by distributed sorting (both scalable and latency-tolerant for blob storage), and hand the optimizer a deterministic canonically-good plan — improving robustness and explainability rather than plan quality 1:17:37 1:19:11.

The full transcript is included in this folder.