Fun MySQL fact of the day: multi-range read optimisation

So far this week, we've looked at 2 of the 3 Nested-Loop Join algorithms MySQL can use to join tables. Before we look at the third one, we need to take a quick detour.

If you recall way back to late March and early April, we discussed how InnoDB stores data in a PRIMARY index. Specifically, you may recall that the PRIMARY index sorts records in primary key order, and each record in the PRIMARY index may be referenced by any number of secondary indices by, again, primary key. You'll also recall that secondary indices are sorted in index order; for example, in a secondary index (a,b,c), records are sorted in ascending order of a->b->c->pk. You may also recall some of the various optimisations we've discussed that MySQL may choose to use when executing your queries. For example, Covering Index Optimisation and Index Condition Pushdowns. And while these optimisations are great, MySQL has even more tricks up its sleeve.

Now, let's imagine a query with a result set of several hundred rows, perhaps something like SELECT * FROM my_table WHERE some_field IN (68, 120311, 384347, 993). Let's also consider that MySQL may choose to perform multiple range scans on a secondary index prefixed with some_field, simply finding one record after another in ranges 68, 993, 120311, and 384347 (or some combination thereof). Let's also assume that, to answer this query, MySQL cannot use Covering Index Optimisation. Then, as you may recall, normally, without Covering Index Optimisation, when InnoDB finds a row from a secondary index, it will use the primary key associated with the record to look-up the row in PRIMARY. You can appreciate that this may result in a substantial amount of random IO since the two indices are not ordered the same way: it's quite possible each interesting record in PRIMARY is on a separate extent or page.

To help reduce the amount of random IO necessary to answer this query, MySQL may decide to use Disk-Sweep Multi-Range Read Optimisation (DSMRR). You'll know it's happening when the Extra column of your EXPLAIN shows Using MRR. When using DSMRR, instead of having the storage engine immediately read the full record from PRIMARY, MySQL buffers the primary key from each secondary index record in a buffer of size read_rnd_buffer_size (default 256KB). Once this buffer is full, MySQL will sort the buffer and then retrieve each record from PRIMARY in primary-key order. This increases the probability of finding multiple rows in the same page or extent and leverages other related disk access optimisations the storage engine offers.