How can I improve the speed of a query on a 20 million+ row table?

Question

I have a query that is used for getting internet traffic statistics of certain IP addresses.

There are separate IP address fields for hosts and blocks of IPs called assignments. The data is stored in 5 minute intervals.

The query results are grouped on the time column, and the total SUMs in and out of these 5 minute intervals are used to plot a graph.

The table is called traffic and contains (at the end of the month) around 21 million records.

SHOW CREATE table traffic:
CREATE TABLE `traffic` (
  `type` enum('v4_assignment','v4_host','v6_subnet','v6_assignment','v6_host') NOT NULL,
  `type_id` int(11) unsigned NOT NULL,
  `time` int(32) unsigned NOT NULL,
  `bytesin` bigint(20) unsigned NOT NULL default '0',
  `bytesout` bigint(20) unsigned NOT NULL default '0',
  KEY `basic_select` (`type_id`,`time`,`type`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1

SELECT traffic.time, SUM(traffic.bytesin), SUM(traffic.bytesout) FROM traffic 
WHERE (
    ( traffic.type = 'v4_assignment' AND type_id IN (231, between 20 to 100 ids,265)) OR 
    ( traffic.type = 'v4_host' AND type_id IN (131, ... a lot of ids... ,1506))) 
    AND traffic.time >= 1343772000 AND traffic.time < 1346450399 
GROUP BY traffic.time
ORDER BY traffic.time;

The following is explain output for the query above:

+----+-------------+---------+-------+---------------+--------------+---------+------+--------+----------------------------------------------+
| id | select_type | table   | type  | possible_keys | key          | key_len | ref  | rows   | Extra                                        |
+----+-------------+---------+-------+---------------+--------------+---------+------+--------+----------------------------------------------+
|  1 | SIMPLE      | traffic | range | basic_select  | basic_select | 8       | NULL | 891319 | Using where; Using temporary; Using filesort |
+----+-------------+---------+-------+---------------+--------------+---------+------+--------+----------------------------------------------+

show indexes from traffic;
+---------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table   | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| traffic |          1 | basic_select |            1 | type_id     | A         |       13835 |     NULL | NULL   |      | BTREE      |         |
| traffic |          1 | basic_select |            2 | time        | A         |    18470357 |     NULL | NULL   |      | BTREE      |         |
| traffic |          1 | basic_select |            3 | type        | A         |    18470357 |     NULL | NULL   |      | BTREE      |         |
+---------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+

This query takes from 30 seconds to 30 minutes to complete. I hope I can improve things using better indexes, or maybe using a different query, but I'm unable to figure it out.

UPDATE:

Following the advise of the helpful commentors, I've created a primary key and added the index traffic_pk (time, type, type_id, id). Unfortunately, it turns out the cardinality of this new index is equal/lower than my original index (basic_select) and MySQL still uses my original key.

UPDATE 2: I dropped my original index basic_select and now the EXPLAIN shows a higher rows value, but less steps in the EXTRA fields. Also the query execution time went down to below a minute! (still a bit too slow, but a major improvement!).

mysql> SHOW CREATE TABLE traffic_test \G;
*************************** 1. row ***************************
       Table: traffic_test
Create Table: CREATE TABLE `traffic_test` (
  `traffic_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `type` enum('v4_assignment','v4_host','v6_subnet','v6_assignment','v6_host') NOT NULL,
  `type_id` int(11) unsigned NOT NULL,
  `time` int(32) unsigned NOT NULL,
  `bytesin` bigint(20) unsigned NOT NULL DEFAULT '0',
  `bytesout` bigint(20) unsigned NOT NULL DEFAULT '0',
  PRIMARY KEY (`time`,`type`,`type_id`,`traffic_id`),
  KEY `traffic_id_IDX` (`traffic_id`)
) ENGINE=InnoDB AUTO_INCREMENT=24545159 DEFAULT CHARSET=latin1

The indexes on the table:

mysql> SHOW INDEX FROM traffic;
+--------------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table        | Non_unique | Key_name       | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+--------------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| traffic_test |          0 | PRIMARY        |            1 | time        | A         |          18 |     NULL | NULL   |      | BTREE      |         |
| traffic_test |          0 | PRIMARY        |            2 | type        | A         |       38412 |     NULL | NULL   |      | BTREE      |         |
| traffic_test |          0 | PRIMARY        |            3 | type_id     | A         |    24545609 |     NULL | NULL   |      | BTREE      |         |
| traffic_test |          0 | PRIMARY        |            4 | traffic_id  | A         |    24545609 |     NULL | NULL   |      | BTREE      |         |
| traffic_test |          1 | traffic_id_IDX |            1 | traffic_id  | A         |    24545609 |     NULL | NULL   |      | BTREE      |         |
+--------------+------------+----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+

Also I simplified the query by not using the OR:

SELECT SQL_NO_CACHE traffic.time, SUM(traffic.bytesin), SUM(traffic.bytesout) 
FROM    traffic
WHERE traffic.type LIKE 'v4_host' AND type_id IN (131,1974,1976,1514,1516,2767,2730,2731,2732,2733,2734,2769,2994,2709,1,4613,4614,4615,4616,326,1520,2652,1518,1521,1522,1523,1524,1525,2203,1515,1513,1467,1508,1973,1510,1975,1511,1475,1476,1468,1469,1470,1471,1472,1473,1500,1507,1478,1480,1481,1482,1483,1484,1485,1479,1486,1487,1488,1489,1490,1491,1495,1499,1494,2269,1474,1519,2204,2976,1922,1493,1492,1497,1496,1498,1501,1502,1503,1526,1509,1506) 
AND traffic.time >= 1342181721 
AND traffic.time < 1343391321 
GROUP BY traffic.time ASC;

Old Execution of this query:

3980 rows in set (6 min 15.27 sec)

New Executiontime:

3980 rows in set (24.80 sec)

EXPLAIN output:

+----+-------------+---------+-------+---------------+---------+---------+------+----------+-------------+
| id | select_type | table   | type  | possible_keys | key     | key_len | ref  | rows     | Extra       |
+----+-------------+---------+-------+---------------+---------+---------+------+----------+-------------+
|  1 | SIMPLE      | traffic | range | PRIMARY       | PRIMARY | 4       | NULL | 12272804 | Using where |
+----+-------------+---------+-------+---------------+---------+---------+------+----------+-------------+

The rows value is still quite high. I think I can improve on this by switching the order of type and type_id in the index since there are only 4 types possible and many more type_ids.

Is this a correct assumption?

Answer 1

1. Table partitioning

Because of the [AND traffic.time >= 1343772000 AND traffic.time < 1346450399] clause, I imagine that you never delete data from this table, or that the table is currently storing data for multiple months. The values in the column [time] seem to be unix timestamps (1346450399 = Fri, 31 Aug 2012 21:59:59 GMT) Partition the table based on time column. That will speed up the data retrieval, as the DB will scan the coresponding partition (much faster then to scan whole table).

• A great partitioning tutorial can be found here: the http://www.arachna.com/roller/spidaman/entry/scaling_rails_with_mysql_table
• You will need to calculate the timestamp ranges for that, but it should not be hard to do.
• Ex: (1346450399 - 1343772000) / 60 / 60 / 24 =~ 31 days. So the max value for the partition holding the data for september (has also 31 days) will be: 1346450399 + ( 31 * 24 * 60 * 60)
• An unix to date calculator can be found here: http://www.onlineconversion.com/unix_time.htm

2. Rewrite the query

Because the "OR" in your WHERE block, the optimizer will choose not to use the index defined. Try to split the query in 2 selects, and make an union.

SELECT 
    traffic.time, 
    SUM(traffic.bytesin), 
    SUM(traffic.bytesout) 
FROM 
    traffic 
WHERE traffic.type LIKE 'v4_assignment' 
    AND type_id IN (1,2,3,4)
    AND traffic.time >= 1343772000 AND traffic.time <= 1346450399 
GROUP BY 
    traffic.time
UNION
SELECT 
    traffic.time, 
    SUM(traffic.bytesin), 
    SUM(traffic.bytesout) 
FROM 
    traffic 
WHERE traffic.type LIKE 'v4_host' 
    AND type_id IN (5,6,7,8)
    AND traffic.time >= 1343772000 AND traffic.time <= 1346450399 
GROUP BY 
    traffic.time
ORDER BY 
    traffic.time

3. New index based on data cardinality

Based on your explain output, I don't see the index beeing used. Maybe because the optimizer decides that it will be easier (cheaper) to make a full table scan then to follow the index. Also, in your current index, the first column has a lower cardinality then the next 2 ones. The first column in any index should be the column with the best (max) cardinality.

Create a new index as:

MYSQL> CREATE INDEX MTIhai_traffic_idx1 ON traffic(time, type, type_id)

Answer 2

I suggest a compound index on (time, type, type_id, bytes_in, bytes_out).

If the (type_id, time, type) combination is unique (what is the primary key of the table by the way?), you could just define the primary key to be (time, type, type_id). Then the clustered index of the table would be this primary key and you wouldn't need the above compound index. Depending what your most common queries are (if they have group by time and/or where time >=? and time <? like this one), they will have efficiency improvement as they will be able to use the clustered index.

You can also rewrite the query like this

• using = instead of LIKE and

• combining GROUP BY with ORDER BY (MySQL proprietary syntax which may improve efficiency):

  SELECT t.time, SUM(t.bytesin), SUM(t.bytesout) 
  FROM traffic AS t 
  WHERE ( t.type = 'v4_assignment' AND t.type_id IN (231, between 20 to 100 ids,265)
       OR t.type = 'v4_host' AND t.type_id IN (131, ... a lot of ids... ,1506)
        ) 
      AND t.time >= 1343772000 AND t.time < 1346450399 
  GROUP BY t.time ASC ;
  

---

Update + correction

When you have defined no PRIMARY and no UNIQUE index on an (InnoDB) table, a hidden 6-byte column is created and used as the clustered index of the table.

So, it may be better to explicitely define a 4-byte auto-incremented integer column and use it in combination with the time column (or all the 3 column above) as a PRIMARY or UNIQUE key. For no other purpose but to have a clustered index that is useful for your queries:

ALTER TABLE traffic
  ADD COLUMN
    traffic_id INT UNSIGNED NOT NULL AUTO_INCREMENT FIRST,
  ADD CONSTRAINT traffic_PK 
    PRIMARY KEY (time, type, type_id, traffic_id) 
  ADD INDEX traffic_id_IDX (traffic_id) ;

or (to have a narrower primary key):

ALTER TABLE traffic
  ADD COLUMN
    traffic_id INT UNSIGNED NOT NULL AUTO_INCREMENT FIRST,
  ADD CONSTRAINT traffic_PK 
    PRIMARY KEY (time, traffic_id), 
  ADD INDEX traffic_id_IDX (traffic_id) ;

---

another suggestion:

Both of these clustered indices are roughly equivalent to the (time, type, type_id, bytes_in, bytes_out) suggested at the beginning.

The only other index that might perform better is the (type, type_id, time, bytes_in, bytes_out). But it depends on how may type_id are on these lists and what percentage of the data they refer to.