Depending on caching strategy, using random UUIDs also decreases the maximum working set size before you become I/O bound by a huge factor. Postgres e.g. relies heavily on the O/S block cache and is subject to this.