Předpokládám, že používáte InnoDB (Stejně byste měli....)
Přečtěte si tedy následující kapitolu z High performance MySQL 2ed, str. 117:http://books.google.com.hk/books?id=BL0NNoFPuAQC&lpg=PA117&ots=COPMB20 20index%20high%20performance%20mysql&pg=PA117#v=onepage&q&f=false
Obecně je UUID špatnou volbou z hlediska výkonu (kvůli shlukovanému indexu) a mají benchmark, který to dokazuje.