possible corruption or other issue that doesnt show on basic scans?

I have a WP table with about 33000 records that suddenly is taking more than a minute to query. According to optimization tools, everything is good but given the sudden nature of the trouble, I doubt that. We went from those tables taking way less than second to query to between 48-93 seconds now each time. Have confirmed no other load on the server slowing it down so its all down to this. Looking for other places to look or check given the issues?