Performance of primary key IDs with gaps (but in sequential order)

Question

I know that having non-sequential IDs is bad for index performance. But assuming all my IDs are created in correct order, but with large gaps: i.e:

154300000
283700000
351300000
464200000

...will the performance be any worse than having gapless auto_increment IDs?

I'll be using MySQL, or perhaps PostgreSQL. The gaps between the IDs would not be even. They'll be BIGINTs with a unix timestamp at the start (left side) of the number, and the rest of the numbers mostly being random, as discussed in another question I asked here:

https://stackoverflow.com/questions/6338956/mysql-primary-keys-uuid-guid-vs-bigint-timestamprandom/6339581

Answer 1

Non-sequential columns as clustered keys can be a problem, particularly if they are pretty random like most UUID generators output, but there problem is the randomness not the gaps. Inserting a value in the middle of existing ones has a chance of causing page splits but inserting a key that is more than one above the largest is no more likely to than inserting the next value would.

As an aside, some UUID generators output relatively sequential values. These are intended for when you have such a column as a significant member in a clustered key or other clustered index.

If you have not done any reading around creating and maintaining balanced tree structures and you have some free time, I recommend finding a half decent chapter on that short of thing (probably something aimed at the level of a year 1 computer science student) - it'll help you understand what work databases do to manage your structures so you can have a better feel for what will help and what will hinder (and what will make little difference either way).

Answer 2

As far as PostgreSQL is concerned, your assumption

having non-sequential IDs is bad for index performance

is generally not true. There are special use cases, where sequential numbers help somewhat, but not with index performance. In normal operation it does not make any difference whatsoever.

Operations on UUID values are a somewhat slower than on int / bigint, because the are 16 bytes wide (as opposed to 4 / 8 bytes).

Generally, having gaps in sequential ID numbers is the rule, not the exception.

For your special case, if you have a small number of instances and control over them, you could set aside separate ranges of a bigint or even just int: sequences with pre-set START value, for instance. Since you don't have mass inserts, there should be plenty of numbers.

For more instances or if you don't have control, I would strongly advice to use UUID instead of any home-grown solution. It's an established, well-tested technique and performs well.

Answer 3

For (normal, relational) database indexes - then I cannot see that it should matter much you have gaps.

As you touch upon yourself, the issue with non-sequential IDs is if they come out of order, increasing index maintenance with writes, such as GUIDs for example.

Where one might address your keys is the size in space vs. what a smaller identity will use, but gap vs. no gap - then I'd say that it shouldn't matter much.