R09 · Week 9 Recall & Drill

Assessment scope

Attempt the recall prompts unaided, then work through the implementations and answer keys. The local programs use explicit fixtures and independent checks; product behavior is tied to named primary sources, not inferred from the toy models. Service deployment and production readiness are separate from this conceptual review. Timing budgets are adjustable practice suggestions.

Sessions covered

• S041 — Indexes — B-Tree Intuition, When to Add
• S042 — Transactions & ACID — Isolation Levels, MVCC
• S043 — Query Planning — EXPLAIN, Execution Plans, Tuning
• S044 — NoSQL Landscape — KV, Document, Column, Graph
• S045 — Data Modelling — Dimensional, Data Vault, OBT

By the end of this revision you can

• Explain why a B-tree lookup stays shallow even at enormous table sizes, and explain three query shapes that may prevent an ordinary seek without claiming every index use is impossible.
• Apply the left-prefix rule to order the columns of a composite index, and predict which queries will use how much of it.
• Compare isolation guarantees for a named engine and explain how snapshot-based repeatable-read behavior can permit write skew.
• Read an execution plan node by node, and investigate a large estimated-versus-actual row mismatch through statistics, correlation, parameter sensitivity and query shape.
• Name the four NoSQL families with a canonical store each, and say what each one gives up to gain what.
• Define the grain of a fact table first, and identify a grain-mixing bug on sight.

90-min structure

The 90-minute budget is pacing guidance, not a claim that full execution and every extension fit every learner's session.

Blank-page reconstruction · 30 min

S041 · Indexes

1. Explain the B-tree mental model — shallow, wide, sorted — and why lookup depth grows so slowly with table size.
2. Name three predicates that may prevent a seek and explain expression-index, covering-scan and skip-scan exceptions.
3. You have a composite index on two columns. Which queries use all of it, part of it, or none of it?

S042 · Transactions & ACID

1. Write out what each letter of ACID promises, with one concrete bug each prevents.
2. Name concurrency anomalies and the guarantees that exclude each for a specified engine, without inventing a universal severity order.
3. Explain multi-version concurrency control in one sentence, and say why readers need not block writers under it.

S043 · Query Planning

1. State the difference between asking for a plan and asking for a plan with actual execution statistics.
2. You see a node where the estimate and the actual row count differ by orders of magnitude. What is wrong, and what do you do?
3. Compare an ordinary indexed predicate, a wrapped expression and a matching expression index; inspect the actual plan.

S044 · NoSQL Landscape

1. Name the four families and one canonical store for each.
2. For each family, say in one sentence what it gives up to gain what.
3. Someone says "we need NoSQL because we have a lot of users". Write the three follow-up questions you ask.

S045 · Dimensional Modelling

1. Define grain, and give a concrete example of a grain-mixing bug and what it does to a total.
2. Explain the slowly-changing dimension pattern that preserves history, in one sentence.
3. Say what makes one-big-table a defensible choice on a columnar warehouse.

Hands-on drill · 30 min

Task: measure when an index actually pays, then analyze an explicit stale-read schedule and verify an atomic guard in an in-memory database. This does not claim a cross-engine concurrent-isolation reproduction.

Step 1 — build a table with two very different distributions (8 min)

# build.py
import random
import sqlite3
 
con = sqlite3.connect(":memory:")
con.executescript("""
CREATE TABLE events (
  id       INTEGER PRIMARY KEY,
  user_id  INTEGER NOT NULL,   -- many values; inspect frequency of the queried value
  status   TEXT    NOT NULL,   -- few values; ok is common, error is rarer here
  payload  TEXT    NOT NULL
);
""")
 
rng = random.Random(0)
rows = [
    (i, rng.randint(1, 2_000), "ok" if rng.random() < 0.95 else "error", "x" * 60)
    for i in range(5_000)
]
con.executemany("INSERT INTO events VALUES (?,?,?,?)", rows)
con.commit()
print("rows:", con.execute("SELECT count(*) FROM events").fetchone()[0])

