MySQL not being able to utilize a compound index?

Hi Shlomi!

I think this is because you have such a smalll dataset – just 10 wee rows.

Make it a some hundred thousends (or tens of thousends) and you should see the index being used.

It all boils to to optimizer statistics. You will get the same result if you do: select * from t where a<2; This is because your range scan reads the entire table. It is faster to read the entire table with a FTS than it is to read the full table by index. Do you get a range scan when you do this? select * from t where (a,b) < (1,2); And do you get an index scan (covering index) when you do this? select a,b from t where (a,b) < (2,2); If the answer to the last two questions… Read more »

Also, I’m a little unsure what mean with row comparators.

is
select * from t where (a,b) < (2,2) equivalent to:

select * from t where a<2 and b<2
OR
select * from t where a<=2 and b<2

in other words:

is (2,1) < (2,2) ?

I’m pretty sure that row comparison operators just can’t use indexes in MySQL.

If you check out:

http://dev.mysql.com/doc/refman/5.0/en/subquery-restrictions.html

You see this gem:

* Row constructors are not well optimized. The following two expressions are equivalent, but only the second can be optimized:

(col1, col2, …) = (val1, val2, …)
col1 = val1 AND col2 = val2 AND …

Possible work around is to make sure you have a covering index when doing ROW() comparisons. mysql> desc SELECT * FROM t WHERE (a,b) > (2,2); +—-+————-+——-+——+—————+——+———+——+——+————-+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +—-+————-+——-+——+—————+——+———+——+——+————-+ | 1 | SIMPLE | t | ALL | NULL | NULL | NULL | NULL | 37 | Using where | +—-+————-+——-+——+—————+——+———+——+——+————-+ 1 row in set (0.00 sec) mysql> alter table t add index (a,b,c); Query OK, 37 rows affected (0.08 sec) Records: 37 Duplicates: 0 Warnings: 0 mysql> desc… Read more »

I *think* we have a bug report for that already, can’t find it in the bugs database though …

Row comparators simply aren’t very well-optimized in MySQL yet. This is a documented limitation, although if memory serves it’s actually mentioned as a subquery limitation.

Some cases are handled properly (equality checks should behave in 5.1). Others you simply have to expand (ie: WHERE (a<2) OR (a=2 AND b<2)).

Hi Justin,

the syntax (a,b) < (x,y)

means:

CASE
WHEN a > x THEN FALSE
WHEN a = x THEN
CASE
WHEN b < y THEN TRUE
ELSE FALSE
END
END

darn…something is not well with literal <

me tries again….

(a,b) < (x,y) is equivalent to:

CASE
WHEN a > x THEN FALSE
WHEN a < x THEN TRUE
ELSE CASE
WHEN b < y THEN TRUE
ELSE FALSE
END
END

1) Have you tried it on 5.1 version of MySQL?
2) Do you get the same explain plan with and without “limit” ?
3) What is the actual time that it took to return the results?

The query isn’t a subquery, however for some reason that is where the docs mentions the restriction about row operators. I suspect it was because the row operators were added at the same time as subqueries.

Really, the restriction should be put somewhere else in the documentation, such as the index section or even where row operators are mentioned in the docs.

Shlomi, as others said — this is just an optimizer weakness at the moment. Peter posted on this a while ago, too: http://www.mysqlperformanceblog.com/2008/04/04/multi-column-in-clause-unexpected-mysql-issue/

[…] code.openark.org, Shlomi Noach writes It seems like MySQL is unable to utilize a compound index when evaluating a plan for a query with a range condition. I’m looking for an explanation. I’ll […]

(a, b) < (…) is notorious for being poorly optimized.

The optimal way to do the query is not

(a<2) OR (a=2 AND b<2)

which involves OR at the top level, hence probably a table scan. Instead, use this equivalent:

(a<=2) AND (a<2 OR b<2)

(Caveat: When there is a huge number of rows with a=2, it will still scan all the a=2 values.)

A further note. (HINT to developers)

It should be easy to transform the parse tree for

WHERE (a, b) <* (x, y)

into

a <= x AND (a < x OR b <* y)

Notes:

* <* represents either < or <=

* other operators should have similar transformations

* (a,b,c) < … — also possible, but much messier (exercise for the reader)
* This is useful only if you have an index starting with `a`. (Only `a` will be used, so including `b` is optional.)

* The index will be scanned _through_ a=x, regardless of b and y.

[…] There’s Bug #35819, which I originally found in this article, which was in turn mentioned in the comments on this post. […]