6 ms·

Instead of doing random bytes, you can also just use a 64 or 128 bit permutation ("block cipher") on standard primary keys, which doesn't rip and tear your indi

Instead of doing random bytes, you can also just use a 64 or 128 bit permutation ("block cipher") on standard primary keys, which doesn't rip and tear your indices.

pestaa 6y ago
So using random GUIDs is equally harmful to indices? And how so?
- larzang 6y ago
  Postgres stores records by primary id sequence. If you have completely random IDs, records inserted at the same time are fragmented across the entire set, which makes accessing them slower if they're meant to be sequential. Whether this matters entirely depends on the type of data you're storing. If you're storing unrelated data which is always random access anyway, non-sequential ids don't really matter. If you're storing related data which is mostly accessed sequentially, e.g. Impressions filtered by a creation date range, it's definitely better to have sequential ids for non-fragmented storage. UUIDv6 isn't as commonplace in libraries as v1 or v4 but offers a good compromise for this.
  - kevincox 6y ago
    Note that this can actually be beneficial if you are sharding the table as now new inserts will be put on different shards. (Of course ideally you would be inserting sequentially but on different shards)
  - wiredfool 6y ago
    No, Mysql does. Postgres doesn't. (edit, at least, some common mysql table types do) (further edit -- You don't actually need a primary key in postgres. You might want one, and depending on how you do it, it's generally good design, but there's no actual requirement for them.)
  - jeltz 6y ago
    No, I do not think this is a good explanation. What you describe is how InnoDB works. PostgreSQL stores the actual records separately from the primary key index so the actual records won't fragment but the primary key index will. The records themselves will roughly be stored in insertion order. A random primary key in PostgreSQL mainly means that inserts into the primary key index will be more expensive and that it will bloat the primary key index to some extent.
- jeltz 6y ago
  Because inserting at the end of a btree (the data structured used by most databases for indexes) is much cheaper than doing random inserts, and as a bonus inserting at the end does not create index bloat since you can mostly avoid page splits. So you will get faster inserts and smaller indexes.
  - dtech 6y ago
    But is there an alternative if you need these hard-to-guess public identifiers? They will always have some randomness and you'll need to index them so it seems unavoidable.
    - rstarast 6y ago
      Use integers as primary keys and don't expose them, and add a (unique) random ID column that's used to interface with the rest of the world. (I understand there'll still be an index for the public key -- the argument would be that you don't bear the cost for that for most queries.)
      - rstarast 6y ago
        This stackoverflow answer to a related question gives a better suggestion https://stackoverflow.com/a/6955055/3403369 https://stackoverflow.com/a/6955055/3403369: Create a separate table mapping integers to unique IDs, and join with this. You can generate that in advance, so can avoid gradually building the index.
      - dtech 6y ago
        > the argument would be that you don't bear the cost for that for most queries Your INSERT becomes even more expensive because you have 2 update 2 indexes, and your lookup doesn't change. I get the benefit if you use the id as a FK or if the database must have data on disk in PK order like MySQL or MSSQL (?). On PostgreSQL if you just insert & read on that key only it seems objectively worse.
    - opmac 6y ago
      Encrypt them on the backend before exposing them to the public. Decrypt in the backed on access. See https://hashids.org/ https://hashids.org/
- tehlike 6y ago
  See this: https://nhibernate.info/blog/2009/03/19/nhibernate-poid-generators-revealed.html https://nhibernate.info/blog/2009/03/19/nhibernate-poid-gene...
dtech 6y ago
Won't the resulting data look random too? In that case I see little benefit of your approach over an UUID as a PK or using a sequential integer as a PK and adding a UUID field with a btree index.
- dasyatidprime 6y ago
  You don't store the scrambled key, you store the sequential-looking key and expose the scrambled key externally. That avoids things like easy key-sequence probing/inference from the outside, but means you don't take the hit of an index with random-looking keys. I've done something similar for weakly-secured spendable tokens in the past, packing some orderly lookup state into 64 bits and then exposing the Speck64/32. That application was actually backed by an object-array sort of storage with numeric indices, so I stored something like object ID, timestamp, and sequence number, and then looked up the right property on the object at validation time. (If I needed strongly-in-the-crypto-sense unguessable IDs for security, I wouldn't do this without doing more research/analysis, since a database-wide key feels like it could be a weak point; compare how peppering is used for password storage in conjunction with salting but not as a replacement. Someone else probably already knows that answer.) (Edit to add cross-reference: ah, looks like tmpyt in another comment claims that YouTube used to do this but then switched away because of the “knowing the small key lets you enumerate everything” loophole.)
  - dasyatidprime 6y ago
    Second additional thought: if you need strong unguessability, you could probably tack it onto that scheme by adding a second column that isn't indexed, but only used as a bearer-token-like add-on to the ID. So the index lookup only happens on the (unscrambled) first part, but the access is aborted if the second part doesn't match.

