CS Fundamentals Trainer · Guides

Choosing a database: access patterns, trade-offs and measured costs

How to choose a database from the questions you will ask of it: the main families (relational, document, key-value, wide-column, graph, search, columnar, time series) and their trade-offs, measured comparisons of documents against tables, queries with and without an index, graph hops, full-text search and row against column layout, one system of record with derived stores, and a checklist for design discussions.

32 min read

"Should we use Postgres, MongoDB, Cassandra, DynamoDB or Redis?" is one of the most common questions in design discussions, and the usual way of answering it, by comparing product features, is the wrong way. Products come and go; the useful question is what shape the data has and what questions you will ask of it. A shop's orders, a chat history, a billion sensor readings, a social graph and a search box all store "data", and each of them is cheap in one kind of database and painfully slow in another.

This guide gives you a way to choose. It starts from access patterns, walks through the main families of databases and what each is good at, and then tests the folklore with measurements: documents against tables, ad hoc queries without an index, graph traversals, full-text search and row against column layout. It finishes with the pattern most real systems end up with (one system of record, plus derived stores fed from it) and with a checklist you can run in an interview or in a design review.

A note on measurements. The numbers marked "measured" come from experiments written for this guide: PostgreSQL 16 on a small cloud VM (2 vCPUs of an Intel Xeon at 2.1 GHz, 8 GB of memory), one client connection, warm caches, plus Go 1.24 programs for the in-memory comparisons. The code is in the appendix. Absolute numbers will differ on your hardware and with your data, so read them for the ratios and the shape of the curve, not for the milliseconds. They also do not say that PostgreSQL is better than any other product; they show what happens when a kind of query meets a kind of storage.

1. Start from the access patterns, not from the product

Before naming a database, write down the questions the application asks, with an estimate of how often (see the capacity estimation guide for how to get those numbers). For a shop, the list might look like this:

QuestionShapeFrequency
Show order 8213 with its linesfetch one record by key, with its childrenvery high
Show all orders of customer 77list by a secondary attributehigh
Reserve stock and create the order, or neitherwrite several records atomicallyhigh
Revenue per product last quarterscan and aggregate everythinglow, but heavy
Search products by words in the nametext matching and rankinghigh
People who bought this also bought…traversal over relationshipsmedium

Each row points to a different strength. Fetch-by-key is what every database does well. Atomic multi-record writes need transactions. Scanning everything is what columnar stores are built for. Text and relationships have their own specialised structures. A database is a bet on which of these questions will matter, so the discipline is to list the questions first and let them rank the candidates.

Three more facts decide a lot and are easy to forget:

2. The families, in one table

FamilyThe data looks likeStrong atWeak atTypical examples
Relational (SQL)tables with typed columns, related by keystransactions, constraints, joins, ad hoc queriesone machine's limits (without extra work), deep graph traversalPostgreSQL, MySQL
Documentself-contained JSON-like recordsfetch a whole aggregate in one read, flexible fieldscross-document joins and transactions, ad hoc analysisMongoDB, Couchbase
Key-valuean opaque value behind a keythe simplest, fastest lookups; easy to partitionany question that is not "give me the value for this key"Redis, DynamoDB (basic use)
Wide-columnrows grouped by a partition key and sorted inside ithuge write volume, range reads inside a partition, scale-outqueries that do not match the table's key design, joinsCassandra, Bigtable, DynamoDB
Graphnodes and edges with propertiesmany-hop relationship queriesbulk aggregation, partitioning a highly connected graphNeo4j and similar
Searchan inverted index over textwords, ranking, typo tolerance, facetsbeing the source of truth, transactionsElasticsearch, OpenSearch, Solr
Time seriesmeasurements with timestampshuge append rates, time-window queries, retention, downsamplingupdating old points, general-purpose queriesTimescaleDB, InfluxDB, Prometheus
Columnar / analyticalthe same table, stored by columnscanning and aggregating a few columns of billions of rowssingle-row reads and updatesClickHouse, BigQuery, Redshift
Object storefiles (blobs) by namecheap, durable storage of large thingsqueries inside the files, low-latency small readsS3 and similar

