InnoDBを使用していると思います（とにかく...）
したがって、高性能MySQL 2ed、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
一般に、UUIDは（クラスター化されたインデックスのために）パフォーマンスの観点からは不適切な選択であり、これを証明するベンチマークがあります。