Tente alterar seu regexp string para "^asdf_[0-9]+" .

LIKE está ancorado (ie LIKE 'asdf_%' diz "uma string começando com asdf_"), enquanto REGEXP não é (REGEXP 'asdf_[0-9]+' procura por isso em qualquer lugar dentro da string).

Observe que fazer REGEXP 'asdf_[0-9]+' é como dizer LIKE '%asdf_%' .

Acho que REGEXP ainda será um pouco mais lento que LIKE , mas esperamos que o início da âncora de linha acelere bastante.