правильно ли я понимаю, что mysql кэширует не сам запрос, а как бы схему его выполнения?
Нет, mysql как раз кеширует непосредственно результат конкретного запроса.
План запроса строится заново для каждого запроса, не найденного в query cache.
query cache может быть и выключен, тогда mysql от запроса не кеширует ни план, ни результат.
Если запрос выполняется к редкоиспользуемой части данных - значит скорей всего пришлось читать с диска. Это варьируется от медленно до смертельно медленно в зависимости от дисков. Затем данные будут жить в кеше данных mysql (см. тюнинг используемых storage engine) и в кеше операционной системы (плюс в query cache результат запроса), пока не будут оттуда вытеснены другими более нужными данными. Сами индексы тоже могут выгружаться из памяти и даже index only scan может пойти на медленный диск.
Запрос, которому пришлось лезть на диск и запрос, все данные для которого уже оказались в памяти - две огромные разницы даже для приличных SSD.