Row identity and primary keys

Every row is named by a 48-bit integer key that is never changed and never handed to another row, except after an explicit PURGE.

Every row in KDBS has one permanent name: its primary key, a 48-bit integer stored in the first column. The key cannot be updated, and once a row with that key has committed, the key never names a different row. The one exception is an explicit PURGE. Because of this rule, indexes, Cabins and other structures can store a row’s key instead of its physical address, and an application can keep a key without worrying that it will later point at someone else’s row.

How it works

The Keystone word

Every row starts with a 64-bit word called the Keystone word. It holds the row’s identity:

 bits 0-47          48-55      56-63
+------------------+----------+----------+
| id (primary key) | flags    | reserved |
+------------------+----------+----------+
  1 .. 2^48 - 1      written 0  written 0

The id field is the primary key. It ranges from 1 to 2^48 − 1 (281,474,976,710,655). 0 means “unset”.
The key is stored only here. It is not stored a second time as an ordinary column.
The first column of every table must have an integer type. Its declared width is for display only: the key always lives in the 48-bit field.

Where a key comes from

Each INSERT row either names its key or leaves it out. The choice is made per row, not per table, and one statement can mix both:

Name the key. Give a value for every column. The first value is the key.
Leave it out. Give one value fewer. The engine issues a key.

INSERT INTO passengers VALUES (500, 'Seo Dahye', 1, '2022-04-05');      -- key 500, named
INSERT INTO passengers VALUES ('Moon Jaewon', 0, '2026-03-01');         -- key issued by the engine
INSERT INTO passengers VALUES (100, 'Baek Nari', 1, '2023-08-17');      -- a named key may sort below the mark

kdbs> INSERT INTO passengers VALUES (500, 'Seo Dahye', 1, '2022-04-05')
INSERTED oid=4005 id=500 page=133 slot=8
kdbs> INSERT INTO passengers VALUES ('Moon Jaewon', 0, '2026-03-01')
INSERTED oid=4005 id=501 page=133 slot=9
kdbs> INSERT INTO passengers VALUES (100, 'Baek Nari', 1, '2023-08-17')
INSERTED oid=4005 id=100 page=133 slot=8

Each table keeps a high-water mark, next_id. It is stored, never computed as max(id) + 1, so deleting the highest row does not make its key available for reissue. An issued key is the current mark. A named key at or above the mark moves the mark past it, which is why naming 500 and then omitting the key gave 501. A named key below the mark does not move it.

Issued keys ascend in the order they are issued, across all cores. Named keys carry no order: a named key may be any free key, in any order. The table’s B+ tree places each row where its key sorts.

When a key is refused

A named key is refused for exactly two reasons. In both cases nothing is written.

Reason	Error class	Example message
The key is already bound to a row, live or deleted	`AlreadyExists`	`duplicate primary key 100 already present at page 133 slot 8`
The key is outside `[1, 2^48 − 1]`	`OutOfRange`	`primary key 0 is outside the Keystone id space [1, 281474976710655]`

kdbs> INSERT INTO passengers VALUES (100, 'Oh Gaeun', 0, '2026-04-02')
                                     ^
ERR duplicate primary key 100 already present at page 133 slot 8 (byte 31)
kdbs> INSERT INTO passengers VALUES (281474976710656, 'Big', 0, '2026-04-02')
                                     ^
ERR primary key 281474976710656 is outside the Keystone id space [1, 281474976710655] (byte 31)

A row with the wrong number of values is refused with both accepted counts:

kdbs> INSERT INTO passengers VALUES (1, 2, 3, 4, 5)
ERR expected 4 value(s) including primary-key column 'id', or 3 to have it issued; got 5

The life of a key

 free ──INSERT──▶ placed, uncommitted ──COMMIT──▶ bound ──DELETE──▶ bound (deleted row)
  ▲                       │                                              │
  └──────ROLLBACK─────────┘                                              │
  ▲                                                                      │
  └─────────────────────────────PURGE (once no reader can see it)────────┘

Rolled back: the key is free again. Naming it a second time places it.
Committed: the key stays bound, even after DELETE. A DELETE only marks the row deleted; the row stays in place for older snapshots, and it holds its key.
Purged: PURGE removes deleted rows in a key range and frees their keys. After it, an INSERT that names the key places a new row.

