Databases: SQL, NoSQL, indexes and sharding

The orders screen takes 9 seconds to load. The table has 20 million rows, and the query reads all of them to find one customer’s last ten orders. One CREATE INDEX later, it takes 4 milliseconds. Databases reward knowing how they find data, and punish not knowing it, quietly at first and then all at once when the data grows.

New to some of these? Open what you need, or skip ahead.

Basics:What are databases, tables and SQL?

A database stores an app’s data so it survives restarts and can be searched quickly. A relational database (PostgreSQL, MySQL) keeps data in tables: rows (one per book, user or order) and columns (id, title, year).

You talk to it with SQL: SELECT title FROM books WHERE year > 2000 reads, INSERT, UPDATE and DELETE change data. Rows refer to other tables through foreign keys (book.author_id points to a row in author), and indexes make lookups by a column fast.

Basics:What is JSON?

JSON is the text format most APIs use to send data. Objects are written in braces with "key": value pairs, lists in square brackets:

{ "id": 7, "name": "Mug", "price": 9.5, "tags": ["kitchen", "gift"], "discount": null }

Values can be strings (in quotes), numbers, true/false, null, objects or lists. Turning JSON into your own types is called decoding (or parsing, or deserializing); the opposite is encoding.

Basics:What does O(n) mean?

Big-O describes how the amount of work grows with the size of the input n:

O(1): the same work whatever the size (reading array[5]).
O(log n): grows very slowly (about 20 steps for a million items).
O(n): grows in step with the input (one pass over the array).
O(n²): comparing every item with every other item, which gets slow fast.

You’ll see it next to every solution, for time and for extra space (memory). The Big-O tutorial explains it properly.

Part Not started

SQL or NoSQL?

Imagine two ways to keep customer records. One office uses a filing cabinet with forms: every customer has a form with the same fields, orders are on separate forms that say which customer they belong to, and a clerk can answer any question (“all customers in Novi Sad who ordered last week”) by cross-referencing. The other office keeps one folder per customer with everything inside: ask for a customer and you get the whole folder instantly, but “everyone who ordered last week” means opening every folder.

The first is a relational (SQL) database. The second is a document database, one kind of NoSQL database. Neither is better; they’re good at different questions.

The choice is about access patterns, consistency and scale, not fashion. Relational databases give you a normalized model, ad hoc queries, joins, constraints and multi-row ACID transactions, and scale vertically and with read replicas a long way. NoSQL stores trade query flexibility for predictable performance at scale on known access patterns: you design the data around the queries (denormalized, partitioned by key), often with weaker consistency or transaction scope. PostgreSQL with JSONB covers many “we need a document store” cases.

Type	Examples	Good at	Weak at
Relational	PostgreSQL, MySQL	Related data, any query, transactions, constraints	Massive write scale on one node
Document	MongoDB, Firestore	Reading/writing whole objects; flexible shape	Joins and queries across many documents
Key-value	Redis, DynamoDB	Very fast lookups by key, huge scale	Anything except lookups by key
Wide-column	Cassandra, ScyllaDB	Huge write volume, time series, partitioned by key	Ad hoc queries, transactions
Search	Elasticsearch, OpenSearch	Full-text search, filters, ranking	Being the source of truth

The same order, two ways

-- Relational: separate tables, linked by keys
CREATE TABLE customers (id BIGINT PRIMARY KEY, name TEXT NOT NULL, city TEXT);
CREATE TABLE orders (
    id          BIGINT PRIMARY KEY,
    customer_id BIGINT NOT NULL REFERENCES customers(id),
    created_at  TIMESTAMPTZ NOT NULL,
    total_cents INT NOT NULL
);
CREATE TABLE order_items (
    order_id   BIGINT REFERENCES orders(id),
    product_id BIGINT NOT NULL,
    quantity   INT NOT NULL
);

-- Any question, by joining:
SELECT c.city, SUM(o.total_cents)
FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.created_at > now() - interval '7 days'
GROUP BY c.city;

{
  "_id": "order-1001",
  "customer": { "id": 42, "name": "Ana", "city": "Novi Sad" },
  "createdAt": "2026-11-08T10:15:00Z",
  "items": [
    { "productId": 7, "name": "Mug", "quantity": 2, "priceCents": 950 }
  ],
  "totalCents": 1900
}

