August 10, 2006

Using UNION to implement loose index scan in MySQL

Posted by peter

One little known fact about MySQL Indexing, however very important for successfull MySQL Performance Optimization is understanding when exactly MySQL is going to use index and how it is going to do them.

So if you have table people with KEY(age,zip) and you will run query something like
SELECT name FROM people WHERE age BETWEEN 18 AND 20 AND zip IN (12345,12346, 12347) do you think it will use index effectively ? In theory it could - it could look at each of the ages from the range and look at all zip codes supplied. In practice - it will not:

PLAIN TEXT
SQL:
  1. mysql> EXPLAIN SELECT  name FROM people WHERE age BETWEEN 18 AND 20 AND zip IN (12345,12346, 12347);
  2. +----+-------------+--------+-------+---------------+------+---------+------+-------+-------------+
  3. | id | select_type | TABLE  | type  | possible_keys | KEY  | key_len | ref  | rows  | Extra       |
  4. +----+-------------+--------+-------+---------------+------+---------+------+-------+-------------+
  5. |  1 | SIMPLE      | people | range | age           | age  | 4       | NULL | 90556 | USING WHERE |
  6. +----+-------------+--------+-------+---------------+------+---------+------+-------+-------------+
  7. 1 row IN SET (0.01 sec)

As you see instead only first index keypart is used (key_len is 4) and zip part where clause is applied after rows are retrived. Notice Using Where. There are even more bad news. Full rows will need to be read to check if zip is in the list, while it could be done only by reading data from the index. MySQL can ether read index only for all rows, in this case you will see "Using Index" in EXPLAIN output or it will read row data for all rows - it can't read Index and perform row read only if it needs to be done at this point.

So MySQL Will not use indexes in all cases when it is technically possible. For multiple key part indexes MySQL will only be able to use multiple keyparts if first keyparts matched with "=". Here is example:

PLAIN TEXT
SQL:
  1. mysql> EXPLAIN SELECT  name FROM people WHERE age=18 AND zip IN (12345,12346, 12347);
  2. +----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
  3. | id | select_type | TABLE  | type  | possible_keys | KEY  | key_len | ref  | rows | Extra       |
  4. +----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
  5. |  1 | SIMPLE      | people | range | age           | age  | 4       | NULL |    3 | USING WHERE |
  6. +----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
  7. 1 row IN SET (0.00 sec)

Note number of rows has decreased from 90556 to 3, whle "key_len" remains the same. This however looks like a bug in the MySQL 5.0.18 I'm using for this demo. It should have had increased to 8.

Lets see how query times differ in these cases:

PLAIN TEXT
SQL:
  1. mysql> SELECT  sql_no_cache name FROM people WHERE age=19 AND zip IN (12345,12346, 12347);
  2. +----------------------------------+
  3. | name                             |
  4. +----------------------------------+
  5. | 888ba838661aff00bbbce114a2a22423 |
  6. +----------------------------------+
  7. 1 row IN SET (0.06 sec)
  8.  
  9.  
  10. mysql> SELECT  SQL_NO_CACHE name FROM people WHERE age BETWEEN 18 AND 22 AND zip IN (12345,12346, 12347);
  11. +----------------------------------+
  12. | name                             |
  13. +----------------------------------+
  14. | ed4481336eb9adca222fd404fa15658e |
  15. | 888ba838661aff00bbbce114a2a22423 |
  16. +----------------------------------+
  17. 2 rows IN SET (1 min 56.09 sec)

As you see difference is tremendous. And it is not what you would intuitively expect - why range which covers 5 rows is hundreds of times slower than single row ? If MySQL Optimizer would handle this case right it would not be but in this case we only can give a hand to MySQL Optimizer and change the query so it can handle it well.... use UNION:

