title: Improving MySQL SELECT performance
body: <h2>The setup</h2>
  
  <p>I have a database which will ultimately contain 13 billion rows. The rows are keyed on 4 values: <code>(asn, cty (country), src (source), time)</code>.</p>
  
  <p>There are roughly 60,000 distinct values for <code>asn</code>, roughly 200 distinct values for <code>country</code>, and roughly 55 distinct values for <code>source</code> -- although not all triplets are valid. There are roughly 500,000 valid triplets.</p>
  
  <p>For each valid triplet I record data into a database once every 5 minutes, with <code>time</code> being the time the data was recorded. After 90 days we delete data off the end. This yield <code>12 (iterations per hour) * 24 (hours) * 90 (days) = 25920 rows per (asn, country, source) tuple</code></p>
  
  <p>My metrics table currently looks like so:</p>
  
  <pre><code>create table `metrics` (
    `time` int(10) unsigned NOT NULL,
    `asn` int(10) unsigned NOT NULL,
    `cty` char(2) NOT NULL,
    `src` char(3) NOT NULL,
    `reqs` int(10) unsigned DEFAULT NULL,
    `rtt` float unsigned DEFAULT NULL,
    `rexb` float unsigned DEFAULT NULL,
    `nae` float unsigned DEFAULT NULL,
    `util` float unsigned DEFAULT NULL,
    PRIMARY KEY (`time`, `asn`, `cty`, `src`),
    KEY (`asn`, `cty`, `src`)
  ) ENGINE=InnoDB DEFAULT CHARACTER SET ascii
  partition by range(time) (
    PARTITION start        VALUES LESS THAN (0),
    PARTITION from20171224 VALUES LESS THAN (UNIX_TIMESTAMP('2017-12-31')),
    PARTITION from20171231 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-07')),
    PARTITION from20180107 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-14')),
    PARTITION from20180114 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-21')),
    PARTITION from20180121 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-28')),
    PARTITION from20180128 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-04')),
    PARTITION from20180204 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-11')),
    PARTITION from20180211 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-18')),
    PARTITION from20180218 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-25')),
    PARTITION from20180225 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-04')),
    PARTITION from20180304 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-11')),
    PARTITION from20180311 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-18')),
    PARTITION from20180318 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-25')),
    PARTITION from20180325 VALUES LESS THAN (UNIX_TIMESTAMP('2018-04-01')),
    PARTITION future       VALUES LESS THAN MAXVALUE
  );
  </code></pre>
  
  <p>I also have a "thresholds" table which records what a "good RTT" looks like and what a "bad RTT" looks like at any given time interval:</p>
  
  <pre><code>create table `thresholds` (
    `time` int(10) unsigned NOT NULL,
    `rtt_good` float NOT NULL DEFAULT 0,
    `rtt_bad` float NOT NULL DEFAULT 100,
    `rexb_good` float NOT NULL DEFAULT 0,
    `rexb_bad` float NOT NULL DEFAULT 100,
    `nae_good` float NOT NULL DEFAULT 0,
    `nae_bad` float NOT NULL DEFAULT 100,
    `util_good` float NOT NULL DEFAULT 0,
    `util_bad` float NOT NULL DEFAULT 100,
    PRIMARY KEY (`time`)
  ) ENGINE=InnoDB
  partition by range(time) (
    PARTITION start        VALUES LESS THAN (0),
    PARTITION from20171224 VALUES LESS THAN (UNIX_TIMESTAMP('2017-12-31')),
    PARTITION from20171231 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-07')),
    PARTITION from20180107 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-14')),
    PARTITION from20180114 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-21')),
    PARTITION from20180121 VALUES LESS THAN (UNIX_TIMESTAMP('2018-01-28')),
    PARTITION from20180128 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-04')),
    PARTITION from20180204 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-11')),
    PARTITION from20180211 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-18')),
    PARTITION from20180218 VALUES LESS THAN (UNIX_TIMESTAMP('2018-02-25')),
    PARTITION from20180225 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-04')),
    PARTITION from20180304 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-11')),
    PARTITION from20180311 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-18')),
    PARTITION from20180318 VALUES LESS THAN (UNIX_TIMESTAMP('2018-03-25')),
    PARTITION from20180325 VALUES LESS THAN (UNIX_TIMESTAMP('2018-04-01')),
    PARTITION future       VALUES LESS THAN MAXVALUE
  );
  </code></pre>
  
  <h2>The query</h2>
  
  <p>Now one of the most common queries that I perform on this data involves returning weighted averages <strong>for each time</strong> for a given asn, or country, or asn+country pair. It looks something like this:</p>
  
  <pre><code>SELECT
      t.time * 1000 as time,
      @rtt := coalesce(m_sum.weighted_rtt, @rtt) as rtt,
      floor(least(100, greatest(0,
          100 * (coalesce(m_sum.weighted_rtt, @rtt) - t.rtt_bad) / (t.rtt_good - t.rtt_bad)
      ))) as rtt_quality,
      @util := coalesce(m_sum.weighted_util, @util) as util,
      floor(least(100, greatest(0,
          100 * (coalesce(m_sum.weighted_util, @util) - t.util_bad) / (t.util_good - t.util_bad)
      ))) as util_quality
  FROM
      thresholds as t
  LEFT JOIN
      (
          SELECT
              m.time,
              sum(m.rtt*m.reqs)/sum(m.reqs) AS weighted_rtt,
              sum(m.util*m.reqs)/sum(m.reqs) AS weighted_util
          FROM metrics AS m
          WHERE m.asn = '7018' and m.cty = 'us'
          GROUP BY m.time
      ) AS m_sum ON t.time = m_sum.time
  ORDER BY t.time asc;
  </code></pre>
  
  <p>And it returns something like this:</p>
  
  <pre><code>+---------------+---------+-------------+----------+--------------+
  | time          | rtt     | rtt_quality | util     | util_quality |
  +---------------+---------+-------------+----------+--------------+
  | 1521234900000 | NULL    | NULL        | NULL     | NULL         |
  | 1521235200000 | 45      | 80          | 3000     | 40           |
  | 1521235500000 | 45      | 80          | 3000     | 40           |
  | 1521235800000 | 65      | 70          | 2000     | 60           |
  | 1521236100000 | 65      | 70          | 2000     | 60           |
  | 1521236400000 | 65      | 70          | 2000     | 60           |
  | 1521236700000 | 65      | 70          | 2000     | 60           |
  | 1521237000000 | 120     | 50          | 4500     | 10           |
        ...           ...         ...         ...           ...
  </code></pre>
  
  <p>Breaking this query down, we:</p>
  
  <ol>
  <li>Filter for only the rows we care about (based on <code>asn</code> and <code>cty</code> in this case)</li>
  <li>Aggregate these values for every <code>time</code> - computing weighted metrics</li>
  <li>Join these aggregated results with a table that contains "threshold" values for every given time (maybe at 5am we consider 100ms to be really poor RTT, but at 5pm when everyone is watching Netflix we consider 100ms pretty good)</li>
  <li>Sort by <code>time</code></li>
  <li>If we don't have a recorded metric for a given time (maybe we didn't deliver traffic to that <code>asn</code>+<code>cty</code> pair for that 5-minute interval) then use the previous 5-minute interval's value (using user-defined variables)</li>
  <li>Compute a "relative goodness" value (<code>*_quality</code>) for each metric</li>
  </ol>
  
  <h2>The variables</h2>
  
  <p>My goal is to get this <code>SELECT</code> query as fast as possible. I can change:</p>
  
  <ul>
  <li>My <code>SELECT</code> query</li>
  <li>The table schema</li>
  <li>The table engine (I have access to MyISAM, InnoDB, and MariaDB's Columnstore)</li>
  <li>The table index</li>
  <li>The partitions</li>
  </ul>
  
  <p>I cannot change:</p>
  
  <ul>
  <li>The database server</li>
  <li>The database configuration</li>
  </ul>
  
  <h2>Previous tests</h2>
  
  <p>I previously did some tests using only about 150 million rows (1% of the final data set - included 300 distinct <code>time</code> values as opposed to the full 25920) and it seemed like InnoDB was the fastest - outperforming Columnstore by 3-4x (InnoDB returned data in approximately 0.7 seconds, Columnstore took approximately 2.5 seconds).</p>
  
  <p>I believe this was true because the <strong>very first</strong> thing we do is filter out the majority of these 150 million rows before any aggregation or other work is done. InnoDB supports indexes which allows me to quickly find the rows I want to filter for and only work with those -- never reading the other data from disk.</p>
  
  <p>Here's the catch, though: I now have 5 billion rows (roughly 40% of the final data set) and I ran the same performance comparison. This time, Columnstore seemed 2x faster than InnoDB! (30 seconds vs 60 seconds for InnoDB)</p>
  
  <p>At least, it was faster the first time I ran a query for a particular <code>asn</code>+<code>country</code>. InnoDB seemed to have intermediate caching because I could then run additional queries with the same <code>asn</code>+<code>country</code> and they completed in under 1 second, but even running the <strong>exact same</strong> query in Columnstore took another 30 seconds</p>
  
  <h2>The question(s)</h2>
  
  <ol>
  <li>Why is Columnstore going faster than InnoDB, even though Columnstore doesn't support indexes (and therefore we have to scan the <strong>entire</strong> table)?</li>
  <li>Am I doing something wrong in either my table definition or my query that could be slowing this down? Thanks to InnoDB's indexing I should only need to read a handful of rows from disk. I don't know why it takes a full minute to do so</li>
  <li>Does anyone have additional performance tips they can provide, unrelated to the two previous questions?</li>
  </ol>
  
  <p>In an ideal world I would like this query to return in under 10 seconds with the full data set of 13 billion rows - although if that's not possible then returning in under 60 seconds is acceptable.</p>
  
  <h2>One additional note</h2>
  
  <p>I have the ability to compute pre-aggregated values and store them in separate tables. I already do this to a small extent. I have three tables: <code>metrics_by_asn</code>, <code>metrics_by_cty</code>, and <code>metrics_by_time</code>. The first two store weighted averages of metrics and are keyed only on <code>(asn, time)</code> or <code>(cty, time)</code>. This effectively reduces this query:</p>
  
  <pre><code>SELECT
      m.time,
      sum(m.rtt*m.reqs)/sum(m.reqs) AS weighted_rtt,
      sum(m.util*m.reqs)/sum(m.reqs) AS weighted_util
  FROM metrics AS m
  WHERE m.asn = '7018'
  GROUP BY m.time
  </code></pre>
  
  <p>To this one:</p>
  
  <pre><code>SELECT
      m.time,
      weighted_rtt,
      weighted_util
  FROM metrics_by_asn AS m
  WHERE m.asn = '7018'
  </code></pre>
  
  <p>The third table <code>metrics_by_time</code> returns summary statistics like the maximum RTT, average RTT, count of rows, etc.</p>
  
  <p>I did not create a <code>metrics_by_asn_and_cty</code> table for two reasons. First, I did not expect to see incredible performance gains. On average, a particular <code>asn</code>+<code>cty</code> pair is only served from 1.3 distinct sources. Therefore most of the time pre-aggregating this wouldn't reduce the number of rows we need to select. Second, we're already hitting some major disk usage limits. Looking at our metrics table alone we have 13 billion rows times roughly 35 bytes per row. That's 455 <strong>gigabytes</strong> for this database. Add in the pre-aggregated tables and additional tables where we dump the raw data used to compute these metrics, and we're sitting around 850 gigabytes on disk. I haven't been told a hard limit on how much data I'm allowed to store, but I'm trying to stay under a terabyte to be safe.</p>