Skip to main content
SereneDBSereneDB
961Contact Us

Adaptive Radix Tree (ART)

An Adaptive Radix Tree (ART) is SereneDB's default secondary index — the index type created by CREATE INDEX when no USING clause is given. It is mainly used to enforce primary key constraints and to speed up point and very highly selective (i.e., < 0.1%) queries. ART indexes are created automatically for columns with a UNIQUE or PRIMARY KEY constraint, and can be created manually with CREATE INDEX.

Persistence​

ART indexes are persisted on disk.

Limitations​

An ART index keeps a second copy of the data it indexes, so the following limitations apply when modifying that data.

Constraint Checking in UPDATE Statements​

UPDATE statements on indexed columns and columns that cannot be updated in place are transformed into a DELETE of the original row followed by an INSERT of the updated row. This rewrite has performance implications, particularly for wide tables, as entire rows are rewritten instead of only the affected columns. A row whose indexed values the UPDATE leaves as they are is updated in place instead, unless the statement sets only indexed columns, sets a column that cannot be updated in place, or sets a floating-point, INTERVAL or TIME WITH TIME ZONE indexed column. A CHECK constraint over several columns makes every UPDATE of the table set all of them, each to itself when the statement doesn't set it. So when a CHECK spans an indexed and a non-indexed column, every UPDATE of the table deletes and re-inserts each row it touches, even one that sets only columns outside the constraint; a CHECK over indexed columns only keeps the in-place path. The same applies to the UPDATE of MERGE INTO, INSERT ... ON CONFLICT DO UPDATE and INSERT OR REPLACE.

Additionally, it causes the following constraint-checking limitation of UPDATE statements. The same limitation exists in other DBMSs, like PostgreSQL.

In the example below, the table has more than 2048 rows, the number of rows an UPDATE processes at a time. The UPDATE is rewritten into a DELETE followed by an INSERT, 2048 rows at a time: when it sets i = 2047 to 2048, the row that holds 2048 comes in the next 2048 rows and has not been changed to 2049 yet, so the UPDATE fails with a constraint violation.

SQL
CREATE TABLE my_table (i INTEGER PRIMARY KEY);
INSERT INTO my_table SELECT range FROM range(3_000);
UPDATE my_table SET i = i + 1;
db error: ERROR: Duplicate key "i: 2048" violates primary key constraint.

A workaround is to split the UPDATE into a DELETE followed by an INSERT, in one transaction: copy the rows to a temporary table, delete them from the table, insert them back with their new values, and drop the temporary table.

SQL
CREATE TABLE my_table (i INTEGER PRIMARY KEY);
INSERT INTO my_table SELECT range FROM range(3_000);
BEGIN;
CREATE TEMP TABLE tmp AS SELECT i FROM my_table;
DELETE FROM my_table;
INSERT INTO my_table SELECT i + 1 FROM tmp;
DROP TABLE tmp;
COMMIT;
SELECT    min(i) AS lowest,    max(i) AS highest,    count(*) AS totalFROM my_table;
 lowest | highest | total
--------+---------+-------
      1 |    3000 |  3000

A client can do the same without a temporary table: run DELETE ... RETURNING * and insert the rows it returns, with their new values, in the same transaction.

Over-Eager Constraint Checking in Foreign Keys​

This limitation occurs if you meet the following conditions:

  • A table has a FOREIGN KEY constraint.
  • An UPDATE of the corresponding PRIMARY KEY table deletes and re-inserts the rows it touches, as described above. One that sets a payload column of type LIST, ARRAY, MAP, UNION, VARIANT or GEOMETRY, or a STRUCT that contains one, always does.
  • The to-be-deleted row exists in the foreign key table.

If these hold, you'll encounter an unexpected constraint violation:

SQL
CREATE TABLE pk_table (id INTEGER PRIMARY KEY, payload VARCHAR[]);
INSERT INTO pk_table VALUES (1, ['hello']);
CREATE TABLE fk_table (id INTEGER REFERENCES pk_table(id));
INSERT INTO fk_table VALUES (1);
UPDATE pk_table SET payload = ['world'] WHERE id = 1;
db error: ERROR: Violates foreign key constraint because key "id: 1" is still referenced by a foreign key in a different table. If this is an unexpected constraint violation, please refer to our foreign key limitations in the documentation

SereneDB does not look ahead: when the DELETE removes the row, it does not know that the INSERT of the same UPDATE puts the key back.

See also​

Edit this page ↗