October 21, 2014

Joining on range? Wrong!

The problem I am going to describe is likely to be around since the very beginning of MySQL, however unless you carefully analyse and profile your queries, it might easily go unnoticed. I used it as one of the examples in our talk given at phpDay.it conference last week to demonstrate some pitfalls one may hit when designing schemas and queries, but then I thought it could be a good idea to publish this on the blog as well.

To demonstrate the issue let’s use a typical example – a sales query. Our data is a tiny store directory consisting of three very simple tables:

“Please excuse the crudity of this model, I didn’t have time to build it to scale or to paint it.” — Dr. Emmett Brown

I populated these tables with enough data to serve our purpose.

Our hypothetical sales query could be to figure out how many LCD TVs were sold yesterday.

Seems like a very successful day! :)

When we look at the data structures it looks quite good – there is index on

in

, there is index on

in

and indexes on other columns used in joins. Let’s verify how the query performed in greater detail:

Somehow this does not look as good as the sales numbers. Query matched 4103 rows, but almost 120000 were scanned. And we have proper indexes on all necessary columns! What does EXPLAIN have to say about this?

To remind – our structure design is:

In 3rd row key_len is only 4 bytes, while the full key length is 4 bytes for itm_prd_id plus 4 bytes for itm_order_timestamp, so 8 bytes in total! Also ref shows only one column being used by the last join.

How should we understand this then? Database reads all ordered items where tag is ‘lcd’, which totals to about 120000 rows as shown by the counters in SHOW STATUS output above, and then filters out those not matching the date range. A very inefficient approach! MySQL was unable to optimize those simple conditions to match both product id and date range by index and read only the relevant rows.

This affects joins only. When you use a range condition on the first (or the only) table, it works as expected:

In this case MySQL does not print ref at all, because there is no join, however you can notice key_len is 8 bytes, so the full index length. It means both index columns will be used to execute the query.

There may be many workarounds to this problem, all depends on the specific case you may need to solve. Essentially it always comes down to removing range condition from join one way or another. For our example query this could mean introducing additional DATE column and using it for filtering instead:

Now the rewritten query:

This query uses 7 bytes of

index – 4 bytes is

and 3 bytes is

(DATE type uses 3 bytes). Also ref shows two columns used in join.

Statistics also look much better.

But remember – different query will likely need a different solution.

You can find several bug reports regarding this problem (e.g. #8569, #19548). Some replies from MySQL indicate this may be eventually fixed in 6.0 or some future version. Others say “it’s a documented behaviour – deal with it”. But in the real world this is a serious bug, not a feature, and it needs fixing.

About Maciej Dobrzanski

Maciek is a former Percona employee.
An IT consultant with the primary focus on systems, databases and application stacks performance and scalability. Expert on open source technologies such as Linux, BSD, Apache, nginx, MySQL, and many more. Co-author of dba square - a blog about how to manage, scale, and optimize MySQL performance!

Comments

  1. zerkms says:

    this doesn’t rely on article (which is good), but for simplification you could remove “JOIN products p ON p.prd_id = t.tag_prd_id”. this part is odd for examined query. and i’m pretty sure that it’s more simple to keep in mind 1 join instead of 2 ;-)

  2. Laurens says:

    It should be possible to trick mysql.
    Basically you create a date table with a date_id (surrogate key) in it.
    You place that id instead of the datefield and you should be able to join properly on the date table where you can use the range function. Yes it is more work and it would be nice if it was fixed but it could be a while.

  3. peter says:

    Laurens,

    Yes. That does the trick. I actually wrote about similar issue 1.5 years ago:
    http://www.mysqlperformanceblog.com/2008/08/01/how-adding-another-table-to-join-can-improve-performance/

  4. Willam says:

    Would it also work to use a subquery?

    SELECT COUNT(1)
    FROM tags t
    JOIN ( SELECT products.prd_id FROM products
    JOIN items_ordered
    ON items_ordered.itm_prd_id = products.prd_id
    WHERE items_ordered.itm_order_timestamp>= ‘2010-05-16 00:00:00′
    AND items_ordered.itm_order_timestamp <'2010-05-17 00:00:00') p

    ON p.prd_id = t.tag_prd_id
    WHERE t.tag_name = 'lcd'

  5. Nikolay says:

    well this problem happen often, that why on big projects, you better “double” any timestamp / datetime column with additional date column.
    then if you need date without time, better use it on date column:

    create table x(
    id int,
    something chat(40),
    created datetime,
    created_date date,
    primary key(id),
    key(created),
    key(created_date)
    );

    then:

    select * from x where created_date = ‘2010-01-06′;

    and not:
    select * from x where created > ‘2010-01-06′ and created < '2010-01-07';

  6. Jeffrey Gilbert says:

    William, subqueries create temp tables which are not a route you want to go if you’re looking at performance gains. I’m curious how this example compares with BETWEEN x AND y versus the range selector used. It’s important to note that this example only works where you’re comparing a range of one item to the selection of one item. once you start getting more days in there your queries would look ridiculous.

  7. Fred says:

    I think you raised one of the most important issue of mysql: it takes ages to have fixed some “obvious” and important issues or bugs.

    also some fixes are not even seen in some populare branches. :(

    regarding this issue: the most challenging problem is to implement a faceted search. Random indexes combination and range searches.

  8. Fred says:

    It would be interesting to have an article about it. :)

Speak Your Mind

*