September 2, 2014

Using index for ORDER BY vs restricting number of rows.

One interesting problem with MySQL Optimizer I frequently run into is making poor decision when it comes to choosing between using index for ORDER BY or using index for restriction.

Consider we’re running web site which sell goods, goods may be from different categories, different sellers different locations which can be filtered on, and there are also bunch of fields which sorting can be performed on such as seller, price, date added etc.

Such configuration often causes serious challenge choosing proper index configuration as it is hard to add all combinations of restrictions and order by to be fully indexed.

An extra problem comes from the fact MySQL prefers when it is possible to use index for further restriction and than using file sort, rather than using index for sorting and doing non-index based filtering for further restrictions. Here is example:

As you can see if given no hint MySQL will prefer to use index on (cat_id,seller_id) and sort all result set by price. This will be good choice if seller_id is selective, if it is not as in this case MySQL needs to sort a lot of rows to display only few.

If we force index as in second query explain will look scary with estimated million of rows to analyze but we got rid of filesort so MySQL can stop as soon as 10 rows are sent. In this case with seller_id being not really selective it is likely it will need to scan less than 100 rows to generate result.

The speed difference between these two example queries is about 100 times so it may be quite serious.

To fix this issue MySQL would need to better take into account column selectivity together with LIMIT range. If there are only few values for given seller_id (as it well can be skewed) using filesort is better as otherwise very large portion of index may need to be scanned to find 10 matching rows, if there are a lot of values of given seller_id, so it is badly selective using index scan is much better idea.

Until MySQL is able to handle this you will have to use force index hint.

The other problem you may have however is calculating count of matching rows which may be even trickier to slow for complex searches which generate a lot of rows.

Another interesting technique is to use sphinx search to accelerate sorting and retrieval which I should explain in details some time in the future.

About Peter Zaitsev

Peter managed the High Performance Group within MySQL until 2006, when he founded Percona. Peter has a Master's Degree in Computer Science and is an expert in database kernels, computer hardware, and application scaling.

Comments

  1. Sheeri says:

    You have to make sure, when you’re doing something like forcing an index due to the character of your data, that you check and make sure the character of the data does not change.

  2. peter says:

    Sheeri,

    Yes that is the bummer with force index hint. It is helpful it you know it is best plan to run the query for all constants, if it is not you’re in trouble.

  3. Dmitri Mikhailov says:

    Runtime optimization in OLTP systems has always been expensive; I always try to turn CBO off by all means available. There is nothing wrong about it if: a) the data distribution is well known and b) is not going to be changed and (c) the database design is solid.

  4. Alexey says:

    Why not change cat_id index to include price also? like (cat_id,seller_id, price)?

    Also, I’ve always wondered why don’t DB developers implement something like “partial sort” algorithm, which doesn’t sort the whole set, but instead picks top N values. I think such algorithm is O(N) and also it doesn’t any tempfiles, one simple scan.

  5. peter says:

    Alexey,

    This is just example I used. Imagine real case with for example 10 different filters and 5 fields you may sort on… you simply can’t build indexes to cover all combinations and as soon as you skip something you start to get the problem.

    It may be with sorting by the date for example etc.

    You’re right about sorting – priority queue (for example) based sort would be possible to use without changing semantics for many LIMIT queries. It was even discussed for years by Optimizer team but was not done.

    This would not exactly help in this case though as even with partial sort you will need to scan full result set while with scan in index order you can stop as soon as needed number of rows was delivered.

  6. Rob says:

    That you’re aware of, are other RDMBS’s better at selecting indexes when using ORDER BY queries or is this a universal limitation? How do the big players (Oracle, MSSQL) and competing open source products (Postgres) compare?

  7. Vlad Fratila says:

    Hi!
    I’m also very interested in Rob’s question about other RDBMSes.
    Also, have the latest versions of MySQL improved on this issue at all?

  8. heasily says:

    it’s fuuny…..but i got a trouble。。。。

    the table:
    ID my_id follow
    1 1 16
    2 1 15
    3 1 14
    4 1 14

    I just want to find out The highest number of follow and order by follow。

    I wrote:
    SELECT follow,count(*) AS NUM FROM wp_fans GROUP BY follow order by NUM desc limit 5

    Follow was index。

    the explain: type:index,Extra:Using index; Using temporary; Using filesort

    i am chinese, so my english is bad…..sorry…..

    THANKS.

Speak Your Mind

*