Step 2 — prove the selectivity rule (12 min)

# selectivity.py
import sqlite3
import time
 
 
# Continue using the same in-memory connection from Step 1.
 
 
def timed(label, sql, params=()):
    con.execute("ANALYZE")
    t0 = time.perf_counter()
    n = con.execute(sql, params).fetchone()[0]
    dt = time.perf_counter() - t0
    plan = con.execute("EXPLAIN QUERY PLAN " + sql, params).fetchall()
    used = repr(plan)  # retain SEARCH/SCAN and COVERING INDEX details
    print(f"{label:<34} {dt*1000:8.2f} ms  rows={n:<8} plan={used}")
 
 
print("--- before any index ---")
timed("selective (one user)",   "SELECT count(*) FROM events WHERE user_id = ?", (1234,))
timed("unselective (status ok)", "SELECT count(*) FROM events WHERE status = 'ok'")
 
con.execute("CREATE INDEX idx_user   ON events(user_id)")
con.execute("CREATE INDEX idx_status ON events(status)")
con.commit()
 
print("--- after both indexes ---")
timed("selective (one user)",   "SELECT count(*) FROM events WHERE user_id = ?", (1234,))
timed("unselective (status ok)", "SELECT count(*) FROM events WHERE status = 'ok'")
timed("rare value (status error)", "SELECT count(*) FROM events WHERE status = 'error'")
 
print("--- expression can prevent an ordinary seek ---")
timed("sargable", "SELECT count(*) FROM events WHERE user_id = ?", (1234,))
timed("non-sargable", "SELECT count(*) FROM events WHERE user_id + 0 = ?", (1234,))

Record the actual plan and counts before interpreting timing. Cardinality is the number of distinct values; predicate selectivity depends on the fraction of rows matching the particular condition. A low-cardinality status can still have a rare value, and a high-cardinality user column can still contain a hot user. Neither column label alone predicts a plan. A single timed run also mixes cache, timer noise and execution overhead; use these times as observations, not a benchmark ranking. Both count queries can be served by a covering index without fetching payload rows; even a broad predicate may benefit from scanning the narrower index. The original binary classifier missed USING COVERING INDEX, so it could label an index-backed query a scan. The repaired code prints the full plan. For user_id+0, an ordinary index need not support a seek, though it may still support a covering scan; a matching expression index is another option. Query shape, projection, data statistics and engine rules matter more than a universal selectivity threshold.

Step 3 — reproduce a lost update (10 min)

Reproduce the logical stale-read schedule deterministically, not with sleeps: A reads 1000; B reads 1000; A approves 600 and writes 400; B also approves 600 and writes its stale 400. The stored balance remains nonnegative, so this is not a demonstration that the row's nonnegative CHECK failed. The failure is that two externally approved withdrawals of 600 were recorded as only one decrement. An actual database may serialize, reject or block the schedule depending on transaction boundaries and isolation. The following code models the stale decisions and separately executes the fixed conditional statement.

import sqlite3
observed_a = observed_b = 1000
approvals = [v >= 600 for v in (observed_a, observed_b)]
stale_final = observed_b - 600
assert all(approvals) and stale_final == 400
assert 1000 - 600*sum(approvals) == -200  # ledger and external effects disagree
 
with sqlite3.connect(":memory:") as db:
    db.execute("CREATE TABLE accounts(id INTEGER PRIMARY KEY, balance INTEGER NOT NULL CHECK(balance>=0))")
    db.execute("INSERT INTO accounts VALUES(1,1000)")
    db.commit()
    accepted=[]
    for _ in range(2):
        result=db.execute("UPDATE accounts SET balance=balance-? WHERE id=? AND balance>=?", (600,1,600))
        accepted.append(result.rowcount == 1)
    assert accepted == [True, False]
    assert db.execute("SELECT balance FROM accounts").fetchone() == (400,)
    db.rollback()
    assert db.execute("SELECT balance FROM accounts").fetchone() == (1000,)

