MySQL queries still slow after deleting bunch of records I need some help with resolving some mysql issues. My website had been running slow since last week and after contacting my host I found out that some queries were taking too long mainly because of table locks. I am a developer but no mysql/database expert. My host suggested that I either delete and/or change the two tables in question to innoDB. So as these tables had a lot of junk data I decided to delete a bunch of records. I would say that these two tables are about 25% of the size when this problem started. Problem is that, it still has not made any difference. So my questions:

Do I need to clear cache or optimize table in order to see the
effects? My host is still suggesting I change those tables to innoDB
which is fine but I'm not sure why deleting that many records have
not made a difference.
Also I have read that it is better to
recreate the table than just optimizing? If needed I can hire a
database admin to help me but I would like to at least try a few
things if this is something simple. Can someone please guide me
through this.

One more important thing to add, it is a legacy website running on php 5.4 and mysql 5.6
Rather than change a pair of tables to InnoDB, it would be better for every table in the database to be converted as InnoDB is a much better storage engine. That said, MyISAM is workable if you don't mind babysitting it every once in a while.
Do I need to clear cache or optimize table in order to see the effects?
⇢ The database engine will clear the cache on its own, but you can force this by restarting the server. Optimising the tables is certainly recommended for MyISAM tables if you haven't done so in a while. This will ensure that the data is in a consistent state and that the indexes are properly linked.
Also I have read that it is better to recreate the table than just optimizing?
⇢ It is sometimes faster to recreate than optimise. If you plan on tackling just the indexes, then DROP and CREATE are your friend. If you want to also check the integrity of the tables, then OPTIMIZE TABLE is what you're looking for. If your site doesn't get too much traffic, you could even look at dropping the index, optimising the table, then recreating the index.
Ideally this should be done for every table in the database, not just the two in question. Databases, like many other things, need the occasional bit of maintenance to remain reliable.