From 5 Hours to 24 Minutes: The PostgreSQL Optimisation That Made Our Queries 500× Faster

Most database performance problems don’t start with bad code.

They start when your indexes quietly stop matching the way your application actually reads data.

That is exactly what happened to us.

We had a PostgreSQL workload processing:

• ~176,000 parent records
• ~2.2 million child records
• ~9,500 batched queries per processing cycle

For smaller tenants, everything worked perfectly.

For our largest tenant, the same background worker took:

4–5 hours

After redesigning our indexes and replacing OFFSET pagination with cursor pagination, the exact same workload dropped to:

24 minutes

No infrastructure changes. No caching layer. No sharding. No query rewrites.

Just:

• Composite indexes
• Cursor pagination
• Removing redundant indexes

The result:

• 10–12× faster end-to-end jobs
• 50–500× faster deep pagination queries
• Massive reduction in DB CPU and connection pool pressure

This article explains why that happened — and why the improvement becomes dramatically larger once your tables reach millions of rows.

The Problem at Scale

Most indexing advice online is written for:

• 10K-row tables
• simple CRUD applications
• shallow pagination
• API-bound systems

That advice breaks down quickly when your workload becomes database-bound.

Our workers processed large datasets in batches:

• reading records
• fetching child rows
• updating flags
• syncing incremental changes
• paginating continuously across millions of rows

At small scale, inefficient queries are invisible.

At millions of rows, they become catastrophic.

The Hidden Killer: OFFSET Pagination

At first glance, OFFSET pagination looks harmless:

SELECT *
FROM records
WHERE tenant_id = 10
ORDER BY id
OFFSET 175750
LIMIT 250;

But PostgreSQL still has to walk past 175,750 rows before returning the next 250.

Now multiply that by thousands of batches.

For our workload:

| Dataset           | Approx batches |
| ----------------- | -------------- |
| ~176K parent rows | ~704 batches   |
| ~2.2M child rows  | ~8,800 batches |

That means later batches become dramatically more expensive.

What OFFSET Actually Does

Batch 1    → scan 0 rows
Batch 400  → scan ~100K rows
Batch 704  → scan ~176K rows
Batch 8000 → scan millions of rows

The deeper the pagination, the slower every query becomes.

This is why jobs that should take minutes slowly drift into hours.

The Indexing Mistake Most Systems Make

We originally had standard single-column indexes:

CREATE INDEX idx_tenant ON records (tenant_id);
CREATE INDEX idx_flag ON records (needs_reprocessing);
CREATE INDEX idx_parent ON child_records (parent_id);

Looks reasonable.

But our actual queries looked like this:

WHERE tenant_id = ?
  AND needs_reprocessing = true
  AND id > ?
ORDER BY id
LIMIT 250;

Or:

WHERE tenant_id = ?
  AND parent_id = ?
  AND id > ?
ORDER BY id
LIMIT 500;

The issue was subtle but deadly.

PostgreSQL could not efficiently satisfy:

• filtering
• sorting
• pagination

…using one index.

So it had to:

• combine indexes with bitmap scans
• filter huge row sets in memory
• sort rows separately
• discard massive amounts of scanned data
• perform sequential scans on large tables

At 2.2 million rows, that becomes extremely expensive.

The 3 Composite Indexes That Changed Everything

We stopped indexing columns individually.

Instead, we indexed the actual access patterns.

1. Tenant + Entity Scope

CREATE INDEX idx_tenant_entity
ON parent_records (tenant_id, entity_id);

Used for scoped reads inside a tenant.

2. Tenant + Incremental Flag + Cursor Column

CREATE INDEX idx_tenant_flag_id
ON parent_records (tenant_id, needs_reprocessing, id);

This became the biggest optimization.

Including id allowed PostgreSQL to:

• filter
• paginate
• sort

…inside the same index scan.

No extra sorting step. No large scans.

3. Tenant + Parent Reference + Pagination

CREATE INDEX idx_tenant_parent_id
ON child_records (tenant_id, parent_id, id);

Perfect for batched child-record processing.

The Second Optimization: Cursor Pagination

Indexes alone were not enough.

We replaced OFFSET pagination with cursor pagination.

Before

OFFSET 175750 LIMIT 250

