Calculate next Primary Key - of specific format

Question

I have a table which holds a list of IDs, and various other columns such as IDName.

The Primary Key of the table is the ID itself, however it does not auto_increment. So, I want to be able to generate / calculate the next primary key, however there is a twist:

The primary key should be in a specific format, i.e. the 8 digit ID is made up of three parts:
<the level><a code><a sequence #>, e.g. <2><777><0123> = 27770123

So, when I am creating a new ID for the table, I want the next sequence number for a specific level and code. E.g. following the example above I might want to know the next sequence number for level 2 with code 777, the result should be an ID 27770124 (0124 being the next in the sequence).

Any help would be much appreciated.

Answer 1

Unless your application is in very high demand the number of collisions will be very low. So I would simply retry if a key error is raised.

select coalesce(max(id), 27770000) + 1
from myTable
where id / 10000 = 2777

The coalesce is there in case that level/code does not yet exist.

Answer 2

This looks like a variant of the gapless sequence problem; also seen here.

Gapless sequences have serious performance and concurrency problems.

Think very hard about what will happen when multiple inserts happen at once. You have to be prepared to retry failed inserts, or LOCK TABLE myTable IN EXCLUSIVE MODE before the INSERT so only one INSERT can be in flight at a time.

Use a sequence table with row locking

What I'd do in this situation is:

CREATE TABLE sequence_numbers(
    level integer,
    code integer,
    next_value integer DEFAULT 0 NOT NULL,
    PRIMARY KEY (level,code),
    CONSTRAINT level_must_be_one_digit CHECK (level BETWEEN 0 AND 9),
    CONSTRAINT code_must_be_three_digits CHECK (code BETWEEN 0 AND 999),
    CONSTRAINT value_must_be_four_digits CHECK (next_value BETWEEN 0 AND 9999)
);

INSERT INTO sequence_numbers(level,code) VALUES (2,777);

CREATE OR REPLACE FUNCTION get_next_seqno(level integer, code integer)
RETURNS integer LANGUAGE 'SQL' AS $$
    UPDATE sequence_numbers 
    SET next_value = next_value + 1
    WHERE level = $1 AND code = $2
    RETURNING (to_char(level,'FM9')||to_char(code,'FM000')||to_char(next_value,'FM0000'))::integer;
$$;

then to get an ID:

INSERT INTO myTable (sequence_number, blah)
VALUES (get_next_seqno(2,777), blah);

This approach means that only one transaction can ever be inserting a row with any given (level,mode) pair at a time, but I think it's race-free.

Beware of deadlocks

There's still a problem where two concurrent transactions can deadlock if they try to insert rows in a different order. There's no easy fix for this; you have to either order your inserts so that you always insert low level and mode before high, do one insert per transaction, or live with deadlocks and retry. Personally I'd do the latter.

Example of the problem, with two psql sessions. Setup is:

CREATE TABLE myTable(seq_no integer primary key);
INSERT INTO sequence_numbers VALUES (1,666)

then in two sessions:

SESSION 1                       SESSION 2

BEGIN;
                                BEGIN;

INSERT INTO myTable(seq_no)
VALUES(get_next_seqno(2,777));
                                INSERT INTO myTable(seq_no)
                                VALUES(get_next_seqno(1,666));

                                INSERT INTO myTable(seq_no)
                                VALUES(get_next_seqno(2,777));

INSERT INTO myTable(seq_no)
VALUES(get_next_seqno(1,666));

You'll notice that the second insert in session 2 will hang without returning, because it's waiting on a lock held by session 1. When session 1 goes on to try to get a lock held by session 2 in its second insert, it too will hang. No progress can be made, so after a second or two PostgreSQL will detect the deadlock and abort one of the transactions, allowing the other to proceed:

ERROR:  deadlock detected
DETAIL:  Process 16723 waits for ShareLock on transaction 40450; blocked by process 18632.
Process 18632 waits for ShareLock on transaction 40449; blocked by process 16723.
HINT:  See server log for query details.
CONTEXT:  SQL function "get_next_seqno" statement 1

Your code must either be prepared to handle this and retry the whole transaction, or it must avoid the deadlock using a single-insert transactions or careful ordering.

Automatically creating non-existent (level,code) pairs

BTW, if you want (level,code) combinations that don't already exist in the sequence_numbers table to be created on first use, that's surprisingly complicated to get right as it's a variant of the upsert problem. I'd personally modify get_next_seqno to look like this:

CREATE OR REPLACE FUNCTION get_next_seqno(level integer, code integer)
RETURNS integer LANGUAGE 'SQL' AS $$

    -- add a (level,code) pair if it isn't present.
    -- Racey, can fail, so you have to be prepared to retry
    INSERT INTO sequence_numbers (level,code)
    SELECT $1, $2
    WHERE NOT EXISTS (SELECT 1 FROM sequence_numbers WHERE level = $1 AND code = $2);

    UPDATE sequence_numbers 
    SET next_value = next_value + 1
    WHERE level = $1 AND code = $2
    RETURNING (to_char(level,'FM9')||to_char(code,'FM000')||to_char(next_value,'FM0000'))::integer;

$$;

This code can fail, so you always have to be prepared to retry transactions. As that depesz article explains, more robust approaches are possible but usually not worth it. As written above, if two transactions concurrently try to add the same new (level,code) pair, one will fail with:

ERROR:  duplicate key value violates unique constraint "sequence_numbers_pkey"
DETAIL:  Key (level, code)=(0, 555) already exists.
CONTEXT:  SQL function "get_next_seqno" statement 1

Answer 3

Ok, so far I've come up with, I think this will meet my requirements (unless there are any suggestions about a more optimal way to do it?)

SELECT ID 
FROM myTable 
WHERE ID > 27770000 
  AND ID < 27780000 
ORDER BY ID DESC 
LIMIT 1