When to use surrogate keys in InnoDB tables at Xaprb

When to use surrogate keys in InnoDB tables

InnoDB is a special case among MySQL storage engines because they have clustered indexes, which means surrogate keys have to be treated differently in InnoDB. This article gives a quick overview of clustered indexes, and explains why they make it even more important to do careful analysis before making decisions about surrogate keys on InnoDB tables.

Overview of clustered indexes in MySQL

A clustered index is just like any other index, except the index holds the data itself, in index order. That is, the index’s leaf nodes are the rows of the table, and the rows are sorted by the index. Because the rows are sorted by the index, there can be only one clustered index per table.

This means when a query uses an index seek to find a row, the seek moves through the index and lands on the data itself. By contrast, non-clustered indexes store a pointer to the data, and the query must then do a “bookmark lookup” to get to the data.

You probably see now why clustered indexes are important. They can create huge performance increases. Once the query finds the data, it has the data — there’s no need to read through more pages (i.e. wait for the hard disk to respond) and do bookmark lookups to find the data. And since the rows are stored in index order, queries that work with ranges of data can use the clustered index to great effect. For example, if a table’s data is clustered on date, it’s highly efficient to select all rows newer than a certain date. The query just seeks into the index and finds the first row; then everything else in the table is guaranteed to be newer, so the query can blindly read every remaining row.

Clustered indexes in MySQL

MySQL’s storage engines are all different. Only InnoDB offers clustered indexes, and InnoDB makes the primary key the clustered index. This means the choice of primary key is critical to performance on the InnoDB engine, especially as tables become large.

Another important factor is the way InnoDB handles non-clustered (also known as secondary) indexes. Instead of pointing directly to the row, each leaf node in a secondary index contains a tuple from the clustered index (otherwise, maintaining secondary indexes would be extremely expensive in the case of a page split). That means secondary indexes are actually at a slight disadvantage in InnoDB compared to other storage engines, because using the index requires navigating two indexes. It also means the size of each secondary index is dependent on the size of the clustered index.

What does this have to do with surrogate keys? Since MySQL doesn’t allow an AUTO_INCREMENT column unless it’s part of the primary key, and InnoDB further restricts this to force it to be the primary key, the clustered index is totally wasted on a meaningless number.

Unfortunately, many people seem to instinctively add an AUTO_INCREMENT column as a primary key by default. Search around the web and you’ll see people frequently giving that advice when telling a beginner how to design tables. Choosing a primary key by examining the data and finding its inherent primary key can help avoid a performance killer.

Exceptions to the rule

There is an important exception to the “avoid surrogate keys” principle. If the table’s primary key is large, the non-clustered indexes are also large, so non-clustered indexes become much less efficient. Not only is a non-clustered index less efficient, the value that results from the non-clustered index’s seek is large too, so navigating the primary key is slower, too. In these cases, using a surrogate key may actually improve performance. It depends on the table.

Written by Xaprb

May 10th, 2006 at 8:55 pm

Posted in SQL

5 Responses to 'When to use surrogate keys in InnoDB tables'

Subscribe to comments with RSS or TrackBack to 'When to use surrogate keys in InnoDB tables'.

[...] When to use surrogate keys in InnoDB tables [...]

9rules Featured » Blog Archive » Featured blogger: Xaprb

17 May 06 at 1:28 am
This is perhaps just me trying to be too smart. Or missing the obvious. But…

I picked up on clustered indexes from your “case study in profiling queries in MySQL”.

Then I read the manual. Then I came up with this idea. Instead of:
```
CREATE TABLE impressions (
  id int NOT NULL auto_increment,
  epoch int NOT NULL,
  count int NOT NULL,
  PRIMARY KEY (id),
  INDEX epoch_idx (epoch)
) ENGINE=InnoDB;
```
I could instead do:
```
CREATE TABLE impressions (
  id int NOT NULL auto_increment,
  epoch int NOT NULL,
  count int NOT NULL,
  PRIMARY KEY (epoch, id),
  UNIQUE INDEX id_idx (id)
) ENGINE=InnoDB;
```
I need the id column to join with other tables, and there can be multiple rows with the same epoch, so epoch cannot be unique.

The vast majority of my queries are operating on a subset of the impressions table and the vast majority of those use epoch to pick the subset.

I then created some sample data using the following perl:
```
my $time = time;
for (my $i = 1; $i < 250000 + 1; $i++) {
    my $r1 = $time - int(rand(100000));
    my $r2 = int(rand(10000));
    print "$i\t$r1\t$r2\n";
}
```
And then used:
```
LOAD DATA INFILE 'sample.sql' INTO TABLE impressions;
```
Note that I’m using exactly the same data on both tables. On my Macbook Pro, the first table loaded in about 6.19 second. The second took 70.16 seconds. Worse yet, as the number of rows increased, the times for the second table appeared to be growing exponentially!

My current working hypothesis is that the extra size used for the clustered index in the second table is causing the problems. Aka your “exceptions to the rule.” But I’m frankly not sure and a little curious. If I shifted the epoch to be seconds since 1st Jan 2000 would that help? Or if I carefully managed my insert process so that I appended a dot followed by an counter to multiple rows with the same epoch - would that help?

How big is too big for the primary key in an InnoDB table?
Murray

28 Feb 07 at 5:01 pm
I would say the choice of (epoch, id) is probably not good for your primary key. You’re inserting random data into epoch, and the table is clustered epoch-first, so you’re going to cause lots of page splits and b-tree re-balancings as you insert the data. That alone might explain the slowness.

If insert speed is your priority, I’d stick with the first table design. But now that you’ve got the data into the second table, test how fast the queries run against it. You’ve just artificially unique-ified a non-unique value, and it might be a good trade-off.

Use SHOW TABLE STATUS to see how big the table and index data is. Compare the two designs. The second will probably be quite a bit bigger.

Xaprb

28 Feb 07 at 8:32 pm
[...] older article from the same site provides a bit more [...]

Marcus Schwartz » Blog Archive » Optimizing MySQL Indexes

30 Nov 07 at 2:49 pm
Murray,

As Xaprb said, your second insert is slow because you are inserting in a random order. Before loading, sort your data in primary key order and the two inserts should run in similar time.

David Phillips

10 Dec 07 at 6:17 pm

Xaprb