В 1GB сървър не разполагайте с innodb_buffer_pool_size повече от около 200M. Задаването му на 800M ще доведе до размяна. MySQL очаква неговите кешове да останат в RAM; когато се разменят на диск, производителността страда ужасно.
Таблицата ви вероятно е твърде голяма, за да бъде изцяло кеширана. Така че "сканирането на таблица" ще издуха кеша, правейки кеша безполезен и заявката ще се изпълнява със скорост на диска. Или намерете начин да избегнете подобни заявки, или вземете повече RAM.