El procedimiento almacenado mysql es 20 veces más lento que la consulta estándar

Solo una suposición:

Cuando ejecuta la consulta a mano, la expresión WHERE ('test' IS NULL or COL1 = 'test') se puede optimizar cuando se analiza la consulta. El analizador puede ver que la cadena 'test' no es nulo, por lo que convierte la prueba a WHERE COL1 = 'test' . Y si hay un índice en COL1 esto será usado.

Sin embargo, cuando crea un procedimiento almacenado, el análisis se produce cuando se crea el procedimiento. En ese momento, no sabe qué @param será, y tiene que implementar la consulta como un escaneo secuencial de la tabla.

Intente cambiar su procedimiento a:

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;

No tengo mucha experiencia con los procedimientos almacenados de MySQL, así que no estoy seguro de que sea la sintaxis correcta.