Mysql – Optimizing multi-table left joins

join;MySQL

I have four tables which I am trying to join together.

Table event

+------------+------------------+------+-----+---------+-------+
| Field      | Type             | Null | Key | Default | Extra |
+------------+------------------+------+-----+---------+-------+
| sid        | int(10) unsigned | NO   | PRI | NULL    |       |
| cid        | int(10) unsigned | NO   | PRI | NULL    |       |
| signature  | int(10) unsigned | NO   | MUL | NULL    |       |
| timestamp  | datetime         | NO   | MUL | NULL    |       |
| is_deleted | tinyint(1)       | NO   | MUL | 0       |       |
+------------+------------------+------+-----+---------+-------+

Indexes – sid,cid,timestamp,is_deleted

Table iphdr

+----------+----------------------+------+-----+---------+-------+
| Field    | Type                 | Null | Key | Default | Extra |
+----------+----------------------+------+-----+---------+-------+
| sid      | int(10) unsigned     | NO   | PRI | NULL    |       |
| cid      | int(10) unsigned     | NO   | PRI | NULL    |       |
| ip_src   | int(10) unsigned     | NO   | MUL | NULL    |       |
| ip_dst   | int(10) unsigned     | NO   | MUL | NULL    |       |
+----------+----------------------+------+-----+---------+-------+

Indexes – sid,cid,(ip_src,ip_dst)

Table tcphdr

+-----------+----------------------+------+-----+---------+-------+
| Field     | Type                 | Null | Key | Default | Extra |
+-----------+----------------------+------+-----+---------+-------+
| sid       | int(10) unsigned     | NO   | PRI | NULL    |       |
| cid       | int(10) unsigned     | NO   | PRI | NULL    |       |
| tcp_sport | smallint(5) unsigned | NO   | MUL | NULL    |       |
| tcp_dport | smallint(5) unsigned | NO   | MUL | NULL    |       |
+-----------+----------------------+------+-----+---------+-------+

Indexes – sid,cid

Table udphdr

+-----------+----------------------+------+-----+---------+-------+
| Field     | Type                 | Null | Key | Default | Extra |
+-----------+----------------------+------+-----+---------+-------+
| sid       | int(10) unsigned     | NO   | PRI | NULL    |       |
| cid       | int(10) unsigned     | NO   | PRI | NULL    |       |
| udp_sport | smallint(5) unsigned | NO   | MUL | NULL    |       |
| udp_dport | smallint(5) unsigned | NO   | MUL | NULL    |       |
+-----------+----------------------+------+-----+---------+-------+

Indexes – sid,cid

The fields 'sid','cid' are common to all the tables and are primary keys in all. The first two tables have about 1M rows while the next two have about 600K and 200K rows respectively.

I need to find distinct IP links for not deleted events. So I write a query like

SELECT 
inet_ntoa(iphdr.ip_src) AS src_ip, iphdr.ip_src AS src_ip_inet, inet_ntoa(iphdr.ip_dst) AS dst_ip, iphdr.ip_dst AS dst_ip_inet, count('*') AS total, count(DISTINCT event.signature) AS count_unique  
FROM 
event
INNER JOIN iphdr ON event.sid = iphdr.sid AND event.cid = iphdr.cid 
LEFT OUTER JOIN tcphdr ON iphdr.sid = tcphdr.sid AND iphdr.cid = tcphdr.cid 
LEFT OUTER JOIN udphdr ON iphdr.sid = udphdr.sid AND iphdr.cid = udphdr.cid 
WHERE event.is_deleted = 0
GROUP BY iphdr.ip_src, iphdr.ip_dst 
order by total desc 
LIMIT 5

The query runs fine and returns result in about 7 seconds.

The MySQL query plan is

-+--------+---------------------------------+
| id | select_type | table  | type   | possible_keys                                  | key     | key_len | ref                               | rows   | Extra                           |
+----+-------------+--------+--------+------------------------------------------------+---------+---------+-----------------------------------+--------+---------------------------------+
|  1 | SIMPLE      | event  | ref    | PRIMARY,index_event_sid,index_event_cid,is_del | is_del  | 1       | const                             | 548283 | Using temporary; Using filesort |
|  1 | SIMPLE      | iphdr  | eq_ref | PRIMARY,index_iphdr_sid,index_iphdr_cid        | PRIMARY | 8       | test.event.sid,test.event.cid |      1 |                                 |
|  1 | SIMPLE      | tcphdr | eq_ref | PRIMARY,index_tcphdr_sid,index_tcphdr_cid      | PRIMARY | 8       | test.iphdr.sid,test.event.cid |      1 | Using index                     |
|  1 | SIMPLE      | udphdr | eq_ref | PRIMARY,index_udphdr_sid,index_udphdr_cid      | PRIMARY | 8       | test.iphdr.sid,test.event.cid |      1 | Using index                     |
+----+-------------+--------+--------+------------------------------------------------+---------+---------+-----------------------------------+--------+---------------------------------+

