Description:
The optimizer behaviour in 5.0 was changed and on some queries  5.0 performs slower than
4.0.

How to repeat:
Please see private

I have the same prob. Same version, but by 10000x times. Former 0.125 sec, now 130 sec!

The cause of the problem is this (already known to cause trouble) invalid optimizer
heurstic:
... when finding out E(#records(ref scan))  
   if (there is a range scan on the same index that uses the same # of key parts(*) ) {
       use E(#records( range scan))
   }

The check (*) is too weak here. It is possible that some table can be accessed via index
IDX with both "range" and "ref" scans but the E(#records) are dramatically different
between the two methods.

This bug is a manifestation of exactly this problem.
4.0 works faster because 4.0's  range optimizer doesn't try to produce ranges from
non-equality clauses (i.e. "t.keypart != someconst" clauses), and the abovementioned
invalid heuristic will not be applied

In 4.1 and 5.x the invalid heuristic is applied and therefore a bad plan is choosen.

I have a patch in the works that fixes the problem, slated for 5.1

The problem is the same as BUG#18940.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/5973

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/6097

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/6195

The fix has been pushed into 5.0.22 tree.

Notes for the changelog:
The bug was caused by the following sequence of actions in the optimizer:

1. Evaluate a possibility of accessing table T using "range" access method on index IDX,
get Estimate(#records)
2. Find out (a rather precise) estimate of number of records E(range(T.IDX)).
...
3. Start to evaluate a possibility of accessing table T using "ref" access method on the
same index index IDX.

4. From the fact that "#max keyparts used in range(T.IDX) == #keyparts used for
ref(T.IDX)" make an [in some cases] wrong conclusion that 
   E(#records(range(T.IDX))) == E(#records(ref(T.IDX))) (*)

The fix is that relevant optimizer code has been re-worked so that conclusion (*) is made
only when it is really appropriate.

Noted in 5.0.22 changelog.

I'm facing a similar issue with 5.0.27. Has this bug been rectified in the releases beyond
5.0.22 or is it going to happen from 5.1 onwards?

Pushed into 5.1.18-beta

Pushed into 5.0.40

triage: Corrected tag from SR51MRU to CHECHED