Week 4: Choosing a Data Model: SQL vs. NoSQL

1. Relational vs. Document/Key-Value/Wide-Column

A relational (SQL) database organizes data into tables with a fixed schema, relates rows across tables with foreign keys, and lets you query across those relationships with joins. Its defining strength is ACID transactions (Atomicity, Consistency, Isolation, Durability) — a multi-step write either fully happens or fully doesn't, and concurrent transactions don't corrupt each other's view of the data. That makes relational databases the default choice whenever correctness across related records matters more than raw write throughput: financial transactions, inventory counts, anything where "half-applied" is unacceptable.

NoSQL is really an umbrella over several different models, each trading away some of the relational database's generality for a specific access pattern's sake:

Key-value (e.g. Redis, DynamoDB):
  get(key) -> value, set(key, value) -- no query language, no
  joins, but extremely fast and trivially shardable by key.
  Fits session storage, caching, feature flags.

Document (e.g. MongoDB):
  Each record is a self-contained JSON-like document, fields
  can vary between documents, nested structures allowed.
  Fits data that's naturally hierarchical and usually read/written
  as one whole unit -- a user profile, a product catalog entry.

Wide-column (e.g. Cassandra, HBase):
  Rows identified by a key, but columns can vary per row and are
  grouped into column families, optimized for very high write
  throughput distributed across many nodes.
  Fits time-series data, event logging, IoT sensor data.

The interview-relevant point is not "NoSQL scales better than SQL" — that's a common oversimplification. Both models can scale horizontally with the right architecture (Week 5 covers sharding, which applies to relational databases too). The real question is which model's native strengths match your access pattern: if the system needs multi-row transactions and rich ad hoc queries across related entities, relational is usually the better starting point; if the system needs simple lookups by a single key at very high throughput, or naturally schema-flexible nested documents, a NoSQL model removes friction the relational model would otherwise impose.

2. Indexing Strategies

Without an index, finding a row that matches a condition means scanning every row in the table — a full table scan, O(n) in the number of rows. An index is a separate, sorted data structure that lets the database jump directly to matching rows instead. The default structure most relational databases use is a B-tree: a balanced, sorted tree where each lookup, insert or delete takes O(log n) rather than O(n), and — critically — the sort order also makes range queries (WHERE created_at > ?) fast, not just exact-match lookups.

SELECT * FROM users WHERE email = 'ana@example.com';

Without an index on email:
  full table scan -- database checks up to 10,000,000 rows

With a B-tree index on email:
  O(log n) traversal -- roughly log2(10,000,000) ~ 24 comparisons
  to locate the matching row(s)

Same idea applies to range queries:
  WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31'
  A B-tree index on created_at lets the database jump to the
  start of the range and scan forward only through matching rows,
  instead of checking every row in the table.

A composite index spans multiple columns, and column order in the definition matters — a composite index on (last_name, first_name) can efficiently serve a query filtering on last_name alone, or on both columns together, but cannot efficiently serve a query filtering on first_name alone. This is the leftmost prefix rule: a composite index is usable only for query conditions that match a prefix of its column order, left to right.

Every index has a real cost, though: it must be updated on every INSERT, UPDATE or DELETE that touches an indexed column, so more indexes mean slower writes, and each index also consumes its own storage. Indexing is therefore a genuine tradeoff, not a free performance upgrade — the right move is indexing the columns your actual queries filter or sort on, not every column that might someday be useful.

3. Normalization vs. Denormalization

Normalization organizes data to minimize redundancy: each fact is stored in exactly one place, and related data is split across tables connected by foreign keys. Its payoff is data integrity — updating a user's name means updating one row, not hunting down every copy of it — but reconstructing a full picture (a user with their orders and each order's line items) requires joining across tables, which gets more expensive as tables grow and, in a sharded or distributed database, can become outright impractical if the related rows don't live on the same node.

Denormalization deliberately duplicates data to avoid those joins — storing a copy of frequently-needed fields directly on the record that needs them, so a single read satisfies the query without touching other tables. The cost moves to writes: every copy of a duplicated fact has to be kept in sync, and a bug or a missed update path can leave copies inconsistent with each other.

Normalized (3 tables, joins required to render an order):
  orders(id, user_id, created_at)
  order_items(id, order_id, product_id, quantity)
  products(id, name, price)
  -- Rendering one order's receipt needs a join across all three

Denormalized (one document, no joins needed):
  {
    "order_id": 501,
    "user_name": "Ana Ruiz",          // duplicated from users
    "items": [
      { "product_name": "Mug", "price": 12.00, "quantity": 2 }
      // product_name and price duplicated from products
    ]
  }
  -- One read returns everything; but if a product's price
     changes, every past order's denormalized copy is unaffected
     by design (a receipt should show the price paid, not today's
     price) -- here duplication is actually correct, not a bug

That last detail matters: denormalization isn't always "stale data you have to fix" — sometimes the duplicated copy is supposed to be a frozen snapshot (an order receipt should show the price paid at purchase time, not today's price), and in that case denormalization is the more correct model, not merely a faster one. The general principle for a system design interview: normalize by default for correctness-critical, relationally complex data, and denormalize deliberately, table by table, wherever a specific read pattern is both frequent and expensive under the normalized form — exactly the same "the numbers justified this" discipline Week 1 introduced for adding a cache.

4. Hands-on Exercise

5. Knowledge Check

Four quick questions. Expand each to check your answer.