As can be seen the index iplink (ip_src,ip_dst) is not used.

If I drop the where clause,

SELECT 
inet_ntoa(iphdr.ip_src) AS src_ip, iphdr.ip_src AS src_ip_inet, inet_ntoa(iphdr.ip_dst) AS dst_ip, iphdr.ip_dst AS dst_ip_inet, count('*') AS total, count(DISTINCT event.signature) AS count_unique  
FROM 
iphdr 
LEFT OUTER JOIN tcphdr ON iphdr.sid = tcphdr.sid AND iphdr.cid = tcphdr.cid 
LEFT OUTER JOIN udphdr ON iphdr.sid = udphdr.sid AND iphdr.cid = udphdr.cid 
INNER JOIN event ON event.sid = iphdr.sid AND event.cid = iphdr.cid 
GROUP BY iphdr.ip_src, iphdr.ip_dst 
order by total desc 
LIMIT 5

The query is 2X faster (Runs in about 3.9s) and returns correct result. Also, the query plan is altered.

+----+-------------+--------+--------+-------------------------------------------+---------+---------+-----------------------------------+---------+----------+----------------------------------------------+
| id | select_type | table  | type   | possible_keys                             | key     | key_len | ref                               | rows    | filtered | Extra                                        |
+----+-------------+--------+--------+-------------------------------------------+---------+---------+-----------------------------------+---------+----------+----------------------------------------------+
|  1 | SIMPLE      | iphdr  | index  | PRIMARY,index_iphdr_sid,index_iphdr_cid   | iplink  | 8       | NULL                              | 1065036 |   100.00 | Using index; Using temporary; Using filesort |
|  1 | SIMPLE      | tcphdr | eq_ref | PRIMARY,index_tcphdr_sid,index_tcphdr_cid | PRIMARY | 8       | test.iphdr.sid,test.iphdr.cid |       1 |   100.00 | Using index                                  |
|  1 | SIMPLE      | udphdr | eq_ref | PRIMARY,index_udphdr_sid,index_udphdr_cid | PRIMARY | 8       | test.iphdr.sid,test.iphdr.cid |       1 |   100.00 | Using index                                  |
|  1 | SIMPLE      | event  | eq_ref | PRIMARY,index_event_sid,index_event_cid   | PRIMARY | 8       | test.iphdr.sid,test.iphdr.cid |       1 |   100.00 |                                              |
+----+-------------+--------+--------+-------------------------------------------+---------+---------+-----------------------------------+---------+----------+----------------------------------------------+

But since I need to filter out deleted events, I add WHERE clause to the INNER JOIN

SELECT 
inet_ntoa(iphdr.ip_src) AS src_ip, iphdr.ip_src AS src_ip_inet, inet_ntoa(iphdr.ip_dst) AS dst_ip, iphdr.ip_dst AS dst_ip_inet, count('*') AS total, count(DISTINCT event.signature) AS count_unique  
FROM 
event
INNER JOIN iphdr ON event.sid = iphdr.sid AND event.cid = iphdr.cid and event.is_deleted = 0
LEFT OUTER JOIN tcphdr ON iphdr.sid = tcphdr.sid AND iphdr.cid = tcphdr.cid 
LEFT OUTER JOIN udphdr ON iphdr.sid = udphdr.sid AND iphdr.cid = udphdr.cid 
GROUP BY iphdr.ip_src, iphdr.ip_dst 
order by total desc 
LIMIT 5

This query runs in about 7s and gives same query plan as query 1

I also tried to use subquery to select only those events that had is_deleted=0 but it gave me an even worse performance (9s)

My questions are –

How do I optimize the first query to make use of the index on (ip_src,ip_dst) (i.e. my group by terms) without sacrificing the where clause?
Why does the where clause (or join with event.is_deleted=0) lead to such a drastic resetting of query plan
Can I re-write the query to make it more efficient?

Best Answer

PLEASE use SHOW CREATE TABLE; DESCRIBE is not descriptive enough.