Atomic guarded mutation plus checking affected rows fixes this single-account invariant. Real payment side effects additionally need an idempotency/transactional-outbox strategy; a database rollback cannot undo an already-sent payment. Retry the whole failed transaction with a bounded policy, not only the last SQL statement.

Indexes, isolation and modeling answer key

A B-tree with fanout b needs roughly log-base-b(N) levels, subject to fill and root details. Equality on the leading key of (country,created_at) identifies a contiguous region; a range on created_at within that region can further bound it. A query on created_at alone may use a skip scan, full index scan or another plan; it is not categorically unusable. Expression predicates, leading-wildcard searches and incompatible collations can prevent an ordinary seek, but matching functional/specialized indexes change the answer. Choose column order from equality/range/order requirements and workload, not “most selective first” alone. Indexes cost storage and maintenance when relevant entries change; a rarely used index may enforce uniqueness or support rare critical queries, so inspect those purposes before removing it.

ACID means atomic transaction effects, consistency with declared invariants and correct application logic, isolation under the selected model, and durability under stated failure assumptions. SQL's common ladder is read uncommitted, read committed, repeatable read, serializable, but engines implement these names differently. Dirty reads, nonrepeatable reads and phantoms are categories, not a universal severity ordering. Snapshot isolation can admit write skew: two on-call doctors each read that both are present and separately mark their own row absent. Their writes are on different rows, yet the joint invariant fails. Serializable execution, locking the shared invariant, or an appropriate constraint can prevent it; serializability is not the only design fix. MVCC retains versions for readers but does not abolish write conflicts or all blocking.

Plain EXPLAIN describes a plan; an analyzing variant in engines that support it actually executes the statement and can mutate data. SQLite EXPLAIN QUERY PLAN does not provide actual operator row/time statistics like PostgreSQL EXPLAIN ANALYZE. An estimate mismatch suggests investigating stale statistics, skew, correlated columns, parameter sensitivity and query expressions—not a guaranteed single diagnosis. Optimizer costs are engine-relative estimates, not milliseconds.

Key-value systems such as Redis favor key-addressed operations; document systems such as MongoDB support nested records and indexes; wide-column systems such as Cassandra organize around partition/clustering access paths; graph systems such as Neo4j support relationship traversal. These families do not imply one fixed consistency/transaction capability, and document stores can enforce validation schemas. Ask which access patterns, scale dimension and consistency/failure requirements justify a move, then compare measured bottlenecks and operational cost.

Set a sales fact grain to one order line: (order_id,line_no) identifies a quantity, unit price and product/customer dimension keys. Do not repeat and sum the order-level total on every line. For an order with two lines priced 10 and 20, summing a repeated order total of 30 yields 60 instead of 30. Separate order-grain facts or aggregate line amounts. A type-2 slowly changing dimension assigns a new surrogate row per version with nonoverlapping validity intervals; fact lookup must select the version valid at event time. Balances are often additive across accounts at the same instant but not across dates; ratios require their numerators and denominators. A one-big-table trades joins for duplication and update management; a Data Vault separates business-key hubs, relationships and historical descriptive satellites. Neither layout removes the need for an explicit grain and reconciliation.

Worked composite-index and expression-index checks

The Step 2 heading preserves the original anchor, but its experiment tests a plan for one fixture; it cannot prove a universal selectivity threshold. Continue with its existing connection. Adding an expression index tests the counterexample to “a function always makes an index useless.” Counts must agree regardless of the access path.

con.execute('CREATE INDEX idx_expression ON events(user_id + 0)')
expression_plan = con.execute('EXPLAIN QUERY PLAN SELECT count(*) FROM events WHERE user_id+0=?',(1234,)).fetchall()
assert con.execute('SELECT count(*) FROM events WHERE user_id+0=?',(1234,)).fetchone()[0] == sum(row[1] == 1234 for row in rows)
print('matching expression index',expression_plan)
con.executescript('CREATE TABLE visits(country TEXT, created_at INTEGER); CREATE INDEX visits_country_time ON visits(country,created_at);')
visits = [('IN',1),('IN',2),('US',1),('US',3)]
con.executemany('INSERT INTO visits VALUES(?,?)', visits)
assert con.execute('SELECT * FROM visits WHERE country=? AND created_at>=? ORDER BY created_at',('IN',2)).fetchall() == [('IN',2)]
assert con.execute('SELECT * FROM visits WHERE created_at>=? ORDER BY country,created_at',(2,)).fetchall() == [('IN',2),('US',3)]
print('composite plan',con.execute('EXPLAIN QUERY PLAN SELECT * FROM visits WHERE country=? AND created_at>=?',('IN',2)).fetchall())

