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    |                | 
+---------------------+------------------+------+-----+---------+----------------+         

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    |                | 
+---------------+------------------+------+-----+---------+----------------+

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    |                | 
+---------------+------------------+------+-----+---------+----------------+

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);

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 ?

Thanks