The Quest Begins (The “Why”)
Picture this: you’ve just shipped a shiny new API that lets users upload cat memes. Everything’s going great until the traffic spikes and your service starts to choke. The culprit? A naïve rate‑limiter that does a COUNT(*) over a massive requests table every single request. I remember staring at the dashboard, watching latency climb from 20 ms to over a second, and feeling like I’d just walked into a boss fight without a weapon.
I needed a way to quickly know how many requests a user made in the last minute without scanning millions of rows. The dragon I had to slay was full table scans on every API call.
The Revelation (The Insight)
The magic trick isn’t some exotic algorithm; it’s simply how you index the data.
A rate limiter usually stores a row per request:
requests
---------
id PK
user_id INT
created_at TIMESTAMP
When you ask “how many rows does user X have in the last 60 seconds?” the database can answer instantly if it can jump straight to the relevant slice of the index.
The insight: a composite B‑tree index on (user_id, created_at) lets the engine:
-
Seek to the first row for that user (thanks to the leading
user_id). - Range‑scan forward only through the timestamps that fall inside the window (thanks to the second column).
Everything outside that slice is never touched. It’s like Neo seeing the Matrix code—you instantly know where the action is and can ignore the rest.
Why does column order matter? If you reversed it to (created_at, user_id), the engine would first have to scan all rows in the time window across all users before it could filter by user_id. That defeats the purpose. The leading column must be the one you filter on with equality (user_id = ?), the second column the one you range on (created_at BETWEEN ? AND ?).
Wielding the Power (Code & Examples)
The Struggle – No Index
-- Table definition (simplified)
CREATE TABLE requests (
id BIGSERIAL PRIMARY KEY,
user_id INT NOT NULL,
created_at TIMESTAMPTZ NOT NULL DEFAULT now()
);
-- The slow query we run on every API hit
SELECT COUNT(*)
FROM requests
WHERE user_id = $1
AND created_at >= now() - interval '1 minute';
Without any index beyond the primary key, PostgreSQL does a sequential scan:
-> Seq Scan on requests (cost=0.00..12345.67 rows=1000000 width=4)
Filter: ((user_id = $1) AND (created_at >= (now() - '00:01:00'::interval)))
On a table with a few million rows, that scan takes hundreds of milliseconds—far too slow for a per‑request check.
The Victory – Adding the Composite Index
CREATE INDEX idx_requests_user_created
ON requests (user_id, created_at);
Now the same query uses an index range scan:
-> Index Scan using idx_requests_user_created on requests (cost=0.42..8.90 rows=10 width=4)
Index Cond: ((user_id = $1) AND (created_at >= (now() - '00:01:00'::interval)))
The planner can jump directly to the first entry for the given user_id and then walk forward only until the timestamp leaves the one‑minute window. The I/O drops from reading megabytes of data to reading just a handful of index nodes—often under a millisecond.
Common Trap #1: Forgetting the ORDER
If you create the index the other way around:
CREATE INDEX idx_requests_created_user
ON requests (created_at, user_id);
the planner may still choose an index scan, but it now has to scan all rows in the time window across every user before it can apply the user_id filter. On a busy system that’s still a lot of work—your query looks fast in isolation but collapses under real traffic.
Common Trap #2: Over‑indexing
Every index adds write overhead. If you’re inserting thousands of rows per second (as a rate limiter does), each insert must update the B‑tree. Benchmark on your hardware; sometimes a partial index that only keeps recent data helps:
CREATE INDEX idx_requests_recent
ON requests (user_id, created_at)
WHERE created_at >= now() - interval '10 minutes';
Older rows are ignored by the index, keeping it smaller and cheaper to maintain while still covering the window you care about.
ASCII Diagram – How the B‑Tree Looks
(user_id, created_at)
/ \
user_id=1000 user_id=1001
/ \ / \
ts=09:00 ts=09:01 ts=09:00 ts=09:01
... ... ... ...
When we ask for user_id=1000 and ts >= now()-1m, the engine descends to the user_id=1000 node, then walks rightward through the timestamp leaves until the condition fails. No need to visit the user_id=1001 subtree at all.
Why This New Power Matters
With that simple index in place, the rate‑limiter check becomes sub‑millisecond even as the requests table grows to tens of millions of rows. Your API can now handle traffic spikes without melting down, and you’ve freed up CPU cycles for actual business logic—like generating those cat memes.
The trade‑off is modest: a bit more storage (the index) and a tiny extra cost on each write. In most write‑heavy scenarios, the read‑speed win far outweighs the write penalty, especially when you can prune old rows with a background job or use partial indexes as shown above.
Compare this to alternatives:
| Approach | Read latency | Write overhead | Complexity |
|---|---|---|---|
| No index (seq scan) | High (100‑500 ms) | Minimal | Low |
| Composite index (user_id, created_at) | Low (<1 ms) | Moderate | Low |
| Separate table per user (sharding) | Low | High (schema churn) | High |
| In‑memory counter (Redis) | Very low | None (but adds another service) | Medium |
For many apps, the composite index hits the sweet spot: you stay within the relational database you already use, avoid extra moving parts, and get the performance you need.
Your Turn
Now that you’ve seen the index awaken, try adding a (user_id, created_at) index to your own rate‑limiter (or any time‑series‑like table) and watch the query plan flip from a sequential scan to an index scan.
Challenge: Run EXPLAIN ANALYZE before and after the index, note the execution time, and share the numbers in the comments. Did you hit the sub‑millisecond mark? What tweaks did you need for your write volume?
Go forth, index wisely, and may your APIs stay fast and your memes ever flowing! 🚀
Top comments (0)