Foreign Keys: The Index You Forgot and the Lock You Didn't Ask For

A foreign key is described as a declarative guarantee that a child row points at a real parent. That is what it is. It is also a standing instruction to the database, executed on every parent delete, to go and find the child rows yourself, and it will do that with whatever access path the child table happens to have.

The child table usually does not have an index. That is the whole problem.

An index is also something the planner will judge you on, and the two failures interact: add the index, and the plan for the parent delete changes shape at the same moment. That is the subject of why the planner rejects your index, and the constraint-validation case adds a second reason the index is needed beyond the query plan, which is the part people miss when they alter the table to add one.

What a foreign key actually costs

CREATE TABLE orders (
    id          bigint PRIMARY KEY,
    customer_id bigint NOT NULL REFERENCES customers (id)
);

CREATE INDEX ON orders (customer_id);

For a large child table that participates in parent deletes or key updates, that index is usually part of the relationship design. PostgreSQL does not require it because small tables, uncommon parent changes, and existing composite indexes can make another choice reasonable.

DELETE FROM customers WHERE id = 88123;

To decide whether the delete is legal, the engine must find every orders row with customer_id = 88123. The parent side is indexed, because the referenced column is a primary key. The child side is not, unless you created that index, so the only available plan is a sequential scan of the entire orders table.

  one parent delete, no child index

    DELETE FROM customers WHERE id = 88123
      -> sequential scan of orders, 10,000,000 rows
      -> filter customer_id = 88123
      -> found 0
      -> allow the delete

  cost: one full table scan, per parent row deleted

Now the same thing as a batch.

DELETE FROM customers WHERE id IN (88123, 88124, 88125, 88126, 88125 ...);  -- 1000 rows

Each row is deleted individually, and each one triggers its own verification. That is 1000 sequential scans of a ten million row table. A statement that looks like a single bulk delete turns into an operation whose cost is rows_deleted × table_size.

With an index on orders (customer_id), the check becomes a btree descent, and the total cost is 1000 × log(n). The difference between those two is the difference between a delete that takes ten minutes and one that takes ten milliseconds, and it is entirely due to one line of DDL.

The important thing to notice is that the cost is invisible in the query plan. The plan says Delete on customers, and the scan appears inside a subplan, so the number that explains your slow delete is not in EXPLAIN of the DELETE itself. It is in the per-trigger or per-row work, and the way to see it is EXPLAIN (ANALYZE, BUFFERS) on the child-side query, or pg_stat_statements showing a disproportionate number of scans.

Cascades make it worse

ON DELETE CASCADE changes the verification from a lookup into an operation, and it is where the missing index stops being a performance detail and becomes an incident.

ALTER TABLE orders
  ADD CONSTRAINT orders_customer_fk
  FOREIGN KEY (customer_id) REFERENCES customers (id)
  ON DELETE CASCADE;

Now deleting one customer is an instruction to find every order belonging to that customer and delete those too.

  DELETE one customer
    find child rows        -> seq scan without an index, fast with one
    delete each child row  -> its own FK check, and its own indexes
    repeat

  and the customers table is locked against the children for the whole time

ON DELETE SET NULL is arguably worse, because instead of a delete per child row it is an update per child row, and updates write to the heap and to every index on the table.

NO ACTION is the default and can be deferred when the constraint is declared deferrable. RESTRICT prevents the referenced action immediately and cannot be deferred. Both still need to find referencing rows; neither makes an unindexed large child table free.

Whichever you chose, the index on the child column is what makes it affordable.

The lock you did not write

Look at the insert side again.

INSERT INTO order_items (order_id, sku, quantity)
VALUES (88123, 'SKU-4471', 2);

One row, one statement, one explicit row lock on order_items. The foreign key adds another one, on customers, to confirm the parent exists and to prevent it from being deleted or having its key changed underneath you.

  INSERT INTO order_items
    locks the new order_items row                (FOR KEY SHARE on parent follows)
    SELECT 1 FROM customers WHERE id = 88123
      -> FOR KEY SHARE on customers 88123

