Possible optimization for sort_merge and UNION ORDER BY LIMIT

September 18, 2007

Author

Peter Zaitsev

Insight for Developers

Share this Post:

Every so often you need to perform sort results retrieved from MySQL when your WHERE clause goes beyound col=const values which would allow MySQL to still use second portion of the index for the order by. Ranges as well as IN lists make this optimization impossible, not even speaking about index merge optimization. Lets look at this example:

<br>CREATE TABLE `utest` (<br>  `c1` int(10) unsigned NOT NULL,<br>  `c2` int(10) unsigned NOT NULL,<br>  `ord` int(10) unsigned NOT NULL,<br>  KEY `c1` (`c1`,`ord`),<br>  KEY `c2` (`c2`,`ord`)<br>) ENGINE=MyISAM DEFAULT CHARSET=latin1<br><br>mysql> explain select * from utest where c1=5 or c2=5 order by ord desc limit 10 G<br>*************************** 1. row ***************************<br>           id: 1<br>  select_type: SIMPLE<br>        table: utest<br>         type: index_merge<br>possible_keys: c1,c2<br>          key: c1,c2<br>      key_len: 4,4<br>          ref: NULL<br>         rows: 162380<br>        Extra: Using sort_union(c1,c2); Using where; Using filesort<br>1 row in set (0.00 sec)<br>

CREATE TABLE `utest` ( `c1` int(10) unsigned NOT NULL, `c2` int(10) unsigned NOT NULL, `ord` int(10) unsigned NOT NULL, KEY `c1` (`c1`,`ord`), KEY `c2` (`c2`,`ord`) ) ENGINE=MyISAM DEFAULT CHARSET=latin1 mysql> explain select * from utest where c1=5 or c2=5 order by ord desc limit 10 G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: utest type: index_merge possible_keys: c1,c2 key: c1,c2 key_len: 4,4 ref: NULL rows: 162380 Extra: Using sort_union(c1,c2); Using where; Using filesort 1 row in set (0.00 sec)

As you can see MySQL 5.1.21 uses sort_merge to access the rows but it can’t use it together with order by efficiently.
I’d say this is limitation as for this case you well could be retrieving sorted streams by the indexes and doing merge sort to get resulted rows in sorted order. Once this is implemented similar approach could be used for optimizing ORDER BY with IN.

This original query (in memory data) takes 1sec. Let’s see how classic pre MySQL 5.0 solution – using UNION instead of single query works in this case:

<br>mysql> explain (select * from utest where c1=5) union (select * from utest where c2=5) order by ord desc limit 10 G<br>*************************** 1. row ***************************<br>           id: 1<br>  select_type: PRIMARY<br>        table: utest<br>         type: ref<br>possible_keys: c1<br>          key: c1<br>      key_len: 4<br>          ref: const<br>         rows: 108112<br>        Extra: <br>*************************** 2. row ***************************<br>           id: 2<br>  select_type: UNION<br>        table: utest<br>         type: ref<br>possible_keys: c2<br>          key: c2<br>      key_len: 4<br>          ref: const<br>         rows: 54268<br>        Extra: <br>*************************** 3. row ***************************<br>           id: NULL<br>  select_type: UNION RESULT<br>        table: <union1,2><br>         type: ALL<br>possible_keys: NULL<br>          key: NULL<br>      key_len: NULL<br>          ref: NULL<br>         rows: NULL<br>        Extra: Using filesort<br>3 rows in set (0.00 sec)<br>

mysql> explain (select * from utest where c1=5) union (select * from utest where c2=5) order by ord desc limit 10 G *************************** 1. row *************************** id: 1 select_type: PRIMARY table: utest type: ref possible_keys: c1 key: c1 key_len: 4 ref: const rows: 108112 Extra: *************************** 2. row *************************** id: 2 select_type: UNION table: utest type: ref possible_keys: c2 key: c2 key_len: 4 ref: const rows: 54268 Extra: *************************** 3. row *************************** id: NULL select_type: UNION RESULT table: <union1,2> type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: NULL Extra: Using filesort 3 rows in set (0.00 sec)

