Skip to content
notes.vinhnq.com

Search

Database & ORMSenior24 min read

Databases: indexes, EXPLAIN, N+1, pagination and soft delete

Review 18 cards
On this page

Databases series: 1. Tables and basic SQL · 2. ERD, joins, GROUP BY · 3. Normalization · 4. Library exercise · 5. Indexes and query performance · 6. Transactions and locking

This post answers why a correct query can still be slow, and how to fix it. Afterwards you can design an index, read EXPLAIN, fix N+1, paginate with keysets and know what soft delete really costs. Read joins and GROUP BY first; staying correct under concurrent requests is covered in Transactions, isolation levels and locking.

Dialect: MySQL 8 with InnoDB. The EXPLAIN output below is real, from MySQL 8.4 on an orders table with 50,000 rows. Where PostgreSQL behaves differently in a way that matters, I say so.

CREATE TABLE orders (
  id          BIGINT AUTO_INCREMENT PRIMARY KEY,
  customer_id BIGINT        NOT NULL,
  status      VARCHAR(16)   NOT NULL,   -- NEW / PAID / SHIPPED / CANCELLED
  total       DECIMAL(12,2) NOT NULL,
  created_at  DATETIME      NOT NULL,
  KEY idx_orders_created (created_at, id),
  KEY idx_orders_cust_status_created (customer_id, status, created_at)
);

1. Indexes

Key idea: an index is a pre-sorted structure that finds rows in O(log n) instead of reading the whole table. It only helps when its column order matches the query and the predicate doesn’t wrap the column in a function; the price is slower writes.

Going deeper: Inside an index (B-trees vs B+trees, clustered tables vs heaps, choosing a primary key, bloat, rebuilds) and Index types beyond the B-tree (GIN, GiST, bitmap, LSM trees).

1.1. What happens without one?

Without an index, finding customer 42’s orders means reading every row (a full table scan): O(n). An index is an auxiliary data structure, kept sorted by one or more columns, that finds rows in O(log n).

1.2. B+trees: the structure underneath

Most indexes in MySQL (InnoDB) and PostgreSQL are B+trees:

flowchart TB
  R["Root: [ 100 | 200 ]"] --> I1["Internal: [ 30 | 60 ]"]
  R --> I2["Internal: [ 130 | 160 ]"]
  R --> I3["Internal: [ 230 | 260 ]"]
  I1 --> L1["Leaf: 1..29"]
  I1 --> L2["Leaf: 30..59"]
  I1 --> L3["Leaf: 60..99"]
  L1 -. "next" .-> L2
  L2 -. "next" .-> L3
  • Each node is a page (16 KB by default in InnoDB) holding hundreds of keys. Thanks to the high fan-out (children per node), the tree is only 3–4 levels deep even with hundreds of millions of rows; the upper levels usually sit in the buffer pool (the database’s RAM cache).
  • Only the leaves hold data (or pointers), and the leaves are linked in a list. A range scan (BETWEEN, >, ORDER BY) finds the starting point and walks the leaves sequentially.
  • A hash is faster for equality but can’t do ranges or ordering. A binary tree is far too tall, one disk read per level.

1.3. Clustered vs secondary indexes in InnoDB

Clustered index (PK) Secondary index
What the leaves hold The entire row The indexed columns + the PK value
How many Exactly one per table Many
Consequence Rows are physically ordered by PK After a match, look up the clustered index by PK to fetch the other columns

That second step is a lookup back to the table (a bookmark lookup). Finding 10,000 rows through a secondary index means 10,000 random jumps, so the optimizer sometimes ignores the index and scans the whole table.

1.4. Composite indexes and the leftmost prefix rule

The index (customer_id, status, created_at) is sorted like a phone book: by customer_id, then status, then created_at.

