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:
| Question | Shape | Frequency |
|---|---|---|
| Show order 8213 with its lines | fetch one record by key, with its children | very high |
| Show all orders of customer 77 | list by a secondary attribute | high |
| Reserve stock and create the order, or neither | write several records atomically | high |
| Revenue per product last quarter | scan and aggregate everything | low, but heavy |
| Search products by words in the name | text matching and ranking | high |
| People who bought this also bought… | traversal over relationships | medium |
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:
- How much data, and how fast does it grow? Gigabytes fit on one machine and make almost any choice work. Terabytes of hot data, or write rates beyond one machine's disk, force partitioning, and partitioning changes which queries stay cheap.
- Who needs the data to be correct, and how correct? Money and stock need atomic updates and constraints. A view counter can lose a few increments.
- How will the questions change? A product in its first year invents new questions every week. Some databases make a new question cheap (add an index, write a query) and some make it a redesign.
2. The families, in one table
| Family | The data looks like | Strong at | Weak at | Typical examples |
|---|---|---|---|---|
| Relational (SQL) | tables with typed columns, related by keys | transactions, constraints, joins, ad hoc queries | one machine's limits (without extra work), deep graph traversal | PostgreSQL, MySQL |
| Document | self-contained JSON-like records | fetch a whole aggregate in one read, flexible fields | cross-document joins and transactions, ad hoc analysis | MongoDB, Couchbase |
| Key-value | an opaque value behind a key | the simplest, fastest lookups; easy to partition | any question that is not "give me the value for this key" | Redis, DynamoDB (basic use) |
| Wide-column | rows grouped by a partition key and sorted inside it | huge write volume, range reads inside a partition, scale-out | queries that do not match the table's key design, joins | Cassandra, Bigtable, DynamoDB |
| Graph | nodes and edges with properties | many-hop relationship queries | bulk aggregation, partitioning a highly connected graph | Neo4j and similar |
| Search | an inverted index over text | words, ranking, typo tolerance, facets | being the source of truth, transactions | Elasticsearch, OpenSearch, Solr |
| Time series | measurements with timestamps | huge append rates, time-window queries, retention, downsampling | updating old points, general-purpose queries | TimescaleDB, InfluxDB, Prometheus |
| Columnar / analytical | the same table, stored by column | scanning and aggregating a few columns of billions of rows | single-row reads and updates | ClickHouse, BigQuery, Redshift |
| Object store | files (blobs) by name | cheap, durable storage of large things | queries inside the files, low-latency small reads | S3 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:
- Transactions (ACID): several changes happen together or not at all, and concurrent users do not see half-done work.
- 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.
- 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.
- 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).
| Question | Tables | Documents |
|---|---|---|
| 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 customer | 0.106 ms | 0.127 ms (index on an expression of the JSON) |
| Orders of one customer, no index | 160 ms | |
| Orders containing a product, no index | 103 ms | 1,135 ms |
| Orders containing a product, with an index | 0.123 ms (B-tree, 20 MB) | 4.0 ms (GIN index, 74 MB) |
| Revenue per product, whole data set | 0.52 to 0.56 s | 2.8 to 3.0 s |
| Size on disk (data and indexes) | 418 MB | 435 MB |
Four conclusions follow, and they are the heart of the "document or relational" debate:
- Embedding wins for reading one aggregate. One read returns the order and its lines, with no join: here 1.6 times faster. This is what documents are for, and it matters more when the pieces would live on different machines.
- Without a matching index, a document store is a full scan. 160 ms for a lookup that takes 0.1 ms with an index, over only a million small documents. This is not a flaw of documents; it is what every database does when no structure serves the question. It is a flaw of the habit of choosing a store because "it needs no schema" and then asking questions it was not shaped for.
- Questions across documents cost more. Counting by a value inside nested arrays needed a larger and slower index, and aggregating over the whole data set was about five times slower than over the tables, because every document has to be opened and parsed.
- Size is not the argument. Both layouts took about the same space here. "Documents are more compact" and "tables are more compact" are both folklore.
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:
- Predictable single-digit-millisecond access by key at almost any size, with capacity that is added by adding machines.
- Very high write rates. Wide-column stores typically append to a log-structured storage engine, which turns random writes into sequential ones.
- Range reads inside a partition (all messages of a conversation, in time order) because the rows in a partition are stored sorted.
What it costs:
- Every access pattern must be designed in advance, usually as its own table or index, keyed for that query. A new question is a new table and a backfill, not an
EXPLAINand an index. - Transactions are limited. They are either absent or restricted: DynamoDB, for example, offers transactions of at most 100 items and 4 MB in total, no transactions that span regions in a global table, and none through secondary indexes. Check what your chosen store promises before you build on "we will just use a transaction".
- Hot keys. If one partition key takes a disproportionate share of traffic (a celebrity's feed, a global counter), the partition becomes the bottleneck, and adding machines does not help.
- Weak ad hoc analysis. Anything that scans a lot is slow or expensive, which is why such stores are usually paired with an analytical store.
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.
| Hops | Users reached (average) | PostgreSQL, recursive query | Go, adjacency lists in memory |
|---|---|---|---|
| 2 | 110 | 0.33 ms | 0.004 ms |
| 3 | 1,108 | 1.7 ms | 0.027 ms |
| 4 | 10,886 | 13 ms | 0.18 ms |
| 5 | 91,298 | 120 ms | 2.0 ms |
| 6 | 285,698 | 919 ms | 14 ms |
Two lessons that are easy to miss:
- The relational database is fine for a few hops. Three hops over three million edges took under two milliseconds. Many "we need a graph database" decisions are made for graphs that PostgreSQL traverses comfortably.
- The cost is set by how many nodes the traversal reaches, in any system. Each extra hop reaches roughly ten times more users and costs roughly eight times more, in both columns, until the traversal covers most of the graph: hop six reaches 95% of all users, and no database makes that cheap. Specialised graph databases help with the constant (the in-memory adjacency lists here were 60 to 80 times faster per query) and with a graph query language, but they do not change the fact that dense graphs explode.
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:
| Query | Time |
|---|---|
LIKE '%word%', no index | 383 ms |
| Full-text search with a GIN index, one term | 1.7 ms |
| Full-text search, two terms with OR, ranked, best ten | 3.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:
| Operation | Row layout | Column layout |
|---|---|---|
SUM(c3) WHERE c7 > 900 (2 columns of 10) | 78 ms | 26 ms (3.0 times faster) |
| Read all 10 fields of 1,000,000 random rows | 47 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
- Time series. Metrics and sensor data are append-heavy, queried by time window, and are deleted or downsampled by age. Dedicated stores (or a time-series extension of a relational database) partition by time, which makes retention a cheap "drop a partition" and recent-window queries fast.
- Object storage. Photos, videos, backups and exports belong in an object store, with only the reference (key, size, content type) in the database. Putting large blobs in database rows makes backups, replication and caches all heavier.
- Caches. An in-memory key-value store in front of the database absorbs repeated reads. It is derived data: it can always be rebuilt, so the question is only what happens on a miss and how stale an answer may be.
- Vector search. Similarity search over embeddings is offered by dedicated stores and by extensions of general-purpose databases. As with text, start with what the existing database can do, and move out when the volume or latency demands it.
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:
- Indexes and queries. Most slowness is a missing index or a bad query, as the measurements above show (160 ms against 0.1 ms).
- Read replicas and caching. Reads usually dominate; replicas and a cache scale them without changing the data model.
- 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:
- Give up some of the relational model for a key-value or wide-column store (section 4), and design your access patterns around the partition key.
- Keep SQL and transactions and pay for distribution. "NewSQL" systems (Spanner and its relatives, among them CockroachDB and YugabyteDB) partition the data across machines and still offer SQL with distributed transactions. Spanner, for example, uses synchronized clocks (TrueTime) to give transactions external consistency. The price is latency: a transaction that must be agreed by replicas in several places waits for a network round trip each time, and a design that keeps a transaction inside one partition stays much faster than one that spans many.
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
- What is the system of record, and what must never be wrong? Choose the store where correctness is cheapest, almost always relational.
- 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.
- How big, and how fast does it grow? Do the arithmetic (capacity estimation) before saying "we need scale".
- 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.
- What consistency does each read need? A bank balance must be current; a like count may be a few seconds old.
- Who will run it, and what do you already know? An unfamiliar database means unfamiliar failures at three in the morning.
- 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
- An online shop. Orders, stock, payments and customers are related, need transactions and constraints, and the questions keep changing: a relational database. Product search starts as the database's full-text feature and moves to a search engine when relevance tuning matters. Product images go to object storage. Reporting runs on a replica or an analytical store.
- Chat messages. The dominant access is "the latest messages in this conversation, in order", at very high write rate and volume, with almost no joins: a wide-column or key-value store partitioned by conversation, sorted by time. Users, groups and billing stay in a relational database.
- Product analytics (billions of events). Append-only, queried by scanning and aggregating a few columns: a columnar store, fed from a queue. Never the transactional database.
- "People you may know". Relationship queries of two or three hops fit a relational database up to a point (section 5); a graph store pays off when depth grows or the graph is the product.
- A prototype with unknown requirements. A relational database, because new questions are cheap. The schema is a feature while you are still learning.
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
- Choosing by popularity or by the last conference talk instead of by access patterns.
- Choosing "schemaless" to avoid design. The schema does not disappear; it moves into the application code, scattered and unchecked, and you meet it again when old documents have a different shape from new ones.
- Asking a store questions it was not shaped for and then blaming the store: scanning a key-value store, or querying nested documents without an index.
- Using the cache or the search index as the source of truth. They are rebuildable views; if you cannot rebuild one, it has become a database without a backup.
- Writing to two stores from the application without an outbox, and trusting that both writes will succeed.
- Assuming transactions exist everywhere. Check the limits of the one you use: items per transaction, whether it crosses partitions or regions, whether indexes take part.
- Putting large files in the database, or running heavy analytics on the transactional database.
- Distributing too early. A partitioned database is harder to query, change and operate; do it when the numbers demand it.
- Believing a benchmark that does not look like your workload. The ratios in this guide change with data size, shape and hardware; measure with your own queries.
14. Things to mention in an interview
- Start by asking for the access patterns, the scale and the consistency needs, and say that the choice follows from them.
- State a default and justify it: relational as the system of record, because of transactions, constraints, ad hoc queries and cheap new indexes.
- Name the trade-off of each family in one sentence: key-value and wide-column trade query flexibility and transactions for scale; documents trade joins for reading an aggregate in one read; search engines and columnar stores are derived views; graph stores matter when depth does.
- Explain derived stores and the outbox: one place of truth, and everything else rebuildable and eventually consistent.
- Use numbers: a lookup without an index is a scan (orders of magnitude slower), and graph cost grows with the nodes reached, not with the product name.
- Mention the limits of transactions in the store you propose, and what you would do when a transaction must cross partitions.
- Show restraint: innovation tokens, and when you would split off a second database (a measured need, not a guess).
Quick recap
- Choose by access patterns first. Write the questions, their frequency and the data volume before naming a product.
- Relational by default for the system of record: transactions, constraints, joins, and indexes that can be added later. Documents win when you read one aggregate; embed what is read and changed together.
- No matching index means a scan in any database: 160 ms against 0.1 ms in the measurement.
- Key-value and wide-column buy scale by fixing the questions in advance and limiting transactions; graph, search and columnar stores are specialised structures for relationship, text and scan-heavy questions.
- Derived stores are views. Write to the system of record, feed the others through an outbox, and be able to rebuild them.
- Distribute last: indexes, then replicas and caches, then partitioning, then a distributed database.
- Each new database must earn its place with a measured need.
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
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), chapter 2 "Data Models and Query Languages", chapter 3 "Storage and Retrieval" (row against column storage, log-structured engines) and chapter 7 "Transactions".
- Dan McKinley, Choose Boring Technology (2015), on innovation tokens.
- PostgreSQL documentation: JSON types and GIN indexes, full text search and recursive queries (WITH).
- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007.
- Fay Chang et al., Bigtable: A Distributed Storage System for Structured Data, OSDI 2006.
- James C. Corbett et al., Spanner: Google's Globally Distributed Database, OSDI 2012 (TrueTime and external consistency).
- Amazon DynamoDB Developer Guide, Working with transactions (item and size limits, no cross-region transactions in global tables).
- Alex Petrov, Database Internals (O'Reilly, 2019), on storage engines and distributed transactions.
Practise this topic: Databases