Primary and Foreign Keys Explained: One Missing Index, 50 ms per Delete

So here is how keys work, in outline. Two tables that belong together are connected by a column: each order stores the id of the customer who placed it, and that copy of the id is the whole connection. The table being pointed at is called the parent, customers here, and the one doing the pointing is the child. Nothing in the database knows about the arrows in the picture. Every program that writes to either table has to keep them pointing at real rows, and when one of them doesn’t, the result is order 1004: a row that refers to a customer who no longer exists, called an orphan. Two rules move that job into the database. A primary key names the column that identifies each row and refuses a second row with the same value, so an id always means exactly one customer. A foreign key says that orders.customer_id refers to customers.id, and refuses any write that would leave an arrow pointing at nothing, from either table. The rest of this post is what those refusals look like, what they cost, and the one place where the cost lands somewhere you would not expect.

A quick reminder about tables that point at each other

The two tables from the picture, as the tests below created them, with primary keys but no foreign key yet:

1
2
3

CREATE TABLE customers (id int PRIMARY KEY, email text NOT NULL UNIQUE, name text NOT NULL);
CREATE TABLE orders    (id bigint PRIMARY KEY, customer_id int NOT NULL,
                        total numeric(10,2) NOT NULL, created_at timestamptz NOT NULL);

The id a child stores is usually a number with no other meaning, so that it never has to change when a customer’s email or name does. A rule the database checks on every write is called a constraint. NOT NULL and UNIQUE above are constraints on one column; primary and foreign keys are the two that define how rows are identified and how tables connect.

Without the foreign key, deleting customer 42, who had 16 orders, simply worked on both engines. This count found what it left behind, and it is the same query that finds orphans in any pair of tables that has run without a key:

1
2
3
4
5
6
7
8
9

DELETE FROM customers WHERE id = 42;   -- customer 42 had 16 orders

SELECT count(*) AS orphans
FROM orders o LEFT JOIN customers c ON c.id = o.customer_id
WHERE c.id IS NULL;

 orphans
---------
      16          (PostgreSQL 18.6 and MySQL 8.4.13 alike)

The tests below ran on this schema with 200,000 customers and 2,000,000 orders, each order assigned to a random customer among the first 190,000, so customers 190,001 to 200,000 have no orders at all. Both engines ran in Docker on the same machine, with the data already cached in memory.

A primary key is checked on every insert

A primary key promises two things about a column: no two rows share a value, and no row leaves it empty. Checking the first promise on every insert would mean reading the whole table if the database had nowhere faster to look, so both engines build an index for the key, a sorted copy of the column with a pointer to each row, and look the new value up in it. On PostgreSQL the catalog shows what declaring the key created, a unique index called customers_pkey and a NOT NULL flag on the column. Inserting a second customer 42 then fails on each engine:

1
2
3

PostgreSQL 18.6: ERROR:  duplicate key value violates unique constraint "customers_pkey"
                 DETAIL:  Key (id)=(42) already exists.
MySQL 8.4.13:    ERROR 1062 (23000): Duplicate entry '42' for key 'customers.PRIMARY'

MySQL’s index is more than a lookup aid. InnoDB, its default storage engine, stores the table’s rows inside the primary key index, in key order, so the key decides where every row lives on disk; the clustered index post measures what that does to reads.

Neither engine requires a primary key by default. A table declared without one accepted two identical rows on both engines, (1, 'a@x') twice, and nothing afterwards can tell them apart, update one without the other, or let another table refer to just one of them. MySQL quietly adds a hidden key of its own to such a table (it showed up in information_schema.INNODB_INDEXES as GEN_CLUST_INDEX), because InnoDB has to store rows in some key’s order, but nothing outside the engine can use it. MySQL can refuse tables without a primary key if sql_require_primary_key is turned on; it was off.

A foreign key is checked from both sides

A foreign key on orders.customer_id promises that every value in that column matches an existing customers.id. The promise can be broken from either table, so the database checks both. Inserting an order for a customer who does not exist is refused, and deleting a customer who still has orders is refused too. Here is the delete of customer 42 again, with the foreign key in place:

1
2
3
4
5

PostgreSQL 18.6: ERROR:  update or delete on table "customers" violates foreign key constraint
                         "orders_customer_fk" on table "orders"
                 DETAIL:  Key (id)=(42) is still referenced from table "orders".