Two remarks on the table. First, the families overlap: PostgreSQL stores JSON documents, does full-text search and runs recursive graph queries; Redis can persist; DynamoDB is both key-value and wide-column. The table says what each design is optimised for, not what it is limited to. Second, the right-hand columns matter as much as the left: every strength is paid for by a weakness, and the weakness is the thing you discover in production.

3. Relational first, and why that is a default and not a religion

A relational database gives you four things at once that are expensive to rebuild later:

  1. Transactions (ACID): several changes happen together or not at all, and concurrent users do not see half-done work.
  2. Constraints: the database itself rejects an order without a customer, a negative balance or a duplicate email. Bugs in application code cannot corrupt data the schema forbids.
  3. Joins and a query language: any question about the data can be asked without having planned for it, and the planner chooses how to answer.
  4. Indexes you can add later: a new access pattern is usually one CREATE INDEX.

The last two matter most while you are still learning what the product is. A document or key-value store tends to be designed around the queries known on day one; a relational schema is designed around the facts and can answer questions nobody had yet.

Measured: the same orders as tables and as documents

The experiment stores 1,000,000 orders twice in PostgreSQL: normalized into orders and order_items (3,000,000 lines, 1 to 5 per order), and as one JSONB document per order with the lines embedded (about 258 bytes of text each).

QuestionTablesDocuments
Fetch one order with its lines (by id)0.137 ms (join of two tables)0.085 ms (one row)
Orders of one customer, with an index on the customer0.106 ms0.127 ms (index on an expression of the JSON)
Orders of one customer, no index160 ms
Orders containing a product, no index103 ms1,135 ms
Orders containing a product, with an index0.123 ms (B-tree, 20 MB)4.0 ms (GIN index, 74 MB)
Revenue per product, whole data set0.52 to 0.56 s2.8 to 3.0 s
Size on disk (data and indexes)418 MB435 MB

Four conclusions follow, and they are the heart of the "document or relational" debate:

The practical rule: embed what is read together and changes together (an order and its lines, a blog post and its comments if they are always shown together), reference what is shared or changes on its own (a product, a customer). That rule works in documents and in tables, and in both it is the question of where the aggregate boundary lies.

4. Key-value and wide-column: scale by narrowing the questions

Systems such as DynamoDB, Cassandra and Bigtable come from one trade: give up the general query language and cross-record guarantees, and in return get lookups and writes whose cost does not grow with the data. They achieve this by partitioning every table by a key, so any request that names the key goes to one place.

What you get:

What it costs:

The earlier measurement shows the same cliff on a small scale: a lookup by key costs about 0.1 ms and the same question with no usable structure costs 160 ms. A key-value store makes the first path the only path, so that the second one cannot happen by accident. That is a feature when you know your questions, and a trap when you do not.

5. Graphs: the cost is the number of nodes you reach

"Friends of friends" and "who is connected to whom within four steps" are relationship questions. In a relational database they are self-joins, written with a recursive query. The experiment builds a follower graph with 300,000 users and 3,000,000 edges (about 10 follows each) and finds everyone within h hops of a random user, in PostgreSQL with a recursive query and in a Go program that keeps adjacency lists in memory.

HopsUsers reached (average)PostgreSQL, recursive queryGo, adjacency lists in memory
21100.33 ms0.004 ms
31,1081.7 ms0.027 ms
410,88613 ms0.18 ms
591,298120 ms2.0 ms
6285,698919 ms14 ms

Two lessons that are easy to miss:

A dedicated graph store earns its place when relationship queries are the core of the product (recommendations, fraud rings, access-control graphs of unbounded depth), when they go deeper than a few hops, or when the queries are awkward to express as joins. For "show my friends' posts", you do not need one.

6. Search: an inverted index, not a LIKE

Looking for a word inside text is a different problem from looking for a value in a column. Matching LIKE '%word%' cannot use an ordinary index, so it reads every row. A search index (an inverted index) stores, for every word, the list of documents containing it, so a query reads only those lists.

The experiment uses 500,000 documents of 40 words each (197 MB), in PostgreSQL:

QueryTime
LIKE '%word%', no index383 ms
Full-text search with a GIN index, one term1.7 ms
Full-text search, two terms with OR, ranked, best ten3.5 ms

