M.A.T.R.I.X

Appearance

7.5.1 — Key-Value and Document Stores ​

A team moves their orders from PostgreSQL to MongoDB because "it scales better". Six months later they need to know total revenue per region per month, and discover the answer requires reading every document.

They did not pick the wrong database. They picked a database whose shape is decided at write time, and then asked a question they had not designed for. That is the entire NoSQL story: relational databases let you decide the question later, and everything else asks you to decide it now, in exchange for something.

This page covers the two families you will actually meet — key-value and document — with the honest version of what each buys.

1. Where NoSQL came from, and what "schemaless" really means ​

Around 2005–2010 several companies hit the same wall: a single relational server could not hold their data, and sharding it by hand was painful because joins, transactions and foreign keys all stop working once rows live on different machines. Amazon's Dynamo paper (2007) and Google's Bigtable paper (2006) described systems that gave up features in order to spread across machines automatically.

The name is unfortunate. "NoSQL" was a conference hashtag, later softened to "not only SQL". What the systems actually gave up was not SQL — several have query languages now — but joins, multi-row transactions, and a schema the database enforces.

And "schemaless" is the most misleading word in the field. There is always a schema. The only question is who enforces it:

  • Relational — the database enforces it. A bad write fails.
  • Document — your application enforces it. A bad write succeeds, and you find out when something reads it.

That is a real trade with a real benefit — adding a field needs no migration, and different documents can legitimately differ — and a real cost: after two years, a collection contains four generations of shape, and every reader must handle all four. The mitigation is to validate at the boundary: a schema library in the application, or the database's own validation rules, so the shape is enforced somewhere deliberate rather than nowhere.

2. Key-value stores ​

The simplest possible database: get(key), put(key, value), delete(key). The value is bytes the store does not interpret.

Because the interface is that small, the implementation can be extremely fast and easy to spread across machines. Hash the key, and you know which machine holds it — no coordination, no lookup table (Chapter 10.6 covers consistent hashing, which is how this survives adding machines).

What you give up is everything that needs to look inside the value. No querying by a field, no sorting by anything but the key, no joins, no aggregation. If you want "all orders over £100" you must have built that index yourself, as another key.

Where they genuinely win:

  • Caching — Redis and Memcached. Chapter 7.6 is the whole story.
  • Sessions — a session id maps to a blob, always fetched whole, always by that id.
  • Feature flags, configuration, rate-limit counters — small values read constantly.
  • Very large simple stores — DynamoDB and Riak, where the access is always by a known key.

The design discipline is that the key is the query. In a key-value store you name keys deliberately: user:42:profile, cart:sess_abc, ratelimit:ip:203.0.113.9:2026-08-02T14. Each key shape corresponds to one question you intend to ask. If you find yourself wanting to scan keys to answer something, that question needed its own key.

DynamoDB deserves a specific mention because it is a key-value store with one extra idea that changes how you model. Its primary key can be a partition key alone, or a partition key plus a sort key. Items sharing a partition key are stored together, sorted, so you can fetch a range within one partition cheaply.

PK = "USER#42"   SK = "PROFILE"              → the profile
PK = "USER#42"   SK = "ORDER#2026-08-01#001" → an order
PK = "USER#42"   SK = "ORDER#2026-08-02#004" → another

One query with PK = "USER#42" AND SK begins_with "ORDER#" returns all of a user's orders, newest last, in one round trip. This is the single-table design idea: instead of tables per entity, you put related items in one partition so that the access pattern you need is a single read. It is powerful and it is unforgiving — you must know your access patterns before you design the keys, and adding a new one later often means a new index or a data rewrite.

3. Document stores ​

A document store keeps semi-structured records — in practice JSON or a binary form of it — addressed by an id, with the ability to query and index fields inside the document. MongoDB is the common example; Couchbase, Firestore and Amazon DocumentDB are others.

js
// One order, complete
{
  _id: "ord_1001",
  customer: { id: "c_42", name: "Ana Ruiz", email: "ana@x.com" },  // (1)
  lines: [                                                          // (2)
    { sku: "SKU-9", name: "Kettle", qty: 1, unitPriceMinor: 2499 },
    { sku: "SKU-4", name: "Toaster", qty: 2, unitPriceMinor: 1899 }
  ],
  status: "shipped",
  placedAt: ISODate("2026-08-01T10:22:00Z")
}

