The only difference between the two test cases below is the presence of a PK. The test case with the PK produces wrong result, the other one works correctly:

– Wrong result
CREATE TABLE t1 (id int NOT NULL AUTO_INCREMENT, a char(3) NOT NULL, b char(3) NOT NULL,
PRIMARY KEY (id),
KEY ba (b, a)
) ENGINE=InnoDB;
INSERT INTO t1 (a, b) VALUES('777','101'),('777','102');

EXPLAIN EXTENDED
SELECT COUNT(DISTINCT b) FROM t1 WHERE a = '777';
-------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------

SELECT COUNT(DISTINCT b) FROM t1 WHERE a = '777';
-------------------

-------------------

-------------------

– Correct result
CREATE TABLE t2 (a char(3) NOT NULL, b char(3) NOT NULL,
KEY ba (b, a)) ENGINE=InnoDB;
INSERT INTO t2 (a, b) VALUES('777','101'),('777','102');

EXPLAIN EXTENDED
SELECT COUNT(DISTINCT b) FROM t2 WHERE a = '777';
-------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------

SELECT COUNT(DISTINCT b) FROM t2 WHERE a = '777';
-------------------

-------------------

-------------------

Notes during analysis (the actual problem is not understood yet).

The query engine requests the next record by calling QUICK_GROUP_MIN_MAX_SELECT::get_next.
The first thing this method does it to call next_prefix(). In both examples above, the result of this call and
all its side-effects seem to be the same. This first call to get_next() produces key '101777'.

The second call to get_next, calls next_prefix again, which calls index_next_different. Since this a
COUNT(DISTINCT) query, the access method uses index_scan instead of index dives. Thus
index_next_different() calls file->ha_index_next(record) during the second call to next_prefix().

For whatever reason, this call produces HA_ERR_END_OF_FILE instead of the next key.
Comparative debugging shows that when InnoDB attempts to fetch the next key, the previous
key is already positioned at the end of the index.

So the main questions are:

• is there any reason why in this case (with an extended InnoDB key) the index scan method is not applicable?
• if index scan is applicable, why it jumps one key further on each access?

Adding more records to table t1 shows that the current position in the index seems to "jump" over the next key to the following key.
Thus:

• 3 and 4 distinct records result in count = 2,
• 5 and 6 distinct records result in count = 3,
  etc.

Specifically re the state of InnoDB, during the second call to next_prefix, InnoDB executes
row_search_for_mysql. If we stop here:

/-------------------------------------------------------------/
/* PHASE 4: Look for matching records in a loop */

rec = btr_pcur_get_rec(pcur);

'pcur->old_rec' = "102777"

This is already the last key, consequently, InnoDB returns EOF.

Specifically re the state of InnoDB, during the second call to next_prefix, InnoDB executes
row_search_for_mysql. If we stop here:

/-------------------------------------------------------------/
/* PHASE 4: Look for matching records in a loop */

rec = btr_pcur_get_rec(pcur);

'pcur->old_rec' = "102777"

This is already the last key, consequently, InnoDB returns EOF.

Explanation by Serg that the reason for the wrong result is because the call pattern to the handler interface is not supported by InnoDB.

<serg> I'm not sure about the contract. if you do a search with HA_READ_KEY_EXACT and then you do index_next, index_next, etc. Whether the engine can only return exact matches or it should go till the end of the index
<serg> normally HA_READ_KEY_EXACT is used for WHERE key=val, so index_next only needs to see exact matches
<timour> serg, the problem is only related to extended keys, right?
<serg> no
<serg> it doesn't have anything to do with extended keys
<serg> it's simply undefined behavior in innodb, so it does different things with and without extended keys
<serg> probably because they didn't consider this use case at all
<serg> with or without extended keys you still do HA_READ_KEY_EXACT and then index_next

Indeed, if one disables EXTENDED keys by commenting out in ha_innodb.cc this line:
innobase_hton->flags=HTON_EXTENDED_KEYS;
loose scan still produces wrong result.

Discussion of a possible solution with Serg:

<timour> serg, I used HA_READ_KEY_EXACT in order to jump to the first sub-group within a group.
<timour> serg, is HA_READ_KEY_OR_NEXT going to do the same?
<serg> HA_READ_KEY_OR_NEXT will do the same if the matching key exists
<serg> say, with the index (1,3,5,7)
<serg> HA_READ_KEY_EXACT for 3 will find 3, HA_READ_KEY_EXACT for 4 will return NOT FOUND
<serg> HA_READ_KEY_OR_NEXT for 3 will find 3, HA_READ_KEY_OR_NEXT for 4 will find 5
<timour> serg, so HA_READ_KEY_OR_NEXT will fail only when it gets to the end of the index, right?
<serg> yes
<timour> serg, then this is not a solution
<timour> The way this is used is as follows:
<serg> why?
<timour> suppose we have a 2-part index:
<timour> (1,10)
<timour> (1, 11)
<timour> (2, 10)
<timour> (2, 11)
<timour> (a, b)
<timour> select (count distinct a) from t1 where b = 11;
<timour> We first jump to the start of each group, where the group in this case is column 'a'.
<timour> So we fetch "1", this is the "group prefix".
<timour> Then we copy the infix "11" that comes from the equality, and we form a new key.
<timour> Now we have to "jump" to the sub-group "1, 11".
<timour> HA_READ_KEY_OR_NEXT will be fine when the sub-group is there.
<timour> Now suppose the third group is:
<timour> (3, 10)
<timour> (3, 13)
<serg> sure, with HA_READ_KEY_OR_NEXT you need to re-check the returned row
<serg> to know whether it satisfies the key
<timour> yes
<serg> and sometimes you need to skip index_next
<timour> ?
<serg> if the third group is (3,10) and the fourth is (4,11)
<serg> then after looking for the third, you'll be already on the fourth
<serg> so, it does require some changes in the logic, but it can work
<timour> serg, The changed logic of course is needed only when we want to employ "ha_index_next" instead of "ha_index_read_map"?
<serg> yes

Glad to see the progress!

Suggestion - add a storage engine property that tells the server if the engine supports this handler call sequence.

any progress?

It was fixed in mysql 5.5.35 and the fix was merged. No test in mysql though.

Thanks! I've added the test case, and will now close this bug report.