The index took 13 seconds to build and 90 MB of space, and the search is more than 200 times faster. Notice what this says about the decision: a general-purpose database with a text index already handles a lot. A dedicated search engine (Elasticsearch, OpenSearch, Solr) is worth its operational cost when you need what the built-in features do not give: relevance tuning, typo tolerance, language analysis for many languages, facets and filters on large result sets, autocomplete, or a corpus too large for one node.

Remember what a search engine is not: it is rarely the source of truth. It is typically fed from the primary database (section 9), can lag behind it, and may lose or reorder updates in ways you would not accept for orders. Treat it as a derived, rebuildable view.

7. Columnar stores: the layout fits the question

A row-oriented database keeps all fields of a record together, which is ideal for "fetch this order" and for updating one record. An analytical query, "sum the price of every order over 900 in this region", needs two columns out of ten, and a row layout drags the other eight through memory too. A column-oriented store keeps each column together, so the query reads only what it needs, and similar values next to each other compress well.

The Go experiment holds 10,000,000 rows of 10 integers (800 MB) in memory in both layouts, on one thread:

OperationRow layoutColumn layout
SUM(c3) WHERE c7 > 900 (2 columns of 10)78 ms26 ms (3.0 times faster)
Read all 10 fields of 1,000,000 random rows47 ms (3.3 times faster)156 ms

Each layout wins at the other's weakness, by a factor of about three here. Real analytical systems do better than this model because they also compress columns and process them in batches, so the gap on disk with billions of rows is much larger; but the principle is the same one. The practical consequence is architectural: do not run heavy analytics on your transactional database (it slows down the users), and do not use a columnar store as the application's main database (single-row reads and updates are its weak spot). Replicate the data into an analytical store instead.

8. The rest: time series, objects, caches, vectors

9. One system of record, and derived stores around it

Real systems seldom end up with one database. They end up with one place where each fact is written and kept correct (the system of record, usually relational), and derived stores that serve other access patterns: a search index, a cache, an analytical warehouse, a recommendation graph. The derived stores can be rebuilt from the record at any time, which is what makes them safe to experiment with.

Diagram: One system of record, several derived stores

The rule that keeps this safe is write to one place first. If the application writes the order to the database and also to the search index as two independent steps, one of them will eventually fail and the two will disagree for good. Instead, write only to the system of record, and record the change in an outbox table in the same transaction; a relay publishes it to the derived stores, which apply it idempotently. That is exactly the pattern, with its failure analysis, in the guide on idempotency and exactly-once effects.

What this costs: derived stores are eventually consistent (a new product may take a second to appear in search), you operate more systems, and you need a way to rebuild each one. What it buys is that each access pattern gets the structure that serves it, without making any of them the place where correctness lives.

10. When one machine is not enough

A single well-configured relational server handles more than most products ever need. The capacity estimation guide shows what one small machine does; a server with several fast disks and a lot of memory does far more. Before distributing anything, check three cheaper steps in order:

  1. Indexes and queries. Most slowness is a missing index or a bad query, as the measurements above show (160 ms against 0.1 ms).
  2. Read replicas and caching. Reads usually dominate; replicas and a cache scale them without changing the data model.
  3. Partitioning inside one database, by time or by tenant, which keeps working sets small.

Only when writes or data exceed one machine do you need a database that spreads the data across nodes, and you then choose between two paths:

In either case, the lesson of the capacity guide applies: the choice follows from the numbers (writes per second, data size, the distance between regions), not from the fashion.

11. A set of questions to decide with

Run through these in order. Most designs are settled within the first three.

Diagram: A decision path for the system of record

  1. What is the system of record, and what must never be wrong? Choose the store where correctness is cheapest, almost always relational.
  2. What are the three or four most frequent and most important access patterns? Check that your candidate answers each of them by an index or a key, not by scanning.
  3. How big, and how fast does it grow? Do the arithmetic (capacity estimation) before saying "we need scale".
  4. What happens when a question is asked that you did not plan for? If the answer is "write a new table and backfill", be sure you accept that.
  5. What consistency does each read need? A bank balance must be current; a like count may be a few seconds old.
  6. Who will run it, and what do you already know? An unfamiliar database means unfamiliar failures at three in the morning.
  7. How do you get out? Data export, schema evolution and the ability to rebuild derived stores determine whether a wrong choice is cheap to fix.

