Bug #68656 ORDER BY ignored in some situations for UPDATE query

Description:
I've created a reduction of an issue in which an UPDATE query with ORDER BY and LIMIT clauses will predictably update the wrong row.

In my reproduction below, the row with id=1 is updated but the row with id=2 has the earlier timestamp. I would expect the second row to be updated, per the ORDER BY clause.

I've included my simplest reduction, which is two rows. But the query appears to behave differently depending on table contents.

* If I add a third row with bar=1 (same as the first two), then the query resumes expected ordering.
* If I add a third row with bar=2 (different from the first two), the problem persists.
* If I add a third and fourth row with bar=2, and a fifth row with bar=1, the problem also persists.

Note: I had a co-worker sanity check my repro on his machine. He has 5.5.25-log, and experiences the same issue.

How to repeat:
DROP TABLE IF EXISTS `foo`;

CREATE TABLE `foo` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `bar` int(11) DEFAULT NULL,
  `baz` datetime DEFAULT NULL,
  `qux` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `index_foo_on_bar_and_qux` (`bar`,`qux`),
  KEY `index_foo_on_baz` (`baz`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO `foo` (bar, baz)
VALUES
  (1, '2013-01-01 00:00:01'),
  (1, '2013-01-01 00:00:00');

UPDATE foo
SET qux = 1
WHERE bar = 1
  AND qux IS NULL
ORDER BY baz ASC
LIMIT 1;

SELECT * FROM foo;
+----+------+---------------------+------+
| id | bar  | baz                 | qux  |
+----+------+---------------------+------+
|  1 |    1 | 2013-01-01 00:00:01 |    1 |
|  2 |    1 | 2013-01-01 00:00:00 | NULL |
+----+------+---------------------+------+

Suggested fix:
Apply the ORDER BY clause so that the expected row is updated and so that the statement replicates correctly.

We found a way to force the UPDATE to respect the ORDER BY, by forcing a different index.

Namely:

UPDATE foo
FORCE INDEX (index_foo_on_baz)
SET qux = 1
WHERE bar = 1
  AND qux IS NULL
ORDER BY baz ASC
LIMIT 1;

I tested all versions.  This is a changed introduced in 5.5.6.
Probably related: http://bugs.mysql.com/bug.php?id=53742

MySQL [test]> SELECT * FROM foo;
+----+------+---------------------+------+
| id | bar  | baz                 | qux  |
+----+------+---------------------+------+
|  1 |    1 | 2013-01-01 00:00:01 |    1 |
|  2 |    1 | 2013-01-01 00:00:00 | NULL |
+----+------+---------------------+------+
2 rows in set (0.00 sec)

MySQL [test]> select version();
+-----------+
| version() |
+-----------+
| 5.5.6-rc  |
+-----------+
1 row in set (0.00 sec)

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

MySQL [test]> SELECT * FROM foo;
+----+------+---------------------+------+
| id | bar  | baz                 | qux  |
+----+------+---------------------+------+
|  1 |    1 | 2013-01-01 00:00:01 | NULL |
|  2 |    1 | 2013-01-01 00:00:00 |    1 |
+----+------+---------------------+------+
2 rows in set (0.00 sec)

MySQL [test]> select version();
+-----------+
| version() |
+-----------+
| 5.5.5-m3  |
+-----------+
1 row in set (0.00 sec)

5.5, 5.6, 5.7 affected.

Noted in 5.5.35, 5.6.15, 5.7.3 changelogs.

For queries of the form UPDATE ... WHERE unique_key ORDER BY ...
LIMIT ..., incorrect rows could be updated. Unique keys permit
multiple NULL values, but the optimizer did not always consider all
of them.

5.5$ bzr log -r 4477
------------------------------------------------------------
revno: 4477
committer: Tor Didriksen <tor.didriksen@oracle.com>
branch nick: 5.5-bug16482467updatelimit
timestamp: Tue 2013-09-10 11:20:29 +0200
message:
  Bug#16482467 ORDER BY IGNORED IN SOME SITUATIONS FOR UPDATE QUERY
  
  For queries like
  update t1 set ... where <unique key> order by ... limit ...
  we need to handle the fact that unique keys allow NULL
  values, and hence can return more than one row.

looks like this fix caused a regression
https://bugs.mysql.com/bug.php?id=72040