Regardless of the number of rows tables have, it's how this data is assigned on disk (and how big that is), and then read into the applicable MySQL memory buffers that matter. The goal is to reduce the memory to disk ratio for "Hot" data. Optimizing indexes is an art. There are also many tricks, like using the right data type (INT not BIGINT), covering indexes (reduces looking at data). Depending on your queries, partitioning may help. Capturing the Query Execution Plan (QEP), learning how to read, understand and improve is necessary to solve your slow queries. http://effectivemysql.com/ has a number of introduction presentations for Optimizing SQL.