Worked decisions

12. Boring technology and innovation tokens

Every database you add brings operational work (backups, upgrades, monitoring, on-call knowledge), its own failure modes, and its own consistency rules, and teams routinely underestimate it. Dan McKinley's "Choose Boring Technology" gives the useful frame: a team has only a few innovation tokens, and each new, unproven technology spends one. Spend them on what makes your product different, and use well-understood tools for everything else. A second database must therefore earn its place with a measured need: a query that is too slow after indexing, a volume the first system cannot take, a feature it cannot offer.

This does not mean "never leave PostgreSQL". It means that the burden of proof is on the new system, and that the decision is made with numbers, such as the ones in this guide.

13. Common mistakes

14. Things to mention in an interview

Quick recap

Appendix: the experiment code

Four sets of programs produced the numbers. orders.sql creates the orders as tables and as documents and holds the queries (time them with pgbench -n -T 5 -c 1 -f query.sql, using \set id random(1,1000000) at the top of each query file). graph.sql and bfs.go build the follower graph and traverse it (export the edges to edges.csv as the comment in graph.sql says, then run go run . in a directory with bfs.go renamed to main.go). fts.sql compares LIKE with a GIN-indexed full-text search. scan.go compares row and column layouts in memory. In the SQL files, the statements that use a colon variable (:id, :c, :p, :s, :h, :t, :u) are written as comments, because they are pgbench templates; remove the leading -- to use them.

orders.sql

-- 1. Orders as tables and as JSON documents. Run with psql -f; about a minute for 1,000,000 orders. Lines starting "-- SELECT" use pgbench variables (:id, :c, :p) and are meant for pgbench.
SET max_parallel_workers_per_gather = 0;
DROP TABLE IF EXISTS order_items, orders, orders_doc;
CREATE TABLE orders (
  id bigint PRIMARY KEY, customer_id int NOT NULL, status text NOT NULL, created_at timestamptz NOT NULL, total int NOT NULL DEFAULT 0);
CREATE TABLE order_items (
  order_id bigint NOT NULL REFERENCES orders(id), line int NOT NULL, product_id int NOT NULL, qty int NOT NULL, price int NOT NULL,
  PRIMARY KEY (order_id, line));
INSERT INTO orders (id, customer_id, status, created_at)
SELECT g, 1 + floor(random() * 100000)::int, (ARRAY['new','paid','shipped','delivered'])[1 + floor(random() * 4)::int],
       timestamptz '2026-10-26' - (random() * 365 || ' days')::interval
FROM generate_series(1, 1000000) g;
INSERT INTO order_items (order_id, line, product_id, qty, price)
SELECT o.id, l, 1 + floor(random() * 5000)::int, 1 + floor(random() * 3)::int, 100 + floor(random() * 9900)::int
FROM orders o, LATERAL generate_series(1, 1 + (o.id % 5)::int) l;                 -- 1 to 5 items, 3 on average
UPDATE orders o SET total = s.t FROM (SELECT order_id, sum(qty * price) t FROM order_items GROUP BY 1) s WHERE s.order_id = o.id;
CREATE INDEX orders_customer ON orders (customer_id);

CREATE TABLE orders_doc (id bigint PRIMARY KEY, doc jsonb NOT NULL);
INSERT INTO orders_doc
SELECT o.id, jsonb_build_object('customer_id', o.customer_id, 'status', o.status, 'created_at', o.created_at, 'total', o.total,
         'items', (SELECT jsonb_agg(jsonb_build_object('product_id', i.product_id, 'qty', i.qty, 'price', i.price) ORDER BY i.line)
                   FROM order_items i WHERE i.order_id = o.id))
FROM orders o;
VACUUM ANALYZE;

