Suggestion for nearly gap-less sequences in postgres

Question

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.

Answer 1

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.