No Gap Ordered Numbering in SQL: A Unique Index to Serialize In Read Committed

If you require a no-gap numbering system, using a sequence is not an option (see reasons here). Instead, you can utilize a table with fixed rows that you manually update. However, let's consider a scenario where you cannot have fixed rows and need to read the last value from the table in order to calculate the next number.

Which isolation level do you think you need? You must be sure that the max() you have read stays the same until you commit the max()+1 insert. This usually requires a serializable isolation level to order the transactions one after the other. You don't want a phantom read to appear once you have calculated the next value.

I have previously discussed how an index can enhance the performance under a serializable isolation level. Here, I will create an index to achieve serialization without using the serializable isolation level.

Here is a simple table:

create table demo (
 primary key(id)
 , id int generated always as identity
 , type varchar(10)
 , num int
 , unique(type, num)
);

My business rule states that each "type" is assigned a number, starting from one for the first row with this type and increasing in the order in which they were committed without allowing any gaps.

The following query can do that:

explain
insert into demo(type,num)
  select type, nextnum from (
   select 'x' type , coalesce(max(num),0)+1 as nextnum
   from demo
   where type='x'
) next
;

In a Serializable isolation level, the SELECT acquires a lock to declare the read intent so that a write can detect a conflict between the read and write state. In PostgreSQL, it is a predicate lock, and in YugabyteDB, a lock on a key range. As I exposed in the previous posts of this series, an index can improve this to avoid lock escalation to the whole table. As, here, I have defined a unique constraint, it has created an index. The same index is also used to get the last value quickly, as it is always at the end of the index.

Without a unique index, an isolation level lower than Serializable would not be able to detect the conflict when two transactions read the same last value simultaneously and then attempt to insert that same value. This situation could lead to duplicate entries. However, at the serializable isolation level, such anomalies would be detected due to the read-write conflict, preventing duplicates from occurring.

As the index is unique, the write-write conflict when two sessions try to insert the same value avoids such an anomaly. For this reason, our logic can work in the Reading Committed isolation level.

Keep in mind that SQL isolation levels were established without considering Multi-Version Concurrency Control (MVCC) reads, explicit locks, or indexes, as these elements are not included in the SQL standard. To achieve efficient and consistent concurrency control, it is essential to understand how your database works and acquires locks. This is also the reason why YugabyteDB is runtime-compatible with PostgreSQL, ensuring similar behavior. Just having wire protocol and dialect compatibility is not enough to successfully migrate applications between PostgreSQL-compatible databases.