POSTGRESQL GAPS IN SEQUENCES

Preamble

Most database tables have a primary key that is a made-up number, and that number is usually made by a sequence. In a previous article, I went into some detail about automatically generated primary keys. You might be surprised to learn that these primary key sequences can occasionally have gaps in them.

This article demonstrates the unexpected fact that sequences can even jump backwards and explains the causes of sequence gaps. It also provides an example of how to construct a gapless sequence.

Gaps in sequences caused by rollback

Transactions in databases frequently behave atomically; when PostgreSQL rolls back a transaction, all of its effects are undone. The documentation explains that this isn’t the case for sequence values.

To avoid blocking concurrent transactions that obtain numbers from the same sequence, a nextval operation is never rolled back; that is, once a value has been fetched it is considered used and will not be returned again. This is true even if the surrounding transaction later aborts, or if the calling query ends up not using the value. For example an INSERT with an ON CONFLICT clause will compute the to-be-inserted tuple, including doing any required nextval calls, before detecting any conflict that would cause it to follow the ON CONFLICT rule instead. Such cases will leave unused “holes” in the sequence of assigned values.

How a gap forms in a sequence is shown in the example below:

FORM A TABLE be_positive (id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY, value integer CHECK (value > 0)); – The identity column is supported by the following sequence: SELECT pg_get_serial_sequence('be_positive', 'id'); pg_get_serial_sequence ════════════════════════════ laurenz.be_positive_id_seq (1 row) INSERT INTO be_positive (value) VALUES (42); INSERT 0 1 INSERT INTO be_positive (value) VALUES (-99); ERROR: new row for relation "be_positive" violates check constraint "be_positive_value_check" DETAIL: Failing row contains (2, -99). INSERT INTO be_positive (value) VALUES (314); INSERT 0 1 TABLE be_positive; id │ value ════╪═══════ 1 │ 42 3 │ 314 (2 rows)

The second statement was rolled back, but the sequence value 2 is not, forming a gap.

This intentional behavior is necessary for good performance. After all, a sequence should not be the bottleneck for a workload consisting of many INSERTs, so it has to perform well. Rolling back sequence values would reduce concurrency and complicate processing.

Gaps in sequences caused by caching

Despite Nextval’s low cost, a sequence could still be the bottleneck in a workload with lots of concurrent tasks. You can get around that by giving a series a cache clause greater than 1 when defining it. If that’s the case, the first call to nextval in a database session will get that many sequence values all at once. There is no need to read the sequence because subsequent calls to nextval use those cached values.

Due to the loss of these stored sequence values at the conclusion of the database session, gaps result.

 CREATE SEQUENCE seq CACHE 20; SELECT nextval('seq'); nextval ═════════ 1 (1 row) SELECT nextval('seq'); nextval ═════════ 2 (1 row)

The database session is now over, so start a new one.

 SELECT nextval('seq'); nextval ═════════ 21 (1 row)

Gaps in sequences caused by a crash

Changes to sequences are logged to WAL, just like changes to all other objects are, so that recovery can recover the state from a backup or after a crash. Since writing WAL impacts performance, not each call to nextval will log to WAL. Rather, the first call logs a value 32 numbers ahead of the current value, and the next 32 calls to nextval don’t log anything. This means that, after a crash, the sequence may have skipped some values.

To demonstrate, I’ll use a little PL/Python function that crashes the server by sending a KILL signal to the current process:

 CREATE FUNCTION seppuku() RETURNS void LANGUAGE plpython3u AS 'import os, signal os.kill(os.getpid(), signal.SIGKILL)';

Let’s observe this in action now:

 CREATE SEQUENCE seq; SELECT nextval('seq'); nextval ═════════ 1 (1 row) SELECT seppuku(); server closed the connection unexpectedly 	This probably means the server terminated abnormally 	before or while processing the request.

When we reconnect, we discover that some values are absent:

 SELECT nextval('seq'); nextval ═════════ 34 (1 row)

Sequences that jump backwards after a crash

It’s not widely known that sequences can advance backwards. If the WAL record that logs the progression of the sequence value has not yet been persistent to disk, a backwards jump may occur. Why? Because the transaction that contained the call to nextval has not yet committed:

 CREATE SEQUENCE seq; BEGIN; SELECT nextval('seq'); nextval ═════════ 1 (1 row) SELECT nextval('seq'); nextval ═════════ 2 (1 row) SELECT nextval('seq'); nextval ═════════ 3 (1 row) SELECT seppuku(); psql:seq.sql:9: server closed the connection unexpectedly 	This probably means the server terminated abnormally 	before or while processing the request.

Now reconnect and fetch the next sequence value:

 SELECT nextval('seq'); nextval ═════════ 1 (1 row)

Although it appears dangerous, there is no risk to the database because the transaction was rolled back along with any potential data modifications that used the “lost” sequence values because it did not commit.

You shouldn’t use sequence values from an uncommitted transaction outside of that transaction, though, which is an interesting conclusion to follow from that.

How to build a gapless sequence

First of all, be cautious before deciding to create a gapless sequence. All transactions that make use of that “sequence” will be serialized. Your ability to modify data will suffer greatly as a result.

A gapless sequence is almost never necessary. Most of the time, you can figure out the order of the rows by looking at the timestamp at the time each row was added. Then you can use therow_number window function to calculate the gapless ordering while you query the data:

 SELECT created_ts, value, row_number() OVER (ORDER BY created_ts) AS gapless_seq FROM mytable;

You can implement a truly gapless sequence using a “singleton” table:

 CREATE TABLE seq (id bigint NOT NULL); INSERT INTO seq (id) VALUES (0); CREATE FUNCTION next_val() RETURNS bigint LANGUAGE sql AS 'UPDATE seq SET id = id + 1 RETURNING id';

It is critical not to create an index on the table in order to receive HOT updates and keep the table from becoming bloated.

Calling thenext_val function will lock the table row until the end of the transaction,  so keep all transactions that use it short.

Conclusion

I’ve demonstrated numerous techniques for making a sequence skip values, occasionally even backwards. But if all you require are distinct primary key values, then that never becomes an issue.

Avoid attempting a “gapless sequence” if you can. You can get it, but a lot will depend on how well you perform.

About Enteros

​​​​Enteros offers a patented database performance management SaaS platform. It proactively identifies root causes of complex business-impacting database scalability and performance issues across a growing number of clouds, RDBMS, NoSQL, and machine learning database platforms.​