Cost increases continuously.

After

WHERE id > $last_seen_id
ORDER BY id
LIMIT 250

Cost stays nearly constant at any depth.

That one change converted our workload from:

Increasing scan cost per batch

to:

Flat index walks across the dataset

This is the reason late-stage batches became hundreds of times faster.

The Real Numbers

Production Workload

| Metric         | Before     | After         |
| -------------- | ---------- | ------------- |
| Parent records | ~176K      | ~176K         |
| Child records  | ~2.2M      | ~2.2M         |
| Total runtime  | 4–5 hours  | 24 minutes    |
| Total batches  | ~9,500     | ~9,500        |
| DB query phase | ~3–4 hours | ~8–12 minutes |

Query-Level Improvements

| Query Type            | Before | After     | Improvement |
| --------------------- | ------ | --------- | ----------- |
| First batch read      | 1–5 s  | 20–80 ms  | 15–50×      |
| Mid-pagination batch  | 3–15 s | 15–60 ms  | 50–200×     |
| Deep-pagination batch | 5–30 s | 15–60 ms  | 100–500×    |
| Scoped UPDATE         | 2–10 s | 50–300 ms | 10–40×      |

The important detail:

The deeper the pagination became, the larger the improvement became.

Batch 1 improved 15×. Batch 8,000 improved 200×+.

That is why the overall job collapsed from hours to minutes.

Why the Gain Was So Extreme

Most articles say indexing improves jobs by:

• 20%
• 30%
• maybe 40%

That is true for API-bound workloads.

But once tables cross:

• hundreds of thousands of rows
• millions of child records
• thousands of batches

…the database becomes the bottleneck.

At that point:

• wrong indexes create massive scan overhead
• OFFSET pagination becomes O(n²)
• sequential scans dominate runtime

Fixing those issues does not give incremental gains.

It changes the entire runtime profile of the system.

The Hidden Win: Removing Indexes

We did not just add indexes.

We removed several too.

Many single-column indexes became redundant once composite indexes existed.

That reduced:

• B-tree maintenance
• INSERT overhead
• UPDATE cost
• write amplification

On millions of upserts, that matters.

We reduced:

• index maintenance operations
• planner confusion
• unnecessary write work

Write-heavy phases became significantly faster too.

The Math Behind 5 Hours → 24 Minutes

Before

~9,500 batches
× average 1.5–2 seconds per batch
≈ 4–5 hours

Because batch latency kept increasing with depth.

After

~9,500 batches
× average 0.1–0.2 seconds per batch
≈ 16–32 minutes

Observed result:

~24 minutes

The improvement was not magic.

We simply changed:

• repeated large scans

into:

• linear index walks

What This Means at Different Scales

| Dataset Size     | Typical Gain |
| ---------------- | ------------ |
| 10K rows         | ~1.5–2×      |
| 50K rows         | ~2–3×        |
| 100K–500K rows   | ~5–10×       |
| Millions of rows | ~8–15×       |

The larger the dataset becomes, the more expensive bad access patterns become.

Which also means:

the larger the optimization opportunity becomes.

The Framework We Use Now

Step 1 — Run EXPLAIN ANALYZE

EXPLAIN (ANALYZE, BUFFERS)
SELECT ...

Look for:

• Seq Scan
• Bitmap Heap Scan
• Rows Removed by Filter
• slow deep-page queries

Step 2 — Map the Full Access Pattern

Think in this format:

(tenant_key, filter_column, pagination_column)

Step 3 — Build Composite Indexes Around Queries

Not around schemas.

Indexes should mirror real query behavior.

Step 4 — Replace OFFSET Pagination

Use:

WHERE id > ?
ORDER BY id
LIMIT ?

Step 5 — Remove Redundant Indexes

If you already have:

(A, B, C)

…you often do not need:

• A
• A,B

as separate indexes.

The Biggest Lesson

Composite indexes are not micro-optimizations.

At large scale, they are often the difference between:

• systems that degrade under growth

and:

• systems that stay predictably fast

The most important realization for us was this:

PostgreSQL was never the problem. Our access patterns were.

Once the indexes matched the way data was actually queried, the database stopped fighting the workload.

And a job that once took half a workday finished in less time than a coffee break.