Quadratic constraint naming for FKs to partitioned tables

From: Manu <manuelreyesbravo(at)gmail(dot)com>
To: Álvaro Herrera <alvherre(at)kurilemu(dot)de>
Cc: pgsql-hackers(at)lists(dot)postgresql(dot)org
Subject: Quadratic constraint naming for FKs to partitioned tables
Date: 2026-11-17 15:58:56
Message-ID: 179493113608.1129989.9179084531222922608@gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi Álvaro,

A foreign key that references a table with N partitions makes N(N+1)/2
index probes in ChooseConstraintName(), because the name of each
partition's row is searched from suffix 1 again. With 10,000
partitions, ALTER TABLE ... ADD FOREIGN KEY takes 43 s on master and
2 s with the attached patch. pg_restore pays the same in post-data:
765 billion instructions there on master, 65 billion patched.

The patch keeps the last suffix chosen in addFkRecurseReferenced() and
starts the next search after it, so the names do not change: an oracle
over 3,880 cases gives the same names as master, and a new test pins a
taken name in the middle. DETACH of a referencing partition had the
same cost and is covered; creating or attaching one referenced
partition is still linear per command. The new extern sits next to
the one in Marko's CF 6842, so one of the two will need a small rebase.

Manu

Attachment Content-Type Size
v1-0001-Avoid-quadratic-name-search-for-FKs-to-partitione.patch text/x-patch 17.0 KB
measurements.txt text/plain 4.9 KB
fk-names-measure.py.txt text/plain 13.1 KB
fk-names-oracle.py.txt text/plain 8.9 KB

Browse pgsql-hackers by date

  From Date Subject
Next Message Ashutosh Sharma 2026-11-17 16:24:52 Re: log XLogPrefetch stats at end of recovery
Previous Message Tình Trần 2026-11-17 15:47:01 Re: [PATCH] Fix interval input at minimum signed field values (BUG #19746)