title: Trouble optimizing MySQL query containing range expression, order by, and limit
body: <p>I'm having trouble optimizing what I think is a reasonable / straightforward query in MySQL. After spending a few late nights on this, I thought I'd post my question here as I'm sure the solution will be obvious to somebody.</p>
  
  <p>Here are the columns in a simplified version of my table T:</p>
  
  <ul>
  <li><strong>id:</strong> varchar(32) not null (primary key)</li>
  <li><strong>timestamp:</strong> bigint(20) unsigned not null</li>
  <li><strong>family:</strong> char(32) not null</li>
  <li><strong>size:</strong> bigint(20) unsigned not null</li>
  </ul>
  
  <p>And here's the query that I need to optimize:</p>
  
  <pre><code>select
    id
  from
    T
  where
    family = 'some constant'
  and
    timestamp between T1 and T2
  order by
    size desc
  limit
    5
  </code></pre>
  
  <p>My table is fairly large (~630M rows) so I'm hoping that an index can do most of the work for me... but I'm having trouble picking the right columns for my index.</p>
  
  <p>It seems that in order for MySQL to use an index to answer a range query (like what I'm doing w/ the timestamp), that column must be the last column in the index. But then there's the "order by", which is on a different column. I'm not sure which one of these columns should be last in my index, so I've tried creating the following indices:</p>
  
  <ul>
  <li><strong>i1</strong>, on (family, timestamp, size)</li>
  <li><strong>i2</strong>, on (family, size, timestamp)</li>
  </ul>
  
  <p>... but neither of these seems to help.</p>
  
  <p>Any idea what I'm doing wrong?</p>
  
  <p>(BTW I'm running MySQL 8 in Amazon RDS, in case that makes a difference.)</p>
  
  <p>Thanks in advance for any helpful suggestions you may have!</p>
  
  <p>EDIT #1 ---------------------------------------</p>
  
  <p>I just created this simplified table that I described above, and copied 10M rows worth of data from the original table to the simplified table, just to keep things clean. Then I ran the following query:</p>
  
  <pre><code>mysql&gt; select
      -&gt;   id, size
      -&gt; from
      -&gt;   T
      -&gt; where
      -&gt;   family = 'be0bf4a203797729f38c6355b6d80903'
      -&gt; and
      -&gt;   timestamp between 1578460425887 and 1584710866343
      -&gt; order by
      -&gt;   size desc;
  </code></pre>
  
  <p>... and took 1.27 seconds. I really need this to be faster, otherwise this sort of query (which I need to run many times per second) will take much too long on the real dataset.</p>
  
  <p>Here are the results of an <code>EXPLAIN</code> on the query above:</p>
  
  <pre><code>+----+-------------+-------+------------+-------+---------------------------+---------------------------+---------+------+--------+----------+------------------------------------------+
  | id | select_type | table | partitions | type  | possible_keys             | key                       | key_len | ref  | rows   | filtered | Extra                                    |
  +----+-------------+-------+------------+-------+---------------------------+---------------------------+---------+------+--------+----------+------------------------------------------+
  |  1 | SIMPLE      | T     | NULL       | range | idx_family_timestamp_size | idx_family_timestamp_size | 136     | NULL | 178324 |   100.00 | Using where; Using index; Using filesort |
  +----+-------------+-------+------------+-------+---------------------------+---------------------------+---------+------+--------+----------+------------------------------------------+
  </code></pre>
  
  <p>I bet it's the filesort that's killing performance. Any ideas?</p>
  
  <p>EDIT #2 ---------------------------------------</p>
  
  <p>Oops, I just realized that I forgot the <code>LIMIT</code> in EDIT #1's query. I've fixed that here, and also grew T to 100M rows -- so now it's 10x the size that it was in my previous edit.</p>
  
  <p>Now my query takes almost 10 sec. to run, and the results of the <code>EXPLAIN</code> are as follows:</p>
  
  <pre><code>mysql&gt; explain
      -&gt; select
      -&gt;   id, size
      -&gt; from
      -&gt;   T
      -&gt; where
      -&gt;   family = 'be0bf4a203797729f38c6355b6d80903'
      -&gt; and
      -&gt;   timestamp between 1578460425887 and 1584710866343
      -&gt; order by
      -&gt;   size desc
      -&gt; limit
      -&gt;   5;
  +----+-------------+-------+------------+-------+-----------------------------------------------------+---------------------------+---------+------+--------+----------+--------------------------------------------------------+
  | id | select_type | table | partitions | type  | possible_keys                                       | key                       | key_len | ref  | rows   | filtered | Extra                                                  |
  +----+-------------+-------+------------+-------+-----------------------------------------------------+---------------------------+---------+------+--------+----------+--------------------------------------------------------+
  |  1 | SIMPLE      | T     | NULL       | range | idx_family_timestamp_size,idx_family_size_timestamp | idx_family_size_timestamp | 144     | NULL | 410744 |   100.00 | Using where; Using index for skip scan; Using filesort |
  +----+-------------+-------+------------+-------+-----------------------------------------------------+---------------------------+---------+------+--------+----------+--------------------------------------------------------+
  </code></pre>