Recently I ran into an interesting performance problem while working on a log entry retention job.
The application stores every request in a log entry table. As you can imagine, that table grows quickly. By the time I started investigating the problem, it contained nearly 400 million rows. Like many applications, we have a retention policy that deletes records older than a certain date.
My original implementation looked like this:
1LogEntry::where('created_at', '<', $cutoffDate)->delete();
There's nothing wrong with that query. Until your table reaches hundreds of millions of rows.
#The Problem
The created_at column wasn't indexed.
That meant every time the retention job ran, the database had to search a massive table just to figure out which rows should be deleted.
The obvious solution would have been to add an index on created_at.
Normally, that's exactly what I would have done.
But creating an index on a table with nearly 400 million rows wasn't something I wanted to do without careful planning. I wasn't sure how long it would take, whether it would impact production, or whether it would require downtime.
I needed another option.
#Looking at the Data
After staring at the table for a while, something stood out.
While created_at wasn't indexed, the primary key was.
More importantly, the IDs and creation dates were naturally related.
As new audit records were inserted, their IDs increased.
That meant the table was already sorted by age.
1ID Created At
2
31 January
42 January
53 January
6...
7152,483 March
8...
9824,901 June
10...
11400,000,000 Today
That changed how I thought about the problem.
Instead of asking:
Which records are older than six months?
I could ask:
At what ID do records become newer than six months?
That sounds like a perfect problem for binary search.
#Binary Search
Binary search works by repeatedly cutting the search space in half. Imagine trying to find where six months ago falls within the IDs.
11 ------------------------------------------------ 400,000,000
2 ^
3 Check here
If the record at the midpoint is older than the cutoff date, the answer must be somewhere to the right. If it's newer, the answer must be somewhere to the left. Each lookup eliminates half of the remaining search space. With 400 million rows, finding the boundary only takes about 29 indexed lookups.
#Real Databases Aren't Perfect
Traditional binary search assumes every position exists. Database IDs usually don't. Instead of asking for an exact ID, I asked the database for the first row at or after the midpoint.
1$current = LogEntry::query()
2 ->where('id', '>=', $mid)
3 ->orderBy('id')
4 ->first(['id', 'created_at']);
That one small change makes the algorithm work even when there are gaps in the primary key.
#Finding the Cutoff
After removing all of the production code, logging, and cleanup logic, the algorithm becomes surprisingly small.
1protected function findLastEligibleId(Carbon $cutoffDate): ?int
2{
3 $low = LogEntry::min('id');
4 $high = LogEntry::max('id');
5
6 $cutoffId = null;
7
8 while ($low <= $high) {
9 $mid = $low + intdiv($high - $low, 2);
10
11 $current = LogEntry::query()
12 ->where('id', '>=', $mid)
13 ->orderBy('id')
14 ->first(['id', 'created_at']);
15
16 if (!$current) {
17 $high = $mid - 1;
18 continue;
19 }
20
21 if ($current->created_at->lt($cutoffDate)) {
22 $cutoffId = $current->id;
23 $low = $current->id + 1;
24 } else {
25 $high = $mid - 1;
26 }
27 }
28
29 return $cutoffId;
30}
Once the cutoff ID has been found, deleting the records is easy.
1LogEntry::where('id', '<=', $cutoffId)
2 ->chunkById(200, function ($logs) {
3 LogEntry::destroy($logs->pluck('id'));
4 });
The expensive part wasn't deleting the records. It was finding them.
#What About Performance?
I tested both approaches against a development database containing roughly 150,000 rows.
- The original search completed in about 44 ms.
- The binary search completed in about 21 ms.
At first glance, that doesn't seem like a huge improvement. The important part isn't how they perform on 150,000 rows.
It's how they scale.
The original query searches using an unindexed column. As the table grows, the amount of work grows with it. The binary search performs a small number of indexed lookups to find the cutoff ID. Whether the table contains one million rows or 400 million rows, it still takes roughly the same number of lookups.
That difference became obvious in production.
As the audit table approached 400 million rows, the original query became so slow that it was no longer a practical solution. The binary search continued to locate the cutoff quickly, allowing the retention job to delete records in manageable batches.
#Final Thoughts
I didn't invent a new algorithm. Binary search has been around for decades. What changed was how I looked at the data. Instead of treating the primary key as just another identifier, I realized it was already a sorted data structure. That opened the door to solving the problem without adding another index or making changes to a very large production table.
Sometimes the best optimization isn't a faster server or another database index. Sometimes it's recognizing that the data already has the structure you need. You just need to look at it from a different angle.