Two locks, one of them on a table the statement never names. This is the same shape as the invisible lock from a trigger, and it has the same consequence: your one-statement insert now participates in the deadlock graph.

  T1                                  T2
  ---                                  ---
  INSERT order_items                 DELETE customer 88123
    create uncommitted child row         lock parent row
    FOR KEY SHARE parent 88123          locks parent and checks child references
    waiting for T2                      waiting for T1

The exact cycle depends on statement order and referential action. A non-key update such as changing email is compatible with FOR KEY SHARE and is not this example. Deleting the parent or changing its referenced key conflicts; if that transaction then waits on the uncommitted child work, the cycle closes. Reproduce the actual pair of statements rather than treating every parent update as conflicting.

If you want to see this rather than infer it, watch the locks from a third session while you run the insert.

SELECT relation::regclass, mode, granted
FROM pg_locks
WHERE locktype = 'relation' OR locktype = 'tuple'
ORDER BY granted, relation::regclass;

A row that appears with granted = false on customers while your insert is running is the key check waiting for another transaction.

Find every missing one at once

The detection is a single query, and it is worth running against production rather than only in review, because the tables that are missing indexes are usually the ones nobody reviews any more.

SELECT
    child.relname        AS child_table,
    att.attname          AS child_column,
    parent.relname       AS parent_table,
    fk.conname           AS constraint_name,
    pg_size_pretty(pg_total_relation_size(child.oid)) AS child_size
FROM pg_constraint fk
JOIN pg_class child      ON child.oid = fk.conrelid
JOIN pg_class parent     ON parent.oid = fk.confrelid
JOIN pg_attribute att
  ON att.attrelid = fk.conrelid AND att.attnum = fk.conkey[1]
WHERE fk.contype = 'f'
  AND NOT EXISTS (
    SELECT 1
    FROM pg_index i
    WHERE i.indrelid = fk.conrelid
      AND i.indisvalid
      AND i.indpred IS NULL
      AND (
        SELECT array_agg(key_column ORDER BY ordinality)
        FROM unnest(i.indkey::smallint[]) WITH ORDINALITY
             AS keys(key_column, ordinality)
        WHERE ordinality <= cardinality(fk.conkey)
      ) = fk.conkey
  )
ORDER BY pg_total_relation_size(child.oid) DESC;

The interesting column is child_size, because that is the table the next parent delete will scan. A missing index on a 200 row lookup table is not worth mentioning. A missing index on a forty million row table is a scheduled outage.

Treat this query as an audit candidate list, not an automatic migration generator. A wider index is useful only when the foreign-key columns are its leading keys in compatible order; partial and invalid indexes do not cover the general check. Review workload, size, write cost, and the exact constraint.

For a hot production table, CREATE INDEX CONCURRENTLY allows ordinary inserts, updates, and deletes to continue. It does more work, takes longer, waits for relevant transactions/snapshots, conflicts with some schema changes, and can leave an invalid index after failure. A quiet window reduces load, but “concurrently” does not mean “blocks writes for the whole build.”

CREATE INDEX CONCURRENTLY idx_orders_customer_id ON orders (customer_id);

Verify what the ORM generated

EF Core creates an index for foreign-key properties by convention unless the columns are already covered or ForeignKeyIndexConvention was removed. That is the opposite of assuming every ORM omits it, and another reason to inspect the actual migration.

modelBuilder.Entity<Order>(b =>
{
    b.HasKey(o => o.Id);
    b.HasOne(o => o.Customer)
     .WithMany(c => c.Orders)
     .HasForeignKey(o => o.CustomerId);

    b.Property(o => o.CustomerId);
});

The generated migration should normally contain both AddForeignKey and CreateIndex. Keep explicit configuration when the production access path needs a particular name, column order, include list, or filter.

