Q:

MySQL extremely slow on very simple SELECT queries

We have a simple web application running on a virtual machine that saves its data in a MySQL 5.5 database with the InnoDB engine. Everything worked fine for around three years, but suddenly it became extremely slow.
For example, I have a very simple table holding addresses:
CREATE TABLE `addresses` (
  `address_id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(64) CHARACTER SET latin1 NOT NULL,
  `firstname` varchar(64) CHARACTER SET latin1 NOT NULL,
  `street` varchar(64) CHARACTER SET latin1 NOT NULL,
  `housenumber` varchar(16) CHARACTER SET latin1 NOT NULL,
  `zip` varchar(5) CHARACTER SET latin1 NOT NULL,
  `city` varchar(64) CHARACTER SET latin1 NOT NULL,
  `email` varchar(64) CHARACTER SET latin1 NOT NULL,
  `phone` varchar(16) CHARACTER SET latin1 NOT NULL,
  `birthdate` date NOT NULL,
  PRIMARY KEY (`address_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin

This table hold around 800 entries which is really not much. But running the query
SELECT * FROM addresses

for test purposes, it seems to never finish. I checked this with the mysql CLI on the server itself: It outputs some rows of the table and then waits very long until it outputs the next rows.
So maybe it is a problem in the data sending phase, but I am not sure.
The VM has 2GB of RAM and only 320MB are used. The CPU also runs at very low 1 to 2%. mytop does not show any other queries that are blocking the server. The IT admin said that they didn't change anything at the hardware side.
I already tried some thing like restarting the database server, restarting the virtual machine. Nothing helped.
edit:
EXPLAIN SELECT * FROM addresses

gives me this result:
+----+-------------+-----------+------+---------------+------+---------+------+------+-------+
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+-----------+------+---------------+------+---------+------+------+-------+
|  1 | SIMPLE      | addresses | ALL  | NULL          | NULL | NULL    | NULL |  793 |       |
+----+-------------+-----------+------+---------------+------+---------+------+------+-------+
1 row in set (0.00 sec)

A:

If the cpu load is low then this indicates that there are no problems with missing indexes, if that was the case the query would just need take more cpu and disk access. Also you said it worked fine for 3 years.
Did you check the general disk access speed (specifically on the partition where the database is located)? E.g. using dd like here.
What you're describing sounds like a dead disk or half-dead raid. Got backups i hope?

A:

You can trying a couple things, 

Do you have indexes setup? 

Indexing makes it possible to quickly find records without doing a full table scan first, cuts execution times dramatically.
CREATE INDEX idx_name ON addresses(name);

Before running the query use the EXPLAIN keyword first,

When used in front of a SELECT query, it will describe how MySQL intends to execute the query and the number of rows it will need to process before it finishes.

Make some changes to your mysql.ini, if its a VM increase the RAM and configure your mysql.ini to see if the performance increases.

There are many MySQL optimizers out there that can guide you.
Help this helps

