Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

B-Trees and Database Indexes

planetscale.com

Post reply on HN
Print view View original

71–80 of 84 posts

Re: B-Trees and Database Indexes

#71

Post by paperplatter »

Sophistifunk wrote: post #22
benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

It's very interesting to me that we have to keep telling people this, but it hasn't become part of the "hive folk knowledge" we all seem to develop. I think DB vendors have been sleeping on an opportunity to encourage better practices.

Because we keep telling people the opposite in academic settings, where the pkey is usually some actual data field(s) you expect to be unique. There's some point to teaching 3NF this way, but it shouldn't be taken literally.

Re: B-Trees and Database Indexes

#72

Post by paperplatter »

eurleif wrote: post #31
benwilber0 wrote: post #28

Earlier quoted context omitted.

Maybe? idk. Not in Postgres. The default index is a B-Tree. A hash-based index would be terrible for disk-seeking, in any case.

https://www.postgresql.org/docs/current/indexes-types.html#I...

Postgres has it, but it didn't used to, and it's still got caveats.

Beyond Postgres, indexing random values is fundamentally harder than indexing sorted ones, whether you've got a hashmap or btree or something else. The often-cited O(1) lookup complexity of a hashmap assumes everything easily fits in uniform-access memory.

Re: B-Trees and Database Indexes

#73

Post by erik_seaberg »

hobs wrote: post #51
paxys wrote: post #24

Earlier quoted context omitted.

DB vendors haven't done enough to offer ID generation as a core part of their system. Ideally "what ID do I use for this object" shouldn't even be a consideration, because of course the database should handle it. It is the system of record after all. Yet your options are pretty much limited to UUID or a basic incremental counter that fails to meet any real world production constraints.

Basic incremental counters work for most real world production constraints. Most people are not going to create tables with 4.2 billion rows, even with failed inserts. If you are doing that its an extreme of either very much you know what you are doing, or you very much do not; I have seen both in production.

A hundred inserts per second is going to hit 2^32 within a year and a half. I've seen that volume repeatedly. A colleague has seen this limit blow up prod. Do you really want to spend time on a project you're sure can never succeed to this extent?

Re: B-Trees and Database Indexes

#74

Post by hobs »

erik_seaberg wrote: post #73
hobs wrote: post #51

Earlier quoted context omitted.

Basic incremental counters work for most real world production constraints. Most people are not going to create tables with 4.2 billion rows, even with failed inserts. If you are doing that its an extreme of either very much you know what you are doing, or you very much do not; I have seen both in production.

A hundred inserts per second is going to hit 2^32 within a year and a half. I've seen that volume repeatedly. A colleague has seen this limit blow up prod. Do you really want to spend time on a project you're sure can never succeed to this extent?

Yep, seen it many times, and I cant tell you how many thousands of times I have seen tables with UUIDv4 primary keys for "future safety" that have 12 rows.

Converting int to bigint is not a big project, I have done more times than I can count just like any database evolution. I have also had customers say "oh, we'll just drop and recreate the table every year because its just some trash data." or "oh wait, we didnt mean to create 100 rows every second every day, that's a bug and costing us a lot of money for something we dont care about."

There's no one size fits all in databases, but most people who don't know better don't need to design a database for scale... because their choices won't work in the long term anyway.

Re: B-Trees and Database Indexes

#75

Post by hobs »

sgarland wrote: post #66
paxys wrote: post #53

Earlier quoted context omitted.

What if I have multiple partitions? Replication? What if I don't want business data to be exposed due to strictly incremental counters? What if I want unique IDs across different tables?

Partitions should not impact the use of an INT PK, except that you’ll need to include the partition key in the PK, e.g. (id, created_at) if partitioning by datetime. The displayed ordering without an explicit ORDER BY may not make sense, but to be fair, there are never any guarantees about implicit order. Replication should be fine, unless you mean active-active in which case I suggest a. not doing that b. using inte…

I could not have said it better myself. I would also add that I keep the slug just as an entirely separate column (or "user visible id") that they can change, had too many systems do things like "invoice id is auto generated" and then a customer coming back and saying "the invoice id has to be this or the auditors will scream!" - don't expose internals of your database to your users and you wont have a bad time.

Re: B-Trees and Database Indexes

#76

Post by erik_seaberg »

hobs wrote: post #74
erik_seaberg wrote: post #73

Earlier quoted context omitted.

A hundred inserts per second is going to hit 2^32 within a year and a half. I've seen that volume repeatedly. A colleague has seen this limit blow up prod. Do you really want to spend time on a project you're sure can never succeed to this extent?

Yep, seen it many times, and I cant tell you how many thousands of times I have seen tables with UUIDv4 primary keys for "future safety" that have 12 rows. Converting int to bigint is not a big project, I have done more times than I can count just like any database evolution. I have also had customers say "oh, we'll just drop and recreate the table every year because its just some trash data." or "oh wait, we didnt m…

That table is a self-limiting problem. It's true that failure is likely, but optimizing for that outcome never adds value, and it would probably make me quit.

