DBMS cheat sheet

Keys & normal forms

── NORMAL FORMS ─────────────────────────────────────────────────
1NF   atomic values, no repeating groups
2NF   1NF + no PARTIAL dependency (on part of a composite key)
3NF   2NF + no TRANSITIVE dependency (non-prime → non-prime)
BCNF  every determinant is a superkey  (3NF without the prime exception)
4NF   BCNF + no multivalued dependency
5NF   4NF + no join dependency

Mnemonic: "the key, the whole key, and nothing but the key"
          2NF fixes "the whole key" · 3NF fixes "nothing but the key"

Anomalies normalisation removes:
  update    — same fact in many rows; miss one and the DB contradicts itself
  insertion — can't record a department until it has an employee
  deletion  — removing the last employee destroys the department

Lossless decomposition: R1 ∩ R2 must be a superkey of R1 or R2.
Tradeoff: BCNF is always lossless but may NOT be dependency-preserving;
           3NF can always be both. Hence "3NF is usually enough".

── FINDING CANDIDATE KEYS ───────────────────────────────────────
Compute attribute closure X⁺: start with X, repeatedly apply any FD
whose left side is inside your set, add its right side. If X⁺ = all
attributes and no proper subset does, X is a candidate key.
  · an attribute never on any RIGHT side  → in EVERY candidate key
  · an attribute only on RIGHT sides      → in NO candidate key
PRIME attribute = part of some candidate key (this is what 2NF/3NF use)

SQL patterns worth memorising

── TOP N PER GROUP (the most-asked pattern) ─────────────────────
WITH r AS (SELECT *, ROW_NUMBER() OVER (PARTITION BY g ORDER BY x DESC) rn
           FROM t)
SELECT * FROM r WHERE rn <= 3;
-- CTE required: you cannot filter a window function in WHERE

── Nth HIGHEST DISTINCT VALUE ───────────────────────────────────
SELECT DISTINCT x FROM (SELECT x, DENSE_RANK() OVER (ORDER BY x DESC) rk
                       FROM t) s WHERE rk = 2;
-- DENSE_RANK, not ROW_NUMBER — ties should share a rank

── ROWS WITH NO MATCH (anti-join) ───────────────────────────────
SELECT c.* FROM customers c
WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id);
-- NEVER `NOT IN (subquery)` on a nullable column → returns 0 rows

── DEDUPLICATE, KEEPING THE NEWEST ──────────────────────────────
DELETE FROM t WHERE id IN (
  SELECT id FROM (SELECT id, ROW_NUMBER() OVER
      (PARTITION BY k ORDER BY created_at DESC, id DESC) rn FROM t) s
  WHERE rn > 1);

── RUNNING TOTAL & MOVING AVERAGE ───────────────────────────────
SUM(x) OVER (ORDER BY d)
AVG(x) OVER (ORDER BY d ROWS BETWEEN 6 PRECEDING AND CURRENT ROW)
-- ROWS counts physical rows; RANGE groups peers with equal sort keys

── PERIOD-OVER-PERIOD CHANGE ────────────────────────────────────
x - LAG(x) OVER (ORDER BY month)
100.0 * (x - LAG(x) OVER (...)) / NULLIF(LAG(x) OVER (...), 0)
-- 100.0 forces float; NULLIF guards division by zero

── PIVOT / CONDITIONAL AGGREGATION ──────────────────────────────
COUNT(*) FILTER (WHERE status = 'paid')              -- standard
SUM(CASE WHEN status = 'paid' THEN 1 ELSE 0 END)      -- portable

── DETAIL + GROUP AGGREGATE ON ONE ROW ──────────────────────────
AVG(salary) OVER (PARTITION BY department_id)
-- impossible with GROUP BY without a self-join

── GAPS IN A TIME SERIES ────────────────────────────────────────
FROM generate_series(d1, d2, '1 day') AS d(day)
LEFT JOIN t ON t.created_at >= d.day AND t.created_at < d.day + 1
-- range predicate, not ::date — a cast on the column kills the index

