Category Archives: MySQL

The hardest task to do well in every frontend/backend system – paging

What is the hardest code to write efficiently in pretty much every frontend and backend system? I think it is paging.

Nearly every system I’ve worked on as full-stack developer has had some sort of reporting whether it is searching and filtering or news-feed style item display, all of these depend on paging. Whilst simple paging is trivial to implement, making it work quickly at scale is a very tricky challenge.

A simple approach (based on SQL, but could be with any backend data store) would be something like:

It looks simple and it works in small-scale development systems. But there a massive number of issues and inefficiencies with this approach:

  • Whilst you need to redo the items query for every page, the count query only needs to be done once for each <query>. Counting is a very expensive operation as it essentially has to fetch all the rows, unless there are some very well optimized keys on your table. This especially the case if you are running over a table larger than a few megabytes on a mobile device, so you need to cache this as much as possible.
  • Often times as the <order> logic has gotten more and more complex I’ve found myself in a situation where some rows are equal in ordering and so they can move around as you switch between pages or redo the query. Always ensure that the last item of ordering is something which is well ordered to avoid this, for example an integer primary key
  • What happens with a LIMIT/OFFSET type query if you get a row inserted before the OFFSET? All the rows shift forwards by one so when you scroll down on your infinite feed you get a duplicate, or the user goes to the next page and sees a repeat of the last entry of the previous page. What happens when a row prior to the OFFSET is deleted? A row between the pages is not seen by the user. In some databases it may be possible to use a long-lived cursor but often in stateless backends for webapps this is not possible. Wherever possible you should try to get a column on the <order> which is simply increasing or decreasing and redo the previous query with use a > against that to ensure you fetch all the rows from the previous point the user saw regardless of what changed above it. This is easy when sorting by primary key, difficult or even impossible otherwise.
  • How do you handle a laggy backend when the user presses the next button multiple times? Does it re-fire the request for the next page multiple times to the backend (consuming unnecessary resources), ignore any presses after the first (better), or does it proceed forward multiple pages, potentially running past the last page and onto blank pages? I’d usually opt for the second approach but limiting so that it always stops on the last page, but it may vary depending on usage case (would users typically want to skip multiple pages quickly, or always want to page through one-at-a-time), backend latency (ie is the data stored locally or remotely, what is the connectivity like)
  • Following on from the above, if you are firing multiple requests for pages, or for infinite scrolling how do you cope with the fact that responses can come back out-of-order? Many times I see it would simply display the content from the last page returned, but this is open to a number of bugs if you are talking about remote services over wireless
  • How do you efficiently abort in-fly calls and database queries if the user changes page – on a large system this could be a significant performance gain

There are quite a large number of optimizations that can be done with paging code, whether this is with a remote backend or locally, for example:

  • Prioritize getting the first page of data to display, say “Showing results 1-50 of …” while the count is loading
  • Track historical data on how long it takes to generate counts or paging, and especially if running single-threaded (eg on a mobile device), delay the count until the main queries have completed and there is some idle time
  • Is it possible to parallelize the two querys against the database so that the query takes half the real-time for the user? Can you use non-blocking IO to open two database connections, one for each query and return a response when both have completed? Can you run 2 separate queries one for count and one for items and update your pager and results separately? For a few rows in a test system this won’t make any difference, but over millions of rows, especially if you need an accurate count, this can save seconds of time
  • Do you actually need a totally accurate count, or can you approximate it, does your database backend support something like this for queries? This can save significant time and resources
  • Have you set up good indexes and verified that they are correctly being used at the scale that you will have in your live environment? Do you optimize well for the common use case?
  • You don’t always need to bother running a count query – if the items returned are less than the items requested you know that you have finished paging and you can automatically count the total from that. This is true whether on the first on the 100th page.
  • Fetch the number of rows that you want to display plus one, so that you know if there is a next page or not. If the number of items is less than you requested you know there won’t be a next page no matter what the total actually is
  • If running on mobile devices or html, limit the number of items that are displayed on an infinite scroller as this can be very memory intensive. Perhaps allow infinite scrolling over 500-1000 rows and then put a next button at the bottom of the page. Or you can do some trickery to replace the top items with a large blank box but this can be very complex and difficult to do well
  • Don’t display a spinner when infinite scrolling (you are starting to load more items before the user hits the bottom of the list right?) Only display the spinner after a short time period or when the user hits the very bottom of the list to give visual feedback that there are more items loading to display

