Centos 6 X64

Thanks for the report.
As a workaround, you might try to set
optimizer_switch='index_condition_pushdown=off'

The bug looks very similar to MDEV-5337, possibly they will be fixed together by the same patch, but it will need to be checked.

The EXPLAIN is the same regardless of ICP settings:

id: 1
select_type: SIMPLE
table: applications
type: range
possible_keys: PRIMARY,index_applications_on_submitted_at,applications_configuration_scope_id_fk
key: applications_configuration_scope_id_fk
key_len: 5
ref: NULL
rows: 37204
Extra: Using where
1 row in set (0.01 sec)

Indexes:
PRIMARY KEY (`id`),
KEY `applications_configuration_scope_id_fk` (`configuration_scope_id`),
KEY `index_applications_on_submitted_at` (`submitted_at`),

The query:
WHERE ...
configuration_scope_id` = 2
AND ($DATE1 <= submitted_at AND submitted_at <= $DATE2)
ORDER BY `applications`.`id`

Which means:
applications_configuration_scope_id_fk – matches the ORDER BY
index_applications_on_submitted_at – doesn't match the ORDER BY

Optimization goes as follows:

make_join_readinfo
push_index_cond
idx=10, index_applications_on_submitted_at
this index doesn't provide ordering suitable for the ORDER BY
tab->select->pre_idx_push_select_cond holds the original WHERE...

JOIN::exec
create_sort_index
test_if_skip_sort_order
test_if_cheaper_ordering
piks idx=12 .. another key.. and it is choosen as the best one..
test_quick_select()...
changed_key= true
return 1;

Just wondering about MySQL... I've checked mysql-5.6.

• The query from the testcase will use range(PRIMARY), without sorting (which
  is probably a bad query plan as it doesnt take advantage of the [selective]
  WHERE?)
• Adding IGNORE INDEX(PRIMARY) causes push_index_cond() to be called with
  keyno=12. That is, it picks the index that matches the ORDER BY, from the
  start.

Debugging the second point further:

• get_quick_record_count() returns quick select with quick->index=10 in both
  5.5 and mysql-5.6.
  = 5.5 calls range optimizer again in make_join_select() but its result
  is still the same

• in mysql-5.6, make_join_select() has "recheck_reason", added by

jorgen.loland@oracle.com-20121207082040-scw8kl51svt5geoc
Bug#15829358: SERIOUS PERFORMANCE DEGRADATION FOR THE QUERY
WITH ORDER BY ... LIMIT N

which causes the optimizer to pick index=12 before ICP is applied.

I am not sure if it is possible to get 5.6 to pick a plan with range+ICP but
then change to a different plan with range but w/o ICP...

Another fix in 5.6 which might be related:
jorgen.loland@oracle.com-20121130124315-4vzmb6vtil0a6bkc
Bug#15848665: QUERY WITH LOOSE INDEX SCAN AND DESC ORDER
RETURNS INCORRECT RESULT

Getting back to debug MariaDB 5.5...

.. test_if_skip_sort_order() has this code at the end:

skipped_filesort:
...
if (!no_changes && changed_key && table->file->pushed_idx_cond)
table->file->cancel_pushed_idx_cond();

it is run ... The problem is that tab->cond is not set to
pre_idx_push_select_cond.

pre_idx_push_select_cond is set by this piece of code above (still in
test_if_skip_sort_order()):

else if (tab->type != JT_ALL)
{
/*
We're about to use a quick access to the table.
We need to change the access method so as the quick access
method is actually used.
*/
...

execution doesn't enter this branch because tab->type == JT_ALL (we've had a
range access before entering create_sort_index). If I manually force the
execution into the if branch, the query seems to work...

It looks like "tab->type != JT_ALL" is incorrect, and it should be changed to
some other condition that will mean "test_if_skip_sort_order() has picked a
different way to read the table".

Looked through bzr history.. the "tab->type != JT_ALL" was there at least since
mysql-5.1 and 2011.

ScottWylie, thanks for reporting this bug, and for the testcase.
The fix is pushed into 5.3, 5.5 and will be included in the next 5.3/5.5 release.

The commit comment refers to MDEV-5337 (for those who need to search for it later)