Suppongo che tu stia usando InnoDB (dovresti comunque....)
Quindi leggi il capitolo seguente di MySQL 2ed ad alte prestazioni, p.117:http://books.google.com.hk/books?id=BL0NNoFPuAQC&lpg=PA117&ots=COPMBsvA7V&dq=uuid%20innodb%20clustered% 20index%20high%20performance%20mysql&pg=PA117#v=onepage&q&f=false
In generale, UUID è una scelta sbagliata dal punto di vista delle prestazioni (a causa dell'indice cluster) e hanno un benchmark per dimostrarlo.