In the document version, showing an order is one read. But the customer’s name is copied into every order: if Ana changes her name, every order document has the old one (sometimes that’s what you want, like on an invoice; sometimes it isn’t). In the relational version, the name lives in one place, and a join brings it in when needed.

A good default for a new app is a relational database like PostgreSQL. Reach for something else when you have a specific need it can’t meet: enormous write volume, a key-value lookup at huge scale, full-text search.

Exerciseeasy

Pick a database

For each feature of a food delivery app, pick a kind of database and give one reason:

Orders, payments and refunds
The courier’s current location, updated every 4 seconds
Searching restaurants by dish name, with typos (“piza”)
A user’s session and shopping cart

›

Ask what each feature does most: complex queries and correctness, lots of tiny writes where only the latest matters, text search, or quick lookups by one key.

SolutionTry it yourself first

Relational (PostgreSQL): money needs transactions (an order and its payment succeed or fail together), constraints, and flexible reporting queries.
Key-value in memory (Redis), keyed by courier: only the latest position matters, writes are tiny and frequent, and Redis has geo commands for “couriers near me”. History, if needed, goes to cheaper storage asynchronously.
A search engine (Elasticsearch/OpenSearch): full-text matching, typo tolerance and ranking; it’s fed from the main database and isn’t the source of truth.
Key-value (Redis) with a TTL: looked up by one key on every request, and losing it occasionally isn’t a disaster.

Real systems use several databases, each for what it’s good at, with one clear source of truth per piece of data.

Modeling for NoSQL

NoSQL modeling starts from the query list, not the entities: “get order by id”, “list a customer’s orders newest first”, “all orders for a restaurant today”. Each query maps to a key design: a partition key (which node) and a sort key (order within the partition), with data denormalized so each query reads one partition. That’s how DynamoDB single-table designs and Cassandra tables work: a new query often means a new table or index, populated by duplicating writes. It scales predictably, and it makes unplanned queries expensive, which is the honest trade-off to state in an interview.

Deep diveACID, BASE and what 'NoSQL has no transactions' really meansInterview favorite

ACID (atomicity, consistency, isolation, durability) describes relational transactions: several rows change together or not at all, and concurrent transactions don’t see each other’s half-done work, at a configurable isolation level (PostgreSQL defaults to READ COMMITTED, not SERIALIZABLE). BASE (“basically available, soft state, eventually consistent”) described early distributed stores that gave up cross-node transactions for availability. Today the line is blurry: MongoDB and DynamoDB have multi-document transactions (with limits), and distributed SQL databases (CockroachDB, Spanner, YugabyteDB) offer serializable transactions across nodes at higher latency. The useful interview answer names the transaction scope you need (“these three writes must be atomic”) and picks a store that provides it.

Choose by access patterns, transaction scope and scale. Relational (PostgreSQL) is the default: joins, constraints, ad hoc queries, ACID; JSONB covers many document needs.
Document/key-value/wide-column: data modeled around known queries (partition key + sort key, denormalized); unplanned queries are expensive.
Search engines and caches are derived stores, never the source of truth.
Polyglot persistence is normal; keep one source of truth per datum and sync derived stores (CDC, outbox).

Check this part

Orders and payments must succeed or fail together, and the business wants flexible reports. Which kind of database?
Transactions, constraints and ad hoc queries are what relational databases are built for.
What is a drawback of copying the customer's name into every order document?
Denormalized data is fast to read and must be updated in many places, or deliberately left as a snapshot.
How is data modeled in a store like DynamoDB or Cassandra?
Predictable at scale; new queries often need new tables or indexes.

Relational databases store related tables and answer flexible queries with transactions; document, key-value and wide-column stores are built for specific access patterns at scale. Choose by how the data is read and written; a relational database is the right default for most apps.

Part Not started

Indexes: finding rows without reading them all

To find “recursion” in a 600-page book, you don’t read every page: you look it up in the index at the back, which is sorted alphabetically and tells you the page. Without the index, you’d have to read the whole book.

A database index is the same: a sorted structure on one or more columns that points to the matching rows. Without one, the database reads the entire table (a full scan). With one, it finds rows in a few steps, even among millions.

