Optimize finding newest x rows from category
Community Wiki answer compiled from comments on the question



You should probably check the InnoDB settings. You may have given very little RAM for MySQL to use. How much RAM do you have, and what's the setting of innodb_buffer_pool_size?

It's usually set up around 70-80% of RAM in servers. Or more if your RAM is larger (say, more than 64GB).

Your index is good, yes. You might get better performance if you make that index  (data_id, timestamp) the PRIMARY KEY (and demote the (id) to a simple index). That would probably improve performance of the query (to a few milliseconds) at the expense however of slightly slower writes.

The UNIQUE (id) index is redundant. You can remove it (but that is irrelevant to the issue). I would probably remove the (data_id) index as well. The fetch index covers that as well. - ypercubeᵀᴹ



A tiny (16M) buffer pool cache leads to a lot of I/O. - Rick James