MySQL query extremely slow after server restart

I am managing a very large database for a custom application I wrote to keep track of visitors.

The DB server was rebooted for the first time in over a year – not even to install any updates, but simply because we needed to move the hardware.

From running a query within 1 second it now takes several minutes. Well, in fact the execution time varies a lot, take a look at the following MySQL execution times (from mysql cli): 2 min 34 sec; 1 min; 34 sec; 1 min 12 sec; 11 sec; 42 sec. In that order, from running the query 6 times in a row.

SELECT DISTINCT SQL_CALC_FOUND_ROWS visits.id FROM visits          
JOIN visits_record ON (visits.id = visits_record.visit_id)             
JOIN records ON (records.id = visits_record.record_id)         
JOIN cities ON (visits.city = cities.id)         
JOIN regions ON (visits.region = regions.id)         
JOIN countries ON (visits.country = countries.id)         
JOIN organisations ON (visits.organisation = organisations.id)         
JOIN isps ON (visits.isp = isps.id) 
WHERE excluded = 0 AND visits.website_id = '101'
ORDER BY visits.time desc 
LIMIT 0,10

Running an EXPLAIN on this query shows:

+----+-------------+---------------+--------+-----------------------------+----------+---------+-------------------------------------+--------+----------------------------------------------+
| id | select_type | table         | type   | possible_keys               | key      | key_len | ref                                 | rows   | Extra                                        |
+----+-------------+---------------+--------+-----------------------------+----------+---------+-------------------------------------+--------+----------------------------------------------+
|  1 | SIMPLE      | visits        | ref    | PRIMARY,excluded,account_id | excluded | 5       | const,const                         | 198380 | Using where; Using temporary; Using filesort | 
|  1 | SIMPLE      | regions       | eq_ref | PRIMARY                     | PRIMARY  | 4       | visits.region           |      1 | Using index; Distinct                        | 
|  1 | SIMPLE      | cities        | eq_ref | PRIMARY                     | PRIMARY  | 4       | visits.city             |      1 | Using index; Distinct                        | 
|  1 | SIMPLE      | isps          | eq_ref | PRIMARY                     | PRIMARY  | 4       | visits.isp              |      1 | Using index; Distinct                        | 
|  1 | SIMPLE      | organisations | eq_ref | PRIMARY                     | PRIMARY  | 4       | visits.organisation     |      1 | Using index; Distinct                        | 
|  1 | SIMPLE      | countries     | eq_ref | PRIMARY                     | PRIMARY  | 4       | visits.country          |      1 | Using index; Distinct                        | 
|  1 | SIMPLE      | visits_record | ref    | visit_id,record_id          | visit_id | 4       | visits.id               |      2 | Distinct                                     | 
|  1 | SIMPLE      | records       | eq_ref | PRIMARY                     | PRIMARY  | 4       | visits_record.record_id |      1 | Using index; Distinct                        | 
+----+-------------+---------------+--------+-----------------------------+----------+---------+-------------------------------------+--------+----------------------------------------------+

And a SHOW INDEX FROM visits shows:

+--------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table  | Non_unique | Key_name   | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+--------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| visits |          0 | PRIMARY    |            1 | id          | A         |     2055015 |     NULL | NULL   |      | BTREE      |         | 
| visits |          1 | excluded   |            1 | account_id  | A         |         548 |     NULL | NULL   |      | BTREE      |         | 
| visits |          1 | website_id |            1 | account_id  | A         |          17 |     NULL | NULL   |      | BTREE      |         | 
+--------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+

• in general there is indexes on all of the columns used in the query.

My my.cnf looks like this:

[mysqld]
datadir=/var/lib/mysql
socket=/var/lib/mysql/mysql.sock
user=mysql
# Default to using old password format for compatibility with mysql 3.x
# clients (those using the mysqlclient10 compatibility package).
old_passwords=1

# Disabling symbolic-links is recommended to prevent assorted security risks;
# to do so, uncomment this line:
# symbolic-links=0

log-bin=mysql-bin
expire_logs_days = 3
max_binlog_size = 100M
server-id=1

max_connections = 2000
key_buffer_size = 2G
max_allowed_packet = 16M
table_cache = 256
sort_buffer_size = 2M
read_buffer_size = 2M
join_buffer_size = 2M
read_rnd_buffer_size = 2M
tmp_table_size = 256M
max_heap_table_size = 256M
myisam_sort_buffer_size = 64M
table_cache = 256
query_cache_size = 32M
query_cache_type = 1
query_cache_limit = 1M

thread_concurrency = 4

innodb_buffer_pool_size = 5G
#innodb_log_file_size = 256M
innodb_log_buffer = 4M
innodb_flush_log_at_trx_commit = 2
innodb_thread_concurrency = 8
innodb_flush_method = O_DIRECT

Bonus info: The tables are InnoDB and CHECK TABLE shows no problems.
No other queries appear especially slow.

The extreme execution time of the query seems related to the number of rows in table visits, since changing the query to say WHERE website_id = 1 instead (where 1 is a very small testsite) the number of rows in the EXPLAIN changes to 813 and the execution time stay between 0.5 and 5 seconds.

Any advice is appreciated. Please ask if there is any information you feel would be useful.

EDIT

Looking at my own post I noticed the query could seem odd to you guys.
All these joins for what reason? But for the sake of simplicity I stripped away a lot of WHERE statements that otherwise addressed all of the joins. It made no difference to performance anyway, and this post only refers to the original query I have written in the beginning of the post.

What does make a big difference to the execution time, however, is getting rid of the joins.
I would not be able to do that in my application, as the search feature would stop working then. But just for your information, without any of the JOIN statement, execution time is way below 1 second.