PLAIN TEXT
SQL:
  1. mysql> SELECT  name FROM people WHERE age=18 AND zip IN (12345,12346, 12347)
  2.     -> UNION ALL
  3.     -> SELECT  name FROM people WHERE age=19 AND zip IN (12345,12346, 12347)
  4.     -> UNION ALL
  5.     -> SELECT  name FROM people WHERE age=20 AND zip IN (12345,12346, 12347)
  6.     -> UNION ALL
  7.     -> SELECT  name FROM people WHERE age=21 AND zip IN (12345,12346, 12347)
  8.     -> UNION ALL
  9.     -> SELECT  name FROM people WHERE age=22 AND zip IN (12345,12346, 12347);
  10. +----------------------------------+
  11. | name                             |
  12. +----------------------------------+
  13. | ed4481336eb9adca222fd404fa15658e |
  14. | 888ba838661aff00bbbce114a2a22423 |
  15. +----------------------------------+
  16. 2 rows IN SET (0.09 sec)

Ethen though this query looks much more complicated MySQL is able to execute it much faster, delivering us expected performance.

You can also use this approach when first key column is not in where clause at all if it has just few values. For example if we would have gender instead of age with just two possible values it would be faster to run such query with union. I bet it would even be so with age even if it would take some 100 queries in the union to do so.

This strategy is best applied if no others work well. Ie if there are range on both keyparts and none of them is selective enough by itself. For example if we would like to only lookup people within single zip I would advice to use index in (zip,age) instead of using this workaround.

And... yes this example is a bit artificial. You would probably use date (or at least year) or birth instead of age, and put zip as first column in the index as it is more selective but it is good enough for illustrative purposes :)

Posted by peter @ 7:27 am :: optimizer, tips  
Print This Post Print This Post book mark Using UNION to implement loose index scan in MySQL in del.icio.usdel.icio.us :: submit Using UNION to implement loose index scan in MySQL to digg.comdigg  
Comment RSS :: Trackback URI  
Related posts: :MySQL: Followup on UNION for query optimization, Query profiling::UNION vs UNION ALL Performance::Descending indexing and loose index scan:
 

