Eu proponho uma maneira mais rápida.

Obtenha a contagem de linhas:

SELECT CEIL(COUNT(*)/2) FROM data;

Em seguida, pegue o valor do meio em uma subconsulta classificada:

SELECT max(val) FROM (SELECT val FROM data ORDER BY val limit @middlevalue) x;

Eu testei isso com um conjunto de dados 5x10e6 de números aleatórios e ele encontrará a mediana em menos de 10 segundos.

Isso encontrará um percentil arbitrário substituindo o COUNT(*)/2 com COUNT(*)*n onde n é o percentil (0,5 para mediana, 0,75 para 75º percentil, etc).