-- Indexes added during the measurements (each was timed before and after):
CREATE INDEX od_cust ON orders_doc (((doc->>'customer_id')::int));      -- document: orders of one customer
CREATE INDEX oi_prod ON order_items (product_id);                       -- tables: lines of one product
CREATE INDEX od_gin ON orders_doc USING gin (doc jsonb_path_ops);       -- document: "orders containing product X"

-- Queries, timed with pgbench -n -T 5 -c 1 and a random :id, :c or :p each time
-- SELECT o.*, i.* FROM orders o JOIN order_items i ON i.order_id = o.id WHERE o.id = :id;      -- tables, one order
-- SELECT doc FROM orders_doc WHERE id = :id;                                                      -- document, one order
-- SELECT id, total FROM orders WHERE customer_id = :c;                                            -- tables, by customer
-- SELECT id, doc->'total' FROM orders_doc WHERE (doc->>'customer_id')::int = :c;                  -- document, by customer
-- SELECT count(*) FROM order_items WHERE product_id = :p;                                         -- tables, by product
-- SELECT count(*) FROM orders_doc
--  WHERE doc @> jsonb_build_object('items', jsonb_build_array(jsonb_build_object('product_id', :p)));  -- document, by product

-- Revenue by product (the whole data set), best of several runs, no parallel workers
SET max_parallel_workers_per_gather = 0;
SELECT product_id, sum(qty * price) r FROM order_items GROUP BY 1 ORDER BY r DESC LIMIT 3;
SELECT (i->>'product_id')::int p, sum((i->>'qty')::int * (i->>'price')::int) r
FROM orders_doc, jsonb_array_elements(doc->'items') i GROUP BY 1 ORDER BY r DESC LIMIT 3;

graph.sql

-- 2. A follower graph: 300,000 users, about 10 follows each (3,000,000 edges). The recursive query at the end uses pgbench variables (:s, :h).
DROP TABLE IF EXISTS follows;
CREATE TABLE follows (src int NOT NULL, dst int NOT NULL, PRIMARY KEY (src, dst));
INSERT INTO follows SELECT DISTINCT s, d FROM (SELECT s, 1 + floor(random()*300000)::int d FROM generate_series(1,300000) s, generate_series(1,10) k) x WHERE s <> d;
VACUUM ANALYZE follows;
SELECT count(*) edges FROM follows;
-- Export the edges for the Go program:  psql -Atc "COPY follows TO STDOUT CSV" > edges.csv

-- Everyone within :h hops of user :s (timed with pgbench for h = 2 to 6)
-- WITH RECURSIVE r(n, depth) AS (
--   SELECT :s::int, 0
--   UNION
--   SELECT f.dst, r.depth + 1 FROM r JOIN follows f ON f.src = r.n WHERE r.depth < :h
-- )
-- SELECT count(DISTINCT n) FROM r;

bfs.go

package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	const N = 300001
	adj := make([][]int32, N)
	f, _ := os.Open("edges.csv")
	sc := bufio.NewScanner(f)
	t0 := time.Now()
	edges := 0
	for sc.Scan() {
		p := strings.Split(sc.Text(), ",")
		a, _ := strconv.Atoi(p[0])
		b, _ := strconv.Atoi(p[1])
		adj[a] = append(adj[a], int32(b))
		edges++
	}
	fmt.Printf("loaded %d edges in %v\n", edges, time.Since(t0))
	for _, h := range []int{2, 3, 4, 5, 6} {
		seen := make([]int32, N)
		rand.Seed(1)
		const runs = 2000
		total := 0
		t := time.Now()
		for i := 1; i <= runs; i++ {
			s := int32(1 + rand.Intn(300000))
			seen[s] = int32(i)
			fr := []int32{s}
			cnt := 1
			for d := 0; d < h; d++ {
				var nx []int32
				for _, u := range fr {
					for _, v := range adj[u] {
						if seen[v] != int32(i) {
							seen[v] = int32(i)
							nx = append(nx, v)
							cnt++
						}
					}
				}
				fr = nx
			}
			total += cnt
		}
		el := time.Since(t)
		fmt.Printf("hops=%d: %.3f ms per query, %d nodes reached on average\n", h, float64(el.Microseconds())/1000/runs, total/runs)
	}
}

fts.sql

