Is there a table size above which SELECT performance degrades significantly?
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)