MySQL è multithreaded il problema è che le singole query non vengono spezzate ma eseguite da un singolo thread, morale della favola, devi cambiare le query per farle andare più veloci (o fare caching aggressivo in RAM), una alternativa è usare librerie come questa per gestire query parallele: http://code.google.com/p/shard-query/