Is there a table size above which SELECT performance degrades significantly? In MySQL, does SELECT performance degrade significantly after a certain table size? I have a table with about 107 million rows and some queries seem stuck in "Sending data" for a long time. Of course, "sending data" is a catchall for all sorts of query processing according to the MySQL manual. This is puzzling because EXPLAIN says that the query is "using where; using index" and only returns about 1700 rows. It's the only query running, so I know it's not a locking issue.

Would it help to split this table into a few hundred smaller tables, if I'm splitting on something that's already part of the key? It seems like the key itself should be better than that solution, but I'm at a loss as to why this query should take so much time.

The table engine in question is TokuDB, but I see the same results with InnoDB. I haven't tried MyISAM or any other engine with this table.

The query is (apologies for obfuscation due to internal data):

SELECT id FROM my_table WHERE my_end_time&gt;=1234567890 AND 
    my_start_time&lt;=2345678901 AND a='XXX' AND b='YYY' 
    ORDER BY my_start_time ASC;


The key it's using is a UNIQUE index on 

a, b, my_start_time, my_end_time
Not sure what version of TokuDB you are running, or what MySQL/MariaDB distribution, but there is an index condition pushdown bug that occurs on queries similar to the one you've provided. We are still waiting for a fix, the only current workaround is to disable ICP when running the problematic query.

Try running the query with ICP turned off. To disable it, issue the following command in the session just before running the query:

SET optimizer_switch='index_condition_pushdown=off';

And please report back success/failure, and the particular versions of TokuDB and MySQL/MariaDB.

(full disclosure, I'm an employee of Tokutek, makers of TokuDB)