Why query with SQL_NO_CACHE runs slower on the first run?
As another answer highlighted, Query Cache is not the only cache. Its use is not even advisable in most cases - in fact, it was removed in MySQL 8.0. The reason is that it has scalability problems (it's governed by a global lock) and it invalidates data far too frequently to be useful in a normal workload.

But InnoDB buffer pool contains indexes and data accessed frequently. After your first query, some indexes and data are cached, so next time they will be read from memory. Probably some data/index pages are accessed only once per query, in which case you should be able to see a slighter difference between second and third execution (first time these pages are not cached).

How to avoid the difference between query execution times? Well, there is no way to make the query faster the very first time it runs, as it needs to read from disk. But then, if your buffer pool is big enough, your query will always be fast. Keep in mind that a big buffer pool is very important for MySQL performance. The general recommendation is to keep it 75-80% of total memory. But in reality, things are more complex:


Other caches and buffers require space. In particular, if you have many users, or if your users run many JOINs or ORDER BYs, per-session buffers should be taken into account.
It is useless to have the buffer pool bigger than your database. And it is generally a waste to have it bigger than hot data (data you access often).


Another thing is, sometimes every server is restarted. When it happens, if the buffer pool is simply emptied, your queries will be slower after restart - until hot data are cached again. But you can avoid this by setting:

innodb_buffer_pool_dump_at_shutdown = 1
innodb_buffer_pool_load_at_startup = 1


In this way, your buffer pool will be (partially) written to disk on shutdown and reloaded at startup, so your queries should be fast even after a restart.