For (country,created_at), country='IN' selects one contiguous leading-key region; adding created_at>=2 bounds it further; created_at>=2 alone spans country groups and may lead to a full index/table scan or a supported skip-scan plan depending on engine/version/statistics. A PostgreSQL 16 multicolumn example should not be silently treated as a promise of a later release's skip-scan behavior. Inspect your engine rather than asserting “none.” With fanout 100, four child-pointer levels give roughly 100 million possible root-to-leaf paths in a simplified full tree; actual height depends on page capacity, leaf occupancy and root layout. Wide shallow branching—not binary splitting per key—is the intuition.

Isolation matrix and plan-reading exercise

PostgreSQL 16 reference, not a SQLite result: Read Uncommitted behaves as Read Committed. Read Committed prevents dirty reads but different statements can observe different committed snapshots, permitting nonrepeatable reads, phantoms and serialization anomalies. Repeatable Read uses a transaction snapshot, preventing those dirty/nonrepeatable/phantom observations but permitting serialization anomalies such as write skew. Serializable additionally prevents committed serialization anomalies through its protocol, potentially aborting transactions which callers must retry in full. Other engines' “Repeatable Read” can differ.

ACID bug examples: atomicity prevents half a transfer persisting on rollback; declared constraints plus correct transaction logic prevent a negative balance (consistency is not automatic business correctness); isolation controls interference such as stale read/modify/write and write skew; durability keeps acknowledged commits under the configured failure/storage assumptions. In the doctors example, both transactions read A=on and B=on, then T1 changes A and T2 changes B; their writes differ, so ordinary write/write conflict checking does not catch the cross-row invariant. Each does write a row the other read—the original opposite statement was wrong.

Read this constructed, not captured, PostgreSQL-style plan fragment:

Nested Loop (cost=0.3..90 rows=10) (actual rows=1000 loops=1)
  Seq Scan on customers (cost=0..10 rows=5) (actual rows=100 loops=1)
  Index Scan on orders (cost=0.3..15 rows=2) (actual rows=10 loops=100)
    Index Cond: (customer_id = customers.id)

Solution: the outer scan underestimated customers 5→100 (20×); each inner execution underestimated matches 2→10 (5×). The inner node's 10 rows are per loop, so total inner output is 1,000, matching the parent. Start investigating at the first bad estimate rather than blaming the top node alone: current statistics, correlations, skew/parameters and predicate shape can all matter. A high loop count makes even a quick inner lookup expensive. Costs compare planner alternatives in engine units; they are not actual milliseconds. EXPLAIN ANALYZE executes the statement; avoid accidentally executing a destructive statement merely to inspect it. A transaction rollback may not undo external side effects of functions.

Store-choice and grain solutions

Ask: which query/access pattern is slow, which scale dimension or measured bottleneck fails, and which consistency/transaction/availability obligations must remain? A high user count alone answers none of them. Cassandra can have tables for distinct queries with duplicated attributes; an unbounded “all events for one user” partition can still become hot or too large.

For a type-2 customer dimension, version 101 covers [Jan 1, Mar 1) and version 102 covers [Mar 1, infinity); a March 1 sale joins version 102, not both. Nonoverlapping half-open intervals prevent boundary double counts. Two account balances of 10 and 20 today sum to 30 across accounts, but summing that same snapshot again tomorrow invents a 60 balance. For ratios, 1/2 plus 9/90 must combine as 10/92≈10.87%, not the 30% mean of 50% and 10%. A columnar one-big-table can avoid joins/compress repeated attributes, but duplicates order-level facts and history unless grain/version ownership is explicit. Data Vault business-key hubs, link relationships and descriptive satellites preserve different concerns; they do not automatically replace an analytics star's query-friendly fact grain.

