3

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 add_free_numbers(column)

Updates addressing some of the questions

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

6
  • How would you check "which sequence numbers are unused"? – ypercubeᵀᴹ Jun 15 at 12:11
  • @ypercubeᵀᴹ As long as the user can supply the currently used numbers to add_free_numbers then that function will reliably determine the unused numbers as described. For an identity column this is trivial, if the sequence is used in some other way e.g. outside the database it's up to the user to supply the used values. – sev Jun 15 at 12:15
  • It's not trivial at all but the comment space is too small for an answer. – ypercubeᵀᴹ Jun 15 at 12:56
  • @ypercubeᵀᴹ in that case I misunderstood the question and probably also problem. Is there another way other than the comments how you could tell me what the problem is? – sev Jun 15 at 12:59
  • 2
    If gaps in your sequences are a reason for you to move from int to bigint, then either you need to switch to bigint anyway, or you have a really very weird use of sequences that leaves to many gaps that it would make a difference to fill them. – jcaron Jun 15 at 19:39
4

The problem is that it is impossible to determine how and where the sequence is used. It doesn't have to be the DEFAULT clause of a column that owns the sequence: nextval could be called anywhere and used in creative ways, even outside the database.

Even if you consider only the case of an identity column, scanning the table for "missing values" would be quite expensive, and it is not clear how that should interact with MVCC.

Finally, most of the requests for gap-less sequences I see are asking for monotonically increasing values, which this solution would not provide.

2
  • (1)Why would it be a problem if nextval is called outside of the database? (2)I agree it would be an expensive action but performing it infrequently could be less expensive than switching to bigint. The interaction with MVCC would indeed be a problem. One could potentially implement it such that during the missing values update it defaults to always incrementing the counter - this would avoid conflicts. (3) Thats true, it would not give monotonically increasing values but could avoid having to move to bigint. – sev Jun 15 at 11:37
  • 1
    Ad 1: because then you cannot determine if a certain value was used or not. – Laurenz Albe Jun 15 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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