MySQL кеширует запросы даже при выключенном кешировании?

Есть монстроидальный запрос. В первый раз он отрабатывает довольно долго (порядка 20-30 секунд). В последующие разы время его выполнения значительно сокращается (до 1-2 секунд).
Логично предположить, что это кеш, но даже при использовании MYSQL_NO_CACHE и при установке query_cache_type в OFF все повторяется.

Что это может быть и как от этого избавиться?

(Отключить кеш необходимо для того, чтобы видеть результаты оптимизации)