(1) The customer's details are embedded, not referenced. (2) The lines are an array inside the document rather than rows in another table.

The gain is real: one read gets the whole order. No joins, no round trips, and the object in the database looks like the object in your code. For a document that is always used whole, that is a genuine simplification and a genuine performance win.

The costs are equally real:

Duplicated data drifts. customer.name is copied into every order. Ana changes her name and you must update every document — the exact update anomaly Chapter 7.1 opened with. Sometimes that is correct, because an order should record the name as it was at the time. Deciding which one you mean is the modelling work, and it is the question people skip.

Documents have a size limit — 16 MB in MongoDB — so an array that grows without bound is a design error waiting to fail. A blog post with embedded comments works until a post gets 40,000 comments.

Updating one element of a large array rewrites the document. Storage engines rewrite whole documents on update, so a 2 MB document updated for a 40-byte change writes 2 MB.

Cross-document queries are weak. MongoDB has $lookup, which is a left outer join, and it is genuinely more limited and generally slower than a relational join — it cannot use most of the plan shapes from Chapter 7.2.1.

The embed-or-reference decision ​

This is the one modelling rule to carry, and it answers most design questions in a document store:

Embed when the data is owned by the parent, always read with it, and bounded in size. Order lines. An address on a customer. Settings on a user.

Reference when the data is shared, queried independently, unbounded, or updated on a different rhythm. A product referenced by orders. Comments that could number in the tens of thousands. Anything with its own lifecycle.

The three questions that decide it: Is it read with the parent every time? Does it change on the parent's rhythm or its own? Can it grow without limit? Two "yes"es to the first two and a "no" to the third means embed.

A hybrid is often best. Embed the snapshot fields you need for display — the product's name and price at time of order — and keep a reference for the live record. This is not duplication by accident; it is the deliberate decision that an order line should record what was true when it was placed. Chapter 9.7.24 makes the same argument for relational order lines.

Transactions and consistency, accurately ​

Older document stores guaranteed atomicity only for a single document. That is not as limiting as it sounds — if your aggregate is one document, a single-document update is a transaction over the whole aggregate. That is exactly why embedding order lines is attractive: adding a line and updating the total is one atomic write.

MongoDB has supported multi-document ACID transactions since 4.0 (and across shards since 4.2), so the old "NoSQL has no transactions" line is out of date. The caveat is that they cost more than a single-document write and are not the shape the system is optimised for; if every operation needs one, the document model is fighting you.

Read concerns and write concerns are the dial, and this is what "eventually consistent by default" means in practice. writeConcern: { w: "majority" } waits for a majority of replicas to acknowledge; w: 1 returns after the primary alone, which is faster and loses the write if that primary fails before replicating. readPreference: secondary spreads read load and can return stale data. These are per-operation choices, which is a genuine advantage — a page view can read stale, a balance check cannot — and a genuine hazard, because the fast defaults are easy to leave in place.

4. What you actually give up, stated plainly ​

Across both families, four things:

Joins. You either denormalise (and own the duplication) or you do the join in the application (and pay N round trips — the N+1 problem of Chapter 7.3.2, now unavoidable rather than a mistake).

Ad-hoc queries. A relational schema answers questions nobody thought of. A key-value schema answers exactly the questions its keys encode. This is the single most underweighted cost, because it is invisible on day one and dominant in year two.

Declared constraints. No foreign keys, and usually no cross-document uniqueness. Referential integrity becomes application code, and application code has bugs and multiple authors.

A single obvious source of truth for a fact. With data duplicated across documents, "which copy is right" becomes a real operational question during an incident.

In exchange you get: horizontal scaling that is built in rather than bolted on, writes that do not need a coordinated schema change, a data shape that matches your objects, and — with the right key design — predictable single-digit-millisecond reads at any size.

5. The honest 2026 position ​

Two things have changed since the arguments were formed, and both should update your default.

Relational databases absorbed the document model. PostgreSQL's jsonb (Chapter 7.1 section 5) stores documents, indexes inside them with GIN, and queries them — while keeping joins, transactions and constraints for the parts of your data that want them. For most applications, "PostgreSQL with a jsonb column where the shape genuinely varies" beats splitting the system across two databases.