If this looks like a lot to think about, I don’t disagree. Simple, buggy and inefficient paging is easy to do, but fully-optimized, highly responsive complex paging is very tricky to do well. But if you want to scale your app you need to focus on this.

Mongo DB Pain

In my latest contract we’re gathering a lot of data very quickly (100k inserts/sec would not be unreasonable) and trying to save it into a database. Before I started the contract the decision had been made to use Mongo Database for this very reason, so when I joined I was glad to finally get a chance to play with some NoSQL software – up until now I’ve just used MySQL and PostgreSQL. There’s some software and programming languages where the more you use them the more they pleasantly surprise you. AngularJS is one of those pieces of software where you start with basic templating and form-element binding but quickly discover there’s a mass of great plugins available. PostgreSQL is another case in point – I had been using MySQL quite happily for years but since starting to use PostgreSQL for some geolocation projects (with the excellent PostGIS extension), I’ve started using it by default for any new projects or designs. At the start it seems like just another database server with some geospatial additions, but then you think “Perhaps I can get the database to validate my input data before inserting”. No problem for Postgres you can specify a regexp constraint for example CHECK (mac ~ '^[0-9a-f]{12}$'::text) to validate a mac address (but you probably want to use the built-in type macaddr). Good luck with doing this in MySQL – by default it doesn’t even care about inserting the wrong data type into a column just silently messes it up… Or perhaps you want to import data from another data source into Postgres – again Foreign Data Wrappers (FDW) to the rescue connecting in to pretty much any other database or data source that you could want.

With Mongo however the more I’ve learnt of it the less impressed I’ve become. Sure, you can do some nice searches without needing schemas and it’s pretty high performance however once you go past simple store/retrievs there are some pretty basic issues that have not been addressed. Here are two I’ve come across in the past week:

Firstly, we have a big table (500m records) with data in a composite primary key (id, timestamp). We have the index on that, and we want to get a list of all the ids in the table. No problem you think – it’s a simple btree; just walk it and you’ll pull out the ids. And yes, it should be like this however there’s no easy way to do this in Mongo. The first thing you see in the documentation is that there is a .distinct() function or a .group() function. Great to get the distinct ids just run db.collection.distinct('id'). However rather than doing something sensible and returning the distinct fields with a cursor it tries to return them all in a single BSON object which is capped at 16mb size. So, if you have less then perhaps 1 million distinct ids in your table it would work, once you go over some magic threshold then your entire process needs redesigning.

Then you notice that in the latest versions of MongoDB, the .aggregate function can return a cursor. So, something like:

should do it. Technically speaking yes, however an open bug report from 4 years ago explains that actually the $group function can’t use indexes. If you add an explain: true to the aggregate you see that it does a full collection scan. But, perhaps if you are clever and force the sort like:

it will use the index, and indeed the explain output shows that it does. However even then it has to search through the whole table before it returns the first item for the cursor! So, if your distinct result is possibly more than 16mb of data in a large table there doesn’t seem to be any way to get the data in a timely manner from the database.

Another issue that I ran into and reported upstream is to do with very poor index selection on the aggregate. See the ticket for more details, but if you run an aggregate query on a collection with the foo column as a unique key:

for some reason Mongo doesn’t follow the obvious and use the first item in the aggregate pipeline as the index. Instead, it chooses to use the _id index meaning that the $match does a full table scan to find the one result that could have been instantly looked up if it had used the correct index. The .find().sort() pipeline doesn’t have this issue.

