Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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

share|improve this question
'I know that having non-sequential IDs is bad for index performance' But how do you know that? At least for PostgreSQL I don't see why it would be so. – dezso Oct 17 '13 at 11:04
@deszo: I think that comes from the fact that PKs in MySQL are clustered indexes which don't work well with "random" values (the same is true for SQL Server) – a_horse_with_no_name Oct 17 '13 at 11:53
@a_horse_with_no_name Yeah, that's true, but here it says 'in sequential order' – dezso Oct 17 '13 at 13:28

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

share|improve this answer

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.

share|improve this answer

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 UUIDs are a somewhat slower than on int or bigint, because the are 16 bytes long (as opposed to 4 / 8 bytes).

Generally, having gaps in the numbering 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.