title: Searching in a historical table for a row in a timestamp, is so slow
body: <p>I'm working with historical tables which are storing each change from "real" tables.</p>
  
  <p>At the moment of retrieving data in a list of timestamps, the performace is horrible.</p>
  
  <p>Here a simplified version of my tables.</p>
  
  <pre><code>CREATE TABLE `changes` (
    `ts` datetime DEFAULT NULL
  ) ENGINE=InnoDB;
  
  CREATE TABLE `history` (
    `h_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
    `start_ts` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
    `end_ts` timestamp NULL DEFAULT NULL,
    `pk` int(11) DEFAULT NULL,
    `note` mediumtext,
    PRIMARY KEY (`h_id`),
    KEY `history_pk_ts_tsev_IDX` (`pk`,`start_ts`,`end_ts`) USING BTREE
  ) ENGINE=InnoDB;
  </code></pre>
  
  <p>And this is the query i'm running:</p>
  
  <pre><code>SELECT * FROM `changes` AS `c`
  JOIN `history` AS `h`
  ON (`h`.`pk` = 9999
      AND `c`.`ts` &gt;= `h`.`start_ts`
      AND `c`.`ts` &lt; IFNULL(`h`.`end_ts`, `c`.`ts` + 1)
     )
  </code></pre>
  
  <p>With 2.500 row in <code>changes</code> and 55.000 rows in <code>history</code>, the query takes about 8 seconds to get the first row, and about 2 minutes to get all.</p>
  
  <p>This tables will grow very rapidly, storing soon milions of rows.</p>
  
  <p>This is the explain result:</p>
  
  <pre><code>|id |select_type |table |partitions |type |possible_keys          |key |key_len |ref |rows  |filtered|Extra                                              |
  |---|------------|------|-----------|-----|-----------------------|----|--------|----|------|--------|---------------------------------------------------|
  |1  |SIMPLE      |c     |           |ALL  |                       |    |        |    |2448  |100     |                                                   |
  |1  |SIMPLE      |h     |           |ALL  |history_pk_ts_tsev_IDX |    |        |    |54227 |16.66   |Using where; Using join buffer (Block Nested Loop) |
  </code></pre>
  
  <p>I've tried to force the index:</p>
  
  <pre><code>SELECT * FROM `changes` AS `c`
  JOIN `history` AS `h` FORCE INDEX (history_pk_ts_tsev_IDX)
  ON (`h`.`pk` = 2476
      AND `c`.`ts` &gt;= `h`.`start_ts`
      AND `c`.`ts` &lt; IFNULL(`h`.`end_ts`, `c`.`ts` + 1)
     )
  </code></pre>
  
  <p>but now this query takes about 10 seconds for the first row. Again, the explain:</p>
  
  <pre><code>|id |select_type |table |partitions |type |possible_keys          |key                    |key_len |ref   |rows  |filtered|Extra                 |
  |---|------------|------|-----------|-----|-----------------------|-----------------------|--------|------|------|--------|----------------------|
  |1  |SIMPLE      |c     |           |ALL  |                       |                       |        |      |2448  |100     |                      |
  |1  |SIMPLE      |h     |           |ref  |history_pk_ts_tsev_IDX |history_pk_ts_tsev_IDX |5       |const |27113 |33.33   |Using index condition |
  </code></pre>
  
  <p>I've tried to create indexes in any order and combinations of them with no luck:</p>
  
  <ul>
  <li>(pk, start_ts, end_ts)</li>
  <li>(start_ts, end_ts)</li>
  <li>(end_ts)</li>
  <li>(end_ts, start_ts)</li>
  <li>...</li>
  </ul>
  
  <p>I've tested in the biggest MySQL RDS available in AWS with the same results, hence is not a hardware problem.</p>
  
  <p>I'm really lost. What am I missing?</p>
  
  <p>Thanks.</p>