There was also a fun issue I discovered whereby when you get a hot row in the database (for example a lot of processes trying to use $inc to update a counter) performance gets absolutely killed by the spinlocks on the data structure. Rather than 50k upsert/sec on the cluster when we had this hot row it went down to about 3k upserts/sec.

This is not to say that Mongo is a bad product, certainly looking at posts from a few years ago it seems that it has come on leaps and bounds since then. However it’s not the be all and end all that many NoSQL champions would claim. And I’m not convinced that the other NoSQL type databases would be all that much better – certainly for basic store/fetch operations but as you get closer to needing the functionality of a traditional RDBMS they are just too immature. Other issues for us recently have been lack of JOIN statements, the lack of schema that means a simple typo on a query can cause it to hang doing a full table scan for a key that doesn’t exist, etc etc. These are not problems with Mongo per-se but rather an issue with the incredible flexibility that NoSQL products offer.

Would I use Mongo again in other projects? Yes probably, but only if we had a requirement for very high performance or schema-less flexibility that something like PostgreSQL simply couldn’t provide.

Blacklisting domains using PowerDNS Recursor

I recently had a client that was wanting to provide a recursive DNS service within his company, however wanted to blacklist a lot of domains to redirect internally. And I mean a lot – over 1 million porn/spam/… domains. It’s one thing to use the excellent unbound recursive DNS software and set up the blocks using the local-data argument, but it was requiring over 6gb of memory to load the list and crashing the process because of that.

As it turns out, yet again PowerDNS to the rescue. I love PowerDNS for its flexibility (so much so that I created a very high performance DNS backend for it and also run a company consulting on DNS deployments).

As the full list of domains would not fit in memory we had to use a database, I took inspiration from a previously posted Lua script which used a tinycdb. Unfortunately tinycdb requires manual compilation and so wasn’t an option, and as the client already had the list of domains in a MySQL deployment we ended up using that. Both PowerDNS authoritative server and recursor can support Lua scripting to do pretty much anything you need, and there are a number of database options that Lua can use. I started off using luadbi as it seemed to have a nicer interface, however unfortunately luadbi only supports lua 5.1 whereas the debian build of PowerDNS uses lua 5.2. This meant switching to use luasql which is a bit lower-level.

So, the following Lua script will redirect any blacklisted subdomains (in the mysql table domains with field name) to 127.0.0.1:

As establishing a MySQL connection each request is quite a high overhead it might well be worth switching to use SQLite in the future, this should be very simple to do by just changing the driver name and connection string.

How (not) to use PostgreSQL functional indexes

Working on a project where we want to store searchable (using LIKE, meaning we can’t use the inbuilt Postgres macaddr type) MAC addresses in a PostgreSQL table I decided create a unique index in order to only allow one modem per entry in the table and also to speed up searches. However we also want to ensure that we dodn’t get upper- and lower-case versions of the same MAC inserted. PostgreSQL to the rescue – you can create a functional index on the table:

Basically this means that it should first lowercase anything that gets inserted, and then check that the unique constraint isn’t violated. It should also mean that something like:

should be indexed and hence work really quickly.

However, while profiling the application I noticed the select statements getting slower and slower the more rows we put into the table – the classical way of seeing that a column is not properly indexed. Looking at the postgres manual I remembered that a functional index actually only speeds up queries where you apply the function to the column, for example something like the below would use the index:

Functionally this was the same as what I was doing, but I didn’t want to have the hassle of remembering to apply that function everywhere we wanted to search by mac. In the end I decided to drop the functional index and just use a standard unique index. I then added a type constraint check which also enforces the value being hex:

Did I ever mention how I love postgres? Take that MySQL!

Easily dumping sample data from any database

Following on from my previous post on the wonders of perl’s DBIx::Class::Schema::Loader, after you have dumped the schema using either the perl scripts provided or the dbicdump commandline tool, you can easily dump the first few rows of each table in JSON using the following very simple perl script:

To dump the whole table simply remove that rows => 10 bit (although as it loads each table into memory and keeps it there before dumping I wouldn’t advise this!)

Alternatively for a NoSQL database like MongoDB: