DBMS
How data is modelled, how transactions stay correct, and how a query gets fast, at the depth an SDE-1 interview asks.
This page covers the database questions an SDE-1 interview actually asks: how you model data, how a transaction stays correct, and how a query gets fast. Answer from Ledgerline and Logsmith, not from a textbook table.
Priority for SDE-1
Normalisation, ACID, isolation anomalies, indexes, joins and basic replication are mandatory before your first interview. MVCC internals, WAL format, LSM compaction and distributed transactions can wait for an offer.
SDE-1 scope vs SDE-2 scope
| Area | SDE-1 must | SDE-2 later |
|---|---|---|
| Modelling | 1NF to 3NF, keys, when to denormalise | Access-pattern modelling, BCNF |
| Transactions | ACID with a failure per letter, read committed vs serializable | SSI, savepoints, retry design |
| Concurrency | Anomalies, SELECT FOR UPDATE, deadlock avoidance | Tuple versions, vacuum, bloat |
| Indexes | B-tree lookup, composite order, write cost | Index-only scans, planner costing |
| Queries | Joins, N+1, EXPLAIN basics | Plan shapes, statistics |
| Operations | Pooling, replica lag, backups | WAL internals, failover, fencing |
| Scale | Read replicas, when sharding is wrong | Shard keys, 2PC, Jepsen reports |
| Storage | Pages and heap at a high level | B-tree vs LSM, compaction |
Start with your own database
Open two psql sessions on Ledgerline. Read a balance inside a BEGIN in one session, update the same row and commit in the other, then re-read in the first.
That is a non-repeatable read, on data you built. An anomaly you have caused yourself is a different answer from one you memorised.
Roadmap
Stage 1: the basics (weeks 1 to 2)
Model Ledgerline from its invariants, normalise it to 3NF on paper, then name the two places you broke the rule on purpose.
Stage 2: interview core (week 6 and week 12)
The week 6 drill adds read committed vs serializable, locking, pooling and N+1. Week 12 of the plan sends you back to EXPLAIN on a real query.
Stage 3: SDE-2 depth (after the offer)
MVCC internals, the WAL format, LSM compaction, distributed transactions and consistency testing. Start with the chapter that matches a bug you have already hit.
Core topics, in order
| Topic | What you must be able to explain | Level |
|---|---|---|
| Relational model | Relations, keys, and why a unique index is the guarantee | SDE-1 must |
| Normalisation | 1NF to 3NF, with the anomaly each step removes | SDE-1 must |
| ACID and isolation | One failure per letter, and the anomaly each level allows | SDE-1 must |
| Indexes | B-tree range vs hash equality, composite order, write cost | SDE-1 must |
| Planning | Cost estimates, and N+1 in application code | SDE-1 must |
| Operation | Pool exhaustion, replica lag, sharding as a last resort | SDE-1 must |
| Engines | B-tree writes in place, LSM appends and compacts | SDE-2 later |
The relational model and keys
A relation is a table with typed columns and no row order. The primary key identifies a row, and a foreign key points at another table's key, so the database rejects rows that point nowhere.
Keep a surrogate key (a generated id) for identity and a unique constraint on the natural key, like an email. Natural values change, so they make poor join columns.
In Ledgerline the idempotency key is a unique index, and that index is what makes a retry safe. Two requests with the same key cannot both insert, so the second returns the stored result.
Normalisation, 1NF to 3NF
First normal form means one atomic value per column. No comma-separated list, no phone1 and phone2.
Second normal form means no non-key column depends on part of a composite key. A transfer table storing account_name against (transfer_id, account_id) breaks it, because the name depends on the account alone.
Third normal form means no non-key column depends on another non-key column. The same account_name beside account_id breaks it, and the name is now spelled two ways in two places. Denormalise only after you measure a read problem, and if you cache a balance, write the cache and the journal in one transaction.
ACID, with a failure per letter
Atomicity: kill -9 mid-transfer and the debit never survives without its credit, because the log holds the partial work until commit.
Consistency: the double-entry invariant holds before and after every commit. This one is your constraint, not a database feature, so it needs a test and a nightly reconciliation.
Isolation: two transfers never see each other's half-finished state. Durability: once COMMIT returns, the row survives a power cut, because the log was flushed first.
A transaction groups statements so they commit or roll back as one. SAVEPOINT lets you undo part of one without losing the rest.
Isolation levels and the anomalies
| Level | Anomaly it still allows | Default for |
|---|---|---|
| Read committed | Non-repeatable read, phantom read | Most OLTP work, and Postgres |
| Repeatable read | Write skew | Reports that need one snapshot |
| Serializable | None, at the cost of aborts | Invariants read then written |
Postgres maps read uncommitted to read committed, and its repeatable read also blocks phantoms. Say those two details, because they show you read the implementation, not just the standard.
Write skew is the anomaly people miss. Two doctors each check that the other is still on call, then both go off call. Each write is valid alone, and the rule breaks in the pair. Only serializable stops it, by aborting one transaction, so your code needs a retry loop.
MVCC and locks
An UPDATE writes a new row version instead of overwriting the old one, and each version records which transaction created it. Readers keep a snapshot, so they never wait for writers.
The cost is garbage. Old versions stay until vacuum removes them, and a long transaction holds the cleanup horizon back. That is how a forgotten BEGIN doubles a table's size.
SELECT ... FOR UPDATE is the other half: it locks the rows it reads, which is what a balance check needs before a debit. In Postgres, reads use snapshots and conflicting writes use row locks.
Indexes
A B-tree keeps keys sorted, so it serves equality, ranges and ORDER BY without a sort. It is the default and the right first answer. A hash index does equality only, with no ranges and no ordering.
For a composite index the column order is the design. (account_id, created_at) serves the account filter and the account plus date range, while (created_at, account_id) does not serve the account-only query.
A covering index holds every column the query needs, so Postgres can answer from the index alone. Every index is still another write on insert and update, plus more log traffic, which is why a small partial index on WHERE status = 'pending' beats indexing the whole table.
Query planning and the N+1 trap
The planner parses, rewrites, estimates the cost of each plan from table statistics, and picks the cheapest. Bad statistics give a bad plan, and ANALYZE is the fix.
N+1 is one query for a list, then one per row inside a loop. A page of 100 transfers becomes 101 round trips, so at 1 ms each you pay 100 ms for nothing. Fix it with a join, one WHERE id = ANY($1), or a batched loader.
Pooling, replicas and sharding
Each Postgres connection is a backend process with its own memory. A pool of tens usually serves more than a pool of thousands, because more connections means more context switching and lock contention. An exhausted pool looks like rising latency and timeouts at the pool, against an idle-looking database, so shorten transactions and bound the pool.
Streaming replication ships log blocks to a standby that is a byte copy, while logical replication ships row changes per table and can cross versions. Either way an async replica lags, so read-your-writes traffic goes to the primary.
Sharding splits rows across databases by shard key. You inherit cross-shard joins, two-phase commit and painful resharding, so reach for it only when one primary cannot hold the writes. Postgres partitioning is not sharding: it lives on one node.
Storage engines: B-tree vs LSM
A B-tree updates pages in place. Reads are one predictable tree walk, and random writes cost page splits plus log traffic, which is the Postgres heap plus B-tree shape.
An LSM tree appends to a memory table and a log, flushes sorted files, and merges them in the background. Writes are sequential and cheap, reads may touch several files, and deletes wait for compaction. Pick a B-tree for read-heavy point workloads and an LSM for write-heavy ingest, which is the trade-off Logsmith's segments and compactor make in miniature.
Failure modes to name out loud
- Disk full, which turns every write into an error.
- A filesystem that lies about
fsync, which quietly breaks durability. - Replica lag, which breaks read-your-writes for a user who just paid.
- An exhausted pool, which looks like a slow database but is a queue.
- A deadlock between two transfers that locked rows in opposite order.
Resources
Learn
- PostgreSQL: transaction isolation: the anomaly table to memorise. SDE-1 must.
- PostgreSQL: index types: what B-tree, hash and GIN each answer. SDE-1 must.
- Database normalization (Wikipedia): a neutral recap of 1NF to 3NF. SDE-1 must.
- PgBouncer: pooling modes and the session-state trade-off. SDE-1 nice.
- PostgreSQL: logical replication: what a replica can and cannot do. SDE-1 nice.
Practice
- Transaction isolation in Postgres, explained: two-session examples you can reproduce in psql. SDE-1 nice.
- CMU 15-445/645: lectures and projects on storage, indexing and concurrency. SDE-2 later.
Long-form
- Designing Data-Intensive Applications: chapters 3, 5, 6 and 7 cover storage, replication, partitioning and transactions. SDE-2 later.
- The Internals of PostgreSQL: how Postgres does MVCC, in diagrams. SDE-2 later.
- Revisiting B+-tree vs LSM-tree: the debate on modern storage hardware. SDE-2 later.
Questions to answer out loud
- Normalise a table with a repeating group and a partial dependency, and name what breaks at each step.
- Give ACID with one concrete failure per letter, using Ledgerline.
- Which anomaly does read committed allow, and which one does serializable prevent?
- What is write skew, and why does Postgres repeatable read still allow it?
- Why does an index on
(account_id, created_at)not help a query that filters oncreated_atalone? - Your list endpoint runs one query plus 200 inside a loop. Name the pattern and the fix.
- What does a replica lagging by two seconds do to a user who just paid?
- When is a bigger connection pool the wrong fix?
SDE-2 later
- How does Postgres store row versions, and what does vacuum reclaim?
- Walk one commit from WAL record to fsync to a visible row.
- Why does LSM compaction cause write stalls, and how do you bound them?
- Why is a cross-shard transaction hard, and what happens when the 2PC coordinator dies?
How this shows up in your projects
- Ledgerline: the unique index is the idempotency arbiter, ordered locks kill deadlocks, and the outbox row is written in the transfer's transaction.
- Ledgerline's chaos test is a durability test. Kill the process a hundred times and the journal still balances, because the log was fsynced before
COMMITreturned. - Logsmith: CRC32 plus an fsync policy is WAL reasoning, the compactor is the LSM trade-off, and consumer offsets are your at-least-once story.
Common mistakes
- Answer ACID with a failure you have actually caused.
- Say which isolation level your service runs at, and why it is enough.
- Check the leftmost column before defending a composite index.
- Measure before denormalising, and write the copy in the same transaction.
- Keep transactions short, and never call an external API inside one.