Re: B-Trees and Database Indexes

#77

Post by franckpachot »

espadrine wrote: post #55
benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

> Use regular bigserial (64bit) PKs for internal table relations and UUIDs (128bit) for application-level identifiers and natural keys These recommendations are database-specific. It is definitely true of MySQL, since its row storage hinges on the primary key (and other indices yield that primary key). To have a hot page cache, you need to always add to the same page, so an incremented primary index is preferred. A U…

It depends on the use cases and performance goals. You may want to distribute the rows that you insert, and then a random UUID makes sense. However, it is too much distributed for B-Tree indexes and the problem is not only cache but the amount of modifications due to leaf block splits. This includes MySQL which stores the primary key in a B-Tree index. Other use cases may benefit from colocating the rows that are inserted together. Think of timeseries, or simply an order entry where you query the recent orders. A sequence makes sense there, to have a good correlation between the index (on time) and the primary key. This avoids too many random reads with low cache hits.

It is wrong to think that distributed databases do not need sequences. YugabyteDB allows it. With YugabyteDB you use hash sharding to distribute them to a small number of hash ranges, so that they don0t go all at the same place, but are not scattered across the whole database. CockroachDB and Spanner doesn't have hash sharding and that's why they do not recommend sequences. There are also use cases where range sharding on the sequence is good when you don't need to distribute the data ingest, but benefit from their colocation when querying.

Re: B-Trees and Database Indexes

#78

Post by cryptonector »

benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

Large keys are not a problem. See the SQLite3 docs about WITHOUT ROWID tables. Essentially any interesting multi-column key will be large, so don't worry about it. On the other hand, while INTEGER PRIMARY KEYs are nice and small, you end up with one extra index in SQLite3 if you have an integer key and also some other key that is really your primary key (or equivalently if you have the primary key you want and you didn't use WITHOUT ROWID).

A covering index always has large keys too.

In SQLite3 the trade-off made is that B-trees have either integer keys and arbitrary values, or arbitrary keys and integer values. When using WITHOUT ROWID the whole row is the key. (IIRC)

Re: B-Trees and Database Indexes

#79

Post by ssernikk »

zelphirkalt wrote: post #49
caseyohara wrote: post #10

Earlier quoted context omitted.

Do you have a recommendation for Wiki software you like to use? My team is in need of an internal knowledge base, and I like the structure of wikis. Most of the SaaS products I've tried or looked at are a bit too shiny/fancy and don't seem to match my mental model of how a wiki-style knowledge base should work.

My recommendation is, if you want a wiki for developers, use something that is based on a markup language, sources pages from a git repo, and does not do too much magic behind the scenes. This will result in a more maintained and liked wiki than any bloated SaaS wiki.

I like using Starlight for this purpose:

https://starlight.astro.build/

Re: B-Trees and Database Indexes

#80

Post by dspillett »

paperplatter wrote: post #69
dspillett wrote: post #43

Earlier quoted context omitted.

> Use regular bigserial (64bit) PKs for internal table relations and UUIDs (128bit) for application-level identifiers and natural keys. If you are worried about size ballooning, rather than the randomness, make sure you actually need more than 32-bit standard integers (well, 31-bit as they tend to be signed and we usually start from 0 or 1 not -2,147,483,648). Avoiding roll-over issues is sometimes a valid concern so…

It's not just about the data size. There are reasons your sequence can increment without a row actually being inserted.

Yep.

# Transactions that are explicitly rolled back, which have inserted to a table with an IDENTITY (or equivalent) column, almost always result in such a gap. Though if this is happening enough that it pushes the count up by an order of magnitude over time, you probably have a design problem…

# To reduce locking issues on the counter many DBs hold a cache of values (SQL Server allocates 1,000 at a time) in the persisted count so after a shutdown, especially an unclean shutdown, or a fail-over if using one of the clustering/mirroring/options options for HA, it is possible that most of these will be skipped. If this is happening enough to be a long-term problem than you have significant infrastructure issues. Such a cache could be per-thread/-process (IIRC it isn't in SQL Server) which is one of the reasons that IDENTITY column values can seem to be out-of-order in high concurrency environments (though you should never care about the actual order of values in such columns so that is a non-issue).

# In some DR processes where old DBs are restored, the values may be artificially updated after restore if used values might have been exposed to an external service (to avoid confusion caused is a number is used twice from the point of view of that external service). This is an extra argument against exposing internal ID values to external systems and in favour of having an additional UUID based identifier for such purposes.

# Also, though this is the most obvious one and hardly needs stating, deleted rows won't “return” their now unused number to be reused. You should scale the type based on rows expected to be inserted, not rows expected to be kept long-term.

If you are expecting hundreds of millions of rows in the lifetime of the table then a type larger than 32-bit is worth considering despite the extra storage needed in data and index pages. I'd not criticise considering it for tens of millions if you want to be more paranoid. Otherwise: 32-bit is very unlikely to not be fine, and 64-bit overkill.

Post reply on HN