Rails, MYSQL and clustered primary keys

Rails by default creates every table with a primary key of ‘id’.  This is a sequence generated key that is globally unique.  There are benefits for insert performance, but depending on your usage model query performance can be impacted by this scheme.

Consider the case of an application, a (the stereotypical) blog that has posts and comments.  Imagine that this is a reasonably high volume blog, so we have lots of posts, and lots of comments, and the nature of the blog is that old posts attract comments over time.

We would end up with data perhaps like the following:

  POSTS
  id     title                                           user_id
  1      My first blog post                                 1
  2      This blogging is wonderful                         1
  3      I'm running out of stuff to write already          1
  4      Look at the funny pictures of my cat               1

  COMMENTS
  id     post_id         comment                         user_id
  1         1            Wow it's exciting you have....     2
  2         1            I know, I'm so excited that ..     1
  3         2            It is wonderful, isn't it ....     2
  4         3            What about your cat ...            2
  5         4            Those are great pictures ...       2
  6         3            Great idea, I posted yest...       1
  7         1            Hey, cool new blog, I'm telling    3
  8         1            John told me about your blog       4
  9         3            Your dog is pretty funny too..     5
  10        3            Fred told everyone about your      2

What we can see is that our comments are getting interleaved – the comments for a blog post are not all together. Inserting always at the end of the table is great for insert performance, it minimises the amount of work in moving data around on disk. But typically inserts are a small fraction of our work – and when you insert you normally insert one thing at a time (one comment, one post). So you can afford a bit of work.

Conversely, this structure isn’t great for query performance. If we imagine that our blog has a model where we get a post, and then show on the bottom of that post all the comments, then we’re going to frequently get all the comments for a given post. We’d obviously build an index on post_id on the comments table.  But if we recall that our database is organised based on pages, what our comment table might look like on disk is:

  COMMENTS
  id     post_id         comment                         user_id
  1         1            Wow it's exciting you have....     2
  2         1            I know, I'm so excited that ..     1
  3         3            What about your cat ...            2
  ------------------------------------------------------------
  4         2            It is wonderful, isn't it ....     2
  5         4            Those are great pictures ...       2
  6         3            Great idea, I posted yest...       1
  ------------------------------------------------------------
  7         1            Hey, cool new blog, I'm telling    3
  8         1            John told me about your blog       4
  9         3            Your dog is pretty funny too..     5
  ------------------------------------------------------------
  10        3            Fred told everyone about your      2

Consider what the database has to do to retrieve all the comments for post 3:

  1. Go to the secondary index for posts, and get the pages in that index that relate to post 3.  This tells you that you need row ids 3, 6, 9 and 10
  2. Go to the table itself (in MYSQL, actually stored as part of the clustered index) and get row 3
  3. This brings into memory page 1, any more retrieves from page 1 will be fast.  But we need no more rows from page 1
  4. Go to the table and get each of rows 6, 9 and 10.  Each of those also bring a page into memory

Sure, on this example, we’ve retrieved 4 rows and it’s cost us 4 pages, plus probably 1-2 index pages, so 6 physical IOs in total.  But on a larger table, this starts to get significant. I’ve built a sample app that has a table where I want to retrieve 1,000 rows in my query, and that table has 1 million rows. The query (on my dodgy server) can take around 5-6 seconds.

What we’d ideally do instead is to change our primary key to be (project_id, id).  This would then organise our database as follows:

  COMMENTS
  id     post_id         comment                         user_id
  1         1            Wow it's exciting you have....     2
  2         1            I know, I'm so excited that ..     1
  7         1            Hey, cool new blog, I'm telling    3
  ------------------------------------------------------------
  8         1            John told me about your blog       4
  4         2            It is wonderful, isn't it ....     2
  3         3            What about your cat ...            2
  ------------------------------------------------------------
  6         3            Great idea, I posted yest...       1
  9         3            Your dog is pretty funny too..     5
  10        3            Fred told everyone about your      2
  ------------------------------------------------------------
  5         4            Those are great pictures ...       2

What we can see is that now the comments for post number 3 are all side by side, so when we go to the table to get a page, the odds are that the page also has other data that we want – we’re reducing our physical IO. Recall also that physical IO is the biggest killer for database performance. In the case of our hypothetical query we’re now avoiding the lookups on the secondary index at all, and we’re retrieving 2 pages from the clustered index – in short, we’ve gone from 5-6 IOs down to 2 IOs.

On my larger sample table, the query comes down to around 400ms, assuming nothing was already in the page cache. This is driven by a reduction in IO, which also reduces the amount by which you’ll empty your cache (i.e. since this user is clearly on a particular post, if they do other things on that post – say, getting the next page of comments, odds are the data they want will be in cache).

Now, in many systems we’d simply go and change the database structure.  Our application typically doesn’t know what’s going on in the database, it just issues queries against it and doesn’t care how the data is physically organised.  However, there’s a big gotcha with Rails.  Rails does lots of things automatically for you to avoid you having to code them.  It does that by introspecting the database structure – it goes and asks the database what columns there are in a particular table, and then adds all those columns into your model as attributes.  This is goodness from a productivity viewpoint.

Unfortunately, what it also does is to use the primary key to decide some things, including to work out which record is the last record in the database when you call, for example, Comment.last.  And the rails magic that does that gets very upset if you change the primary key on the table so that it’s anything other than id.

I’ve tried a few flavours of this, and the short answer here seems to be:

  1. MYSQL won’t cluster by anything other than the primary key if the primary key is unique
  2. You can’t use partitioning to achieve the same result, because there are limits on the number of partitions, both physical and administrative, and because any partitioning key must also be present in any index (so we can’t partition on post_id, it’s not present in the primary key)
  3. Rails won’t let you change the primary key

I’ve looked into the composite_primary_keys Gem, which lets you change the primary key.  I’m nervous because it doesn’t look extremely well supported, Rails 4 is coming, and it seems much more invasive than what I intended for this relatively simple use case.  I’m actually not aiming to change the way Rails uses the table, I’m just aiming to order it differently on disk.

I’ve debugged through some of the code that breaks to see what is going on.  The underpinnings seem to be a structure called Arel, presumably standing for array of relationships, or something similar.  This looks to be the structure that is filled in when the database is introspected, and the @primary_key within this structure is nil if you change the primary key.  This in turn breaks Comment.last, as it’s looking to add an order_by clause based on the column in the primary key. Which is sort of amusing, because Rails doesn’t let you have a primary key other than id, but it still goes and asks the database what the primary key is. Perhaps at some point there was intent to allow different keys. Perhaps that’s how composite_primary_keys works.

My theory is that I can patch this such that the Arel structure, if there is no primary key found, assumes that the primary key is “id”, rather than leaving it nil.  For my application, I could directly patch this because all my tables have primary keys.  If this were to be contributed back into the Rails base, then I’d do it as something switchable on the model itself – so in the model you could declare:

assume_primary_key: true

And Rails would assume, for that table, that the primary key is “id” even if it couldn’t get that from the database.

Something to look at sometime when I have enough spare time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s