I've yet to see anyone mention storing UUIDs in a BINARY(16) column. Use exactly 128 bits to store 128 bits. We'd still have the random sort problem though.