Can this query be any faster?

Question

I have got the following query:

SELECT SQL_CALC_FOUND_ROWS *
FROM (
SELECT *
FROM 
(  
    SELECT M.id, M.project_id, M.reply_toaddress as reply_toemailaddress, M.phone_no, M.subject,M.message, M.timestamp_received, M.done, M.postpone,  "mail" AS type, M.firstname, M.prefix, M.surname
    FROM messages M
    LEFT JOIN link_projects_mailboxes LPMB 
        ON M.mailbox_id = LPMB.mailbox_id
    WHERE M.main_message_id =0  
         AND LPMB.projects_id = 13  AND ( 0 OR  (M.done = 0 AND M.postpone = 0 ))  AND M.status = 0  
    GROUP BY M.id 
) M
UNION 
(
    SELECT C.id, C.project_id, C.reply_toemailaddress, C.phone_no, C.subject,C.message, C.timestamp_received, done, postpone, "call" AS type , C.firstname, C.prefix, C.surname
    FROM calls C
    WHERE 1 
         AND projects_id = 13  AND ( 0 OR  (C.done = 0 AND C.postpone = 0 ))  AND C.status = 0  
) 
) x ORDER BY  `timestamp_received`  asc  LIMIT 30

The problem is that this query is running on 700.000 rows with 19.2GB data. The query runs for about 3 minutes.

If I explain the query I recieve the following result:

Do you guys have any suggestions?

EDIT: Show Create table:

CREATE TABLE `messages` (
  `id` int(10) NOT NULL AUTO_INCREMENT,
  `mailbox_id` int(11) NOT NULL,
  `submessage_of` int(11) NOT NULL,
  `main_message_id` int(11) NOT NULL,
  `project_id` int(11) NOT NULL COMMENT 'Takes project from afasmssql_sync DB',
  `categorie_id` int(11) NOT NULL,
  `call_id` int(11) NOT NULL,
  `to` text NOT NULL,
  `cc` text NOT NULL,
  `bcc` text NOT NULL,
  `message_id` varchar(255) NOT NULL,
  `bytes` int(11) NOT NULL,
  `from` varchar(255) NOT NULL,
  `sender` varchar(255) NOT NULL,
  `reply_toaddress` varchar(255) NOT NULL,
  `reply_toemailaddress` varchar(255) NOT NULL,
  `subject` varchar(255) NOT NULL,
  `order_id` int(10) NOT NULL DEFAULT '0',
  `order_location` varchar(255) NOT NULL,
  `firstname` varchar(200) NOT NULL,
  `prefix` varchar(50) NOT NULL,
  `surname` varchar(200) NOT NULL,
  `emailaddress` varchar(200) NOT NULL,
  `phone_no` varchar(255) NOT NULL,
  `zipcode` varchar(6) NOT NULL,
  `house_no` varchar(6) NOT NULL,
  `house_no_add` varchar(50) NOT NULL,
  `street` varchar(200) NOT NULL,
  `city` varchar(200) NOT NULL,
  `country` varchar(50) NOT NULL,
  `language` varchar(50) NOT NULL,
  `message` longtext NOT NULL,
  `message_plain` longtext NOT NULL,
  `message_stripped` longtext NOT NULL,
  `quality_status` tinyint(1) NOT NULL,
  `quality_by` int(11) NOT NULL,
  `quality_date` datetime NOT NULL,
  `done` tinyint(1) NOT NULL,
  `done_date` datetime NOT NULL,
  `done_by` int(11) NOT NULL,
  `postpone` tinyint(1) NOT NULL,
  `status` int(11) NOT NULL,
  `manually` tinyint(1) NOT NULL,
  `timestamp_received` datetime NOT NULL,
  `timestamp` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  KEY `mailbox_id` (`mailbox_id`),
  KEY `submessage_of` (`submessage_of`),
  KEY `main_message_id` (`main_message_id`),
  KEY `subject` (`subject`),
  KEY `done` (`done`),
  KEY `postpone` (`postpone`),
  KEY `status` (`status`),
  KEY `project_id` (`project_id`),
  KEY `categorie_id` (`categorie_id`),
  KEY `call_id` (`call_id`),
  KEY `done_date` (`done_date`),
  KEY `timestamp_received` (`timestamp_received`),
  KEY `from` (`from`),
  KEY `reply_toemailaddress` (`reply_toemailaddress`),
  KEY `timestamp` (`timestamp`),
  FULLTEXT KEY `message` (`message`)
) ENGINE=MyISAM AUTO_INCREMENT=685579 DEFAULT CHARSET=utf8

CREATE TABLE `link_projects_mailboxes` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `projects_id` int(11) NOT NULL,
  `mailbox_id` int(11) NOT NULL,
  `timestamp` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  KEY `projects_id` (`projects_id`,`mailbox_id`)
) ENGINE=MyISAM AUTO_INCREMENT=156 DEFAULT CHARSET=latin1

