Approximate MySQL Query Time For A Where Clause On A 10 Million Records Table
10 million records is nothing to MySQL.
Database design is VERY importmant - INDEX the field(s) that will be searched.
Don't index every field.
When you get into the billions of records then look into Partitioning tables.
RAM, more RAM, and just to be sure add more RAM. MySQL loves RAM.
For best speeds, make sure the MySQL server is a dedicated box - NOT a VM.
I would lean more towards Linux for the OS.
Hire a database admin.