// Explicit configuration when convention is not the complete design
modelBuilder.Entity<Order>()
    .HasIndex(o => o.CustomerId)
    .HasDatabaseName("idx_orders_customer_id");

Then the migration produces both, and the next person to read the schema sees the relationship and the access path together, which is where you want them.

Two related settings are worth checking in the same pass, because both are the same category of mistake: an unenforced constraint that looks enforced.

SQLite does not enforce foreign keys unless you turn it on, and the setting is off by default and per connection.

PRAGMA foreign_keys = ON;

If you are seeing SQLite in an edge deployment, that pragma needs to run on every connection, not once at startup. MySQL on MyISAM ignores the constraints entirely, since the engine has no transactions to roll back with.

SQL Server can add or re-enable a constraint without checking existing rows. New writes may still be checked when the constraint is enabled, but the constraint remains untrusted and the optimizer cannot assume all stored rows comply.

ALTER TABLE orders WITH NOCHECK
ADD CONSTRAINT fk_customer
FOREIGN KEY (customer_id) REFERENCES customers (id);

WITH NOCHECK is a migration tool, not a healthy steady state. Find is_not_trusted and is_disabled separately, repair legacy rows, and re-enable with WITH CHECK CHECK CONSTRAINT when the data is valid.

SELECT conname, conrelid::regclass, convalidated
FROM pg_constraint
WHERE contype = 'f' AND NOT convalidated;

A production-ready architecture

  every foreign key
        |
        v
  +------------------------------------------+
  | is there a compatible leading child index? |
  +------------------------------------------+
     | no                          | yes
     v                             v
  assess size and parent actions  verify write cost and usage
  in a quiet window
        |
        v
  +---------------------------------------------+
  | what does the parent delete do?            |
  +---------------------------------------------+
     | RESTRICT / NO ACTION -> lookup, indexed |
     | CASCADE             -> delete per child |
     | SET NULL            -> update per child |
     +---------------------------------------------+
        |
        v
  +--------------------------------------------------+
  | budget the lock: the check takes FOR KEY SHARE    |
  | on the parent, so inserts can deadlock with       |
  | parent updates                                    |
  | validate any constraint added WITHOUT checking    |
  | turn FK enforcement on in SQLite, every connection|
  +--------------------------------------------------+

A delivery checklist:

1. For each foreign key, decide from child size, parent delete/key-update behavior, cascades, and existing leading composite indexes; a non-unique child index is the usual answer, not a universal law.
2. Run the detection query against production, ordered by child table size, not only against your dev database.
3. On hot tables, use CREATE INDEX CONCURRENTLY outside a transaction block; monitor progress and remove/rebuild an invalid index after failure.
4. Reassess ON DELETE CASCADE on large tables. A cascade on an unindexed child column is a delete storm.
5. Include referenced-row locks, one per foreign key, plus triggers and uniqueness checks in deadlock analysis; “two locks per insert” is too small for many schemas.
6. Check convalidated and find any NOT VALID constraints that were never validated.
7. Turn on PRAGMA foreign_keys per connection in SQLite, and confirm the engine is not one that ignores constraints.
8. Add the index in the ORM configuration next to the relationship, so a future migration cannot produce the constraint without it.
9. Watch for a child table growing large, because the missing index is cheap at 1000 rows and expensive at ten million.
10. Test a parent delete against a large child table. If it takes longer than it should, this is why.

Failure stories worth testing

Delete one customer with a large order history and time it

Do it against a child table with an index, then against the same table without one, on a copy. The difference is one btree lookup versus a full table scan, and it is the cleanest demonstration of why the child index is a correctness-adjacent requirement rather than a tuning detail.

Delete a thousand parents in a loop and watch the query statistics

With an unindexed child column the same scan repeats a thousand times. Comparing the runtime of the loop against the runtime of the same delete in a single statement with cascades makes the multiplicative cost obvious.

Force a child insert versus parent delete/key-change cycle

