We have multi-user application (like MailChimp,Constant Contact) . Each of our customers has it's own contact's list (from 5 to 100.000 contacts). Everything is stored in one BIG database (currently 25G). Since we released our product we have the following data history.

5 years of data history : - users/customers (200+) - contacts (40 million records) - campaigns - campaign_deliveries (73.843.764 records) - campaign_queue ( 8 millions currently )

As we get more users and table records increase our system/web app is getting slower and slower . Some queries takes too long to execute .

SCHEMA

Table contacts

--------------------+------------------+------+-----+---------+----------------+
| Field               | Type             | Null | Key | Default | Extra          |
+---------------------+------------------+------+-----+---------+----------------+
| contact_id          | int(10) unsigned | NO   | PRI | NULL    | auto_increment | 
| client_id           | int(10) unsigned | YES  |     | NULL    |                | 
| name                | varchar(60)      | YES  |     | NULL    |                | 
| mail                | varchar(60)      | YES  | MUL | NULL    |                | 
| verified            | int(1)           | YES  |     | 0       |                | 
| owner               | int(10) unsigned | NO   | MUL | 0       |                | 
| date_created        | date             | YES  | MUL | NULL    |                |  
| geolocation         | varchar(100)     | YES  |     | NULL    |                | 
| ip                  | varchar(20)      | YES  | MUL | NULL    |                | 
+---------------------+------------------+------+-----+---------+----------------+  
PRIMARY KEY  (`contact_id`),
  UNIQUE KEY `owner` (`owner`,`mail`),
  KEY `contacts_index_mail` (`mail`),
  KEY `index_contacts_date_created` (`date_created`),
  KEY `index_contacts_ip` (`ip`),

Table campaign_deliveries

+---------------+------------------+------+-----+---------+----------------+
| Field         | Type             | Null | Key | Default | Extra          |
+---------------+------------------+------+-----+---------+----------------+
| id            | int(11)          | NO   | PRI | NULL    | auto_increment | 
| newsletter_id | int(10) unsigned | NO   | MUL | 0       |                | 
| contact_id    | int(10) unsigned | NO   | MUL | 0       |                | 
| sent_date     | date             | YES  | MUL | NULL    |                | 
| sent_time     | time             | YES  | MUL | NULL    |                | 
| smtp_server   | varchar(20)      | YES  |     | NULL    |                | 
| owner         | int(5)           | YES  | MUL | NULL    |                | 
| ip            | varchar(20)      | YES  | MUL | NULL    |                | 
+---------------+------------------+------+-----+---------+----------------+
INDEXES
PRIMARY KEY  (`id`),
  UNIQUE KEY `newsletter_id` (`newsletter_id`,`contact_id`),
  KEY `newsletter_delivery_FKIndex1` (`newsletter_id`),
  KEY `newsletter_delivery_FKIndex2` (`contact_id`),
  KEY `newsletter_delivery_owner` (`owner`),
  KEY `index_nd_sent_date` (`sent_date`),
  KEY `index_nd_sent_time` (`sent_time`),
  KEY `index_ip` (`ip`)

Table campaign_queue

+---------------+------------------+------+-----+---------+----------------+
| Field         | Type             | Null | Key | Default | Extra          |
+---------------+------------------+------+-----+---------+----------------+
| queue_id      | int(10) unsigned | NO   | PRI | NULL    | auto_increment | 
| newsletter_id | int(10) unsigned | NO   | MUL | 0       |                | 
| owner         | int(10) unsigned | NO   | MUL | 0       |                | 
| date_to_send  | date             | YES  |     | NULL    |                | 
| contact_id    | int(11)          | NO   | MUL | NULL    |                | 
| date_created  | date             | YES  |     | NULL    |                | 
+---------------+------------------+------+-----+---------+----------------+
INDEXES
PRIMARY KEY  (`queue_id`),
  UNIQUE KEY `newsletter_id` (`newsletter_id`,`contact_id`),
  KEY `newsletter_queue_index1` (`newsletter_id`),
  KEY `newsletter_queue_index4` (`owner`),
  KEY `newsletter_queue_index5` (`newsletter_id`),
  KEY `contacts_contact_id` (`contact_id`)

Slow queries LOG --------------------------------------------

Query_time: 350 Lock_time: 1 Rows_sent: 1 Rows_examined: 971004

SELECT COUNT(*) as total FROM contacts WHERE (contacts.owner = 70 AND contacts.verified = 1);

Query_time: 235 Lock_time: 1 Rows_sent: 1 Rows_examined: 4455209

SELECT COUNT(*) as total FROM contacts WHERE (contacts.owner = 2);

EXPLAIN

EXPLAIN SELECT COUNT(*) as total FROM contacts WHERE (contacts.owner = 112 AND contacts.verified = 1);

+----+-------------+----------+------+---------------+-------+---------+-------+--------+-------------+
| id | select_type | table    | type | possible_keys | key   | key_len | ref   | rows   | Extra       |
+----+-------------+----------+------+---------------+-------+---------+-------+--------+-------------+
|  1 | SIMPLE      | contacts | ref  | owner         | owner | 4       | const | 644817 | Using where | 
+----+-------------+----------+------+---------------+-------+---------+-------+--------+-------------+

How can we optimize it ? Queries should take no more than 30 secs to execute? Can we optimize it and keep all data in one BIG database or should we change app's structure and set one single database to each user ?

EDIT table indexes added below schema

Thanks