The issue I'm facing is namely on inserts. What I've got is basically an online voting system; I have a registration table, matching a user to a ballot. I run the student government elections for a number of colleges, one of which has over 30k students on each ballot. So over the last few years, with a few ballots a year, I've gotten to over 1.5mil rows. I had actually assumed this isn't much, specially because I only have 3 columns: ballotID (mediint(4)), voterID (medint(7)), and voted (tinyint(1)). Obviously not much being stored.
When I went to add to the voters list this year, I noticed that while in the past I could usually put in sets of 5k voters at once (more then that and the system timed out, a fault of the shared host server I'm on), and usually inserted an average of 300 voters a second, this year, I could barely process 20 voters per second. I checked with the host and the server load was no greater than in the past. When I decided to delete all registrants before 2010, the insert speed shot up to about 250 voters per second. But as the list got higher again, it went back to a crawl.
So I firstly know that one big limit for me is my host. I should get a VPS server at the least, I think, but I'm trying to see what I can do until I can afford to do that.
I also make sure to properly cast my data, and as for index on the registrants table, I used a combination of ballotID and voterID for the key (after all, a user can only be registered for a ballot once).
I have a second table for voter tags which is basically just ballotID (mediint(4)), voterID (medint(7)), tag (varchar(30)). The key on that table is all 3 columns. This table is at about 2.2 mil records and is as slow as the registration table. Both have data fed into them during the above mentioned process, and are included in the insert speeds mentioned above.