4 ms·

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

by pestaa 6y ago

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...

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

by pestaa 6y ago

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

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...