Instead of doing random bytes, you can also just use a 64 or 128 bit permutation ("block cipher") on standard primary keys, which doesn't rip and tear your indices.

pestaa 6y ago

So using random GUIDs is equally harmful to indices? And how so?

larzang 6y ago
Postgres stores records by primary id sequence. If you have completely random IDs, records inserted at the same time are fragmented across the entire set, which makes accessing them slower if they're meant to be sequential. Whether this matters entirely depends on the type of data you're storing. If you're storing unrelated data which is always random access anyway, non-sequential ids don't really matter. If you're storing related data which is mostly accessed sequentially, e.g. Impressions filtered by a creation date range, it's definitely better to have sequential ids for non-fragmented storage. UUIDv6 isn't as commonplace in libraries as v1 or v4 but offers a good compromise for this.
- kevincox 6y ago
  Note that this can actually be beneficial if you are sharding the table as now new inserts will be put on different shards. (Of course ideally you would be inserting sequentially but on different shards)
- wiredfool 6y ago
  No, Mysql does. Postgres doesn't. (edit, at least, some common mysql table types do) (further edit -- You don't actually need a primary key in postgres. You might want one, and depending on how you do it, it's generally good design, but there's no actual requirement for them.)
- jeltz 6y ago
  No, I do not think this is a good explanation. What you describe is how InnoDB works. PostgreSQL stores the actual records separately from the primary key index so the actual records won't fragment but the primary key index will. The records themselves will roughly be stored in insertion order. A random primary key in PostgreSQL mainly means that inserts into the primary key index will be more expensive and that it will bloat the primary key index to some extent.
jeltz 6y ago
Because inserting at the end of a btree (the data structured used by most databases for indexes) is much cheaper than doing random inserts, and as a bonus inserting at the end does not create index bloat since you can mostly avoid page splits. So you will get faster inserts and smaller indexes.
- dtech 6y ago
  But is there an alternative if you need these hard-to-guess public identifiers? They will always have some randomness and you'll need to index them so it seems unavoidable.
  - rstarast 6y ago
    Use integers as primary keys and don't expose them, and add a (unique) random ID column that's used to interface with the rest of the world. (I understand there'll still be an index for the public key -- the argument would be that you don't bear the cost for that for most queries.)
    - rstarast 6y ago
      This stackoverflow answer to a related question gives a better suggestion https://stackoverflow.com/a/6955055/3403369 https://stackoverflow.com/a/6955055/3403369: Create a separate table mapping integers to unique IDs, and join with this. You can generate that in advance, so can avoid gradually building the index.
    - dtech 6y ago
      > the argument would be that you don't bear the cost for that for most queries Your INSERT becomes even more expensive because you have 2 update 2 indexes, and your lookup doesn't change. I get the benefit if you use the id as a FK or if the database must have data on disk in PK order like MySQL or MSSQL (?). On PostgreSQL if you just insert & read on that key only it seems objectively worse.
  - opmac 6y ago
    Encrypt them on the backend before exposing them to the public. Decrypt in the backed on access. See https://hashids.org/ https://hashids.org/
tehlike 6y ago
See this: https://nhibernate.info/blog/2009/03/19/nhibernate-poid-generators-revealed.html https://nhibernate.info/blog/2009/03/19/nhibernate-poid-gene...

dtech 6y ago

Won't the resulting data look random too? In that case I see little benefit of your approach over an UUID as a PK or using a sequential integer as a PK and adding a UUID field with a btree index.

dasyatidprime 6y ago
You don't store the scrambled key, you store the sequential-looking key and expose the scrambled key externally. That avoids things like easy key-sequence probing/inference from the outside, but means you don't take the hit of an index with random-looking keys. I've done something similar for weakly-secured spendable tokens in the past, packing some orderly lookup state into 64 bits and then exposing the Speck64/32. That application was actually backed by an object-array sort of storage with numeric indices, so I stored something like object ID, timestamp, and sequence number, and then looked up the right property on the object at validation time. (If I needed strongly-in-the-crypto-sense unguessable IDs for security, I wouldn't do this without doing more research/analysis, since a database-wide key feels like it could be a weak point; compare how peppering is used for password storage in conjunction with salting but not as a replacement. Someone else probably already knows that answer.) (Edit to add cross-reference: ah, looks like tmpyt in another comment claims that YouTube used to do this but then switched away because of the “knowing the small key lets you enumerate everything” loophole.)
- dasyatidprime 6y ago
  Second additional thought: if you need strong unguessability, you could probably tack it onto that scheme by adding a second column that isn't indexed, but only used as a bearer-token-like add-on to the ID. So the index lookup only happens on the (unscrambled) first part, but the access is aborted if the second part doesn't match.