[Maria-developers] order by x limit y optimization

26 Apr 2009

      Hi!

Just was looking at processlist and thinking "why he cannot optimize
such a easy case". I think there is a possible BOOST place (this is
common query in many apps):

mysql> select count(*) from url;
+----------+
| count(*) |
+----------+
| 17945916 | 
+----------+
1 row in set (0.00 sec)

mysql> 
mysql> show full processlist;
+------+------+-----------+-----------+---------+------+----------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Id   | User | Host      | db        | Command | Time | State
| Info
|
+------+------+-----------+-----------+---------+------+----------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|   78 | root | localhost | eeindexer | Query   |  141 | Sorting result
| INSERT INTO udm_url_tmp SELECT url.rec_id FROM url WHERE
next_index_time<=1240742878  ORDER BY hops LIMIT
256                                                                                                                                                     
.....
So, it takes HUGE time to find out 256 rows with least hops. How I would
make it manually (MySQL engine has internally better ways to do it):

mysql> select min(hops) from url;
+-----------+
| min(hops) |
+-----------+
|         0 | 
+-----------+
1 row in set (0.12 sec)

mysql> select count(hops) from url where hops=0;
+-------------+
| count(hops) |
+-------------+
|           1 | 
+-------------+
1 row in set (0.00 sec)

mysql> select count(hops) from url where hops=1;
+-------------+
| count(hops) |
+-------------+
|          92 | 
+-------------+
1 row in set (0.00 sec)

mysql> select count(hops) from url where hops=2;
+-------------+
| count(hops) |
+-------------+
|        9790 | 
+-------------+
1 row in set (0.00 sec)

mysql> 
mysql> SELECT url.rec_id FROM url WHERE  hops in (0,1,2,3) ORDER BY hops
LIMIT 256;
+--------+
| rec_id |
+--------+
|      1 | 
|     82 | 
|    121 | 
|     55 | 
|     63 | 
|     39 | 
|     65 | 
|    100 | 
|    129 | 
|     85 | 
|     25 | 
|     11 | 
|     12 | 
|     54 | 
|      3 | 
|    101 | 
|      7 | 
|     50 | 
|     76 | 
|     77 | 
|     10 | 
|     24 | 
|     14 | 
|      2 | 
|     57 | 
|     46 | 
|     44 | 
|     17 | 
|    122 | 
|    135 | 
|      8 | 
|     51 | 
|    104 | 
|    124 | 
|     35 | 
|     56 | 
|    116 | 
|     62 | 
|     41 | 
|     78 | 
|    126 | 
|     15 | 
|     26 | 
|     40 | 
|     90 | 
|     80 | 
|     13 | 
|     36 | 
|     45 | 
|     70 | 
|     60 | 
|    117 | 
|     47 | 
|    114 | 
|    132 | 
|     19 | 
|     96 | 
|    118 | 
|     74 | 
|      9 | 
|    120 | 
|     95 | 
|     23 | 
|    136 | 
|     71 | 
|    130 | 
|     83 | 
|     33 | 
|    111 | 
|    125 | 
|     81 | 
|     43 | 
|     97 | 
|     28 | 
|     73 | 
|    109 | 
|     98 | 
|    105 | 
|    133 | 
|    128 | 
|    106 | 
|      4 | 
|    102 | 
|    127 | 
|      5 | 
|     30 | 
|    115 | 
|    123 | 
|     27 | 
|      6 | 
|    113 | 
|     93 | 
|     48 | 
|  10047 | 
|  55273 | 
|   7120 | 
|  21448 | 
|  16872 | 
|  17985 | 
|   9862 | 
|  20979 | 
|  45717 | 
|    491 | 
|  16943 | 
|  18183 | 
|   1753 | 
|  21176 | 
|  16486 | 
|   7578 | 
|   2329 | 
|   9824 | 
|   1239 | 
|    400 | 
|   6470 | 
|   8052 | 
|   2752 | 
|   1258 | 
|  16039 | 
|    593 | 
|  49887 | 
|   5884 | 
|   7119 | 
|   3011 | 
|   7819 | 
|  14710 | 
|    244 | 
|   6881 | 
|  16518 | 
|    240 | 
|  16445 | 
|  49988 | 
|  62181 | 
|  61227 | 
|  61651 | 
|  18118 | 
|   9951 | 
|  54964 | 
|  61197 | 
|  16361 | 
|  21452 | 
|  15361 | 
|   2840 | 
|  16479 | 
|  17006 | 
|   2768 | 
|   7917 | 
|  61198 | 
|  21556 | 
|   2650 | 
|   2525 | 
|  55022 | 
|  54911 | 
|  55672 | 
|  15326 | 
|  14763 | 
|  15493 | 
|  55156 | 
|  21435 | 
|  49959 | 
|  18242 | 
|   1887 | 
|   6437 | 
|  19407 | 
|   7593 | 
|   2355 | 
|  16908 | 
|  16102 | 
|   1275 | 
|  57868 | 
|  15943 | 
|   7977 | 
|  16079 | 
|  14712 | 
|  49874 | 
|  17269 | 
|  55851 | 
|  57783 | 
|   3442 | 
|  18085 | 
|  50913 | 
|   4067 | 
|  19402 | 
|   2785 | 
|   7920 | 
|  16456 | 
|  19143 | 
|  15141 | 
|  54895 | 
|   3578 | 
|   2905 | 
|  16623 | 
|  16802 | 
|   6472 | 
|   5894 | 
|   7004 | 
|  14711 | 
|   2545 | 
|  19184 | 
|   2994 | 
|   3297 | 
|   7993 | 
|  10034 | 
|  51738 | 
|  16854 | 
|   7007 | 
|   7583 | 
|  15967 | 
|   3720 | 
|  54940 | 
|  15299 | 
|   2343 | 
|   9896 | 
|   7016 | 
|  19668 | 
|  16128 | 
|  21624 | 
|   7529 | 
|   3521 | 
|  16602 | 
|  16089 | 
|  54821 | 
|  51589 | 
|  61828 | 
|  19690 | 
|   3608 | 
|  17946 | 
|  61146 | 
|   2265 | 
|   9809 | 
|   2509 | 
|  54729 | 
|   2426 | 
|  21617 | 
|   7543 | 
|   1841 | 
|   3700 | 
|  21391 | 
|  21442 | 
|  55155 | 
|   7532 | 
|   3490 | 
|   7821 | 
|   1891 | 
|   9876 | 
|   3677 | 
|  10019 | 
|   2862 | 
|  16186 | 
|  16299 | 
|  16528 | 
|  50641 | 
|   5926 | 
|  55135 | 
|  16800 | 
|  54734 | 
|  19375 | 
+--------+
256 rows in set (0.09 sec)

mysql> 

So why not to look on index cardinality, limit size (let say, less than
1% of table), min or max value of field ordered by and then exclude big
part of table to avoid unnecessary work?

   Tõnu

[Maria-developers] order by x limit y optimization

Tonu Samuel