11 Comments »

  1. 1. Michael Otto

    How does SELECT name FROM people WHERE age in (18,19,20,21,22) AND zip IN (12345,12346, 12347); perform here?

    Comment :: August 11, 2006 @ 12:58 pm

  2. 2. Dmitry

    Talking about MySQL 5 - what if you had two indices on `age` and `zip` separately, how would it look like in explain?

    Comment :: August 11, 2006 @ 1:01 pm

  3. 3. peter

    Michael,

    You’re right. This problem seems to be partially fixed and IN works for this case as well as union

    mysql> explain SELECT name FROM people WHERE age in (18,19,20,21,22) AND zip IN (12345,12346, 12347);
    +—-+————-+——–+——-+—————+——+———+——+——+————-+
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
    +—-+————-+——–+——-+—————+——+———+——+——+————-+
    | 1 | SIMPLE | people | range | age | age | 4 | NULL | 16 | Using where |
    +—-+————-+——–+——-+—————+——+———+——+——+————-+
    1 row in set (0.16 sec)

    mysql> SELECT name FROM people WHERE age in (18,19,20,21,22) AND zip IN (12345,12346, 12347);
    +———————————-+
    | name |
    +———————————-+
    | ed4481336eb9adca222fd404fa15658e |
    | 888ba838661aff00bbbce114a2a22423 |
    +———————————-+
    2 rows in set (0.05 sec)

    I actually ment a bit different case but I thought I should simplify it which turned to be not the best way around.
    I’ll post one more post in couple of days to show where union will be the only this which can help you :)

    Comment :: August 11, 2006 @ 2:05 pm

  4. 4. peter

    Dmitry,

    This is not the case where index merge can apply:

    mysql> explain SELECT SQL_NO_CACHE name FROM people WHERE age BETWEEN 18 AND 22 AND zip IN (12345,12346, 12347);
    +—-+————-+——–+——-+—————+——+———+——+——+————-+
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
    +—-+————-+——–+——-+—————+——+———+——+——+————-+
    | 1 | SIMPLE | people | range | age,zip | zip | 3 | NULL | 19 | Using where |
    +—-+————-+——–+——-+—————+——+———+——+——+————-+
    1 row in set (0.00 sec)

    As you see it can use only one of the indexes it selects to use zip as it is more selective;
    As corelation between indexes is not known it is hard to tell what will be faster to use one of indexes only or
    to intersect row pointers from both indexes.

    If you would need OR in this case Index merge would apply.

    mysql> explain SELECT SQL_NO_CACHE name FROM people WHERE age BETWEEN 18 AND 22 OR zip IN (12345,12346, 12347);
    +—-+————-+——–+————-+—————+———+———+——+——-+—————————————-+
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
    +—-+————-+——–+————-+—————+———+———+——+——-+—————————————-+
    | 1 | SIMPLE | people | index_merge | age,zip | age,zip | 1,3 | NULL | 38821 | Using sort_union(age,zip); Using where |
    +—-+————-+——–+————-+—————+———+———+——+——-+—————————————-+
    1 row in set (0.00 sec)

    Comment :: August 11, 2006 @ 2:15 pm

  5. 5. Yuan WANG

    Hi peter:

    Sorry to disturb you but I don’t quite understand the big performance difference between the “age=19″ query and the “age BETWEEN 18 AND 22 AND” query. According to the output of the EXPLAINs, I think the process of executing the “age=19″ query is:
    1. Perform an index scan of KEY(age, zip), with scankey “age=19″. For key_len is 4, the condition on zip is useless in this step;
    2. For each rows returned by the index scan above, retreive that row from the table and test where it’s zip is in (12345, 12346, 12347)
    And I think the process of executing the “age BETWEEN 18 AND 22 AND” query is:
    1. Perform an index range scan of KEY(age, zip), start with “age=18″ and end with “age=22″. For key_len is 4, the condition on zip is useless in this step;
    2. For each rows returned by the index scan above, retreive that row from the table and test where it’s zip is in (12345, 12346, 12347)
    So the main difference should be the first step. If the data has a uniform distribution, number of rows checked and returned by the first step of the “age=19″ query should be about 1/5 of the “age BETWEEN 18 AND 22 AND” qeury, so would be the total cost.

    However, the difference of the real cost is much more tremendous. So chould you be so kind to give some more words about the reason of the performance difference?

    Comment :: August 12, 2006 @ 5:28 am

  6. 6. peter

    Yuan WANG,

    If query with where clause “age=19 and zip in (…)” is executed what really is performed is sequence of lookups
    age=19 and zip=const. Key length=4 is missleading in this case. It seems to be EXPLAIN bug in this case.

    For query with “age between 19 and 22 and zip in (…)” what you have described is happening - index range lookup is performend on age condition and zip condition only checked after row is read.

    You can use FLUSH STATUS; SHOW STATUS; and check Handler_XXX stats to see how query execution was performed.

    Comment :: August 13, 2006 @ 8:52 am

  7. 7. Apachez

    Is this a MySQL Optimizer bug (which we could expect to be fixed in near future) or is this “by design” for the next couple of years ?

    I mean the UNION is a nice workaround but needs more code and logic where just writing a “WHERE col BETWEEN 19 AND 22″ is so much easier :-)

    Comment :: August 14, 2006 @ 11:32 am

  8. 8. MySQL Performance Blog » MySQL: Followup on UNION for query optimization, Query profiling

    [...] Few days ago I wrote an article about using UNION to implement loose index scan. [...]

    Pingback :: August 14, 2006 @ 1:46 pm

  9. 9. James Day

    Apachez, one of many areas where it’s known that the optimizer can be improved. They are gradually being done, no particular schedule for when each one is done. Other than more slowly than we’d all like. :)

    James Day
    Support Engineer, MySQL AB

    Comment :: August 16, 2006 @ 11:30 am

  10. 10. How adding another table to JOIN can improve performance ? | MySQL Performance Blog

    [...] have described couple of solutions to this problem - using IN list instead of range or UNION which however require [...]

    Pingback :: August 1, 2008 @ 10:10 pm

  11. 11. How to select the first/least/max row per group in SQL at Xaprb

    [...] Peter Zaitsev has written in detail about this technique, so I won’t go into it too much more here. If it suits your purposes, it can be a very good solution. [...]

    Pingback :: August 8, 2008 @ 8:39 am

 

Subscribe without commenting


This page was found by: union all & index ra... mysql select type in...