MySQL 8.4.13:    ERROR 1451 (23000): Cannot delete or update a parent row: a foreign key
                 constraint fails (`shop`.`orders`, CONSTRAINT `orders_customer_fk` ...)

A delete like that is the case any test finds: delete a customer, count their orders, fail. It is also the usual reason for leaving the check to the application. The code that deletes a customer can delete their orders in the same transaction, the code that adds an order can check first that the customer exists, and each of those is correct on its own. What a transaction does not cover is another transaction running at the same time. On both engines, at their default isolation levels, one transaction checked that customer 42 existed and two seconds later inserted an order for it. In between, a second transaction deleted customer 42’s orders, then customer 42, and committed. Then the first one committed too, and the new order pointed at nobody, in three runs out of three. The check had read a customer who was about to disappear, and the delete had removed every order it could see, which did not include one that did not exist yet. With the foreign key in place, both engines refused the insert (violates foreign key constraint on PostgreSQL, error 1452 on MySQL), because the key’s check runs at the moment of the insert and locks the customer row it finds, so that customer cannot be deleted until the order is committed (the same lock is behind a deadlock that Deadlocks Part 1 measures).

Running the same two transactions in the other order split the engines. When the order was inserted first and committed after the delete, PostgreSQL’s delete did not see the uncommitted order and left it orphaned, three runs out of three. MySQL’s delete waited 1.4 s for the insert to commit and then removed the new order along with the others, because at its default level a delete locks the range of index entries it scans. Raising both transactions to SERIALIZABLE also stopped the first case without a foreign key, by failing one of them (PostgreSQL: could not serialize access due to read/write dependencies among transactions; MySQL: deadlock, error 1213), which the application then has to catch and retry; the post on isolation levels explains why. None of this needs a bug, and a test suite that sends one request at a time never sees it. Other writes skip the application altogether: a query typed into a terminal, one an AI assistant wrote, a bulk load, a second service writing the same tables. The database is the one place every write passes through (the business logic post makes that argument in full).

A handful of orphans does not stay a handful of rows. A report that joins orders to customers drops them, a report that reads orders alone counts them, and the two totals stop agreeing. Any statement that writes from such a join, an invoice run or a loyalty tier or a copy into the warehouse, carries the disagreement into another table, where it outlives the orphans. The ids can also come back. In MySQL 5.7, the manual says, the auto-increment counter lived only in memory and restarted from the highest id still in the table. Deleting the newest customer while their orders stayed, restarting 5.7.44 and inserting a signup produced this:

1
2
3
4

MySQL 5.7.44:  INSERT INTO customers (email) VALUES ('new-signup@x');   -- given id 5

| email        | orders | lifetime_value |
| new-signup@x |      3 |         245.50 |

The new customer inherited three orders it never placed. MySQL 8.0 made the counter survive restarts, and 8.4.13 gave the same signup id 6. PostgreSQL sequences do not move backwards on their own, only when someone sets them back, which a restore or a hand-made data fix sometimes does.

The constraint has a second job: it is the only place the database records how two tables connect. A tool that reads the schema instead of the application code finds that record in the catalog, the system tables in which the database describes itself. Given a foreign key on customer_id and another on a placed_by column pointing at a staff table, the catalog listed both:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

PostgreSQL 18.6:  SELECT conrelid::regclass AS child, pg_get_constraintdef(oid) AS definition
                  FROM pg_constraint WHERE contype = 'f';

 child  |                     definition
--------+----------------------------------------------------
 orders | FOREIGN KEY (customer_id) REFERENCES customers(id)
 orders | FOREIGN KEY (placed_by) REFERENCES staff(id)

MySQL 8.4.13:     SELECT TABLE_NAME, COLUMN_NAME, REFERENCED_TABLE_NAME, REFERENCED_COLUMN_NAME
                  FROM information_schema.KEY_COLUMN_USAGE WHERE REFERENCED_TABLE_NAME IS NOT NULL;

| orders     | customer_id | customers             | id                     |
| orders     | placed_by   | staff                 | id                     |

The same table created without the two constraints did not appear in either list. That is what ORM model generators, diagram tools and AI assistants writing SQL from a schema dump have to work with. With the key declared, the join is written down. Without it, all they have is the column name: customer_id next to a customers table is an easy guess, but nothing in the name placed_by says staff, and a model guessing from names will still pick a join and write the query around it. The post on what AI gets wrong about databases covers the other places where the schema and the data drift apart.

