Indexing Like Neo: Dodging Bullets in Your Database

The Quest Begins (The "Why")

I was knee‑deep in building a tiny rate‑limiter for a side‑project API. The idea was simple: every request hits a table that logs the user‑id and the timestamp, and we deny the request if there are more than N hits in the last minute.

At first the table looked harmless:

CREATE TABLE request_log (
    id          BIGSERIAL PRIMARY KEY,
    user_id     BIGINT NOT NULL,
    ts          TIMESTAMPTZ NOT NULL
);

I slapped a plain index on user_id and called it a day. The first few hundred requests flew by, but once the log grew to a few million rows the latency spiked. The query the limiter ran was essentially:

SELECT COUNT(*)
FROM request_log
WHERE user_id = $1
  AND ts >= now() - interval '1 minute';

Even with the user_id index, the planner had to scan all rows for that user because the timestamp predicate couldn’t be used for a range scan. It was like trying to dodge a barrage of bullets while blindfolded—you knew the direction, but you kept getting hit.

I felt stuck. The limiter was supposed to be lightning‑fast, yet each check was costing tens of milliseconds. Time to grab the map and find the real shortcut.

The Revelation (The Insight)

The “aha!” moment came when I realized the problem wasn’t the amount of data; it was the shape of the index. A single‑column index on user_id gives you a fast way to jump to the first row for a user, but after that you still walk through every row in chronological order until you hit the time window.

What we really need is an index that can skip straight to the relevant slice of time for each user. In other words, a composite (multi‑column) index on (user_id, ts).

With that layout, the B‑tree stores entries sorted first by user_id, then by ts. When the planner sees the WHERE user_id = $1 AND ts >= … clause, it can:

1. Jump directly to the block for the given user_id.
2. Inside that block, perform a range scan on the timestamp, stopping as soon as it leaves the one‑minute window.

No more wasted walks through stale rows. The index becomes a covering index for our query because it contains everything the planner needs (user_id and ts). The database can satisfy the query by reading only the index pages—no trips to the heap at all.

Let’s draw a tiny ASCII picture of how the index looks:

(user_id, ts) B‑tree (simplified)

          (user_id=42, ts=10:00)
                 /            \
   (user_id=42, ts=09:58)   (user_id=42, ts=10:02)
        /        \               /        \
 (42,09:55) (42,09:56)   (42,10:01) (42,10:03)

When we ask for “last minute”, the planner starts at the leftmost node that satisfies ts >= 09:59 and walks right until it hits ts > 10:00. Only a handful of nodes are visited.

Wielding the Power (Code & Examples)

Before – the struggle

-- Only a single‑column index
CREATE INDEX idx_request_log_user_id ON request_log(user_id);

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM request_log
WHERE user_id = 12345
  AND ts >= now() - interval '1 minute';

Typical output (on a few‑million‑row table):

 Aggregate  (cost=... rows=1 width=8)
   ->  Index Scan using idx_request_log_user_id on request_log  (cost=... rows=... width=0)
         Index Cond: (user_id = 12345)
         Filter: (ts >= (now() - '00:01:00'::interval))
         Rows Removed by Filter: 124578   <-- lots of wasted rows

Notice the “Rows Removed by Filter” line—those are the rows we read just to throw away.

After – the victory

-- Composite index that matches our query pattern
CREATE INDEX idx_request_log_user_id_ts ON request_log(user_id, ts);

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM request_log
WHERE user_id = 12345
  AND ts >= now() - interval '1 minute';

Typical output now:

 Aggregate  (cost=... rows=1 width=8)
   ->  Index Only Scan using idx_request_log_user_id_ts on request_log  (cost=... rows=... width=0)
         Index Cond: ((user_id = 12345) AND (ts >= (now() - '00:01:00'::interval)))
         Heap Fetches: 0

Index Only Scan means the planner never touched the main table—everything was satisfied from the index. The “Rows Removed by Filter” column is now zero (or a tiny number if the index isn’t perfectly covering). Latency dropped from ~12 ms to ~0.3 ms in my benchmarks—a 40× speed‑up.

Common traps to avoid

Trap	Why it hurts	Fix
Index on ts only	You can jump to the time window, but you’ll scan all users in that minute, which is usually far larger than the per‑user slice.	Keep user_id as the leading column.
Forgetting to ANALYZE after creating the index	The planner may still pick a bad plan if stats are stale.	Run ANALYZE request_log; or let autovacuum do its job.
Over‑indexing (adding every column)	Every extra index adds write overhead and storage cost.	Benchmark; only add indexes that match actual query patterns.

Why This New Power Matters

With the composite index in place, the rate‑limiter became snappy enough to handle thousands of requests per second on a modest VM. The same principle applies to any lookup that filters on a high‑cardinality column (like a user id) and a range on a timestamp, monotonic counter, or even a lexical range (e.g., WHERE category = 'books' AND price BETWEEN 10 AND 20).

Think of it like giving your database a pair of night‑vision goggles: it can see exactly where the data it needs lives, instead of fumbling through the dark. The trade‑off is modest—writes are a tiny bit slower and the index occupies extra space—but for read‑heavy workloads (which most APIs are) the payoff is massive.

If you’re still using a single‑column index for a query that also has a range predicate, stop. Grab the composite index, run an EXPLAIN, and watch the query plan go from “Index Scan + Filter” to a clean “Index Only Scan”. You’ll feel like you just dodged a barrage of bullets—Neo style—without breaking a sweat.

Your Turn

Pick a table in your own project that you query with an equality filter plus a range (time, price, score, etc.). Add a composite index that leads with the equality column, run EXPLAIN ANALYZE before and after, and share the numbers. Did you shave off milliseconds? Seconds? Let’s see those victory metrics in the comments!

Happy indexing! 🚀