Playing with MySQL’s index merge

So, I mentioned before that I found out about index_merge at the MySQL Conference. I was wondering why I had not heard more about it since it came out in 5.0.3. When talking with some MySQL people about it, I received mixed results. So, I decided to kind of run my own tests on some data and see what I could figure out.

I apologize for WordPress’ bad output. =(

The Data

I created a table with 5 million rows. Early tests with MySQL’s Harrison Fisk (HarrisonF) over my shoulder with small data sets showed MySQL would optimize out the indexes in favor of table scans. I wanted to avoid that. This is my table schema:


CREATE TABLE `test2` (
`id1` int(10) unsigned NOT NULL default '0',
`id2` int(10) unsigned NOT NULL default '0',
`id3` int(10) unsigned NOT NULL default '0',
`dt` datetime NOT NULL default '0000-00-00 00:00:00',
`somevar` varchar(255) NOT NULL default '',
KEY `id1` (`id1`),
KEY `id2` (`id2`)
) ENGINE=MyISAM

The field id1 was filled with random vaules between 1 and 5000. I filled id2 with random values between 1 and 100, except that about half the data has the value 999 in it. This was to emulate the issue we were seeing on the smaller table. We found that if a value was in more than n% of the rows, the optimizer would skip the index. I wanted to test that on larger data sets. id3 was filled with random values between 1 and 1000000. dt was a random date/time between 1999 and 2008. and somevar was a random string chars.

Intersect Merges


mysql> explain select count(*) from test2 where id2=99 and id1=4795;
+----+-------------+-------+-------------+---------------+---------+---------+------+------+----------------------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------------+---------------+---------+---------+------+------+----------------------------------------------------+
| 1 | SIMPLE | test2 | index_merge | id1,id2 | id1,id2 | 4,4 | NULL | 3 | Using intersect(id1,id2); Using where; Using index |
+----+-------------+-------+-------------+---------------+---------+---------+------+------+----------------------------------------------------+

This is the most basic of example. MySQL uses the two indexes, finds where they intersect and merges the data together. This query is quite fast, although a key on the two together would be faster. If you have this showing up a lot, you probably need to combine the two keys into one. I should also note that in this example, only the keys are needed, no data from the tables. This is important.


mysql> explain select sql_no_cache somevar from test2 where id2=99 and id1=4795;
+----+-------------+-------+------+---------------+------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+-------+------+-------------+
| 1 | SIMPLE | test2 | ref | id1,id2 | id1 | 4 | const | 930 | Using where |
+----+-------------+-------+------+---------------+------+---------+-------+------+-------------+

As you see, as soon as we ask for data that is not in the indexes, our intersect is dropped in favor of using the key with the least values and simply scanning on those to match the rest of the where clause. This was the case pretty much every time I tried it. I was never able to use an index_merge with intersect when requesting data not available in the key.

Union Merges


explain select sql_no_cache somevar from test2 where id2=99 or id1=4795;
+----+-------------+-------+-------------+---------------+---------+---------+------+-------+-----------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------------+---------------+---------+---------+------+-------+-----------------------------------+
| 1 | SIMPLE | test2 | index_merge | id1,id2 | id2,id1 | 4,4 | NULL | 27219 | Using union(id2,id1); Using where |
+----+-------------+-------+-------------+---------------+---------+---------+------+-------+-----------------------------------+

mysql> select sql_no_cache somevar from test2 where id2=99 or id1=4795;
26237 rows in set (0.20 sec)

This merge type takes to keys involved in an OR and then merges the data much like a UNION statement would. As you can see, in this case, it did use the index even though we requested `somevar` that is not in the index.

To show the alternative to this, I selected using id3 instead of id1. id3 has no index.


mysql> explain select sql_no_cache somevar from test2 where id2=99 or id3=266591;
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| 1 | SIMPLE | test2 | ALL | id2 | NULL | NULL | NULL | 5000000 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+

mysql> select sql_no_cache somevar from test2 where id2=99 or id3=266591;
25252 rows in set (26.01 sec)

As you can see, this does a table scan even though there is a key on id2. It does you know good.

Sort Union Merge


mysql> explain select sql_no_cache id1, id2 from test2 where id2=99 or id1 between 4999 and 5000;
+----+-------------+-------+-------------+---------------+---------+---------+------+-------+----------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------------+---------------+---------+---------+------+-------+----------------------------------------+
| 1 | SIMPLE | test2 | index_merge | id1,id2 | id2,id1 | 4,4 | NULL | 44571 | Using sort_union(id2,id1); Using where |
+----+-------------+-------+-------------+---------------+---------+---------+------+-------+----------------------------------------+

mysql> select sql_no_cache somevar from test2 where id2=99 or id1 between 4999 and 5000;
27295 rows in set (0.19 sec)

This behaves much like the union merge. However, because one index is using a range, MySQL must first sort one index and then merge the two. Again, if I switch this to an AND instead of an OR, index_merge is not used in favor of scanning the id2 indexed data for matches to the rest of the where clause.

Conclusion

Hmm, after all this, I see why this was not a big announcement. It can only make bad SQL and tables better. Tables and queries that are already optimized using composite indexes will see no benefit from this. At best this will help me with some one off queries or reports that are only run monthly where I don’t want to pollute the indexes with special cases just for those queries.

Advertisements

One Response to Playing with MySQL’s index merge

  1. > I was never able to use an index_merge with intersect when requesting data not available in the key.

    The optimizer is actually able to use and will consider the plan where it does index_merge intersection plus full record fetch to get columns that are not index (i.e. ‘using intersect’ w/o ‘using index’).

    However, this plan is only useful when adding cost of reading the second index allows to significantly reduce the cost of reading full records. This happens then table records are much bigger than index records.

    Overall we’re trying to be conservative here because sometimes index conditions are correlated – you get nearly the same sets of records selected by both indexes, and expending the cost to scan the second index doesn’t give you much.

    To sum up, index intersection is useful when you have *big* table and can’t afford maintaining a composite index.

    Hope that clarifies things a bit.

    Sergey Petrunia, index_merge implementor.

%d bloggers like this: