How do you choose between a document store, a key-value store, a wide-column store and a graph database for a new service?

The selection criterion is the query, not the entity

The instinct is to describe the domain — "we have users, and users have orders, and orders have items" — and then ask which store fits that shape. It is the wrong starting point, because every one of these stores can hold that data. What separates them is what happens when you read it.

Ask for the access patterns first, written down as a list, each with its cardinality and its latency requirement. "Fetch a user's profile by user id, single-digit milliseconds, fifty thousand a second." "List the last fifty readings for one device, ordered newest first." "Find every account within four hops of a known fraudulent one." That list is the specification. In a relational database you can defer it, because indexes can be added later against a schema you designed around entities. In a wide-column or key-value store you cannot, because the primary key is the access path, and a query that was not in the list at design time may require a new table and a backfill of everything you have already written.

What each category is genuinely good at

A key-value store is for retrieval by a key you already hold, with no requirement to search on anything else. Sessions, feature flags, rendered fragments, rate-limit counters, idempotency records. The value is opaque to the store, which is why it is fast and why you can never ask a question about its contents. Redis and DynamoDB in its simplest form both sit here. If your list contains one access pattern and it starts with "given the id", stop looking.

A document store suits an aggregate that is loaded and saved whole, and whose shape varies between instances. A product catalogue where every category has different attributes, a CMS page tree, an insurance quote whose fields depend on the product. The document boundary is doing real work: it is the unit of atomicity, so keeping data that changes together inside one document removes a class of consistency problem. MongoDB has supported multi-document transactions since 4.0 on replica sets and 4.2 across shards, so the old "no transactions" objection is stale, but a design that leans on them heavily is usually a relational schema wearing a disguise. The constraint that bites is size: a MongoDB document is capped at 16 MB, so an aggregate with an unbounded child collection — a chat room's messages, an account's audit trail — must not be modelled as one document however natural the containment feels.

A wide-column store is for very high write throughput with reads that fetch an ordered range inside a known partition, and for writes that must be accepted in more than one region. Cassandra's primary key is two things at once: a partition key that decides which node owns the data, and clustering columns that decide the sort order within it. You model the table as the answer to one question.

-- CQL. The date bucket keeps a busy device's partition from growing without bound.
CREATE TABLE reading_by_device (
  device_id  uuid,
  bucket     date,
  reading_at timestamp,
  value      double,
  PRIMARY KEY ((device_id, bucket), reading_at)
) WITH CLUSTERING ORDER BY (reading_at DESC);

That table answers "latest readings for this device today" almost perfectly: one partition, one node, sequential read, already sorted. It cannot answer "which devices reported above 90 in the last hour" at all. A Cassandra secondary index on value would not rescue you either, because it fans the query out to every node in the ring. The honest answer is a second table keyed by the second question, populated by the same write path, and the price is that the two copies can now disagree and you own reconciling them. DynamoDB's equivalent is a global secondary index, which is cheaper to declare but is maintained asynchronously, so it is eventually consistent and carries its own capacity.

A graph database earns its place when the traversal depth is not known in advance and the traversal is the workload. Fraud rings, entitlement inheritance, dependency impact analysis, recommendation over a social graph. The reason is mechanical: each hop is a pointer dereference from the node you are already on, so a five-hop query costs five hops rather than five joins whose intermediate result sets multiply. What does not justify a graph engine is a fixed hierarchy or a bill of materials three levels deep — a recursive CTE in PostgreSQL handles that comfortably, and adding a second datastore for it is a cost with no return.

"It scales better" is not an argument

This is the sentence that ends interviews, and it needs unpicking rather than avoiding.

Nothing about being non-relational makes a store faster. What makes a distributed store scale is that its access pattern requires no coordination: every read and write touches one partition, so adding nodes adds capacity linearly. When a candidate says NoSQL scales better, the thing they have actually observed is that these products make cross-partition queries either impossible or obviously expensive, which forces a design that scales. A relational schema with the same partition-local access pattern, sensible indexes and a connection pool will serve a very large workload from one machine — and modern instances are large. Meanwhile the version that scales in Cassandra scales because you denormalised, and the duplicated facts are now your problem to keep in step: no foreign key will tell you the two tables disagree.

So the reasons to pick a distributed non-relational store are specific. The write volume genuinely exceeds what one primary can absorb. You need writes accepted in multiple regions with local latency, and your domain tolerates last-write-wins. The data is enormous but every query is partition-local by nature. The schema is genuinely heterogeneous per tenant. Absent one of those, the choice is being made on fashion, and an interviewer who has migrated a system back off one of these will recognise it immediately.

What to say when the queries are unknown

The most useful thing you can offer, and the answer that most often gets skipped, is that not knowing the access patterns yet is itself a selection criterion — and it points at the relational database. It is the only option in the list where the cost of a query nobody anticipated is an index rather than a migration. Committing to a partition key in month one for a product whose queries will be discovered in month six is the decision people regret, and saying so out loud is worth more than naming the right product.