Recall quiz — corrected answers

1. Index exists, no speedup? A broad noncovering predicate may favor scan, expression/collation may prevent a seek, or estimates/cache/I/O can dominate. Refreshing statistics is a diagnostic step, not a guaranteed speedup.
2. Composite index coverage? Leading country, country-plus-time, and time-only have different bounds as worked above; query result correctness never depends on the optimizer choosing the proposed index.
3. Write skew? Two transactions read a shared invariant and change different rows; serializability, invariant-level locking or an appropriate enforceable constraint are possible fixes.
4. Estimate 100, actual million? Inspect the first bad node, per-loop quantities, statistics, correlation and query parameters; not automatically “statistics, never query.”
5. Move to a document store? Show access-pattern and bottleneck evidence, explicit schema/version validation and required transaction/failure semantics. Do not trade away invariants just to adopt a category name.

Answer constraints and corrections

A query plan is optimizer evidence for that data and engine, not a universal selectivity law. SQLite locking may reject a competing writer rather than reproduce another engine's isolation anomaly. A conditional update can encode the balance invariant atomically; application success must depend on affected rows. Composite index usefulness depends on predicate shape, not simply the most selective column first.

Gap analysis + next week preview · 10 min

• Can you predict SEARCH versus SCAN without pretending an index is categorically useless? Compare the actual expression-index plan and independent row counts.
• Can you separate the stale-read payment schedule from the row CHECK invariant and name PostgreSQL 16 isolation guarantees? Do not widen sleeps and call that a proof.
• Can you identify the first incorrect estimate and the per-loop multiplier, then reconcile the fact-table total?

Mark each answer unaided, hinted or not yet; select a failed assumption and use a new counterexample for the retest rather than memorizing one fixture. Keep the input contract, boundary case and independent expected answer next to any execution result.

Next week: S046–S050 cover bounded/unbounded data, Spark execution, Kafka logs, stream windows and orchestration. Carry grain and atomic publication forward when deciding shuffle keys and retry boundaries.

Corrective source notes

• PostgreSQL 16 indexes — PostgreSQL 16 B-tree bounds depend on leading equalities and the first inequality; nonleading-only predicates do not make all index use impossible. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• PostgreSQL 16 isolation — PostgreSQL 16 Read Uncommitted acts as Read Committed; Repeatable Read prevents phantoms but can permit serialization anomalies. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• PostgreSQL 16 EXPLAIN — PostgreSQL planner costs are relative cost units, not measured milliseconds. PostgreSQL actual rows/time are per-execution averages when a node loops; multiply by loops for total work. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• EXPLAIN QUERY PLAN — SQLite EQP can report covering indexes and SEARCH/SCAN distinctions; preserve full output rather than a substring classifier. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Indexes On Expressions — SQLite expression indexes require the indexed expression to match the query expression apart from minor syntactic differences. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Microsoft dimensional modeling facts, grain — Additive, semi-additive and non-additive measures require different aggregation rules; the lesson independently derives grain/ratio counterexamples. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Schema Validation - Database Manual - MongoDB Docs — MongoDB supports explicit schema validation despite its flexible default document schema. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Introduction | Apache Cassandra Documentation — Cassandra data modeling starts with access patterns and denormalizes data around queries rather than relying on relational joins. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Redis data types | Docs — Redis offers native data structures rather than arbitrary relational query semantics. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.
• Graph database concepts - Getting Started — Neo4j models entities as nodes and connections as typed relationships with properties. Retrieved 2026-10-07; exact passage reviewed 2026-10-07.

These passages support the named propositions, not blanket product certification. The lesson-specific derivations and fixtures are separate evidence; runtime boundaries are stated beside each worked exercise.