-- 3. Full-text search over 500,000 documents of 40 words from a skewed 20,000-word vocabulary. The queries that use :t and :u are for pgbench.
DROP TABLE IF EXISTS articles;
CREATE TABLE articles AS
SELECT d AS id, string_agg('word' || wid, ' ') AS body
FROM (SELECT d, 1 + floor(power(random(), 3) * 20000)::int AS wid FROM generate_series(1,500000) d, generate_series(1,40) k) x
GROUP BY d;
ALTER TABLE articles ADD PRIMARY KEY (id);
VACUUM ANALYZE articles;
SELECT count(*) docs, pg_size_pretty(pg_total_relation_size('articles')) size FROM articles;

-- Without an index (term is a random 'word10000'..'word19999', :t is the number)
-- SELECT count(*) FROM articles WHERE body LIKE '%word' || :t || '%';

-- With a stored tsvector and a GIN index
ALTER TABLE articles ADD COLUMN tsv tsvector GENERATED ALWAYS AS (to_tsvector('simple', body)) STORED;
CREATE INDEX articles_tsv ON articles USING gin (tsv);
VACUUM ANALYZE articles;
-- SELECT count(*) FROM articles WHERE tsv @@ to_tsquery('simple', 'word' || :t);

-- Two terms, ranked, best ten
-- SELECT id FROM articles
-- WHERE tsv @@ to_tsquery('simple', 'word' || :t || ' | word' || :u)
-- ORDER BY ts_rank(tsv, to_tsquery('simple', 'word' || :t || ' | word' || :u)) DESC LIMIT 10;

scan.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const N = 10_000_000

type Row [10]int64

func best(f func() int64) (time.Duration, int64) {
	var b time.Duration = 1 << 62
	var r int64
	for i := 0; i < 5; i++ {
		t := time.Now()
		r = f()
		if d := time.Since(t); d < b {
			b = d
		}
	}
	return b, r
}

func main() {
	rows := make([]Row, N)
	var cols [10][]int64
	for c := range cols {
		cols[c] = make([]int64, N)
	}
	rng := rand.New(rand.NewSource(1))
	for i := 0; i < N; i++ {
		for c := 0; c < 10; c++ {
			v := rng.Int63n(1000)
			rows[i][c] = v
			cols[c][i] = v
		}
	}
	// Analytics: SUM(c3) WHERE c7 > 900  (touches 2 of 10 columns)
	dr, sr := best(func() (s int64) {
		for i := range rows {
			if rows[i][7] > 900 {
				s += rows[i][3]
			}
		}
		return
	})
	dc, sc := best(func() (s int64) {
		a, b := cols[3], cols[7]
		for i := range b {
			if b[i] > 900 {
				s += a[i]
			}
		}
		return
	})
	fmt.Printf("SUM(c3) WHERE c7>900, %d rows x 10 int64 (%d MB of data)\n  row layout:    %7.1f ms (%.1f GB/s of memory touched)\n  column layout: %7.1f ms   -> %.1fx faster, results equal: %v\n",
		N, N*80/1_000_000, ms(dr), float64(N*80)/dr.Seconds()/1e9, ms(dc), dr.Seconds()/dc.Seconds(), sr == sc)
	// Fetch whole rows by random id (OLTP): 1,000,000 random full-row reads
	ids := make([]int, 1_000_000)
	for i := range ids {
		ids[i] = rng.Intn(N)
	}
	dr2, a := best(func() (s int64) {
		for _, id := range ids {
			r := &rows[id]
			for c := 0; c < 10; c++ {
				s += r[c]
			}
		}
		return
	})
	dc2, b := best(func() (s int64) {
		for _, id := range ids {
			for c := 0; c < 10; c++ {
				s += cols[c][id]
			}
		}
		return
	})
	fmt.Printf("fetch all 10 fields of 1,000,000 random rows\n  row layout:    %7.1f ms\n  column layout: %7.1f ms   -> row layout %.1fx faster, results equal: %v\n", ms(dr2), ms(dc2), dc2.Seconds()/dr2.Seconds(), a == b)
}
func ms(d time.Duration) float64 { return float64(d.Microseconds()) / 1000 }

Sources

Practise this topic: Databases

More guides