If you want UUIDs to double as a nonce (I use them this way), then you will need to use v4 UUIDs and yes, they are basically impossible to index because they should be normally distributed across a very large range of possibilities.

If you want incrementing UUIDs, use v1 UUIDs, which are based MAC address + a timestamp. These change in a predictable way and are more indexable.