Opening this based on SAMU-98

Please refer to that link for repro instructions.

General concept is-

SELECT id

FROM   table

WHERE  varcharcol = 'avalue'

       AND varbool = 1

       AND vargroup = 'auuid'

ORDER  BY varnumber

LIMIT  0, 20;

Where-

CREATE TABLE `table` (

  `id` char(32) NOT NULL DEFAULT '',

  `varcharcol` varchar(80) DEFAULT NULL,

  `anothervarcharcol` varchar(255) DEFAULT NULL,

  `adatetime` datetime DEFAULT NULL,

  `varbool` tinyint(1) DEFAULT NULL,

  `vargroup` varchar(32) DEFAULT NULL,

  `varnumber` varchar(130) DEFAULT NULL,  

  PRIMARY KEY (`id`),

  KEY `key1` (`vargroup`,`varbool`),

  KEY `key2` (`varcharcol`,`adatetime`),

  KEY `key3` (`varcharcol`,`varnumber`,`anothervarcharcol`),

  KEY `key4` (`varbool`,`varcharcol`,`varnumber`)  

) ENGINE=InnoDB DEFAULT CHARSET=utf8

Note that the rows present in the table matter for the repro to work. Please use the data attached to the linked issue.

WHEN optimizer_use_condition_selectivity=1 (since 10.4.2- in 10.4.1, behavior is the same when optimizer_use_condition_selectivity=4), performing the above repro results in MariaDB's optimizer picking key3. This key is rated poorly for the WHERE condition compared to key1 or key4. However, it is "usable" for the ORDER BY clause. Still, key4 would fit the WHERE and ORDER BY better, and should be chosen.

On the hardware we tested this on, when key4 or even key1 are chosen, execution occurs in less than 1 second. When key3 is chosen, execution takes multiple seconds. Most often we see a three order of magnitude gap between "good" and "bad" behavior.

There is another weirdness to this where if you add IGNORE INDEX(key2) which is not a candidate key and should not be involved, MariaDB's optimizer magically corrects its behavior and picks key4 instead of key3.

The problem seems to boil down to test_if_cheaper_ordering and this code-

      if (best_key < 0 ||

          (select_limit <= MY_MIN(quick_records,best_records) ?

           keyinfo->user_defined_key_parts < best_key_parts :

           quick_records < best_records) ||

          (!is_best_covering && is_covering))

Filing this as a regression as 10.2.27 does not have this problem and that should also be following logic like optimizer_use_condition_selectivity=1, so a regression occurred since then.