La procedura memorizzata mysql è 20 volte più lenta della query standard

Solo un'ipotesi:

Quando esegui manualmente la query, l'espressione WHERE ('test' IS NULL or COL1 = 'test') può essere ottimizzato durante l'analisi della query. Il parser può vedere che la stringa 'test' non è null, quindi converte il test in WHERE COL1 = 'test' . E se c'è un indice su COL1 questo verrà utilizzato.

Tuttavia, quando si crea una stored procedure, l'analisi si verifica quando viene creata la procedura. In quel momento, non sa cosa @param sarà e deve implementare la query come scansione sequenziale della tabella.

Prova a modificare la tua procedura in:

IF @param IS NULL
THEN BEGIN
  SELECT * FROM table1
  UNION ALL
  SELECT * FROM table2
  ...
END;
ELSE BEGIN
  SELECT * FROM table1 WHERE col1 = @param
  UNION ALL
  SELECT * FROM table2 WHERE col1 = @param
  ...
END;
END IF;

Non ho molta esperienza con le stored procedure MySQL, quindi non sono sicuro che sia tutta la sintassi corretta.