The check on the child side is a lookup in the parent’s primary key index for every row written. PostgreSQL runs it as an internal trigger, which EXPLAIN ANALYZE on an insert lists by name (Trigger for constraint orders_customer_fk: calls=200000). To see what it costs, both engines inserted 200,000 orders in one statement, with and without the foreign key, and with and without an index on orders.customer_id:

On PostgreSQL the check itself was the cost: 2.5 to 2.8 microseconds per row, comparing medians with and without the index, enough to more than double this bulk insert. On MySQL the check added little that could be told apart from run-to-run noise, and the extra time came from maintaining the index on customer_id, which MySQL insists a foreign key has. For an application inserting rows one at a time over a network, a few microseconds per row is far below the cost of the round trip. For a bulk load, it is real, and it is the honest case for loading first and adding the constraint afterwards.

There is one more cost, which only shows up with concurrent writes: while an order is being inserted, the parent customer row is locked against deletion, and two transactions writing children of the same parent can end up waiting on each other. Deadlocks Part 1 measures that case.

The index the foreign key needs on the other side

The parent side of the check runs in the other direction. When a customer is deleted, the database has to prove that no order still points at it, which means searching orders.customer_id for that value. If that column has an index, the search is a lookup. If it does not, the only way to prove a value is absent is to read every row of the orders table.

MySQL does not let that happen. Declaring the foreign key created an index on orders.customer_id automatically, named after the constraint, and trying to drop it failed with ERROR 1553 (HY000): Cannot drop index 'orders_customer_fk': needed in a foreign key constraint. PostgreSQL creates an index for the primary key it points at, but nothing on the referencing column; the documentation says that “since a DELETE of a row from the referenced table … will require a scan of the referencing table for rows matching the old value, it is often a good idea to index the referencing columns too,” and leaves it to you.

The test deleted 200 customers who had no orders, the cheapest delete there is, since nothing has to be refused or cascaded:

Without the index, PostgreSQL spent 10.2 and 10.5 seconds in two runs, almost all of it in the foreign key trigger, which EXPLAIN ANALYZE reported as time=10218.440 calls=200: about 51 ms per customer, each one a full read of the 2,000,000-row orders table to find nothing. A single delete took 47 ms. With the index the same 200 deletes took 1.0 and 1.6 ms, and a single one 0.025 ms. MySQL, with the index it insisted on, took 0.6 to 1.2 ms.

When the parent is deleted or its key changes

Refusing the delete is the default, but it is one of several choices, declared on the foreign key itself. ON DELETE RESTRICT (or the default, NO ACTION, which on PostgreSQL differs only in when the check runs and on MySQL not at all) refuses the delete while children exist. ON DELETE CASCADE deletes the children with the parent. ON DELETE SET NULL keeps the children and empties their reference, which needs a column that allows empty values. The same choices exist for a change of the parent’s key, as ON UPDATE.

A cascade makes one statement do as much work as there are children. Customer 200,000 was given 100,000 orders, and deleting the customer with ON DELETE CASCADE deleted all of them, leaving none behind on either engine. That took 17, 20 and 46 ms on PostgreSQL, and 171 to 183 ms on MySQL, with the index on orders.customer_id in place on both. A cascade is the right shape when the children have no meaning without the parent, like the lines of an order. When the children are records someone will want later, like orders and invoices, refusing the delete keeps a mistake from removing them.

ON UPDATE CASCADE is where the natural key from the earlier note gets expensive. For this test the same data was loaded into a second pair of tables in which customers are keyed by email and orders store the customer’s email instead of an id. When that customer with 100,000 orders changed their email, the database rewrote the email in every one of those orders:

With the id as the key, the email lives in one row and nothing refers to it, so changing it is a one-row update. With the email as the key, the change touched 100,001 rows, and each rewritten order also rewrote its entry in the index on the email column. For a customer with 16 orders the natural-key change took under 1 ms after the first run, which is why the cost of a natural key tends to show up late, on the heaviest customers. The generic id post covers naming; the random UUID post covers what a random surrogate key costs instead of a sequential one.

Partitioning changes how parents get deleted. A partitioned table is one table stored as several pieces, each holding the rows for a range of some column’s values, usually a date, so that a month of old orders can be removed by dropping its piece instead of deleting its rows one at a time. Foreign keys get in the way of that on both engines, in different ways.