Most indexes are B-trees: sorted, balanced, O(log n) lookups and range scans, ordered by the indexed columns left to right. A composite index on (a, b, c) serves predicates on a, a, b, a, b, c and sorts in that order, but not b alone (the leftmost-prefix rule). Covering indexes (INCLUDE columns) answer queries without touching the table. Every index costs write amplification and storage, and the planner may still choose a scan when a predicate matches a large share of rows. EXPLAIN (ANALYZE, BUFFERS) is the ground truth.

An index for a customer's recent orders

-- The query the orders screen runs:
SELECT id, created_at, total_cents
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 10;

-- Without an index: reads all 20 million rows, sorts the matches, keeps 10.
-- With this index: jumps to customer 42's entries, already sorted by date, reads 10.
CREATE INDEX orders_customer_created ON orders (customer_id, created_at DESC);

-- Check what the database actually does:
EXPLAIN ANALYZE
SELECT id, created_at, total_cents FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 10;
-- Index Scan using orders_customer_created on orders … (actual time=0.03..0.05 rows=10)

The index has two columns, in a deliberate order: first customer_id (to find this customer’s orders), then created_at (so they’re already sorted newest first). The database reads exactly the ten rows it needs.

Indexes aren’t free: every INSERT and UPDATE must update every index on the table too, and they take disk space. Add them for the queries your app actually runs, not for every column.

Spot the bugThe admin report that scans everything

Tap the line with the bug.

CREATE INDEX orders_customer_created ON orders (customer_id, created_at);

-- Admin dashboard: today's orders, newest first
SELECT id, customer_id, total_cents
FROM orders
WHERE created_at >= current_date
ORDER BY created_at DESC;

The index is sorted by customer_id first. Today’s orders are scattered across every customer’s section of it, so the index can’t jump to them: the query filters only on created_at, which is the second column. The database reads the whole table (or the whole index). A composite index helps queries that use its leftmost columns.

This query needs its own index, starting with the column it filters on:

CREATE INDEX orders_created ON orders (created_at DESC);

Run EXPLAIN on every query that matters: “Seq Scan on orders” on a big table is the warning sign.

Predict the output

A table has 10 million rows. Roughly how many steps does a lookup by an indexed column take, compared with a full scan?

Practice: indexes for a feature

List the queries the feature runs: “a user’s notifications, unread first, newest first”, “count of unread notifications”.
Look at the WHERE and ORDER BY: WHERE user_id = ? AND read = false ORDER BY created_at DESC.
Put equality filters first, then the sort column: (user_id, read, created_at DESC).
Check with EXPLAIN on realistic data, not an empty development database (the planner behaves differently on 50 rows).
Don’t index everything: a table with 12 indexes makes every insert update 12 structures.

When the planner ignores your index

Predict the output

orders has 20 million rows; 60% have status = 'delivered'. There's an index on status. What does PostgreSQL most likely do for SELECT * FROM orders WHERE status = 'delivered'?

Index design notes

Equality columns first, then range/sort columns. (tenant_id, created_at) serves “this tenant’s recent rows”; (created_at, tenant_id) doesn’t.
Functions defeat indexes: WHERE lower(email) = ? needs an expression index on lower(email) (or a case-insensitive column type).
Covering indexes (INCLUDE (total_cents)) avoid heap reads for hot queries; index-only scans also need a well-vacuumed table.
Write cost: each index adds work to every insert/update and WAL volume; remove unused ones (pg_stat_user_indexes).
Build safely: CREATE INDEX CONCURRENTLY on live tables, or you lock writes for the duration.

B-tree: O(log n) lookups and ordered range scans; composite indexes follow the leftmost-prefix rule; order columns as equality → range/sort.
Planner chooses scans for unselective predicates; use partial or composite indexes for low-cardinality columns; expression indexes for lower(x).
Covering (INCLUDE) for hot reads; every index costs writes and storage; build with CONCURRENTLY; verify with EXPLAIN (ANALYZE, BUFFERS) on production-like data.

Check this part

What does an index let the database do?
Like a book's index, it's sorted, so lookups take a few steps.
An index on (customer_id, created_at). Which query can use it well?
A composite index helps queries that use its leftmost column.
Why might PostgreSQL ignore an index on status for status = 'delivered'?
Use partial or composite indexes for low-cardinality columns.
How do you add an index to a large, live PostgreSQL table without blocking writes?
It takes longer but doesn't hold a write lock for the whole build.

