High Fibre Programming

It’s fairly common to need to iterate through all the rows in a given table and perform an action on each. The usual way to do this is fetch rows from the database in batches using LIMIT, specifying an offset and number of rows to be returned.

SELECT * FROM `myBigTable` LIMIT :OFFSET, :ROW_COUNT;

After each batch of rows is processed, the offset is increased by the size of the batch and the process is repeated until all rows have been processed.

Now that’s not exactly rocket science, but there is a problem – as the offset increases, the time taken for the query to execute progressively increases, which can mean processing very large tables will take an extremely long time. The reason is because offset works on the physical position of rows in the table which is not indexed. So to find a row at offset x, the database engine must iterate through all the rows from 0 to x.

The obvious solution would be to use the primary key instead of offset:

SELECT * FROM `myBigTable` WHERE `id` > :OFFSET LIMIT :BATCH_SIZE;

The problem here is that MySQL doesn’t guarantee that rows appear in the table in the same order as the primary key, so you could end up processing some rows twice, and worse still, some rows not at all. Luckily this can be easily solved by using ORDER BY:

SELECT * FROM `myBigTable` WHERE `id` > :OFFSET ORDER BY `id` ASC;

This might seem a bit counterintuitive using ORDER BY when we want to speed things up, but remember we’re ordering on a uniquely indexed column which will be fast anyway, and compared to the alternative of iterating through each row using an offset, it’s a huge improvement.

Conclusion

The general rule of thumb is “never use offset in a limit clause”. For small tables you probably won’t notice any difference, but with tables with over a million rows you’re going to see huge performance increases.

Remember, this doesn’t just apply to iterating through tables but whenever offset is used. For example implementing pagination of large tables, if the first few pages load quickly but subsequent pages load progressively slower then it’s likely this is the cause (or you are missing some indices!)

The PEAR Cache_Lite package is an excellent caching system; lightweight and fast, however when put into use on a high-traffic website a few issues came to light. The first problem we hit was stampeding.

What’s stampeding?

Stampeding is the situation when a request, let’s say from User1, arrives for a cached item that has expired. The cache system returns boolean false and the process of rebuilding that cached data begins, calling the database, formatting the data and so on.

If, during this process of rebuilding the cached data, another request arrives for the same cached item, let’s say from User2, another process of rebuilding the cached data begins. This is because the process started by User1 has not yet finished and so the cache system still returns boolean false when requested for the cached item.

So now we have two processes running, regenerating the same cache item. The situation can get out of hand if more and more requests for the same cache item arrive – causing the load on the web server or database to increase, and everything to potentially grind to a halt.

The solution

What’s required is for the cache system to know that a particular cache is being regenerated and therefore return the old cache until the new data has been regenerated. Thankfully this can be achieved very simply with the addition of just one extra line of code into the Cache_Lite class, Lite.php.

The trick is to touch() the cache file immediately after realising it has expired in the Cache_Lite::get() function. After touching the file, the get function will return false and the calling code will regenerate the cache data.

@touch($this->_file);

By touching the file, the modification time of the cache file is set to the current time and therefore all subsequent requests will think the cache is still valid and return the old data. Once the first process has regenerated the data, it saves it and the cache file once again contains up-to-date data.

Some finishing touches

By touching the cache, processes immediately following the one which is regenerating the fresh data will return out-of-date data, albeit by a matter of seconds – which in most cases really won’t matter nor be noticed.

If, however, something were to happen to the process regenerating the data, such as an uncaught exception, database timeout, etc that it would fail and not save the cache, then the old cache will be valid until it expires again – so it will have effectively been valid for twice its intended lifetime.

We can limit this by setting the modification time in the touch command to be the current time, minus the cache lifetime, plus 60s – which would mean that if the regenerating process were to fail, the cache would only be valid for another 60s.

@touch($this->_file, time() - abs($this->_lifeTime) + 60);