In PostgreSQL sequences are designed to have gaps for reasons mentioned in this post https://stackoverflow.com/questions/9984196/postgresql-gapless-sequences. My question is: could sequences not be made to be nearly gap-less by periodically (let's say once a day) checking which sequence numbers are unused and adding those back to the sequence to use?
I assume that currently postgres implements a sequence as a counter which it increments every time it's accessed. Instead it could be implemented with a list of free values & a counter. The sequence would then work as follows:
# python style pseudo code class Sequence: def __init__(self): self.free_numbers_set =  self.counter = 0 def get_next_sequence_value(self): if not isempty(self.free_numbers_set): id = self.free_numbers_set.pop(0) else: id = self.counter id ++ return id def add_free_numbers(self, column): for i in range(0:self.counter): if not i in column: free_numbers_set.append(i) free_numbers_set.sort()
Everytime we need a new id we run
get_next_sequence_value() and periodically we run
Updates addressing some of the questions
- For identity columns, getting the currently used values would be trivial. In other cases it would be up to the user to supply a list of values which are already in use.
- The interaction with MVCC would need to be thought about. One could potentially implement it such that during the missing values update, the sequence would default to only incrementing the counter - this would avoid conflicts.
I believe this solution could provide less sparse sequences which would allow users to use smaller id types (int vs bigint) while being backwards compatible with the current implementation.