CREATE TABLE `calls` (
  `id` int(10) NOT NULL AUTO_INCREMENT,
  `actionline_id` int(11) NOT NULL,
  `projects_id` int(11) NOT NULL,
  `project_id` int(11) NOT NULL COMMENT 'Takes project from afasmssql_sync DB',
  `categorie_id` int(11) NOT NULL,
  `call_direction` varchar(255) NOT NULL,
  `subject` varchar(255) NOT NULL,
  `order_id` int(10) NOT NULL DEFAULT '0',
  `order_location` varchar(255) NOT NULL,
  `firstname` varchar(200) NOT NULL,
  `prefix` varchar(50) NOT NULL,
  `surname` varchar(200) NOT NULL,
  `reply_toemailaddress` varchar(200) NOT NULL,
  `phone_no` varchar(255) NOT NULL,
  `zipcode` varchar(6) NOT NULL,
  `house_no` varchar(6) NOT NULL,
  `house_no_add` varchar(50) NOT NULL,
  `street` varchar(200) NOT NULL,
  `city` varchar(200) NOT NULL,
  `country` varchar(50) NOT NULL,
  `language` varchar(50) NOT NULL,
  `message` longtext NOT NULL,
  `done` tinyint(1) NOT NULL,
  `done_date` datetime NOT NULL,
  `done_by` int(11) NOT NULL,
  `postpone` tinyint(1) NOT NULL,
  `status` int(11) NOT NULL,
  `timestamp_received` datetime NOT NULL,
  `timestamp` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  KEY `mailbox_id` (`actionline_id`),
  KEY `subject` (`subject`),
  KEY `done` (`done`),
  KEY `postpone` (`postpone`),
  KEY `status` (`status`),
  KEY `project_id` (`project_id`),
  KEY `projects_id` (`projects_id`),
  FULLTEXT KEY `message` (`message`)
) ENGINE=MyISAM AUTO_INCREMENT=8941 DEFAULT CHARSET=utf8

EDIT: EXPLAIN based on Strawberries answer:

Answer 1

Since the two inner SELECTs have no common rows, change UNION to UNION ALL. That will save a dedup pass. Run each of them to see which one is slower; then we can focus on it.

These 'composite' indexes may help it run significantly faster:

M:  INDEX(mailbox_id, message_id, done, postpone, status) -- in any order
calls:  INDEX(projects_id, done, postpone, status) -- in any order 

If you did not need SQL_CALC_FOUND_ROWS, this would be much faster:

( SELECT ... FROM M ... ORDER BY ... LIMIT 30 )
UNION ALL
( SELECT ... FROM M ... ORDER BY ... LIMIT 30 )
ORDER BY ... LIMIT 30;   -- yes, repeated again

It would require suitable indexes, probably the ones suggested above, with timestamp_received added on the end. And the virtually useless JOIN LPMB should be replaced by AND EXISTS ( SELECT ... FROM LPMB ... )

That UNION+LIMIT trick gets more complex, but still possible, if you are paginating with OFFSET.

Unrelated:

Get rid of indexes on individual flags; they are usually useless.

You should move from MyISAM to InnoDB. FULLTEXT (slightly different) is available in later versions.

@dacrovinunghi - MySQL has no "bitmap" index type.

WHERE 1 and 0 OR come from dynamically building the WHERE clause, but not taking the time to keep it clean. I prefer to build an array of clauses to be AND'd, then implode them. Or, if none, avoid the WHERE all together.

It may be better to remove the "done" (etc) items from the table. That would eliminate that part(s) of the WHERE and shrink the table, making it more compact and efficient.

Answer 2

So, just to make things more readable, let's start with this query, and run the EXPLAIN on that instead...

SELECT SQL_CALC_FOUND_ROWS *
  FROM
     ( SELECT M.id
            , M.project_id
            , M.reply_toaddress as reply_toemailaddress
            , M.phone_no
            , M.subject
            , M.message
            , M.timestamp_received
            , M.done
            , M.postpone
            , "mail" type
            , M.firstname
            , M.prefix
            , M.surname
         FROM messages M
         JOIN link_projects_mailboxes LPMB 
           ON LPMB.mailbox_id = M.mailbox_id 
        WHERE M.main_message_id = 0  
          AND LPMB.projects_id = 13  
          AND M.done = 0 
          AND M.postpone = 0 
          AND M.status = 0  
        UNION 
       SELECT C.id
            , C.project_id
            , C.reply_toemailaddress
            , C.phone_no
            , C.subject
            , C.message
            , C.timestamp_received
            , C.done
            , C.postpone
            , "call" type 
            , C.firstname
            , C.prefix
            , C.surname
         FROM calls C
        WHERE C.projects_id = 13  
          AND C.done = 0 
          AND C.postpone = 0 
          AND C.status = 0  
     ) x 
 ORDER 
    BY timestamp_received ASC
 LIMIT 30;

EXPLAIN for same:

+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+
| id   | select_type  | table      | type | possible_keys    | key         | key_len | ref                 | rows  | Extra          |
+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+
|    1 | PRIMARY      | <derived2> | ALL  | (NULL)           | (NULL)      | (NULL)  | (NULL)              |  218  | Using filesort |
+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+
|    2 | DERIVED      | LPMB       | ref  | projects_id      | projects_id | 4       |                     |    1  | Using index    |
+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+
|    2 | DERIVED      | M          | ref  | mailbox_id,      | mailbox_id  | 4       | ccc.LPMB.mailbox_id | 7,735 | Using where    |
|      |              |            |      | main_message_id, |             |         |                     |       |                |
|      |              |            |      | done,            |             |         |                     |       |                |
|      |              |            |      | postpone,        |             |         |                     |       |                |
|      |              |            |      | status           |             |         |                     |       |                |
+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+
|    3 | UNION        | C          | ref  | done,            | done        | 1       |                     |     4 | Using where    |
|      |              |            |      | postpone,        |             |         |                     |       |                |
|      |              |            |      | status,          |             |         |                     |       |                |
|      |              |            |      | projects_id      |             |         |                     |       |                |
+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+
|(NULL)| UNION RESULT | <union2,3> | ALL  | (NULL)           | (NULL)      | (NULL)  | (NULL)              | (NULL)|                |
+------+--------------+------------+------+------------------+-------------+---------+---------------------+-------+----------------+