MySQL does not allow them at all. Creating a partitioned table with a foreign key, referencing a partitioned table from a plain one, and partitioning a table that already has a foreign key all failed the same way on MySQL 8.4.13: ERROR 1506 (HY000): Foreign keys are not yet supported in conjunction with partitioning. PostgreSQL allows foreign keys in both directions, with one condition that shapes the schema. A partitioned table’s primary key has to include the partition column, so orders partitioned by created_at has the key (id, created_at), and a child cannot refer to orders(id) alone; PostgreSQL refused that with there is no unique constraint matching given keys. The child has to carry the partition column too:

1
2
3
4
5
6
7
8

-- PostgreSQL 18.6: orders and its lines, partitioned by the same date
CREATE TABLE orders (id bigint, created_at date NOT NULL,
                     customer_id int NOT NULL REFERENCES customers (id),
                     PRIMARY KEY (id, created_at)) PARTITION BY RANGE (created_at);
CREATE TABLE order_lines (id bigint, order_id bigint NOT NULL, order_created_at date NOT NULL, qty int,
                          PRIMARY KEY (id, order_created_at),
                          FOREIGN KEY (order_id, order_created_at) REFERENCES orders (id, created_at))
  PARTITION BY RANGE (order_created_at);

With both tables split by the same date, an old month has to go children first: detaching the October partition of orders while October’s lines still existed failed with removing partition "orders_2026_10" violates foreign key constraint, and detaching and dropping the lines’ October partition first, then the orders’, went through.

The strategy that works on both engines is to decide which tables get partitioned before deciding where the foreign keys go. The tables that grow without limit and get trimmed by date (events, logs, order history) tend to be at the edge of the schema: they refer to other tables, and nothing refers to them. Keeping it that way is a design choice. On PostgreSQL such a table can keep its foreign keys to the unpartitioned tables it points at; the partitioned orders above still refused an order for customer 999. On MySQL it has to give them up, so the references from that one table become a check the application makes, plus a scheduled run of the orphan count from the start of this post, while the tables at the center, customers and orders and products, stay unpartitioned and keep theirs. When a partitioned table does have to be referenced, the children carry its partition column and get partitioned the same way, as above.

What to check in your own schema

Everything above, in one table:

Two catalog queries find the gaps on PostgreSQL. Both were checked against a table created without a primary key and a foreign key whose index had been dropped, and each listed exactly that one:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

-- Foreign keys whose referencing columns have no index
SELECT c.conrelid::regclass AS child_table, c.conname, pg_get_constraintdef(c.oid)
FROM pg_constraint c
WHERE c.contype = 'f'
  AND NOT EXISTS (SELECT 1 FROM pg_index i
                  WHERE i.indrelid = c.conrelid
                    AND (i.indkey::int2[])[0:cardinality(c.conkey)-1] @> c.conkey);

-- Tables without a primary key
SELECT n.nspname, c.relname
FROM pg_class c JOIN pg_namespace n ON n.oid = c.relnamespace
WHERE c.relkind = 'r' AND n.nspname NOT IN ('pg_catalog', 'information_schema')
  AND NOT EXISTS (SELECT 1 FROM pg_constraint p WHERE p.conrelid = c.oid AND p.contype = 'p');

On MySQL only the second question applies:

1
2
3
4
5
6
7

SELECT t.table_schema, t.table_name
FROM information_schema.tables t
WHERE t.table_type = 'BASE TABLE'
  AND t.table_schema NOT IN ('mysql', 'sys', 'information_schema', 'performance_schema')
  AND NOT EXISTS (SELECT 1 FROM information_schema.table_constraints c
                  WHERE c.table_schema = t.table_schema AND c.table_name = t.table_name
                    AND c.constraint_type = 'PRIMARY KEY');

Adding a foreign key to a table that has run without one means every existing row is checked first, and any orphan makes the statement fail. The 2,000,000-row test took 134 ms on PostgreSQL and 9.7 s on MySQL, where the online DDL documentation says adding a foreign key copies the table unless foreign_key_checks is off. PostgreSQL can split the job: ADD CONSTRAINT ... NOT VALID starts checking new writes immediately without reading old rows, and a later VALIDATE CONSTRAINT checks the old rows without blocking writes. Run the orphan count from the start of this post first, because the validation stops at the first one it finds.