CODEWITHSUNDEEP
databasepostgresqldatabase-designforeign-keys
ady
ady

Reputation: 1168

Database internals: implementation of a foreign key constraint

How is the foreign key implemented, for example, in PostgreSQL?

I noticed that a lot of hashing is involved in the creation of a foreign key, so I suppose that a hash based index is created on the foreign key column that references the primary key column. If so (for instance, when we want to remove a row from the referenced table - this one with the primary key or the so called master table) we can easily check if the row from the referenced table is actually referenced or not. What's more, probably DBMS requires that there is at least a B+ tree index on the referenced primary key column, because when we want to insert a new row to the referencing table, we can easily check if a row with the required primary key value exists in the referenced table. Some sources claim that a trigger is used to ensure the foreign key constraint.

Upvotes: 3

Views: 1946

Answers (2)

Erwin Brandstetter
Erwin Brandstetter

Reputation: 659187

In Postgres, the referenced column(s) in the master table need to have a UNIQUE or PRIMARY KEY constraint. Per documentation:

The referenced columns must be the columns of a non-deferrable unique or primary key constraint in the referenced table.

Both of which are currently always implemented with a btree index. So there is always a btree index on the referenced column(s):

The referencing column(s) do(es) not have to be indexed at all. If rows in the master table are never updated or deleted, this may be good enough. Else, the referencing column(s) should also be indexed, but that's not enforced by the system. This is just about performance optimization, not data integrity.

The actual implementation of the FK constraint itself is an entry in the system catalog pg_constraint, a special internal trigger and another entry in pg_depend.

Upvotes: 2

ady
ady

Reputation: 1168

I checked that, indeed, there is no index created by PostgreSQL for a foreign key (using this query: https://stackoverflow.com/a/25596855/1245175).

On the other hand, a few triggers are created for a foreign key:

test=# SELECT tgname AS trigger_name
  FROM pg_trigger
 WHERE tgname !~ '^pg_';
 trigger_name
--------------
(0 rows)

test=# ALTER TABLE LINEITEM ADD CONSTRAINT LINEITEM_FK1 FOREIGN KEY (L_ORDERKEY)  REFERENCES ORDERS;
ALTER TABLE
test=# SELECT tgname AS trigger_name                                                               
  FROM pg_trigger
 WHERE tgname !~ '^pg_';
         trigger_name        
------------------------------
 RI_ConstraintTrigger_a_16419
 RI_ConstraintTrigger_a_16420
 RI_ConstraintTrigger_c_16421
 RI_ConstraintTrigger_c_16422

So, I suppose that during the foreign key creation in PostgreSQL, a hash map is created for the referenced table and then a probing is executed for each row of the referencing table.

Interestingly enough, MonetDB creates indexes of different types for primary and foreign keys (probably join-index and hash-index, respectively). 

sql>select * from sys.idxs;
+------+----------+------+-------------+
| id   | table_id | type | name        |
+======+==========+======+=============+
| 6467 |     6446 |    0 | orders_pk   |
| 6470 |     6464 |    1 | lineitem_fk |
+------+----------+------+-------------+
2 tuples (3.921ms)

What's more, Oracle enforces primary key constraints using indexes and by default it does not create any index for a foreign key, however, there are some foreign key indexing tips: https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:292016138754

Upvotes: 0

Related Questions