Query Can it use the index?
WHERE customer_id = ? Yes (1-column prefix)
WHERE customer_id = ? AND status = ? Yes (2-column prefix)
WHERE customer_id = ? AND status = ? ORDER BY created_at Yes, with no sort
WHERE customer_id = ? AND created_at > ? Only the customer_id part (skipping status breaks the chain)
WHERE status = ? No (missing the first column)

Column order when designing a composite index:

  1. Columns compared with equality (=, IN) first.
  2. The sort or range column (>, BETWEEN) last. After a range column, the columns behind it can no longer be used for seeking.
  3. Among equality columns, the more selective one often goes first, but what matters more is that the index serves as many queries as possible through its leftmost prefixes.
Checking with EXPLAIN: key_len tells you how many columns are used
EXPLAIN SELECT id, status, created_at FROM orders
WHERE customer_id = 42 AND status = 'PAID'
ORDER BY created_at DESC LIMIT 10;
type: ref   key: idx_orders_cust_status_created   key_len: 74   ref: const,const
rows: 1     Extra: Backward index scan; Using index
EXPLAIN SELECT * FROM orders WHERE customer_id = 42 AND created_at > '2026-01-10';
type: ref   key: idx_orders_cust_status_created   key_len: 8   ref: const
rows: 25    filtered: 50.00   Extra: Using index condition
  • key_len: 8 = only the 8 bytes of customer_id (BIGINT) are used for the lookup; created_at is only filtered afterwards.
  • key_len: 74 = 8 (BIGINT) + 66 (VARCHAR(16) in utf8mb4: 16×4 + 2 length bytes), so both columns are used.
  • Since MySQL 8.0.13 there’s index skip scan: it can sometimes use an index without its first column if that column has very few distinct values. Don’t design around it.

1.5. Covering indexes

If every column the query needs is in the index, the database never goes back to the table; EXPLAIN shows Using index. The SELECT id, status, created_at example above is covering, because id is the PK, which every InnoDB secondary index carries.

PostgreSQL calls this an index-only scan and has INCLUDE for non-searchable payload columns: CREATE INDEX ... ON orders (customer_id) INCLUDE (total). It also depends on the visibility map (a map of pages whose rows are visible to everyone), so a table that isn’t vacuumed often still has to visit the heap.

1.6. Selectivity: when an index doesn’t help

Selectivity = distinct values / total rows. email is close to 1; status with 4 values across 50,000 rows is close to 0.

EXPLAIN SELECT * FROM orders WHERE status = 'PAID';
type: ALL   key: NULL   rows: 50170   filtered: 10.00   Extra: Using where

No index starts with status: full table scan.

The optimizer relies on statistics (how the data is distributed); stale stats (after a big data load) lead to bad plans. Refresh them with ANALYZE TABLE (MySQL) or ANALYZE (Postgres); MySQL 8 also has histograms: ANALYZE TABLE orders UPDATE HISTOGRAM ON status.

1.7. Sargability: don’t wrap the column in a function

-- Can NOT use the index on created_at
EXPLAIN SELECT * FROM orders WHERE DATE(created_at) = '2026-01-10';
-- type: ALL, rows: 50170

-- Can use the index: compare the bare column against a half-open range
EXPLAIN SELECT * FROM orders
WHERE created_at >= '2026-01-10' AND created_at < '2026-01-11';
-- type: range, key: idx_orders_created, rows: 1440
PostgreSQL: filtering by date also depends on the session time zone

WHERE created_at::date = '2024-06-10' is not sargable and also computes “June 10” in the session’s TimeZone. The app (on UTC) and a developer’s laptop (on Vietnam time) get different answers. How to write it as a half-open range with an explicit offset is in Storing dates and times in PostgreSQL, MySQL and JSON.

1.8. What indexes cost

  • Slower writes: every INSERT updates every index; every UPDATE of an indexed column updates that index.
  • Memory: indexes compete with data for the buffer pool.
  • Redundant indexes: (a) is redundant if you already have (a, b).