An index is a sorted lookup structure on columns, so the database can jump to matching rows instead of reading the whole table. A composite index helps only queries that use its leftmost columns. Indexes speed up reads and slow down writes; check plans with EXPLAIN.

Part Not started

Replicas and sharding

When one library branch gets too busy, there are two fixes. You can open copies of the branch with the same books, so more people can read at once, but new books arrive at the main branch first and reach the copies a little later. Or you can split the collection: A–M in one building, N–Z in another, so each building handles half the work, but a question that spans both needs two trips.

Databases scale the same two ways: replicas (copies, for more reads) and sharding (splitting the data, for more writes and more storage).

Replication scales reads and availability: a primary takes writes and streams changes to replicas, usually asynchronously, so replicas lag by milliseconds to seconds (more under load). Partitioning/sharding scales writes and data size: rows are assigned to shards by a shard key, via hash (even spread, no range queries across shards) or ranges (efficient ranges, hot-spot risk). The shard key is the most consequential and least reversible decision: it determines load balance, which queries are single-shard, and what resharding will cost.

Reading your own writes with replicas

fun updateName(userId: Long, name: String) {
    primary.update("UPDATE users SET name = ? WHERE id = ?", name, userId)
    recentWriters.put(userId, Instant.now())          // remember who just wrote
}

fun profile(userId: Long): Profile {
    val wroteRecently = recentWriters[userId]?.isAfter(Instant.now().minusSeconds(5)) == true
    val db = if (wroteRecently) primary else replica  // read your own writes from the primary
    return db.queryProfile(userId)
}

void updateName(long userId, String name) {
    primary.update("UPDATE users SET name = ? WHERE id = ?", name, userId);
    recentWriters.put(userId, Instant.now());                          // remember who just wrote
}

Profile profile(long userId) {
    Instant wrote = recentWriters.get(userId);
    boolean recent = wrote != null && wrote.isAfter(Instant.now().minusSeconds(5));
    return (recent ? primary : replica).queryProfile(userId);          // read your own writes from the primary
}

async function updateName(userId: number, name: string): Promise<void> {
  await primary.query("UPDATE users SET name = $1 WHERE id = $2", [name, userId]);
  recentWriters.set(userId, Date.now());                               // remember who just wrote
}

async function profile(userId: number): Promise<Profile> {
  const wrote = recentWriters.get(userId) ?? 0;
  const db = Date.now() - wrote < 5_000 ? primary : replica;           // read your own writes from the primary
  return db.queryProfile(userId);
}

Replicas receive changes a moment after the primary does. If a user saves their new name and the next screen reads from a replica, they may see the old name and think the save failed. Reading from the primary for a few seconds after a user writes (or for that user’s own data) avoids it. With several servers, “who wrote recently” must live in a shared place, or in the user’s session or token.

Predict the output

A user changes their display name. The app saves it on the primary database, then immediately reloads the profile from a read replica that is 2 seconds behind. Which name does the user see?

Choosing a shard key

Predict the output

An orders table is range-sharded by order id (ids 1–10M on shard 1, 10M–20M on shard 2, and so on). Ids come from an auto-incrementing sequence. Which shard receives new orders?

Candidate shard key for orders	Spread	Single-shard queries	Risk
`order_id` (hashed)	Even	“Get order by id” only	“A customer’s orders” hits every shard
`customer_id`	Even (many customers)	“A customer’s orders”, “get order” if id embeds the shard	A huge B2B customer becomes a hot shard
`created_at` (range)	All writes on the newest shard	Time ranges	Hot shard
`country`	Very uneven	Country reports	Most traffic on a few shards

Production puzzles

Spot the bugPage 5,000 of the order history

Tap the line with the bug.

-- API: GET /admin/orders?page=5000&size=50
SELECT id, customer_id, created_at, total_cents
FROM orders
ORDER BY created_at DESC, id DESC
LIMIT 50 OFFSET 249950;

OFFSET 249950 still makes the database find, sort and discard 249,950 rows on every request: deep pages get linearly slower and an export job walking all pages is O(n²). Worse for users, offsets shift: new orders inserted at the top push everything down, so the next page repeats rows (or skips them, after deletes).

