MySQL очень медленный на очень простых запросах SELECT

У нас есть простое веб-приложение, работающее на виртуальной машине, которое сохраняет свои данные в базе данных MySQL 5.5 с движком InnoDB. Все работало нормально около трех лет, но внезапно стало очень медленно.

Например, у меня есть очень простая таблица с адресами:

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

В этой таблице содержится около 800 записей, что на самом деле немного. Но выполняя запрос

SELECT * FROM addresses

для тестовых целей он, кажется, никогда не закончится. Я проверил это с помощью mysql CLI на самом сервере: он выводит несколько строк таблицы, а затем очень долго ждет, пока не выведет следующие строки.

Так что, возможно, это проблема на этапе отправки данных, но я не уверен.

Виртуальная машина имеет 2 ГБ оперативной памяти и используется только 320 МБ. ЦП также работает на очень низком уровне от 1 до 2%. mytop не показывает никаких других запросов, блокирующих сервер. ИТ-администратор сказал, что они ничего не меняли со стороны оборудования.

Я уже пробовал что-то вроде перезапуска сервера базы данных, перезапуска виртуальной машины. Ничего не помогло.

редактировать:

EXPLAIN SELECT * FROM addresses

дает мне такой результат:

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