You seem to be working with IPv4 IP addresses. IPv6 is upon us!

Your query inherently must do a full table scan in order to get the "total" upon which you do the ORDER BY. Since there are a million rows, it will take time.

count('*')

The quotes are not needed.

The two SELECTs are likely to be identical; order across JOIN does not matter. It does matter across LEFT JOIN. (INNER and OUTER add nothing.)

Suggestion...

First, see if this gives the correct information (albeit incomplet info):

SELECT  e.sid, e.cid, COUNT(*) AS total
FROM  event AS e
JOIN  iphdr as h ON e.sid = h.sid
                AND  e.cid = h.cid
WHERE  e.is_deleted = 0
GROUP BY  i.ip_src, i.ip_dst
ORDER BY  total DESC
LIMIT  5;

If so, then use that as a subquery, a la FROM (that-select) and LEFT JOIN to the other two tables to get the rest of the info.

The trick... The subquery is doing less work since it is touching 2 tables (vs 4). The LEFT JOINs only have to do 5 probes each, not a million.

Related Solutions

Mysql – High Disk IO, How to mitigate

As DTest pointed out, provide more information about your problem.

Regarding caching, you could possibly increase your innodb buffer pool size to allow more data and indexes to be cached in memory. If you have frequent updates, you may not benefit from the query cache and might be better off using that RAM for innodb buffer pool.

If you want to put all your data and indexes in RAM, then MySQL Cluster might be your answer.

EDIT
It looks like your SELECT statements are using proper indexes. Could you provide an explain plan for your update statement? You will have to rewrite it as a SELECT statement to do that. Do a SELECT * FROM same table and with same where clause as your UPDATE statement.

Mysql – get column from too many tables in thesql

If all the tables use the MyISAM Storage Engine and have the same table structure, I have some good news for you.

You can create a single table that consumes no additional space except a .frm file and some mapping info. The key is to take advantage of the MERGE (MRG_MyISAM) Storage Engine.

Here is how you can do this:

CREATE TABLE XMerge LIKE X1;
ALTER TABLE XMerge ENGINE=MRG_MYISAM
UNION=(X1,X2,X3,X4) INSERT_METHOD=LAST;

Using this method, you can query the 4 tables at the same time like this:

SELECT ReqF FROM XMerge WHERE EmpName='John';

Was that simple, or what ???

In your case, you have 75 tables. You would do this:

CREATE TABLE XMerge LIKE X1;
ALTER TABLE XMerge ENGINE=MRG_MYISAM
UNION=(X1,X2,X3,X4,X5,X6,X7,X8,X9,
X10,X11,X12,X13,X14,X15,X16,X17,X18,X19,
X20,X21,X22,X23,X24,X25,X26,X27,X28,X29,
X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,
X40,X41,X42,X43,X44,X45,X46,X47,X48,X49,
X50,X51,X52,X53,X54,X55,X56,X57,X58,X59,
X60,X61,X62,X63,X64,X65,X66,X67,X68,X69,
X70,X71,X72,X73,X74,X75) INSERT_METHOD=LAST;
SELECT ReqF FROM XMerge WHERE EmpName='John';

The beauty of this is that creating a MERGE table takes milliseconds. Just make sure every table has an index on EmpName. Better to do 75 indexed lookups that 75 full table scans. If there is no index on EmpName, you need to do this:

ALTER TABLE X1 ADD UNIQUE KEY (EmpName);
ALTER TABLE X2 ADD UNIQUE KEY (EmpName);
.
.
.
ALTER TABLE X75 ADD UNIQUE KEY (EmpName);
CREATE TABLE XMerge LIKE X1;
ALTER TABLE XMerge ENGINE=MRG_MYISAM
UNION=(X1,X2,X3,X4,X5,X6,X7,X8,X9,
X10,X11,X12,X13,X14,X15,X16,X17,X18,X19,
X20,X21,X22,X23,X24,X25,X26,X27,X28,X29,
X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,
X40,X41,X42,X43,X44,X45,X46,X47,X48,X49,
X50,X51,X52,X53,X54,X55,X56,X57,X58,X59,
X60,X61,X62,X63,X64,X65,X66,X67,X68,X69,
X70,X71,X72,X73,X74,X75) INSERT_METHOD=LAST;
SELECT ReqF FROM XMerge WHERE EmpName='John';

Give it a Try !!!

Best Answer

Related Solutions

Mysql – High Disk IO, How to mitigate

Mysql – get column from too many tables in thesql

Related Question