Use barriers in two sessions so one creates an uncommitted child while the other locks the parent for delete or referenced-key change, then let each reach the other’s resource. A non-key update such as email is compatible with FOR KEY SHARE and should be a negative control.

Run the missing-index query on a database with real history

Sort by child table size. In most systems there is one or two tables where the answer is a large table, which is exactly the one that gets deleted from on a schedule.

Add a foreign key with NOT VALID, then distinguish old and new rows

Seed an orphan before adding the constraint, then add it NOT VALID. The legacy orphan remains, but a new orphaning insert should fail: PostgreSQL enforces new writes while postponing the initial table scan. VALIDATE CONSTRAINT must later fail until the old row is repaired.

Common mistakes

Mistake	What actually happens	Better decision
Assuming the constraint creates the child index	Only the referenced side is indexed	Add a non-unique index on the child column
Believing a batched parent delete is one scan	Each row triggers its own verification	Index the child, then re-measure
Using ON DELETE CASCADE on an unindexed child column	A full scan plus a delete per child row, per parent	Index first, then re-evaluate the cascade
Treating ON DELETE SET NULL as cheaper than cascade	It is an update per child row, with index writes	Same index requirement
Expecting a one-row insert to hold one lock	The key check takes a lock on the parent	Budget two locks, and two in the deadlock graph
Treating NOT VALID as disabled	New writes are enforced but legacy rows are not proven	Repair old rows, validate, and check convalidated
Leaving PRAGMA foreign_keys off in SQLite	References are not enforced at all	Set it on every connection
Using WITH NOCHECK as a default in SQL Server	Existing bad rows are never found	Use it deliberately, validate afterwards
Reading the plan for the DELETE only	The scan is in a per-row subplan	Look at the child-side access path and buffers
Treating CONCURRENTLY as zero-cost	Writes continue, but the build does extra scans/work and can leave an invalid index	Monitor it, run outside a transaction block, and plan failure cleanup
Fixing only the tables you know about	The expensive ones are the ones nobody reviewed	Run the query ordered by child table size

The complete story in one minute

A foreign key makes the referenced column indexed, because it has to be a primary key or unique, and it makes the referencing column not indexed at all, because nothing about the constraint requires that. The consequence is that when you delete or change a parent key, the engine has to find the referencing child rows, and with no index on the child column the only plan available is a sequential scan of the entire child table. A delete of one parent is one scan. A delete of a thousand parents is a thousand scans, and the number that explains your slow delete is not in the plan for the DELETE itself. Cascades make it worse, because ON DELETE CASCADE reads and deletes every child row and ON DELETE SET NULL reads and updates every child row, and both are per parent row.

The second cost is the lock. To check the key, the engine takes a FOR KEY SHARE lock on the parent row, so an INSERT into a child table holds a lock on a table the statement never names. Two locks in a transaction that looks like a single-row insert, which is entirely enough to deadlock against a transaction updating that parent. The same shape appears with triggers, and the same budget applies.

The usual performance repair is a non-unique child index whose leading columns match the foreign key in order. It is not automatic PostgreSQL DDL because tiny or operationally static relationships may not justify the write cost, and an existing composite index may already cover the lookup. EF Core normally creates this index by convention; inspect the generated schema because conventions can be removed and legacy databases do not inherit them.

Use CREATE INDEX CONCURRENTLY on hot tables when ordinary writes must continue, while planning for extra build work and invalid-index cleanup after failure. Check convalidated separately: a PostgreSQL NOT VALID foreign key still rejects new violations but has not proven pre-existing rows. Adding the index was one task. Proving the access path, enforcement state, and lock behavior for the relationship was the schema design.

Technical references

• PostgreSQL foreign-key constraints and referencing indexes
• PostgreSQL ALTER TABLE, NOT VALID, and validation
• PostgreSQL concurrent index builds
• PostgreSQL row-level lock modes
• EF Core relationship conventions and foreign-key indexes
• SQLite foreign-key support
• SQL Server foreign-key trust and disabling