droidPart 6 · Indexes and the Optimizer

Indexes and the Optimizer · Stage 5

UNIQUE

Add unique indexes, by CREATE UNIQUE INDEX or by UNIQUE in a column of CREATE TABLE, that refuse an INSERT or UPDATE giving a row another row's value, compare values only, let NULLs repeat, and refuse to be built over values that already repeat.

Not run yet · 8 tests

Why this stage exists

The primary key already refuses a duplicate: the table's tree cannot hold two cells with one key. Many columns need the same promise without being the key: an email address, a username, an order number from another system. Checking for them with a full scan before every INSERT would turn each insert into a read of the whole table.

An index makes the check cheap. Equal values sit side by side in it, so "is this value already here?" is one seek. That is all a UNIQUE constraint is in this engine, and in most others: an index that refuses a second entry with the same value.

Compare the value, not the entry

The entries of section 54 are built to be unique already: value, then table key. That is exactly why the unique check must not compare whole entries. ('a@x', 1) and ('a@x', 7) are different entries, and the tree would happily hold both. The constraint is about the value alone:

Unique index on email: ('a@x',1) ('b@x',2)

header

cells = 2

cell 0

key = 1

cell 1

key = 2

free space

insert ('a@x', 7): seek 'a@x', find ('a@x',1), another row: 01605

header

cells = 2

cell 0

key = 1

updated

cell 1

key = 2

free space

Each cell is 10 bytes. A cell that moves one position moves by 10 bytes.

Cells labelled by their table key. The seek ignores the table key: it lands on the first entry with the value, and any entry there that is not the row's own is a conflict.

For an UPDATE, the one entry with the value that is allowed is the row's own: update u set email = 'a@x' where id = 1 on row 1 changes nothing and must not fail.

NULL is not a value to collide with

NULL means "unknown", and two unknowns are not known to be equal. SQL takes that literally here: a unique column may hold NULL in any number of rows. The NULL entries are still in the index (they sort first), the check just skips them.

Order, failure and transactions

The check is something only writing can find, like a duplicate primary key, so it runs after every other check: for an INSERT, the key (00701) first, then each unique index in the order they were created. When it fails, the statement fails as a whole, and the rules you already have take back anything it wrote. Inside a transaction, only that statement fails; the ones around it stay.

An UPDATE of many rows checks each row as it changes it. With unique values 1 and 2, update u set n = 2 changes row 1 first, finds row 2 already holding 2, and fails: 01605, and the statement changes nothing. Checking each row as it changes is also why, in engines whose SET takes expressions, set n = n + 1 over 1 and 2 can fail even though its final result would be fine. Some engines can defer the check to the end of the statement or the transaction; this one does not.

Building over existing duplicates

CREATE UNIQUE INDEX on a column whose values already repeat cannot succeed: the constraint would be false the moment it existed. Build the entries as for any index; equal values end up next to each other, so a pass over neighbours finds any repeat. Then the statement is 01606, and it leaves nothing behind: no index in indexes, no page allocated, the name still free.

The algorithm in words

Check a row against a unique index

Before writing the row, for each unique index of the table, in the order they were created.

1.If the row's value in the indexed column is NULL, it conflicts with nothing: go on.
2.Seek the index to the first entry with that value, whatever its table key.
3.If that entry exists, has the same value, and belongs to another row, the statement is 01605.
4.For an UPDATE, an entry that belongs to the row being changed is not a conflict: the row keeps its own value.

Create a unique index

Build it as any index, and look for neighbours that are equal.

1.Run the checks of CREATE INDEX: table, column, name.
2.Build the entries. Since equal values sort next to each other, two rows with the same non-NULL value make two neighbouring entries.
3.If any two neighbours have the same non-NULL value, the statement is 01606, and every page it allocated is taken back.
4.Record the index in the catalog with its unique flag.

UNIQUE in CREATE TABLE

Sugar for the statement above.

1.Accept UNIQUE among a column's options, at most once.
2.After creating the table, create a unique index on that column named <table>_<column>_key. If an index already has that name, the CREATE TABLE is 01602 and nothing is created.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 57.

Input	Output
`create unique index by_email on u (email);`	`Create index statement executed successfully`
`create table p (id int, email varchar(40) unique);`	creates the table and the unique index `p_email_key`
an INSERT or UPDATE giving a row another row's value	`[ERROR:01605] <message>`
CREATE UNIQUE INDEX over values that repeat	`[ERROR:01606] <message>`
`indexes`	`[INDEX] by_email on u (email) root=<page> UNIQUE`
`ast create unique index by_email on u (email);`	`Statement: CREATE UNIQUE INDEX`, then `Index:`, `Table:`, `Columns:`
`ast` of a CREATE TABLE with `unique not null`	`email varchar(40) NOT NULL UNIQUE`
`explain create unique index by_email on u (email);`	`[PLAN] └── CreateIndex (index=by_email, table=u, unique)`

unique is a keyword.

What you should see when done

shell

$droid --db people.db
Welcome to droid!
>create table p (id int, email varchar(40) unique);
Create table statement executed successfully
>insert into p (id, email) values (1, 'a@x');
Insert statement executed successfully (1 rows)
>insert into p (id, email) values (2, 'a@x');
[ERROR:01605] 'a@x' is already in p_email_key
>insert into p (id, email) values (3, NULL);
Insert statement executed successfully (1 rows)
>insert into p (id, email) values (4, NULL);
Insert statement executed successfully (1 rows)
>indexes
[INDEX] Indexes: 1
[INDEX]   p_email_key on p (email) root=3 UNIQUE
>.exit
exiting.. good bye!

The messages are yours to word; the tests check only the codes.

Common bugs in this stage

Comparing whole entries. The table keys always differ, so nothing ever conflicts.
Treating NULL as a value. The second NULL is refused.
An UPDATE conflicting with itself. Setting a row to the value it already has must succeed.
Writing first, checking after. The row or the entry stays behind unless the statement's pages are taken back.
A failed CREATE UNIQUE INDEX leaving its pages or its catalog record. The name must be free afterwards.

Language notes

The page above is the same for every language. These are the only language-specific hints.

C: give your index compare function a flag "values only" so the same function serves the seek of a unique check.
C++: a comparator that stops before the table key, beside the full one, keeps both explicit.
Rust: compare the value slice of the entry with cmp and ignore the trailing key; a #[derive(Ord)] on the whole entry is the wrong order for this check.
Zig: slice the entry before its last four bytes and compare that.

Loading starter code…

No run yet

8 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.