No-gap sequence in PostgreSQL and YugabyteDB
Tags: yugabytedb, postgres, distributed, sql
Published: 2023-08-24 14:49:47

**Sequences** are special **in a SQL database**, distributed or not. To be scalable, they **are not transactional** and, consequently, the result may show some **gaps** and **unpredictable ordering**.

## Non-transactional sequences

In PostgreSQL, I create a table where the `id` comes from a sequence:
```sql
create sequence my_sequence;
create table demo (
 primary key(id)
 , id bigint default nextval('my_sequence')
 , value text
);
```
I insert two rows, but with a failed attempt that was rolled back:
```sql
begin transaction;
insert into demo(value) values('one');
commit;
begin transaction;
insert into demo(value) values('two');
rollback;
begin transaction;
insert into demo(value) values('two');
commit;
```

The result has a gap:
```sql
postgres=# select * from demo order by id;

 id | value
----+-------
  1 | one
  3 | two
(2 rows)
```

This has nothing to do with ordering and cache and is because the sequence increment is not transactional and was not rolled back. Generally, it doesn't matter because sequences are used to generate a unique number and that works.

## Cached sequences

There's another reason for seeing gaps even when no transactions were rolled back. To avoid incrementing a single row each time we get the next value, a range of values is cached: 
```sql
alter sequence my_sequence cache 100;
```
PostgreSQL caches it per connection, and the range of value is lost if we reconnect:
```sql
insert into demo(value) values('three');
\connect
insert into demo(value) values('four');
insert into demo(value) values('five');
```
Here is the result
```sql
postgres=# select * from demo order by id;

 id  | value
-----+-------
   1 | one
   3 | two
   4 | three
 104 | four
 105 | five
(5 rows)
```

In **YugabyteDB**, the sequence can be cached on the tablet server and you may not see this gap when re-connecting. However, YugabyteDB is elastic and resilient by allowing nodes to be added or removed and this may also introduce a gap. Non cached sequences are not scalable and that why by default YugabyteDB sets a minimum cache (`--ysql_sequence_cache_minval=100`) that forces a minimum even if the CREATE SEQUENCE sets it lower.

This should not be a problem. SQL sequences are provided to generate unique values in a scalable way, and doing so by incrementing a number is an implementation detail. You should not expect expect anything else than a unique number from a sequence. If you do, you don't need a dedicated database object to do a simple transactional `udpate my_counter set my_value=my_value+1 returning val` on a row. 

## Re-numerotation after commit

If you generate a number for a sequence and need a no-gap numbering, you can do that after commit, with another column:
```sql
alter table demo add column num bigint;
create unique index demo_num on demo(num asc);
alter table demo add unique using index demo_num;
```

I run a job that adds the no-gap numbering for the rows that don't have a number yet in this column:
```sql
update demo 
 set num=new.num
 from (
  select id
   , coalesce( (select max(num) from demo) ,0)
     + row_number()over(order by id)
     as num
  from demo where num is null order by id
 ) new where demo.id=new.id
;
```
You can check the execution plan to be sure that it uses an Index Scan to get the `max(num)`. The result is:
```sql
postgres=# select * from demo order by num;
 id  | value | num
-----+-------+-----
   1 | one   |   1
   3 | two   |   2
   4 | three |   3
 104 | four  |   4
 105 | five  |   5
(5 rows)
```

This can be sufficient if you want a no-gap number before a specific point in time, like some end of month accounting. Be aware of the cost of this in PostgreSQL where updating a single column copies the whole row, with WAL, bloat, and need to vacuum consequences. YugabyteDB doesn't have those problems.

## Transaction ordering (external consistency)

The order in which transactions are committed is determined at commit time by the database. Two transactions may be committed in a different order than the `nextval()` execution inside them. To be scalable, the sequence value retrieval doesn't request a transaction lock. Without explicit locking, it's impossible to determine which transaction will commit first. The linear sequence of transactions is unknown before commit, where databases mark them with an internal clock (such as SCN in Oracle, LSN in PostgreSQL, HLC in YugabyteDB).

While this method allows database sequences to scale, it also means that the visible order of your transaction may differ from the sequence number that was retrieved. Ignoring this can cause problems in production, even if it isn't immediately apparent in unit tests. Any application that relies on the sequence order has a bug that will break your business logic on race conditions.

If sequence order is a requirement, a single counter must be used, and a single row table updated with an exclusive lock acquired until commit. A sequence is not needed for this. However, this will affect scalability, which is why SQL databases provide a special object with a non-transactional behavior for the specific use-case of generating unique numbers.

Here is an example where an application uses a sequence to check for new rows, incrementally, and relies on the last sequence number processed to get only the new rows since the last execution.

I delete previous rows and insert a single one. It has `id=204`:
```sql
postgres=# alter sequence my_sequence cache 1;
delete from demo;
ALTER SEQUENCE
postgres=# delete from demo;
DELETE 5
postgres=# insert into demo(value) values('six');
INSERT 0 1
postgres=# \! psql -c "select * from demo"
 id  | value | num
-----+-------+-----
 204 | six   |
(1 row)
```

The job that checks for new rows remembers this number and will get new rows with:
```sql
postgres=# \! psql -c "select * from demo where id > 204"
 id | value | num
----+-------+-----
(0 rows)
```