Relational databases scale further than the 2010 argument assumed. Managed PostgreSQL and MySQL now run comfortably at scales that used to be quoted as impossible, and distributed SQL systems — CockroachDB, Spanner, Vitess, Aurora — offer horizontal scaling while keeping SQL and transactions.

So the defensible default is: start relational. Reach for a key-value store when the access is genuinely by key and the volume or latency demands it, and for a document store when documents genuinely vary and are genuinely read whole. "We might need to scale" is not a reason — it is the reason people give for a decision that costs them the ability to ask new questions.

What the interviewer will push on ​

"When would you choose a document store over a relational database?" When the aggregate is read and written whole, the shape genuinely varies between records, and you do not need to query across documents. Then show the other side: you are deciding your access patterns at design time and paying for new questions later. Anyone who answers "when you need to scale" has not used one in anger.

"What does schemaless actually mean?" That the database does not enforce the schema — the application does. There is always a schema. The tell is naming the two-year cost: four generations of document shape in one collection, all of which every reader must handle, and the mitigation of validating at the boundary.

"Embed or reference?" Embed when owned by the parent, always read with it, and bounded. Reference when shared, independently queried, or unbounded. Then volunteer the hybrid: embed a snapshot of the fields you display, keep a reference for the live record — because an order line should record the price as it was.

"How do you model a user's orders in DynamoDB?" Same partition key, different sort key prefixes, so one query with begins_with returns them in one read. That is single-table design. The tell is stating its condition honestly: you must know the access patterns before you design the keys, and a new pattern later means a new index or a rewrite.

"Do document stores have transactions?" Yes — MongoDB since 4.0, across shards since 4.2. But the more interesting answer is that a single-document write is already atomic over the whole aggregate, which is exactly why embedding is attractive, and if you need multi-document transactions constantly, the document model is the wrong shape for that data.

"What do you give up with NoSQL?" Joins, ad-hoc queries, declared constraints, and one obvious source of truth. Emphasise ad-hoc queries: it is invisible on day one and dominant in year two, when someone asks a question the keys were not designed for.

One thing to volunteer: point out that PostgreSQL's jsonb gives you the document model inside a relational database, with GIN indexes on the document contents, so the choice is rarely all-or-nothing any more. It reframes the question from "which database" to "which parts of my data are actually document-shaped", which is the more useful question.

Recall

  • NoSQL gave up joins, multi-row transactions and an enforced schema in exchange for automatic horizontal scaling. The trade is not about SQL the language.
  • "Schemaless" means the application enforces the schema, not that there is none. The cost lands in year two as several generations of shape in one collection; validate at the boundary.
  • Key-value: get/put/delete on opaque values. The key is the query — name keys after the questions you intend to ask. Scanning keys means a question that needed its own key.
  • DynamoDB's partition key plus sort key keeps related items together and sorted, which is what makes single-table design work — and what makes an unanticipated access pattern expensive.
  • Document stores query and index fields inside the document. One read gets the whole aggregate; the costs are duplicated data drifting, a size limit, whole-document rewrites, and weak cross-document joins.
  • Embed when owned by the parent, read with it, and bounded. Reference when shared, independently queried, or unbounded. The hybrid — embed a snapshot, keep a reference — is usually right, because an order should record the price as it was.
  • A single-document write is atomic over the whole aggregate, which is the real reason embedding is attractive. Multi-document ACID transactions exist in MongoDB 4.0+; needing them constantly means the model is wrong.
  • The real cost of NoSQL is the ad-hoc query you have not thought of yet. Default to relational; PostgreSQL's jsonb with GIN gives the document model without giving up joins and constraints.

Self-test: Who enforces the schema in a document store, and when does that bill arrive? · Name the three questions that decide embed versus reference · Why is PK = USER#42, SK = ORDER#… one read instead of two? · What does a single-document atomic write actually buy you? · Which NoSQL cost is invisible on day one? · What changed since 2010 that should move your default?

Next: 7.5.2 covers the remaining three families — wide-column, graph and time-series — and gives the decision procedure for picking among all of them.