kdbs> DELETE FROM passengers WHERE id = 100
DELETED 1
kdbs> INSERT INTO passengers VALUES (100, 'Baek Nari II', 1, '2023-08-17')
                                     ^
ERR duplicate primary key 100: a row with this key was deleted; PURGE frees its key (page 133 slot 8) (byte 31)
kdbs> PURGE FROM passengers WHERE id = 100
PURGED 1
kdbs> INSERT INTO passengers VALUES (100, 'Baek Nari II', 1, '2023-08-17')
INSERTED oid=4005 id=100 page=133 slot=9

The engine never issues a purged key by itself. Only an INSERT that names it takes it again.

The key cannot be updated

The key is the row’s identity, not one of its fields. An UPDATE that assigns it is refused when the statement is compiled, so nothing is written:

kdbs> UPDATE passengers SET id = 9 WHERE id = 1
                            ^
ERR primary-key column 'id' cannot be updated at byte 22; it is the tuple's identity, not a field of it

To give a row a new key, delete it and insert a new row.

What it guarantees

One key, one committed row. A key is bound to at most one committed row for the life of the table, except across a PURGE that freed it.
A stored key never points at the wrong row. A key kept elsewhere can dangle (its row was deleted), but it cannot name another committed row unless that key was purged and inserted again.
The issue cursor never goes back. next_id only rises, and an issued key is never issued twice.
Every reader re-checks. Indexes, Cabins and Waystone trails store keys. Each one compares a stored key against the row actually found, so a purged and re-inserted key reads as the new row.

What it costs

Keys are unique, not gapless. A failed insert can use up an issued key, and a caller may skip ranges. Nothing in the engine depends on keys being consecutive.
Deleted rows keep their keys and their space until PURGE runs. A key that was deleted cannot be named again before that.
Sparse named keys use the key budget faster. The budget is the key space (2^48 − 1 keys per table), not a row count. Naming key 1,000,000 moves the mark past every key below it.
No key changes. A row that needs a different key must be deleted and inserted again.
A purged key is a new identity. A system outside the engine that recorded a key must treat a purged and reused key as a different row. The purge is written to the log, which records when the key was freed.

How to observe it

DESCRIBE shows the mark (next_id), the keys used and the keys left. The key column reports autoincrement=if-omitted: the engine issues a key only when the INSERT leaves it out.

kdbs> DESCRIBE passengers
oid=4005 root_page_id=133 clustered_type=BTREE next_id=502 columns=4 ids_issued=501 ids_remaining=281474976710154 budget_used=0.000% height=1 leaves=1
pos=0 name=id type=int64 notnull=yes pk=yes autoincrement=if-omitted
pos=1 name=name type=varchar notnull=yes pk=no autoincrement=no cabin=auto
pos=2 name=member type=bool notnull=yes pk=no autoincrement=no cabin=auto
pos=3 name=joined_on type=date notnull=yes pk=no autoincrement=no cabin=auto

SHOW BUDGET lists key use for every table, with warnings as a table nears its limit:

kdbs> SHOW BUDGET
relations=14 warning=0 exhausted=0 capacity=281474976710655 warn_at=90.000%
...
rel=airlines issued=3 remaining=281474976710652 used=0.000% warn=no exhausted=no
rel=passengers issued=501 remaining=281474976710154 used=0.000% warn=no exhausted=no
rel=flights issued=4 remaining=281474976710651 used=0.000% warn=no exhausted=no
rel=tickets issued=9 remaining=281474976710646 used=0.000% warn=no exhausted=no

The INSERTED reply names the key and where the row was placed. The slot is the slot at placement; a later insert into the same page can move it.

Limitations

The key must be the first column, and an integer. There are no composite or text primary keys.
A named key must be an integer literal. A non-integer value is refused InvalidArgument.
An omitted key can be refused. If another session names the exact key the engine just issued, the engine draws again. After 8 such draws in a row the INSERT is refused AlreadyExists. This needs a client that names each next key as it is issued.
PURGE runs in autocommit only, on B+ tree tables only, and needs the admin role. It waits up to 1 second for older readers and is then refused with a retryable TXN_CONFLICT. See PURGE.
No engine-internal purge exists. Deleted rows are removed only by PURGE.
A known defect can refuse a named key AlreadyExists when one key is inserted, rolled back and named again about 600 times with the same indexed value and a new covered value. See Known gaps.