To practise picking indexes on a real schema, Designing an airline booking database has an index table for each main query (flights by route and date, the seat map, counting free seats with a partial index) and an exercise.

2. Reading EXPLAIN

Key idea: look at type (the access method), key/key_len (which index, how many columns) and Extra (an extra sort? a temp table?). EXPLAIN only estimates; for the real numbers use EXPLAIN ANALYZE.

Column Meaning
type Access method, best to worst: const (PK/unique lookup on a constant) → eq_ref (join on PK/unique) → ref (non-unique index lookup) → range → index (full index scan) → ALL (full table scan)
key The index actually used (possible_keys are just candidates)
key_len Bytes of the index used; tells you how many columns of a composite index are in play
rows Estimated rows to read
filtered Estimated % of rows left after the conditions
Extra Using index (covering), Using where, Using index condition (ICP, filtering on the index itself), Using filesort (needs a sort), Using temporary (temp table, usually from GROUP BY/DISTINCT)

EXPLAIN ANALYZE (MySQL 8.0.18+) actually runs the query and prints real timings and row counts per step; PostgreSQL uses EXPLAIN (ANALYZE, BUFFERS). Careful: on an UPDATE/DELETE it really executes, so wrap it in a transaction and roll back.

My routine for a slow query:

  1. Get the real query and parameters from the slow query log or APM (don’t guess).
  2. EXPLAIN ANALYZE: which step costs most, and are estimated rows far off the actual numbers?
  3. If they’re far off, refresh statistics before adding indexes.
  4. Check sargability, index column order, and whether a covering index is possible.
  5. Measure again on production-sized data; “fast” on 1,000 rows proves nothing.
Reading PostgreSQL plans: two posts to read next

3. The N+1 problem

Key idea: one query loads N records, then lazy loading fires one more query per record: 1 + N queries. Fix it by loading the related data deliberately in one or a few queries.

// Load 100 orders
List<Order> orders = orderRepository.findTop100ByStatus(Status.PAID);   // 1 query
for (Order o : orders) {
    // customer is LAZY -> every iteration fires another query
    System.out.println(o.getCustomer().getName());                    // +100 queries
}

Each query takes 1 ms, but with round-trips 101 queries become 100+ ms, and the connection is held longer. The ORM hides it, so it slips into production easily.

Detecting it: log SQL in dev (spring.jpa.show-sql, or better datasource-proxy/p6spy to see parameters), hibernate.generate_statistics, or tests that assert the query count for important endpoints.

Fixing it:

// 1. JOIN FETCH: a single query
@Query("select o from Order o join fetch o.customer where o.status = :status")
List<Order> findPaidWithCustomer(@Param("status") Status status);

// 2. Entity graph: declarative instead of JPQL
@EntityGraph(attributePaths = "customer")
List<Order> findTop100ByStatus(Status status);

// 3. DTO projection: fetch only the columns you need, no entities (Java record)
public record OrderView(Long id, BigDecimal total, String customerName) {}

@Query("""
       select new com.example.OrderView(o.id, o.total, c.name)
       from Order o join o.customer c
       where o.status = :status
       """)
List<OrderView> findViews(@Param("status") Status status);
# 4. Batch fetching: turns N lazy queries into ceil(N/50) queries using WHERE id IN (...)
spring.jpa.properties.hibernate.default_batch_fetch_size=50

Don’t use FetchType.EAGER to “fix” N+1: keep every association LAZY and fetch deliberately per use case.

Traps when fixing N+1: paging a collection, MultipleBagFetchException, EAGER
  • JOIN FETCH on a collection combined with pagination: Hibernate can’t apply LIMIT in SQL (the join multiplies rows), so it loads everything and paginates in memory, with warning HHH90003004 (Hibernate 6). The right way: page the ids first, then fetch by that id list, or use batch fetching.
  • Fetching two List collections (bags) at once throws MultipleBagFetchException. Dodging it with Set still gives you a Cartesian product. Split it into several queries.
  • FetchType.EAGER is the wrong direction because N+1 still happens with JPQL queries; it just happens every time.

