> However if you want any sort of efficient lookup on the external key (UUID), your database still needs an index on the UUID, and you are back at square one Y

> However if you want any sort of efficient lookup on the external key (UUID), your database still needs an index on the UUID, and you are back at square one Yes and no. It depends on whether your database treats primary keys differently than other indexes. For example, in InnoDB primary keys are always clustered indexes: the row data is directly stored in a btree arranged by the PK; secondary indexes just store PK values in their leaf nodes, so that they can do a lookup on the clustered index. As a result, in InnoDB smaller PKs are preferable. So performance is generally better when using an incremental ID as PK and then UUID as a secondary index, as opposed to the reverse. Assuming you have multiple secondary indexes, the total table size will also be smaller in InnoDB with integer PK than with UUID PK.