As Thor said, you probably just have an indexing problem on your table. I know that the more recent MySQL table types handle very large data sets well, so this should not be a problem.