── KEYSET PAGINATION (never deep OFFSET) ────────────────────────
WHERE (created_at, id) < (?, ?) ORDER BY created_at DESC, id DESC LIMIT 20

── SAFE INCREMENT / TRANSFER ────────────────────────────────────
UPDATE accounts SET balance = balance - 100
 WHERE id = ? AND balance >= 100;   -- atomic; check rowcount

── OPTIMISTIC CONCURRENCY ───────────────────────────────────────
UPDATE t SET v = ?, version = 8 WHERE id = ? AND version = 7;
-- 0 rows ⇒ someone else won ⇒ reload and retry

── RECURSIVE HIERARCHY ──────────────────────────────────────────
WITH RECURSIVE t AS (
  SELECT id, mgr, 1 d FROM e WHERE id = ?
  UNION ALL                                -- ALL, not UNION
  SELECT e.id, e.mgr, t.d+1 FROM e JOIN t ON e.mgr = t.id
  WHERE t.d < 10)                          -- depth guard vs cycles
SELECT * FROM t;

Execution order & NULL logic

── EXECUTION ORDER (explains nearly every error message) ────────
1 FROM/JOIN → 2 WHERE → 3 GROUP BY → 4 HAVING
            → 5 SELECT → 6 DISTINCT → 7 ORDER BY → 8 LIMIT

WHERE can't use a SELECT alias (SELECT runs later) — ORDER BY can
WHERE can't use an aggregate (no groups yet) — use HAVING
Non-aggregated SELECT column must be in GROUP BY
Window functions run after WHERE → filter them in an outer query

── THREE-VALUED LOGIC ───────────────────────────────────────────
NULL = NULL      → UNKNOWN      NULL IS NULL   → TRUE
NULL != 5        → UNKNOWN      NULL + 5       → NULL
FALSE AND UNKNOWN → FALSE       TRUE OR UNKNOWN → TRUE
WHERE keeps a row only when the condition is TRUE.

Five NULL bugs that ship:
  · status != 'x' silently EXCLUDES NULL rows → use IS DISTINCT FROM
  · NOT IN (subquery) returns nothing if the subquery has any NULL
  · COUNT(col) ignores NULLs; COUNT(*) doesn't → the two disagree
  · AVG(col) divides by the NON-NULL count → missing data inflates it
  · UNIQUE allows MULTIPLE NULLs → no protection against duplicate unknowns
Fixes: COALESCE(x, default) · NULLIF(x, 0) · IS [NOT] DISTINCT FROM

Index rules

Join algorithms & EXPLAIN

── READING EXPLAIN ANALYZE — inside-out, bottom-up ──────────────
FIRST: compare estimated rows vs actual rows.
       Order-of-magnitude gap ⇒ fix STATISTICS before adding indexes.

Seq Scan + high "Rows Removed by Filter" → missing index
Nested Loop with huge actual outer rows   → bad estimate
Sort … "external merge Disk: 42MB"        → raise work_mem, or index the order
Hash … "Batches: 8"                       → hash spilled; raise work_mem
Index Scan then many heap fetches         → make the index COVERING
Fast alone, slow under load               → lock contention, not the plan

EXPLAIN            = plan + estimates only
EXPLAIN ANALYZE    = actually RUNS it (careful with DML!)
EXPLAIN (ANALYZE, BUFFERS) = plus cache hit/read counts

Isolation grid

✓ = prevented, ✗ = possible. *MySQL's repeatable read does prevent phantoms via gap locks — stronger than the standard requires.

── ANOMALIES ────────────────────────────────────────────────────
dirty read          read uncommitted data
non-repeatable read same row, different value within one transaction
phantom read        same query, new rows appear
lost update         two read-modify-writes, one silently overwrites
write skew          both read a valid state, write DIFFERENT rows,
                    jointly break an invariant  ← SI cannot prevent this