The query looks scare but in fact in completes in 1.05 sec not significantly faster than sort index merge in this case.

As the query time implies MySQL is not smart enough in this case to “dive into” the union and add ORDER BY ORD LIMIT 10 to individual queries.
What if we do int manually ?

<br>mysql> explain (select * from utest where c1=5 order by ord desc limit 10) union (select * from utest where c2=5 order by ord desc limit 10) order by ord desc limit 10 G<br>*************************** 1. row ***************************<br>           id: 1<br>  select_type: PRIMARY<br>        table: utest<br>         type: ref<br>possible_keys: c1<br>          key: c1<br>      key_len: 4<br>          ref: const<br>         rows: 108112<br>        Extra: Using where<br>*************************** 2. row ***************************<br>           id: 2<br>  select_type: UNION<br>        table: utest<br>         type: ref<br>possible_keys: c2<br>          key: c2<br>      key_len: 4<br>          ref: const<br>         rows: 54268<br>        Extra: Using where<br>*************************** 3. row ***************************<br>           id: NULL<br>  select_type: UNION RESULT<br>        table: <union1,2><br>         type: ALL<br>possible_keys: NULL<br>          key: NULL<br>      key_len: NULL<br>          ref: NULL<br>         rows: NULL<br>        Extra: Using filesort<br>3 rows in set (0.00 sec)<br>

mysql> explain (select * from utest where c1=5 order by ord desc limit 10) union (select * from utest where c2=5 order by ord desc limit 10) order by ord desc limit 10 G *************************** 1. row *************************** id: 1 select_type: PRIMARY table: utest type: ref possible_keys: c1 key: c1 key_len: 4 ref: const rows: 108112 Extra: Using where *************************** 2. row *************************** id: 2 select_type: UNION table: utest type: ref possible_keys: c2 key: c2 key_len: 4 ref: const rows: 54268 Extra: Using where *************************** 3. row *************************** id: NULL select_type: UNION RESULT table: <union1,2> type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: NULL Extra: Using filesort 3 rows in set (0.00 sec)

As you can see explain does not really change (it does not show if index is used for finding rows or sorting as well) but query speed goes to less than
0.01 sec.

So it is great optimization which you need to do manuall for the time being.

What is also interesting is the fact MySQL is unable to handle even basic UNION with limit (without order by) optimally – in creates result set for the union fully and when only takes 10 rows from it:

<br>mysql> explain (select * from utest where c1=5 ) union (select * from utest where c2=5 ) limit 10 G<br>*************************** 1. row ***************************<br>           id: 1<br>  select_type: PRIMARY<br>        table: utest<br>         type: ref<br>possible_keys: c1<br>          key: c1<br>      key_len: 4<br>          ref: const<br>         rows: 108112<br>        Extra: <br>*************************** 2. row ***************************<br>           id: 2<br>  select_type: UNION<br>        table: utest<br>         type: ref<br>possible_keys: c2<br>          key: c2<br>      key_len: 4<br>          ref: const<br>         rows: 54268<br>        Extra: <br>*************************** 3. row ***************************<br>           id: NULL<br>  select_type: UNION RESULT<br>        table: <union1,2><br>         type: ALL<br>possible_keys: NULL<br>          key: NULL<br>      key_len: NULL<br>          ref: NULL<br>         rows: NULL<br>        Extra: <br>3 rows in set (0.00 sec)<br>

mysql> explain (select * from utest where c1=5 ) union (select * from utest where c2=5 ) limit 10 G *************************** 1. row *************************** id: 1 select_type: PRIMARY table: utest type: ref possible_keys: c1 key: c1 key_len: 4 ref: const rows: 108112 Extra: *************************** 2. row *************************** id: 2 select_type: UNION table: utest type: ref possible_keys: c2 key: c2 key_len: 4 ref: const rows: 54268 Extra: *************************** 3. row *************************** id: NULL select_type: UNION RESULT table: <union1,2> type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: NULL Extra: 3 rows in set (0.00 sec)

Such query takes about 0.9 sec on the test data. Another possible optimizer improvement to do.

P.S This post is inspired by Does MySQL Optimize UNION with LIMIT clause topic on our MySQL Forums.