4. Pagination: OFFSET vs keyset

Key idea: OFFSET reads and throws away N rows, so deeper pages get slower. Keyset fetches the rows after the last row of the previous page using an indexed key, so every page is equally fast.

4.1. OFFSET gets slower with every page

SELECT * FROM orders ORDER BY id LIMIT 20 OFFSET 40000;
-> Limit/Offset: 20/40000 row(s)
    -> Index scan on orders using PRIMARY  (rows=40020)

To return 20 rows, the database reads and throws away 40,000 rows: the cost is linear in the offset. If rows are inserted or deleted between two requests, users also see duplicated or skipped rows.

4.2. Keyset (cursor) pagination

-- First page
SELECT id, created_at, total FROM orders
ORDER BY created_at DESC, id DESC
LIMIT 20;

-- Next page: pass the (created_at, id) of the last row of the previous page
SELECT id, created_at, total FROM orders
WHERE created_at < :last_created_at
   OR (created_at = :last_created_at AND id < :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;

With an index on (created_at, id), the database jumps straight to the cursor position and reads exactly 20 rows: page 1 and page 10,000 are equally fast. It’s a bookmark: you open the book where you stopped instead of counting pages from the start.

The cursor is usually encoded (base64 of created_at|id) into an opaque next_cursor string so clients don’t depend on internal details.

In Spring Data JPA, OFFSET is Pageable + Page (with an extra COUNT(*)), while Slice fetches size + 1 rows to skip the count: see the pagination and dynamic filters post.

If you’re stuck with OFFSET: deferred join, and the cost of COUNT(*)

The deferred join trick: paginate over a covering index to get just the ids, then join back for the full columns of those 20 rows.

SELECT o.*
FROM orders o
JOIN (SELECT id FROM orders ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 40000) page
  ON page.id = o.id
ORDER BY o.created_at DESC, o.id DESC;

The database still skips 40,000 entries; it just skips them in a compact index instead of full rows. Advanced REST API design measures the trick on PostgreSQL: it relies on an index-only scan, so it is only fast once the visibility map has been VACUUMed (right after a bulk load, the deferred join was slower than a plain OFFSET). That post also covers cursor pagination at the API level: cursors clients can’t tamper with, and a whitelist of sort fields.

SELECT COUNT(*) for “total pages” also has to scan all matching data, because InnoDB doesn’t keep an exact row count due to MVCC (each transaction may see a different count). On big tables, consider dropping the total page count or showing an estimate.

5. Soft delete

Key idea: set deleted_at = NOW() instead of DELETE, and filter WHERE deleted_at IS NULL everywhere. You can restore data, but the cost is often underestimated.

Benefits: recover from accidental deletes; keep history and an audit trail; FKs from historical data don’t break (old orders still point at a discontinued product).

Costs:

  1. Every query has to remember the filter. Miss one and deleted data comes back. Hibernate has @SQLRestriction("deleted_at is null") (6.3+, replacing the deprecated @Where), @SQLDelete to turn a delete into an update, and @SoftDelete since 6.4. Native queries, reports and BI tools still filter by hand.
  2. Uniqueness breaks when someone signs up again with the same email (block below).
  3. Tables and indexes bloat with dead data. Indexes should account for deleted_at or be partial.
  4. Legal: GDPR or Vietnam’s 2025 Personal Data Protection Law (Decree 13/2023 before it) can require actually deleting personal data.
  5. Cascades: soft delete a customer, and what happens to their orders and addresses? ON DELETE no longer helps, so you write that logic yourself.

Exercises

My own exercises (the course has none for this part).

Exercise 1: Index for a “my orders” screen

Task: an API returns a customer’s 10 most recent orders for a given status: WHERE customer_id = ? AND status = ? ORDER BY created_at DESC LIMIT 10. Design an index that avoids sorting, and avoids going back to the table if only id, status, created_at are needed.

Solution to Exercise 1

(customer_id, status, created_at): the two equality columns first, the sort column last. EXPLAIN gives type: ref, Extra: Backward index scan; Using index:

  • no Using filesort: the index is already sorted, it just reads backwards;
  • Using index: covering, because id is the PK and is already in the secondary index.

If you also need total: either accept 10 lookups (cheap) or append total to the index (trading index size for coverage).

Exercise 2: Fix a non-sargable query

Task: a report runs WHERE YEAR(created_at) = 2026 AND MONTH(created_at) = 3 and always does a full scan. Rewrite it.

Solution to Exercise 2
WHERE created_at >= '2026-03-01' AND created_at < '2026-04-01'

The half-open range [start of month, start of next month) is correct at any timestamp precision (including fractional seconds), unlike BETWEEN '2026-03-01' AND '2026-03-31 23:59:59', which can miss rows in the last second.

Exercise 3: Move a paginated API to keyset

Task: GET /orders?page=2000&size=20 is slow. Switch to cursors.

Solution to Exercise 3
  • New API: GET /orders?size=20&cursor=<opaque>.
  • The server decodes the cursor into (created_at, id), runs the keyset query from section 4.2, and returns items plus a next_cursor (encoded from the last row), or null at the end.
  • It needs an index on (created_at, id).
  • Keep the old API around for a while for existing clients (deprecate it gradually), since keyset can’t “jump to page 2000”.

Exercise 4: Unique email with soft delete

Task: the user table uses soft delete, and someone who deletes their account and signs up again with the same email gets a duplicate error. Fix it while still guaranteeing no two active accounts share an email.

Solution to Exercise 4

The active_email generated column plus a unique key (section 5). I ran it: soft-deleting a@x.com and inserting a@x.com again succeeds, leaving two rows with only one active. On Postgres, use a partial unique index.

Exercise 5: Read an EXPLAIN with Using filesort

Task: an admin screen runs SELECT id, total, created_at FROM orders WHERE status = 'PAID' ORDER BY created_at DESC LIMIT 50, and EXPLAIN shows type: ALL, Extra: Using where; Using filesort. Explain each part and propose a fix.

Solution to Exercise 5
  • type: ALL: a full table scan, because no index starts with status.
  • Using filesort: after filtering, the database sorts every PAID row by created_at itself before taking the first 50, so the LIMIT does nothing to reduce the scan.
  • Fix: an index on (status, created_at), equality column first, sort column last. The database jumps to the status = 'PAID' slice, reads it backwards by created_at and stops after 50 rows (Backward index scan, no more filesort).
  • Each row still needs a lookup back to the table for total; to drop that step, use (status, created_at, total).
  • On selectivity: status has few distinct values, but the index still pays off because it serves the sort + LIMIT, not the filter.
  • Finally, measure again with EXPLAIN ANALYZE on production-sized data.

Remember

  • Can you explain why an InnoDB PK should be short and increasing?
  • Given a WHERE ... ORDER BY, can you order the columns of a composite index and verify it with key_len and Extra?
  • Can you spot a non-sargable predicate and rewrite it as a half-open range?
  • Do you know the four ways to fix N+1, and the trap of JOIN FETCH on a collection with pagination?
  • Do you know when to use OFFSET vs keyset, and what soft delete forces you to handle?

Interview questions

Junior

What is an index and why does it make queries faster?

An auxiliary data structure (usually a B+tree) kept sorted by some columns, so lookups take O(log n) instead of a full O(n) scan.

The trade-off is slower writes and extra storage.

What’s the N+1 problem?

One query loads N parent records, then each record triggers another query for related data: 1 + N queries in total.

It usually comes from ORM lazy loading. Fix it with JOIN FETCH, an entity graph, batch fetching or a DTO projection.

When should you not add an index?

When it barely helps reads but still slows down every write.

  • The table is tiny (a full scan is cheap anyway).
  • The column has low selectivity and doesn’t serve a sort.
  • The table is write-heavy and queries on that column are rare.
  • The new index is a prefix of an existing one ((a) is redundant next to (a, b)).

Every index slows down INSERT/UPDATE and takes space in the buffer pool.

Mid

Which queries can a composite index (a, b, c) serve?

Those using a leftmost prefix: a, a,b, a,b,c.

Plus ordering by the next column when the previous ones are equality matches. It doesn’t help b or c on their own. After a range condition on b, c can no longer be used for seeking.

What’s a covering index, and how do you spot one in EXPLAIN?

An index that contains every column the query needs, so the database never visits the table.

MySQL shows Using index in Extra; Postgres shows Index Only Scan. In InnoDB the PK is always in secondary indexes, so it counts as covered.

Why is a large OFFSET slow, and what do you use instead?

The database reads and discards offset rows before returning anything, so the cost grows linearly with page depth. Use keyset pagination instead.

Keyset: WHERE (sort_key, id) < (last_sort_key, last_id) ORDER BY sort_key DESC, id DESC LIMIT n with a matching index. On MySQL, expand it into the OR form to get a range scan.

An API suddenly got slow. How do you investigate the SQL?

Get the real SQL and parameters, run EXPLAIN ANALYZE, fix based on evidence, then measure again on production-sized data.

  • Get the real query from the slow query log or APM.
  • EXPLAIN ANALYZE: the most expensive step, and estimated vs actual rows; if they’re far apart, refresh statistics first.
  • Check type (any ALL?), key/key_len (how many index columns are used), Extra (Using filesort, Using temporary), sargability and the composite index column order.

Senior

Why is a UUID v4 primary key bad for InnoDB, and what would you use instead?

InnoDB orders rows physically by the PK; a random UUID v4 scatters inserts across the tree and is copied into every secondary index. Use an increasing PK.

  • Random inserts cause page splits, half-empty pages, and a much larger set of “hot” pages the buffer pool must hold.
  • The 16-byte key (36 bytes if stored as text) is copied into every secondary index.
  • Options: a BIGINT AUTO_INCREMENT internal PK plus a unique UUID column for external use, or a time-ordered id such as UUIDv7/ULID stored as BINARY(16).
  • MySQL’s UUID_TO_BIN(uuid, 1) swaps the time parts of a UUID v1 so it becomes increasing.
Are you in favour of soft delete?

It depends on the data: yes for data that may need restoring or must keep historical references, provided you deal with its costs.

  • Automatic filtering (@SQLRestriction/@SoftDelete).
  • Uniqueness among active rows (partial index or generated column).
  • Indexes that account for deleted_at.
  • An archive/hard-delete job after N days, and compliance with requests to erase personal data.

Often a meaningful business state (CANCELLED) or an archive table plus an audit log beats a generic deleted flag.

Useful phrases for interviews

  • “Let me look at the execution plan first; I’d rather measure than guess which index is missing.”
  • “This predicate isn’t sargable because the column is wrapped in a function, so I’d rewrite it as a half-open range.”
  • “I’d put the equality columns first in the composite index and the sort column last, so the database can skip the filesort.”
  • “In InnoDB the primary key is the clustered index, which is why I want it short and monotonically increasing.”
  • “OFFSET pagination degrades linearly with page depth, so for an infinite feed I’d switch to keyset pagination.”
  • “N+1 usually comes from lazy loading inside a loop; I’d fix it with a fetch join or batch fetching and add a test that counts queries.”
  • “Soft delete is useful, but it has real costs: every query needs the filter and unique constraints need a partial index.”
  • “Before adding an index, I’d check whether the optimizer’s row estimates are anywhere near the actual numbers.”
  • “A random UUID primary key scatters inserts across the clustered index, so I’d use a time-ordered id instead.”

Notes based on the Fundamentals of Backend course (Ronin Engineer), rewritten in my own words.