── FIXING LOST UPDATE (best first) ──────────────────────────────
1. arithmetic in the DB:  SET balance = balance - 100   ← atomic, no locks
2. SELECT ... FOR UPDATE                                ← explicit row lock
3. optimistic: WHERE version = 7, retry on 0 rows

── 2PL ──────────────────────────────────────────────────────────
growing phase (acquire only) → shrinking phase (release only)
STRICT 2PL holds exclusive locks to commit → strict schedules,
   no cascading rollback. The standard.
Deadlock: DB builds a wait-for graph, detects the cycle, ABORTS a victim
   (an OS can't — it has no safe rollback). Prevent by locking rows in a
   consistent order and keeping transactions short.

── MVCC ─────────────────────────────────────────────────────────
Writers make new VERSIONS; readers take NO locks and see a snapshot.
→ readers never block writers, writers never block readers
→ but write-write contention on the same row remains
→ old versions are garbage: VACUUM (PG) / undo log (MySQL)

── WAL & RECOVERY ───────────────────────────────────────────────
RULE: the log record reaches stable storage BEFORE the data page.
Commit = flush log to the commit record → one fsync (~1 ms)
  ⇒ commit rate is bounded by DISK, not CPU. Group commit batches them.
Log record holds BEFORE-image (undo) and AFTER-image (redo).
STEAL + NO-FORCE buffer policy ⇒ BOTH redo and undo are needed.
ARIES: analysis → redo (repeat ALL history) → undo losers (write CLRs).
Checkpoint = the RTO dial: frequent → fast recovery, more steady I/O.
Bonus uses of the WAL: point-in-time recovery, replication, CDC.

Numbers

The distinction table

Decision trees

Which index?

What does the hot query do?
├─ equality on one column         → single-column B+ tree
├─ equality + range/sort          → composite: EQUALITY first, range/sort LAST
├─ equality on a small subset     → PARTIAL index on that predicate
├─ compares a transformed value   → EXPRESSION index (LOWER(x), (a+b))
├─ full-text or JSONB containment → GIN
├─ geospatial                     → GiST
└─ range scan on an append-only
   time-ordered table             → BRIN
Then ask: can it be COVERING? (include the selected columns)
Then ask: does an existing index already cover this prefix?

Which isolation level?

Is being briefly wrong a bug or a shrug?
├─ SHRUG (listings, dashboards)     → READ COMMITTED
├─ needs a stable snapshot across
│  several reads (a report)         → REPEATABLE READ / snapshot
├─ read-modify-write on one row     → don't rely on isolation:
│                                     do the arithmetic IN the UPDATE,
│                                     or SELECT ... FOR UPDATE
└─ multi-row INVARIANT (write skew) → SERIALIZABLE
                                      + retry serialisation failures

"This query is slow"

1. EXPLAIN ANALYZE. Never guess.
2. estimated vs actual rows wildly different?  → ANALYZE (statistics)
3. Seq Scan removing most rows by filter?      → add an index
4. index exists but unused?                    → function/cast on column,
                                                  low selectivity, or stale stats
5. Sort or Hash spilling to disk?              → work_mem, or index the order
6. still slow?                                 → question the QUERY
                                                  (SELECT *, DISTINCT hiding a
                                                   bad join, deep OFFSET)
7. still slow?                                 → question the SCHEMA
                                                  (materialised view, summary
                                                   table, or move it to a warehouse)

Schema design order

entities + ACCESS PATTERNS → relationships & cardinality
  → normalise to 3NF → name any deliberate denormalisation
  → keys (surrogate PK + UNIQUE natural key)
  → constraints (NOT NULL, CHECK, FK with explicit ON DELETE)
  → indexes for the hot queries (column order reasoned)
  → time: TIMESTAMPTZ, and what needs HISTORY
     (a mutable product price silently re-prices old orders —
      capture the price ON THE ORDER LINE)
  → say what you'd defer: partitioning, archival, sharding