MySQL queries are 10 to 100 times slower after OS reboot
When you reboot the OS you remove all of the disk reads that have previously put into operating system disk cache (RAM). Once you've rebooted, the operating system will have to read the MySQL data from disk, which is several orders of magnitude slower than reading from cache (RAM). 

Optimise "fixes" this as it causes MySQL to read all of the table data from disk, enabling the OS to cache the data.

Linux uses most free RAM as disk cache. You can see this using the free command:

[oracle@ora12c1 ~]$ free
             total       used       free     shared    buffers     cached
Mem:       4050844     840072    3210772          0      97268     349716
-/+ buffers/cache:     393088    3657756
Swap:      4063228          0    4063228
[oracle@ora12c1 ~]$ 


Restarting MySQL has no affect on this cache, as it is the operating system that has cached the data, not MySQL.

To "fix" your problem you'll have to force the OS to read the data from disk so that it will cache it. You can use the Unix dd tool to do this. For example:

dd if=/var/mysql/data/mytable.idb of=/dev/null




Tip: you can verify how much of a given file is in the disk cache with the vmtouch command. That command can also purge the file out of the filesystem cache, or force loading the file into the filesystem cache. See http://hoytech.com/vmtouch/