Use keyset (cursor) pagination: remember where the last page ended and continue from there, using the index:

-- First page
SELECT id, customer_id, created_at, total_cents
FROM orders
ORDER BY created_at DESC, id DESC
LIMIT 50;

-- Next page: the client sends back the last row's (created_at, id) as an opaque cursor
SELECT id, customer_id, created_at, total_cents
FROM orders
WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC
LIMIT 50;
-- served by an index on (created_at DESC, id DESC): constant time for every page

The id tie-breaker makes the order unique, so rows with the same timestamp are never skipped or repeated. On sharded data, keyset pagination is also what makes a merged, cross-shard listing possible (each shard returns its next N after the cursor).

Exercisehard

Shard the messages of a chat app

A chat app stores 5 billion messages, growing by 50 million a day. Queries: “the last 50 messages of a conversation, then older ones as you scroll”, “a user’s conversation list, newest activity first”, and “search my messages”. One PostgreSQL primary can’t keep up with writes. Choose a shard key (or keys), describe the tables or indexes per query, and explain what happens with a conversation that has 2 million members.

›

Two of the queries are about one conversation; one is about one user. One key can’t make both single-shard, so consider two copies of different data, each partitioned for its own query.

SolutionTry it yourself first

Messages: partition by conversation_id (hashed), clustered by (conversation_id, message_id) with time-ordered ids (Snowflake-style or ULID). “Last 50” and “scroll back” are single-partition range reads with a keyset cursor. This fits Cassandra/ScyllaDB or sharded PostgreSQL (Citus) equally well.
Conversation list: a separate table partitioned by user_id: (user_id, last_activity_at, conversation_id), updated asynchronously when a message is sent (a fan-out write per member via a queue). “My conversations, newest first” is one partition read.
Search: a search index (Elasticsearch/OpenSearch) fed from the message stream, with per-user access filtering; not the source of truth.
Huge conversations: a 2-million-member channel concentrates writes and reads on one partition. Bucket it in time ((conversation_id, day) as the partition key) so one partition isn’t unbounded, cache the latest page aggressively (everyone reads the same tail), and don’t fan out activity updates to 2 million users’ lists per message: mark channels “large” and compute their position lazily.
Ids: time-ordered, globally unique ids generated without coordination (no single sequence), embedding enough to route by.
Resharding: hash with many virtual partitions (e.g. 4,096 logical buckets mapped to fewer physical nodes) so adding nodes moves buckets, not rows one by one.

Replicas scale reads and availability; async lag breaks read-your-writes: route a user’s reads to the primary after their writes, or wait for the replica to reach the write’s LSN.
Shard key: high cardinality, even load, keeps hot queries single-shard. Avoid monotonic range keys (all writes on the last shard) and skewed keys (country, a whale customer). Use many logical buckets for cheaper resharding.
Different queries may need differently partitioned copies (per conversation vs per user), maintained asynchronously.
Keyset pagination with a unique tie-breaker, never deep OFFSET.

Check this part

What do read replicas help with?
Writes still go to the primary; replicas receive the changes a moment later.
A user saves a change and the next screen shows the old value. A likely cause?
Read from the primary for that user right after they write.
Why is an auto-incrementing id a bad range shard key?
Monotonic keys create a write hot spot; hash them or pick another key.
Why replace OFFSET pagination with keyset pagination?
Keyset pages cost the same at any depth and stay stable under inserts.

Read replicas copy the primary database to serve reads, with a small lag that can show users stale data right after they write. Sharding splits data across databases by a key, which must spread load evenly and keep each query on one shard. Paginate with keys, not offsets.

Key takeaways

Relational databases are the right default; NoSQL stores are for specific access patterns at large scale.
An index lets the database jump to rows instead of reading the whole table; composite indexes help queries that use their first column.
Check slow queries with EXPLAIN; a full scan of a big table is the usual culprit.
Replicas add read capacity but lag a little; sharding splits data by a key so writes scale.

Choose stores by access patterns and transaction scope; keep one source of truth and derive the rest.
Design indexes from queries: equality then range columns, partial and expression indexes, verified with EXPLAIN on real data.
Handle replica lag explicitly for read-your-writes; pick shard keys for even load and single-shard hot queries.
Keyset pagination everywhere data is large or changing.