Query Optimization – How to Optimize a Query with Multiple Derived Tables Containing ‘IN’ and ‘GROUP BY’

mariadbperformancequery-performance

I'm collecting nmap data every five minutes and storing it in a database. Information about each scan (e.g. start and end time) is stored in the scans table:

CREATE TABLE `scans` (
  `scan_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `start_time` datetime NOT NULL,
  `end_time` datetime NOT NULL,
  `nmap_version` varchar(20) DEFAULT NULL,
  `nmap_args` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`scan_id`)
) ENGINE=InnoDB AUTO_INCREMENT=34901 DEFAULT CHARSET=utf8

Information about the hosts scanned (e.g. hostname, MAC address) is stored in the hosts table:

CREATE TABLE `hosts` (
  `scan_id` int(10) unsigned NOT NULL,
  `host_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `hostname` varchar(255) NOT NULL,
  `ip_address` int(10) unsigned NOT NULL,
  `mac_address` bigint(20) unsigned DEFAULT NULL,
  `mac_vendor` varchar(255) DEFAULT NULL,
  `status` varchar(20) NOT NULL,
  `hops` int(10) unsigned DEFAULT NULL,
  `last_boot` datetime DEFAULT NULL,
  PRIMARY KEY (`host_id`),
  KEY `scan_id` (`scan_id`),
  KEY `idx_status` (`status`),
  KEY `idx_hostname` (`hostname`),
  CONSTRAINT `hosts_ibfk_1` FOREIGN KEY (`scan_id`) REFERENCES `scans` (`scan_id`) ON DELETE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=2262995 DEFAULT CHARSET=utf8

Now I want to fetch the information from the most recent scan of one or more (up to about a thousand) hosts. The most recent scan will not necessarily be the same for all hosts. I also want to fetch the last time each host was up.

I've been using the following query, but it's slow (it takes about six seconds to fetch the data for three hosts):

SELECT hosts.hostname,
       INET_NTOA(hosts.ip_address) AS ip,
       CONV(hosts.mac_address, 10, 16) AS mac,
       hosts.mac_vendor AS mac_vendor,
       hosts.status AS status,
       scans.start_time AS last_scan,
       u.last_seen AS last_seen
FROM hosts
JOIN (
       -- ID of most recent scan for each host
       SELECT MAX(hosts.scan_id) AS max_scan_id,
              hosts.hostname
       FROM hosts
       WHERE hosts.hostname IN ('foo', 'bar', 'baz')
       GROUP BY hosts.hostname
     ) AS t
  ON (hosts.scan_id = t.max_scan_id AND hosts.hostname = t.hostname)
JOIN scans
  ON scans.scan_id = t.max_scan_id
JOIN (
       -- Last time each host was up
       SELECT MAX(scans.start_time) AS last_seen,
              hosts.hostname
       FROM scans
       JOIN hosts
         ON scans.scan_id = hosts.scan_id
       WHERE hosts.status = 'up'
       GROUP BY hosts.hostname
     ) AS u
  ON hosts.hostname = u.hostname

The EXPLAIN shows that one of the derived queries is doing a table scan:

+------+-------------+------------+--------+----------------------+--------------+---------+--------------------+---------+---------------------------------------------------------------------+
| id   | select_type | table      | type   | possible_keys        | key          | key_len | ref                | rows    | Extra                                                               |
+------+-------------+------------+--------+----------------------+--------------+---------+--------------------+---------+---------------------------------------------------------------------+
|    1 | PRIMARY     | <derived2> | ALL    | NULL                 | NULL         | NULL    | NULL               |   12855 | Using where                                                         |
|    1 | PRIMARY     | scans      | eq_ref | PRIMARY              | PRIMARY      | 4       | t.max_scan_id      |       1 |                                                                     |
|    1 | PRIMARY     | hosts      | ref    | scan_id,idx_hostname | scan_id      | 4       | t.max_scan_id      |      81 | Using where                                                         |
|    1 | PRIMARY     | <derived3> | ref    | key0                 | key0         | 767     | t.hostname         |      10 |                                                                     |
|    3 | DERIVED     | hosts      | ref    | scan_id,idx_status   | idx_status   | 62      | const              | 1136083 | Using index condition; Using where; Using temporary; Using filesort |
|    3 | DERIVED     | scans      | eq_ref | PRIMARY              | PRIMARY      | 4       | wmap.hosts.scan_id |       1 |                                                                     |
|    2 | DERIVED     | hosts      | range  | idx_hostname         | idx_hostname | 767     | NULL               |   12855 | Using index condition                                               |
+------+-------------+------------+--------+----------------------+--------------+---------+--------------------+---------+---------------------------------------------------------------------+

I tried adding the IN clause to the outer query and the second subquery (three IN clauses total), which worked great when searching for a single host, but actually performed worse than the original with a large number of hosts.

I also tried creating a temporary table to hold only the hostnames to be matched and a temporary table to hold the results of each subquery:

CREATE TEMPORARY TABLE hosts_to_match (
    hostname VARCHAR(255) NOT NULL PRIMARY KEY
);

INSERT INTO hosts_to_match
VALUES ('foo'), ('bar'), ('baz');

CREATE TEMPORARY TABLE last_scan (
    hostname VARCHAR(255) NOT NULL PRIMARY KEY, 
    scan_id INT(10) UNSIGNED NOT NULL
);

INSERT INTO last_scan (
    scan_id, 
    hostname
) 
SELECT MAX(hosts.scan_id),
       hosts.hostname 
FROM hosts_to_match 
JOIN hosts 
  ON hosts_to_match.hostname = hosts.hostname 
GROUP BY hosts.hostname;

CREATE TEMPORARY TABLE last_seen (
    hostname VARCHAR(255) NOT NULL PRIMARY KEY,
    last_seen DATETIME NOT NULL
);

INSERT INTO last_seen (
    last_seen, 
    hostname
) 
SELECT MAX(scans.start_time),
       hosts.hostname 
FROM hosts_to_match 
JOIN hosts 
  ON hosts_to_match.hostname = hosts.hostname 
JOIN scans 
  ON scans.scan_id = hosts.scan_id 
WHERE hosts.status = 'UP' 
GROUP BY hosts.hostname;

SELECT hosts.hostname, 
       INET_NTOA(hosts.ip_address) AS ip,
       CONV(hosts.mac_address, 10, 16) AS mac, 
       hosts.mac_vendor,
       hosts.status,
       scans.start_time,
       last_seen.last_seen
FROM last_scan
JOIN hosts
  ON (last_scan.hostname = hosts.hostname AND last_scan.scan_id = hosts.scan_id)
JOIN scans
  ON scans.scan_id = last_scan.scan_id
JOIN last_seen
  ON hosts.hostname = last_seen.hostname;

But populating the last_scan and last_seen temporary tables is slow for a large number of hosts.

EXPLAIN for SELECT used to populate last_scan:

+------+-------------+----------------+-------+---------------+--------------+---------+------------------------------+------+----------------------------------------------+
| id   | select_type | table          | type  | possible_keys | key          | key_len | ref                          | rows | Extra                                        |
+------+-------------+----------------+-------+---------------+--------------+---------+------------------------------+------+----------------------------------------------+
|    1 | SIMPLE      | hosts_to_match | index | PRIMARY       | PRIMARY      | 767     | NULL                         |  166 | Using index; Using temporary; Using filesort |
|    1 | SIMPLE      | hosts          | ref   | idx_hostname  | idx_hostname | 767     | wmap.hosts_to_match.hostname | 2573 |                                              |
+------+-------------+----------------+-------+---------------+--------------+---------+------------------------------+------+----------------------------------------------+

EXPLAIN for SELECT used to populate last_seen:

+------+-------------+----------------+--------+---------------------------------+--------------+---------+------------------------------+------+----------------------------------------------+
| id   | select_type | table          | type   | possible_keys                   | key          | key_len | ref                          | rows | Extra                                        |
+------+-------------+----------------+--------+---------------------------------+--------------+---------+------------------------------+------+----------------------------------------------+
|    1 | SIMPLE      | hosts_to_match | index  | PRIMARY                         | PRIMARY      | 767     | NULL                         |  166 | Using index; Using temporary; Using filesort |
|    1 | SIMPLE      | hosts          | ref    | scan_id,idx_status,idx_hostname | idx_hostname | 767     | wmap.hosts_to_match.hostname | 2573 | Using where                                  |
|    1 | SIMPLE      | scans          | eq_ref | PRIMARY                         | PRIMARY      | 4       | wmap.hosts.scan_id           |    1 |                                              |
+------+-------------+----------------+--------+---------------------------------+--------------+---------+------------------------------+------+----------------------------------------------+

How can I speed this up? I'm using MariaDB 5.5.47.

Best Answer

You can really benefit from an index on hosts (hostname, scan_id) for this query, and possibly another one including status (especially for the second query below). Your query may also benefit from transferring some joins to per-row totals:

CREATE INDEX idx_hostname_scanid ON hosts (hostname, scan_id);
CREATE INDEX idx_hostname_status_scanid ON hosts (hostname, status, scan_id);

SELECT hosts.hostname,
       INET_NTOA(hosts.ip_address) AS ip,
       CONV(hosts.mac_address, 10, 16) AS mac,
       hosts.mac_vendor AS mac_vendor,
       hosts.status AS status,
       scans.start_time AS last_scan,
       (SELECT MAX(scans.start_time)
        FROM hosts
        JOIN scans ON (scans.scan_id = hosts.scan_id)
        WHERE hosts.hostname = t.hostname AND hosts.status = 'up') AS last_seen
FROM (
       -- ID of most recent scan for each host
       SELECT MAX(hosts.scan_id) AS max_scan_id, hosts.hostname
       FROM hosts
       WHERE hosts.hostname IN ('foo', 'bar', 'baz')
       GROUP BY hosts.hostname
     ) t
JOIN hosts ON (hosts.hostname = t.hostname AND hosts.scan_id = t.max_scan_id)
JOIN scans ON (scans.scan_id = t.max_scan_id);

Also, considering that you already trust the last scan to be the one with the highest id, you may speed-up your query by trusting the last_seen time to be the one with the highest id:

CREATE INDEX idx_hostname_scanid ON hosts (hostname, scan_id);
CREATE INDEX idx_hostname_status_scanid ON hosts (hostname, status, scan_id);

SELECT hosts.hostname,
       INET_NTOA(hosts.ip_address) AS ip,
       CONV(hosts.mac_address, 10, 16) AS mac,
       hosts.mac_vendor AS mac_vendor,
       hosts.status AS status,
       scans.start_time AS last_scan,
       lss.start_time AS last_seen
FROM (
       -- ID of most recent scan for each host
       SELECT MAX(hosts.scan_id) AS max_scan_id, hosts.hostname
       FROM hosts
       WHERE hosts.hostname IN ('foo', 'bar', 'baz')
       GROUP BY hosts.hostname
     ) t
JOIN hosts ON (hosts.hostname = t.hostname AND hosts.scan_id = t.max_scan_id)
JOIN scans ON (scans.scan_id = t.max_scan_id)
LEFT JOIN (
       SELECT MAX(hosts.scan_id) AS max_scan_id, hosts.hostname
       FROM hosts
       WHERE hosts.hostname IN ('foo', 'bar', 'baz') AND hosts.status = 'up'
       GROUP BY hosts.hostname
     ) ls ON (ls.hostname = t.hostname)
LEFT JOIN scans lss ON (lss.scan_id = ls.max_scan_id);

Related Solutions

Mysql – Identical query, tables, but different EXPLAIN and performance

Just make a simple join. Sub-queries does not provide the best result quite often

EXPLAIN SELECT l.id, l.level_name, l.date_published, l.rating
FROM levels AS l
INNER JOIN users_favorites AS uf 
ON uf.level_id = l.id
WHERE l.user_id = 2;

MySQL – How to Decide Which Execution Plan is Better

Multiplying the rows is invalid for several reasons:

Many times, the rows examined are an approximation (based on statistics, not accurate), good for query plan selection, but not for performance calculation
The total number of rows examined on a nested loop join (A, B) is not rows_examined_on_table_A * rows_examined_on_table_B, but rows_examined_on_table_A + rows_returned_from_table_A * rows_examined_on_table_B. Where clauses can make a huge difference on that, although it is true that the mentioned calculations is many times used as a broad approximation, assuming the indexes are being created properly and the main causes of filtering out results.
Modern MySQL versions do not use always a nested loop join approach for executing joins and subqueries. Check 5.6 subquery optimizations and other optimization documents on the same manual. Additionally, some of the new optimization techniques do not modify the predicted examined rows, which at some times can be way lower than the one printed, even if it has been calculated exactly.

In particular, on your first query, you are hitting a well know MySQL bug? limitation? in which an IN subquery is identified as a DEPENDENT SUBQUERY, even if it really isn't, forcing the outmost query to be executed without an index (full table scan) in order to test all possible values of the first table. That is usually an indicator that it is a bad query. It seems not to bee too bad in this case, as the table is small, but it is usually an indication of bad performance.

The other thing that should bring your attention is the Using temporary; Using filesort. Filtering is not the only thing where you should focus, as these extra pieces of information are telling you that a large sorting has to be done using a temporary table (that may or may not end up on disk, but at least has to be materialized). That is another indicator of potential bad performance, that in some cases can be avoided with the right indexes.

I will not tell you which is the right query to use (partially, because I do not know all the variables: indexes, tables structure, etc., and in most cases it will depend on the particular hardware/resources available), but I will tell you the tools to decide:

Profile the query- obtain the post execution times and how much of it it is being invested in what. You can use SHOW PROFILES up to 5.5, and the performance_schema starting with 5.6.
As time can be sometimes variable (for example, depending on other queries being executed at the same time, depending on the buffer pool contents) Obtain post-execution statistics with SHOW SESSION STATUS. In particular:
```
FLUSH SESSION STATUS;
SELECT ... ;
SHOW STATUS like 'Hand%';
```
will give you the exact number of handler calls done (approximately, the number of rows read and written for that particular query- although that is not 100% accurate, as it depends on the particular engine implementation).

You may also want to monitor other status variables, like the created temporary tables, created temporary tables on disk and sort passes/sorted rows.

All of these will give you post-execution, exact, time-independent parameters to evaluate the performance of a query. Percona even has a patch for the slow log to output that information on the logs instead of using performance_schema.

With those extra pieces of information you will be able to evaluate more objectively which query is better, and not relying exclusively on EXPLAIN, which only provides limited pre-execution information.

Best Answer

Related Solutions

Mysql – Identical query, tables, but different EXPLAIN and performance

MySQL – How to Decide Which Execution Plan is Better

Related Question