๐Ÿ“š Study Notes / Home / ADBMS / Cheat Sheet
Adv. DBMS ยท 1-Page Cheat Sheet

ADBMS โ€” Quick Revision Cheat Sheet

Everything in the subject, condensed for quick revision.

โ† Full sessions

S1 What's Inside a Database

  • Layered architecture: SQL โ†’ parser โ†’ optimizer โ†’ execution engine โ†’ storage engine โ†’ disk.
  • Storage manager handles pages/files; query processor handles plans.
  • A DBMS = reliable, concurrent, crash-safe access to data far bigger than RAM.
  • Key concerns: durability, concurrency, query speed, recovery.
  • Data lives on disk in fixed-size pages; RAM is a cache.

S2 Storage Engine โ€” Pages & Records

  • Disk I/O happens in fixed pages (typically 4KBโ€“16KB), the unit of read/write.
  • Slotted page: header + slot array (grows down) + records (fill up); slots hold offsets.
  • Variable-length records โ†’ slot indirection lets records move without changing their ID.
  • Record ID (RID) = (page #, slot #) โ€” stable pointer.
  • Tuples store header (null bitmap, length) + fixed then variable fields.

S3 Heap Files & Free Space

  • Heap file: unordered collection of pages holding records; insert anywhere with space.
  • Track free space via free-space map (FSM) or linked list of pages.
  • Insert: find page with room โ†’ write โ†’ update slot; Delete: mark slot, may compact.
  • Full scan = O(N) pages โ€” motivates indexes.
  • Page-directory pattern maps page IDs to locations.

S4 Buffer Pool

  • Buffer pool = in-RAM cache of disk pages; avoids slow disk reads.
  • Frames hold pages; a page table maps page ID โ†’ frame.
  • Pin count protects in-use pages from eviction; dirty bit marks modified pages needing flush.
  • Evict only unpinned pages; write back if dirty.
  • Replacement policy decides victim (default LRU).

S5 Keeping Right Pages in Memory

  • Plain LRU fails on sequential scans (cache flooding / sequential flooding).
  • LRU-K tracks last K accesses โ†’ distinguishes hot pages from one-time scans.
  • Clock / Second-chance: cheap LRU approximation using a reference bit.
  • MRU / scan-resistant policies help large scans.
  • Goal: maximize hit ratio, minimize disk I/O.

S6 Indexes & B+ Trees

  • Index = sorted structure for fast lookup without full scan.
  • B+ tree: balanced, all data in leaves, leaves linked for range scans.
  • Search / insert / delete = O(log n); high fan-out โ†’ shallow (3โ€“4 levels).
  • Internal nodes store only keys (routing); leaves store keys + RIDs/values.
  • Great for equality and range; vs hash index = equality only, O(1).

S7 Index Maintenance & Choice

  • Delete/insert may trigger split (overflow) or merge/borrow (underflow).
  • Clustered index: table rows sorted by key (one per table); non-clustered: separate, points via RID.
  • Composite index obeys left-prefix rule; covering index answers query from index alone.
  • Indexes speed reads but slow writes & cost space โ€” index selectively.
  • Bulk-load by sorting then bottom-up build (faster than repeated inserts).

S8 SQL โ†’ Query Plan

  • Pipeline: parse โ†’ bind/analyze (catalog check) โ†’ rewrite โ†’ optimize โ†’ plan.
  • SQL becomes relational algebra (ฯƒ select, ฯ€ project, โ‹ˆ join).
  • Logical plan = what; physical plan = how (which operators/access paths).
  • Plan = tree of operators executed bottom-up.
  • Catalog/system tables store schema, stats, indexes.

S9 Query Execution

  • Volcano / Iterator model: every operator exposes open(), next(), close().
  • Rows pulled one at a time up the tree (pull-based) โ€” pipelined, low memory.
  • Access paths: sequential scan vs index scan.
  • Vectorized & push-based models process batches โ†’ less per-row overhead.
  • Operators: scan, filter, project, join, aggregate, sort.

S10 Sort, Join, Group (Out-of-Core)

  • External merge sort: sort runs in memory, merge passes; O(N log N) with disk passes.
  • Nested-loop join O(NยทM) (block/index variants cut cost).
  • Sort-merge join: sort both, merge โ€” good if pre-sorted / range.
  • Hash join: build hash on smaller side, probe โ€” best for equi-joins, O(N+M).
  • Group-by via sorting or hashing; spill to disk when too big.

S11 Query Optimization

  • Optimizer picks cheapest plan from huge search space.
  • Cost-based: uses statistics (cardinality, histograms, selectivity) to estimate cost.
  • Rule/heuristic: push down selections/projections, reorder joins.
  • Join ordering via dynamic programming (System R) โ€” exponential, pruned.
  • Bad row estimates โ†’ bad plans; key risk = cardinality estimation error.

S12 Transactions & ACID

  • Transaction = atomic unit of work; commit or rollback as a whole.
  • ACID: Atomicity, Consistency, Isolation, Durability.
  • Anomalies: dirty read, non-repeatable read, phantom, lost update.
  • Isolation levels: Read Uncommitted โ†’ Read Committed โ†’ Repeatable Read โ†’ Serializable.
  • Serializability = gold standard; equivalent to some serial order.

S13 Concurrency Control

  • 2PL (Two-Phase Locking): growing (acquire) then shrinking (release) phase โ†’ serializable.
  • Strict 2PL holds all locks till commit โ†’ avoids cascading aborts.
  • Shared (read) vs exclusive (write) locks; risk of deadlock (detect via wait-for graph / timeouts).
  • MVCC: readers see a snapshot, never block writers (versions + timestamps).
  • Optimistic CC: run, then validate before commit.

S14 Recovery โ€” WAL & ARIES

  • WAL (Write-Ahead Logging): log the change before writing the data page.
  • ARIES 3 phases: Analysis โ†’ Redo (repeat history) โ†’ Undo (rollback losers).
  • Each record has an LSN; CLR logs undo actions for idempotent recovery.
  • Checkpoints bound recovery work; STEAL/NO-FORCE policy needs both undo & redo.
  • Guarantees Atomicity + Durability after crash.

S15 Modern Storage โ€” LSM & Columnar

  • LSM-tree: in-memory memtable โ†’ flush to immutable SSTables; background compaction. Write-optimized.
  • Reads check memtable then SSTables; Bloom filters skip files that lack a key.
  • Columnar (column store): store per-column โ†’ great compression & analytic scans (OLAP).
  • Row store = OLTP, column store = OLAP/analytics; DuckDB = embedded vectorized columnar.
  • Vectorized execution + compression (RLE, dictionary) speed scans.

S16 Distributed Databases

  • Partitioning / sharding: split data across nodes (hash / range / round-robin).
  • Replication for availability; leader-follower or multi-leader.
  • 2PC (Two-Phase Commit): prepare โ†’ commit for atomic distributed txns (blocking on coordinator failure).
  • CAP theorem: under a partition, choose Consistency or Availability.
  • Trade-offs: eventual consistency, latency vs consistency (PACELC).