title: MySQL query optimiser showing random behaviour for a query on table with primary and composite indexes
body: <p>I have a MySQL table on which I am executing a query. The query is taking a long time ~15 minutes to return results in some instances but in other instances, it returns results within milliseconds.
  The two queries only differ in the value of a column in where clause.</p>
  
  <h1>Table Syntax</h1>
  
  <pre><code>CREATE TABLE `tests` (
    `id` varchar(36) NOT NULL,
    `some_other_id` varchar(36) NOT NULL,
    `col_1` varchar(64) NOT NULL,
    `col_2` varchar(128) DEFAULT NULL,
    `col_3` varchar(64) DEFAULT NULL,
    `status` varchar(32) NOT NULL,
    `created_at_epoch` bigint(20) NOT NULL,
    `updated_at_epoch` bigint(20) NOT NULL,
    `updated_by` varchar(64) NOT NULL,
    `version` int(11) NOT NULL,
    `col_4` text,
    `col_5` varchar(64) DEFAULT NULL,
    PRIMARY KEY (`id`),
    KEY `some_other_id_col_1_col_2_idx` (`some_other_id`,`col_1`,`col_2`)
  ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
  </code></pre>
  
  <p><strong><em>id</em></strong> and <strong><em>some_other_id</em></strong> are created using timestamp and random characters after that, an example of some_other_id is "15632901521370150qGUCAQpVuUWK-bJg"</p>
  
  <p>The table has ~60 million records with ~56 gigabytes of data.</p>
  
  <p><strong>Please note the value of some_other_id in following queries.</strong></p>
  
  <pre><code>select test.id, test.col_3, test.col_5, test.created_at_epoch, test.col_2, test.col_1, test.col_4, test.status, test.some_other_id, test.updated_at_epoch, test.updated_by, test.version from tests test where test.some_other_id='**VAL_1**' and (test.status in ('activated')) and test.id&gt;='' order by test.id limit 2;
  --Executes within milliseconds.
  --Explain plan gives key as "some_other_id_col_1_col_2_idx".
  
  select test.id, test.col_3, test.col_5, test.created_at_epoch, test.col_2, test.col_1, test.col_4, test.status, test.some_other_id, test.updated_at_epoch, test.updated_by, test.version from tests test where test.some_other_id='**VAL_1**' and (test.status in ('activated')) and test.id&gt;='' order by test.id limit 1;
  --Takes ~14-15 minutes.
  --Explain plan gives key as "PRIMARY".
  
  select test.id, test.col_3, test.col_5, test.created_at_epoch, test.col_2, test.col_1, test.col_4, test.status, test.some_other_id, test.updated_at_epoch, test.updated_by, test.version from tests test where test.some_other_id='**VAL_1**' and (test.status in ('activated')) and test.id&gt;='' order by test.id limit 3;
  --Executes within milliseconds.
  --Explain plan gives key as "some_other_id_col_1_col_2_idx".
  
  select test.id, test.col_3, test.col_5, test.created_at_epoch, test.col_2, test.col_1, test.col_4, test.status, test.some_other_id, test.updated_at_epoch, test.updated_by, test.version from tests test where test.some_other_id='**VAL_2**' and (test.status in ('activated')) and test.id&gt;='' order by test.id limit 2;
  --Takes ~14-15 minutes.
  --Explain plan gives key as "PRIMARY".
  
  select test.id, test.col_3, test.col_5, test.created_at_epoch, test.col_2, test.col_1, test.col_4, test.status, test.some_other_id, test.updated_at_epoch, test.updated_by, test.version from tests test where test.some_other_id='**VAL_2**' and (test.status in ('activated')) order by test.id limit 2;
  --Takes ~14-15 minutes.
  --Explain plan gives key as "PRIMARY".
  
  select test.id, test.col_3, test.col_5, test.created_at_epoch, test.col_2, test.col_1, test.col_4, test.status, test.some_other_id, test.updated_at_epoch, test.updated_by, test.version from tests test where test.some_other_id='**VAL_2**' and (test.status in ('activated')) and test.id&gt;='' limit 2;
  --Executes within milliseconds.
  --Explain plan gives key as "some_other_id_col_1_col_2_idx".
  </code></pre>
  
  <p>I am not able to understand the behaviour here and am looking for some explanation on how this could happen.
  I am using MySQL 5.6</p>