There is no new row yet. 

A transaction starts and inserts a new row. It has `id=205`:
```sql
postgres=# begin transaction;
BEGIN
postgres=*# insert into demo(value) values('seven') returning *;
 id  | value | num
-----+-------+-----
 205 | seven |
(1 row)

INSERT 0 1
```
In the meantime another transaction does the same. 
As there's no cache, the number follows with no gap, `id=206`:
```sql
postgres=*# \! psql -c "insert into demo(value) values('eight') returning *"
 id  | value | num
-----+-------+-----
 206 | eight |
(1 row)

INSERT 0 1
```
So, the users have seen the insertion of `id=205` and `id=206` with an impression of ordering.

My job queries for new rows since the last execution and finds only the committed one, as the other is not visible yet:
```sql
postgres=*# -- read only new records (last check was 204)
postgres=*# \! psql -c "select * from demo where id > 204"
 id  | value | num
-----+-------+-----
 206 | eight |
(1 row)
```
This job remembers `id=206` as the last value processed, to start the next incremental round from there.

I used `begin transaction` to reproduce the overlaping transactions but the same happens in autocommit in a shorter time. Now the transaction commits and the job runs again:
```sql
postgres=*# commit;
COMMIT

postgres=# -- read only new records (last check was 206)
postgres=# \! psql -c "select * from demo where id > 206"
 id | value | num
----+-------+-----
(0 rows)
```

The row with `id=205` is lost by this incremental job and will never be processed because it thinks that it has seen all rows before `id=206` but this is wrong:
```sql
postgres=# select * from demo;
 id  | value | num
-----+-------+-----
 204 | six   |
 205 | seven |
 206 | eight |
(3 rows)
```
The problem here is that `id=205` was generated, from the sequence, before `id=206` but, because of the ordering of concurrent transactions, it was visible after it. In the real order of the SQL transactions, `id=206` happened before `id=205`. You can't rely on sequences (or even timestamps) to know in which order the transactions happened, unless you control the order with transactional DML and pessimistic locking. 

## No-gap ordered sequence from a transactional SQL table

If you want an ordered no-gap sequence, you need to implement it yourself from a transactional table. With write locks, it will force the commit order. This is quite easy but you must accept that having multiple sessions asking for the next value for one sequence will have to queue to get their number and this will reach some scalability limits.

A simple way is implementing those in a table with a function to get the next value. Here is an example where I want a no-gap sequence starting at one each year, to generate invoice numbers:
```sql
create table next_invoice_number(
 year int primary key, num int default 1
);

create function next_invoice_number(year int) returns int as $$
  insert into next_invoice_number as tab (year)
  values(next_invoice_number.year)
  on conflict (year) do
  update set num=tab.num+1
  returning tab.num
  ;
$$ language sql;
```

The function will increment the value and return it. If there's no record yet for the year, a new one is created. 

This, with serializable isolation level, will generate no-gap numbers:

```sql
create table invoices (
 primary key(year, num) 
 , year int, num int
);

insert into invoices 
 select 2023, next_invoice_number(2023) 
 from generate_series(1,10)
 returning num
;
```

The result:
```sql
postgres=# select * from invoices order by num;
 year | num
------+-----
 2023 |   1
 2023 |   2
 2023 |   3
 2023 |   4
 2023 |   5
 2023 |   6
 2023 |   7
 2023 |   8
 2023 |   9
 2023 |  10
(10 rows)
```

# No-Gap and Scalability

With `pgbench`, I test the throughput when generating numbers from one session only:

```sql
\! pgbench -t 1000 -nf <(echo '
insert into invoices values (2023, next_invoice_number(2023) );
') -c 1 

pgbench (16beta2, server 15.1 (Debian 15.1-1.pgdg110+1))
transaction type: /dev/fd/63
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
maximum number of tries: 1
number of transactions per client: 1000
number of transactions actually processed: 1000/1000
number of failed transactions: 0 (0.000%)
latency average = 0.981 ms
initial connection time = 5.319 ms
tps = 1019.719332 (without initial connection time)
```

Now I can compare this 1019 transactions per second, at 1 millisecond latency, with a run with 10 concurrent threads:

```sql
\! pgbench -t 1000 -nf <(echo '
insert into invoices values (2023, next_invoice_number(2023) );
') -c 10

pgbench (16beta2, server 15.1 (Debian 15.1-1.pgdg110+1))
transaction type: /dev/fd/63
scaling factor: 1
query mode: simple
number of clients: 10
number of threads: 1
maximum number of tries: 1
number of transactions per client: 1000
number of transactions actually processed: 10000/10000
number of failed transactions: 0 (0.000%)
latency average = 14.528 ms
initial connection time = 53.172 ms
tps = 688.320969 (without initial connection time)
```

There is a trade-off here. If you need no-gap numbering, there's no other solution than having a single point of truth, locked exclusively until the end of the transaction, to generate the numbers.

Note that all those examples work the same in PostgreSQL and in YugabyteDB. I've created the unique constraint on `num` by creating the unique index beforehand so that I can precise ASC for range sharding. The default would have been HASH on YugabyteDB but there's a good chance that if you want a no-gap sequence you will also do some range queries on it.