Hi Álvaro,
On Thu, Nov 12, 2026 at 3:29 PM Álvaro Herrera <[email protected]>
wrote:
> I think the case in heap_truncate_check_FKs() could be made faster by
> using a ScalarArrayOpExpr (SK_SEARCHARRAY in nbtree), but I think we
> don't have any precedent where we manufacture that kind of thing for
> DDL use.
The attached patches do that, on top of master (77bba54, after your
b0496e30830). heap_truncate_check_FKs() does its lookups through
heap_truncate_find_FKs(), so that is the function they change.
0001 stands alone: TRUNCATE ... CASCADE passed heap_truncate_find_FKs()
the whole, growing list at every level, so a chain of N tables made N
lookups of up to N relations. It now passes only the relations added
at the previous level; each level adds the same relations in the same
order.
0002 lets systable_beginscan() take SK_SEARCHARRAY keys. nbtree
already handles them on the index path. On the heap path, used with
ignore_system_indexes or while reindexing, the heap scan would compare
the column with the array datum itself and return wrong rows, so 0002
keeps those keys out of it and checks them in systable_getnext(). An
index without amsearcharray raises an error. It is in genam.c rather
than a seqscan fallback in the caller because systable_beginscan()
makes that decision, and the caller would have to duplicate it.
0003 makes heap_truncate_find_FKs() do one confrelid = ANY scan instead
of the seqscan. Its test is in unsafe_tests, since it reconnects with
ignore_system_indexes; it fails if the genam.c part of 0002 is
reverted.
On precedent: no DDL code builds such keys today; outside nbtree only
nodeIndexscan.c does. The simpler alternative, one index probe per
relation, needs no genam.c change, so I measured it in the same cells
("probes" in measurements.txt). It gets the same gains in large
catalogs, but in a fresh database a commit with 1,000 ON COMMIT DELETE
ROWS tables that have triggers costs 21.8% more than master, against
2.7% with 0003: every probe sets up an index scan.
CPU instructions, master vs patched, median of 3 (measurements.txt
and the scripts that produced it are attached too):
- TRUNCATE of two PK/FK pairs in a catalog with 100,000 other FKs,
net of a TRUNCATE of four plain tables: 26.45M -> 1.02M
- whole commit with those 1,000 temp tables, in that catalog:
557.21M -> 34.91M
- TRUNCATE ... CASCADE down a chain of 1,000 tables: 3990.78M ->
1486.45M with 0001 alone, 637.02M with all three
The price, in a fresh database: that commit costs 2.7% more (33.90M ->
34.83M, under 1M instructions), 1.0% with 100 tables, and a TRUNCATE
of 1,000 tables in one statement 0.3% more. With 1,000 FKs in the
catalog the commit is already 11.0% cheaper. The other cells are
within run-to-run variation (measurements.txt, section 5).
The scripts count instructions, so they need builds without
assertions, as build.sh makes them.
Regards,
Manu
From cd801605381a33c31730bdad4ae0d0fc31fdf32d Mon Sep 17 00:00:00 2001
From: Manuel Reyes Bravo <[email protected]>
Date: Fri, 13 Nov 2026 17:11:29 -0300
Subject: [PATCH v1 1/3] Avoid repeated foreign key lookups in TRUNCATE CASCADE
ExecuteTruncateGuts() calls heap_truncate_find_FKs() once per level of
references, and passed it the whole, growing list of relations, so each
level looked up again the referencers of every relation found so far:
for a chain of N tables, N lookups of up to N relations. Pass it only
the relations added at the previous level instead. The referencers of
the others are already in the list, so each level adds the same
relations as before, in the same order. A relation can be found again,
for example through a cycle of foreign keys; skip it. Add a test where
the cascade reaches such a cycle.
Discussion: https://postgr.es/m/[email protected]
---
src/backend/commands/tablecmds.c | 18 ++++++++++++++----
src/test/regress/expected/truncate.out | 26 ++++++++++++++++++++++++++
src/test/regress/sql/truncate.sql | 18 ++++++++++++++++++
3 files changed, 58 insertions(+), 4 deletions(-)
diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index b670092..7bbc26b 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -2055,19 +2055,28 @@ ExecuteTruncateGuts(List *explicit_rels,
rels = list_copy(explicit_rels);
if (behavior == DROP_CASCADE)
{
- for (;;)
+ List *pending = list_copy(relids);
+
+ /*
+ * Each iteration only needs the referencers of the rels added by the
+ * previous one; those of older rels were already added.
+ */
+ while (pending != NIL)
{
List *newrelids;
- newrelids = heap_truncate_find_FKs(relids);
- if (newrelids == NIL)
- break; /* nothing else to add */
+ newrelids = heap_truncate_find_FKs(pending);
+ list_free(pending);
+ pending = NIL;
foreach(cell, newrelids)
{
Oid relid = lfirst_oid(cell);
Relation rel;
+ if (list_member_oid(relids, relid))
+ continue;
+
rel = table_open(relid, AccessExclusiveLock);
ereport(NOTICE,
(errmsg("truncate cascades to table \"%s\"",
@@ -2077,6 +2086,7 @@ ExecuteTruncateGuts(List *explicit_rels,
truncate_check_activity(rel);
rels = lappend(rels, rel);
relids = lappend_oid(relids, relid);
+ pending = lappend_oid(pending, relid);
/* Log this relation only if needed for logical decoding */
if (RelationIsLogicallyLogged(rel))
diff --git a/src/test/regress/expected/truncate.out b/src/test/regress/expected/truncate.out
index 1e88e86..5d83da6 100644
--- a/src/test/regress/expected/truncate.out
+++ b/src/test/regress/expected/truncate.out
@@ -138,6 +138,32 @@ SELECT * FROM trunc_e;
(0 rows)
DROP TABLE truncate_a,trunc_c,trunc_b,trunc_d,trunc_e CASCADE;
+-- TRUNCATE ... CASCADE reaching a cycle of foreign keys: trunc_cyc_b is
+-- found through trunc_cyc_a, and trunc_cyc_a references it back
+CREATE TABLE trunc_cyc_r (id int PRIMARY KEY);
+CREATE TABLE trunc_cyc_a (id int PRIMARY KEY, r int REFERENCES trunc_cyc_r, b int);
+CREATE TABLE trunc_cyc_b (id int PRIMARY KEY, a int REFERENCES trunc_cyc_a);
+ALTER TABLE trunc_cyc_a ADD FOREIGN KEY (b) REFERENCES trunc_cyc_b;
+INSERT INTO trunc_cyc_r VALUES (1);
+INSERT INTO trunc_cyc_a VALUES (1, 1, NULL);
+INSERT INTO trunc_cyc_b VALUES (1, 1);
+UPDATE trunc_cyc_a SET b = 1;
+TRUNCATE TABLE trunc_cyc_r CASCADE;
+NOTICE: truncate cascades to table "trunc_cyc_a"
+NOTICE: truncate cascades to table "trunc_cyc_b"
+SELECT count(*) FROM trunc_cyc_r
+ UNION ALL
+ SELECT count(*) FROM trunc_cyc_a
+ UNION ALL
+ SELECT count(*) FROM trunc_cyc_b;
+ count
+-------
+ 0
+ 0
+ 0
+(3 rows)
+
+DROP TABLE trunc_cyc_r, trunc_cyc_a, trunc_cyc_b;
-- Test TRUNCATE with inheritance
CREATE TABLE trunc_f (col1 integer primary key);
INSERT INTO trunc_f VALUES (1);
diff --git a/src/test/regress/sql/truncate.sql b/src/test/regress/sql/truncate.sql
index 54f26e3..0a902bd 100644
--- a/src/test/regress/sql/truncate.sql
+++ b/src/test/regress/sql/truncate.sql
@@ -78,6 +78,24 @@ SELECT * FROM trunc_e;
DROP TABLE truncate_a,trunc_c,trunc_b,trunc_d,trunc_e CASCADE;
+-- TRUNCATE ... CASCADE reaching a cycle of foreign keys: trunc_cyc_b is
+-- found through trunc_cyc_a, and trunc_cyc_a references it back
+CREATE TABLE trunc_cyc_r (id int PRIMARY KEY);
+CREATE TABLE trunc_cyc_a (id int PRIMARY KEY, r int REFERENCES trunc_cyc_r, b int);
+CREATE TABLE trunc_cyc_b (id int PRIMARY KEY, a int REFERENCES trunc_cyc_a);
+ALTER TABLE trunc_cyc_a ADD FOREIGN KEY (b) REFERENCES trunc_cyc_b;
+INSERT INTO trunc_cyc_r VALUES (1);
+INSERT INTO trunc_cyc_a VALUES (1, 1, NULL);
+INSERT INTO trunc_cyc_b VALUES (1, 1);
+UPDATE trunc_cyc_a SET b = 1;
+TRUNCATE TABLE trunc_cyc_r CASCADE;
+SELECT count(*) FROM trunc_cyc_r
+ UNION ALL
+ SELECT count(*) FROM trunc_cyc_a
+ UNION ALL
+ SELECT count(*) FROM trunc_cyc_b;
+DROP TABLE trunc_cyc_r, trunc_cyc_a, trunc_cyc_b;
+
-- Test TRUNCATE with inheritance
CREATE TABLE trunc_f (col1 integer primary key);
--
2.56.1
From 0ab4f861dd807dace66e51a4f647ef98edb8d714 Mon Sep 17 00:00:00 2001
From: Manuel Reyes Bravo <[email protected]>
Date: Fri, 13 Nov 2026 17:11:29 -0300
Subject: [PATCH v1 2/3] Allow SK_SEARCHARRAY scan keys in systable_beginscan()
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
A btree index scan handles a "column = ANY (array)" scan key itself, in
one scan of the index. systable_beginscan() can hand such a key to the
index, but not to the heap scan it uses instead when the index cannot
be used (ignore_system_indexes, a REINDEX of that index, or indexOK =
false): a heap scan does not know about SK_SEARCHARRAY and would
compare the column with the array datum itself, returning wrong rows.
In the heapscan case, leave the SK_SEARCHARRAY keys out of the heap
scan and check them in systable_getnext() instead, against each element
of the array. Set them aside before bsysscan is set, since looking up
the array's element type can itself scan a catalog. Raise an error if
such a key is given for an index that does not support it. Scans
without such keys do what they did before.
No caller passes SK_SEARCHARRAY keys yet; the next commit does, in
heap_truncate_find_FKs().
Suggested-by: Ãlvaro Herrera <[email protected]>
Discussion: https://postgr.es/m/[email protected]
---
src/backend/access/index/genam.c | 152 ++++++++++++++++++++++++++++++-
src/include/access/relscan.h | 3 +
src/include/access/skey.h | 2 +
src/tools/pgindent/typedefs.list | 1 +
4 files changed, 154 insertions(+), 4 deletions(-)
diff --git a/src/backend/access/index/genam.c b/src/backend/access/index/genam.c
index 98ac5bc..31b6e29 100644
--- a/src/backend/access/index/genam.c
+++ b/src/backend/access/index/genam.c
@@ -19,8 +19,10 @@
#include "postgres.h"
+#include "access/amapi.h"
#include "access/genam.h"
#include "access/heapam.h"
+#include "access/htup_details.h"
#include "access/relscan.h"
#include "access/tableam.h"
#include "access/transam.h"
@@ -30,6 +32,7 @@
#include "storage/bufmgr.h"
#include "storage/procarray.h"
#include "utils/acl.h"
+#include "utils/array.h"
#include "utils/injection_point.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
@@ -377,6 +380,96 @@ index_compute_xid_horizon_for_tuples(Relation irel,
* ----------------------------------------------------------------
*/
+/* An SK_SEARCHARRAY key of a heap scan, with its array deconstructed */
+typedef struct SysScanArrayKey
+{
+ ScanKeyData key;
+ Datum *elems; /* its non-null elements */
+ int nelems;
+ ArrayType *detoasted; /* copy made by detoasting, or NULL */
+} SysScanArrayKey;
+
+/*
+ * Set aside the SK_SEARCHARRAY keys of a heap scan in sysscan->arraykeys,
+ * and return the other keys, *nheapkeys of them, for the heap scan itself.
+ */
+static ScanKey
+systable_split_array_keys(SysScanDesc sysscan, int nkeys, ScanKey key,
+ int *nheapkeys)
+{
+ ScanKey heapkey = palloc_array(ScanKeyData, nkeys);
+
+ sysscan->arraykeys = palloc_array(SysScanArrayKey, nkeys);
+ *nheapkeys = 0;
+ for (int i = 0; i < nkeys; i++)
+ {
+ SysScanArrayKey *akey;
+ ArrayType *arr;
+ int16 elmlen;
+ bool elmbyval;
+ char elmalign;
+ bool *nulls;
+ int n;
+
+ if (!(key[i].sk_flags & SK_SEARCHARRAY))
+ {
+ heapkey[(*nheapkeys)++] = key[i];
+ continue;
+ }
+
+ akey = &sysscan->arraykeys[sysscan->narraykeys++];
+ akey->key = key[i];
+ akey->elems = NULL;
+ akey->nelems = 0;
+ akey->detoasted = NULL;
+ if (key[i].sk_flags & SK_ISNULL)
+ continue; /* a null array matches nothing */
+
+ arr = DatumGetArrayTypeP(key[i].sk_argument);
+ if ((Pointer) arr != DatumGetPointer(key[i].sk_argument))
+ akey->detoasted = arr;
+ get_typlenbyvalalign(ARR_ELEMTYPE(arr), &elmlen, &elmbyval, &elmalign);
+ deconstruct_array(arr, ARR_ELEMTYPE(arr), elmlen, elmbyval, elmalign,
+ &akey->elems, &nulls, &n);
+ /* the operator is strict, so null elements match nothing */
+ for (int j = 0; j < n; j++)
+ {
+ if (!nulls[j])
+ akey->elems[akey->nelems++] = akey->elems[j];
+ }
+ pfree(nulls);
+ }
+
+ return heapkey;
+}
+
+/*
+ * Does a heap tuple satisfy every SK_SEARCHARRAY key of the scan?
+ */
+static bool
+systable_match_array_keys(SysScanDesc sysscan, HeapTuple tup)
+{
+ TupleDesc tupdesc = RelationGetDescr(sysscan->heap_rel);
+
+ for (int i = 0; i < sysscan->narraykeys; i++)
+ {
+ SysScanArrayKey *akey = &sysscan->arraykeys[i];
+ Datum value;
+ bool isnull;
+ bool match = false;
+
+ value = heap_getattr(tup, akey->key.sk_attno, tupdesc, &isnull);
+ for (int j = 0; j < akey->nelems && !isnull && !match; j++)
+ match = DatumGetBool(FunctionCall2Coll(&akey->key.sk_func,
+ akey->key.sk_collation,
+ value, akey->elems[j]));
+ if (!match)
+ return false;
+ }
+
+ return true;
+}
+
/*
* systable_beginscan --- set up for heap-or-index scan
*
@@ -395,6 +488,14 @@ index_compute_xid_horizon_for_tuples(Relation irel,
* The routine checks the normal cases for whether an indexscan is safe,
* but caller can make additional checks and pass indexOK=false if needed.
* In standard case indexOK can simply be constant TRUE.
+ *
+ * A scan key can be SK_SEARCHARRAY, "column = ANY (array)": set the flag
+ * after ScanKeyInit(), with sk_argument an array of the operator's right-hand
+ * input type, which the caller keeps until systable_endscan(). A row matches
+ * if the (strict) operator is true for the column and any non-null element.
+ * The index must support such keys (amsearcharray). A heap scan cannot
+ * handle them (see skey.h), so in the heapscan case we leave them out of it
+ * and check them in systable_getnext() instead.
*/
SysScanDesc
systable_beginscan(Relation heapRelation,
@@ -405,6 +506,8 @@ systable_beginscan(Relation heapRelation,
{
SysScanDesc sysscan;
Relation irel;
+ ScanKey heapkey = key;
+ int nheapkeys = nkeys;
if (indexOK &&
!IgnoreSystemIndexes &&
@@ -413,7 +516,7 @@ systable_beginscan(Relation heapRelation,
else
irel = NULL;
- sysscan = palloc_object(SysScanDescData);
+ sysscan = palloc0_object(SysScanDescData);
sysscan->heap_rel = heapRelation;
sysscan->irel = irel;
@@ -432,6 +535,25 @@ systable_beginscan(Relation heapRelation,
sysscan->snapshot = NULL;
}
+ /*
+ * In the heapscan case, set aside the SK_SEARCHARRAY keys now, before
+ * bsysscan is set below: that may look up the array's element type in the
+ * syscache, and the systable_endscan() of a nested catalog scan would
+ * clear bsysscan before table_beginscan_strat() checks it.
+ */
+ if (irel == NULL)
+ {
+ for (int i = 0; i < nkeys; i++)
+ {
+ if (key[i].sk_flags & SK_SEARCHARRAY)
+ {
+ heapkey = systable_split_array_keys(sysscan, nkeys, key,
+ &nheapkeys);
+ break;
+ }
+ }
+ }
+
/*
* If CheckXidAlive is set then set a flag to indicate that system table
* scan is in-progress. See detailed comments in xact.c where these
@@ -464,6 +586,10 @@ systable_beginscan(Relation heapRelation,
}
if (j == IndexRelationGetNumberOfAttributes(irel))
elog(ERROR, "column is not in index");
+ if ((key[i].sk_flags & SK_SEARCHARRAY) &&
+ !irel->rd_indam->amsearcharray)
+ elog(ERROR, "index \"%s\" does not support array scan keys",
+ RelationGetRelationName(irel));
}
sysscan->iscan = index_beginscan(heapRelation, irel, false,
@@ -484,9 +610,12 @@ systable_beginscan(Relation heapRelation,
* it's unlikely that such scans will occur in parallel.
*/
sysscan->scan = table_beginscan_strat(heapRelation, snapshot,
- nkeys, key,
+ nheapkeys, heapkey,
true, false);
sysscan->iscan = NULL;
+
+ if (heapkey != key)
+ pfree(heapkey);
}
return sysscan;
@@ -552,12 +681,17 @@ systable_getnext(SysScanDesc sysscan)
}
else
{
- if (table_scan_getnextslot(sysscan->scan, ForwardScanDirection, sysscan->slot))
+ while (table_scan_getnextslot(sysscan->scan, ForwardScanDirection, sysscan->slot))
{
bool shouldFree;
htup = ExecFetchSlotHeapTuple(sysscan->slot, false, &shouldFree);
Assert(!shouldFree);
+
+ if (sysscan->narraykeys == 0 ||
+ systable_match_array_keys(sysscan, htup))
+ break;
+ htup = NULL;
}
}
@@ -630,6 +764,16 @@ systable_endscan(SysScanDesc sysscan)
else
table_endscan(sysscan->scan);
+ for (int i = 0; i < sysscan->narraykeys; i++)
+ {
+ if (sysscan->arraykeys[i].elems)
+ pfree(sysscan->arraykeys[i].elems);
+ if (sysscan->arraykeys[i].detoasted)
+ pfree(sysscan->arraykeys[i].detoasted);
+ }
+ if (sysscan->arraykeys)
+ pfree(sysscan->arraykeys);
+
if (sysscan->snapshot)
UnregisterSnapshot(sysscan->snapshot);
@@ -681,7 +825,7 @@ systable_beginscan_ordered(Relation heapRelation,
elog(WARNING, "using index \"%s\" despite IgnoreSystemIndexes",
RelationGetRelationName(indexRelation));
- sysscan = palloc_object(SysScanDescData);
+ sysscan = palloc0_object(SysScanDescData);
sysscan->heap_rel = heapRelation;
sysscan->irel = indexRelation;
diff --git a/src/include/access/relscan.h b/src/include/access/relscan.h
index d761410..0a42ce5 100644
--- a/src/include/access/relscan.h
+++ b/src/include/access/relscan.h
@@ -232,6 +232,9 @@ typedef struct SysScanDescData
struct IndexScanDescData *iscan; /* only valid in index-scan case */
struct SnapshotData *snapshot; /* snapshot to unregister at end of scan */
struct TupleTableSlot *slot;
+ /* SK_SEARCHARRAY keys, checked by genam.c in heap-scan case */
+ int narraykeys;
+ struct SysScanArrayKey *arraykeys;
} SysScanDescData;
#endif /* RELSCAN_H */
diff --git a/src/include/access/skey.h b/src/include/access/skey.h
index 64e7a80..ca0e2ca 100644
--- a/src/include/access/skey.h
+++ b/src/include/access/skey.h
@@ -49,6 +49,8 @@
* SK_SEARCHARRAY, SK_SEARCHNULL and SK_SEARCHNOTNULL are supported only
* for index scans, not heap scans; and not all index AMs support them,
* only those that set amsearcharray or amsearchnulls respectively.
+ * (systable_beginscan() checks SK_SEARCHARRAY keys itself when it falls
+ * back to a heap scan.)
*
* A ScanKey can also represent an ordering operator invocation, that is
* an ordering requirement "ORDER BY indexedcol op constant". This looks
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index f10eb46..5779c22 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3062,6 +3062,7 @@ SyncStandbySlotsConfigData
SyncingRelationsState
SysCacheIdentifier
SysFKRelationship
+SysScanArrayKey
SysScanDesc
SysScanDescData
SyscacheCallbackFunction
--
2.56.1
From 871e05438526c4d75313c93db9a1639adb2cfa1d Mon Sep 17 00:00:00 2001
From: Manuel Reyes Bravo <[email protected]>
Date: Fri, 13 Nov 2026 17:11:29 -0300
Subject: [PATCH v1 3/3] Use the confrelid index in heap_truncate_find_FKs()
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
heap_truncate_find_FKs(), which heap_truncate_check_FKs() uses for
TRUNCATE and for ON COMMIT DELETE ROWS at commit, still scanned all of
pg_constraint. Look up all the relations of its list in one scan of
the confrelid index, with confrelid = ANY (array), so that only the
foreign keys referencing the list are visited. One scan rather than a
probe per relation, because each probe pays for setting up an index
scan. When the function climbs to a partitioned parent constraint, the
extra pass looks up only the relations that adds.
Add a test to unsafe_tests that runs these lookups with
ignore_system_indexes, through the heap scan path of
systable_beginscan().
In a nearly empty database a long list still costs a little more than
the old seqscan: with 1,000 ON COMMIT DELETE ROWS temporary tables that
have triggers, a commit costs about 3% more (under 1M instructions).
Suggested-by: Ãlvaro Herrera <[email protected]>
Discussion: https://postgr.es/m/[email protected]
---
src/backend/catalog/heap.c | 39 +++++++++++----
src/test/modules/unsafe_tests/Makefile | 2 +-
.../expected/truncate_heapscan.out | 47 +++++++++++++++++++
src/test/modules/unsafe_tests/meson.build | 1 +
.../unsafe_tests/sql/truncate_heapscan.sql | 26 ++++++++++
5 files changed, 104 insertions(+), 11 deletions(-)
create mode 100644 src/test/modules/unsafe_tests/expected/truncate_heapscan.out
create mode 100644 src/test/modules/unsafe_tests/sql/truncate_heapscan.sql
diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index c8ec7b4..03bfdaa 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -4107,13 +4107,21 @@ heap_truncate_find_FKs(List *relationIds)
SysScanDesc fkeyScan;
HeapTuple tuple;
bool restart;
+ Datum *elems;
+ int nelems;
+ int nsearched = 0;
+ ArrayType *arr;
oids = list_copy(relationIds);
/*
- * Must scan pg_constraint. It is a seqscan although confrelid is
- * indexed, because probing the index once for each relation in the list
- * costs more than one pass over a small catalog.
+ * Must scan pg_constraint. Look up all the relations in our list in one
+ * scan of the index on confrelid, which is only set nonzero by FK
+ * constraints, so we visit just the foreign keys that reference our list.
+ * One scan with confrelid = ANY rather than a probe per relation, because
+ * each probe pays for setting up an index scan, which adds up for long
+ * lists such as those of ON COMMIT DELETE ROWS. A restart only needs to
+ * look up the relations added since the previous pass.
*/
fkeyRel = table_open(ConstraintRelationId, AccessShareLock);
@@ -4121,21 +4129,30 @@ restart:
restart = false;
parent_cons = NIL;
- fkeyScan = systable_beginscan(fkeyRel, InvalidOid, false,
- NULL, 0, NULL);
+ /* confrelid = ANY (the relations not looked up yet) */
+ elems = palloc_array(Datum, list_length(oids) - nsearched);
+ nelems = 0;
+ for_each_from(cell, oids, nsearched)
+ elems[nelems++] = ObjectIdGetDatum(lfirst_oid(cell));
+ nsearched = list_length(oids);
+ arr = construct_array_builtin(elems, nelems, OIDOID);
+ ScanKeyInit(&key,
+ Anum_pg_constraint_confrelid,
+ BTEqualStrategyNumber, F_OIDEQ,
+ PointerGetDatum(arr));
+ key.sk_flags |= SK_SEARCHARRAY;
+
+ fkeyScan = systable_beginscan(fkeyRel, ConstraintForeignRelIndexId,
+ true, NULL, 1, &key);
while (HeapTupleIsValid(tuple = systable_getnext(fkeyScan)))
{
Form_pg_constraint con = (Form_pg_constraint) GETSTRUCT(tuple);
- /* Not a foreign key */
+ /* Only foreign keys set confrelid, but check anyway */
if (con->contype != CONSTRAINT_FOREIGN)
continue;
- /* Not referencing one of our list of tables */
- if (!list_member_oid(oids, con->confrelid))
- continue;
-
/*
* If this constraint has a parent constraint which we have not seen
* yet, keep track of it for the second loop, below. Tracking parent
@@ -4155,6 +4172,8 @@ restart:
}
systable_endscan(fkeyScan);
+ pfree(arr);
+ pfree(elems);
/*
* Process each parent constraint we found to add the list of referenced
diff --git a/src/test/modules/unsafe_tests/Makefile b/src/test/modules/unsafe_tests/Makefile
index a85c854..003cd22 100644
--- a/src/test/modules/unsafe_tests/Makefile
+++ b/src/test/modules/unsafe_tests/Makefile
@@ -1,6 +1,6 @@
# src/test/modules/unsafe_tests/Makefile
-REGRESS = rolenames setconfig alter_system_table guc_privs
+REGRESS = rolenames setconfig alter_system_table guc_privs truncate_heapscan
REGRESS_OPTS = \
--create-role=regress_authenticated_user_db_sr \
--create-role=regress_authenticated_user_db_ssa \
diff --git a/src/test/modules/unsafe_tests/expected/truncate_heapscan.out b/src/test/modules/unsafe_tests/expected/truncate_heapscan.out
new file mode 100644
index 0000000..5fda65d
--- /dev/null
+++ b/src/test/modules/unsafe_tests/expected/truncate_heapscan.out
@@ -0,0 +1,47 @@
+--
+-- TRUNCATE foreign key lookups through the heap scan of pg_constraint
+-- (ignore_system_indexes), where systable_beginscan() has to check the
+-- confrelid = ANY key itself.
+--
+CREATE TABLE trunc_isi_a (id int PRIMARY KEY) PARTITION BY RANGE (id);
+CREATE TABLE trunc_isi_a1 PARTITION OF trunc_isi_a FOR VALUES FROM (0) TO (10);
+CREATE TABLE trunc_isi_b (id int PRIMARY KEY, a int REFERENCES trunc_isi_a)
+ PARTITION BY RANGE (id);
+CREATE TABLE trunc_isi_b1 PARTITION OF trunc_isi_b FOR VALUES FROM (0) TO (10);
+CREATE TABLE trunc_isi_c (b int REFERENCES trunc_isi_b);
+INSERT INTO trunc_isi_a VALUES (1);
+INSERT INTO trunc_isi_b VALUES (1, 1);
+INSERT INTO trunc_isi_c VALUES (1);
+-- ignore_system_indexes only takes effect at connection start. Only SHOW,
+-- the TRUNCATEs and a count run with it: DDL may use an index anyway and
+-- warn.
+\c -reuse-previous=on "options=-cignore_system_indexes=on"
+SHOW ignore_system_indexes;
+ ignore_system_indexes
+-----------------------
+ on
+(1 row)
+
+TRUNCATE trunc_isi_a1, trunc_isi_b1; -- fail
+ERROR: cannot truncate a table referenced in a foreign key constraint
+DETAIL: Table "trunc_isi_b" references "trunc_isi_a1".
+HINT: Truncate table "trunc_isi_b" at the same time, or use TRUNCATE ... CASCADE.
+TRUNCATE trunc_isi_a1 CASCADE;
+NOTICE: truncate cascades to table "trunc_isi_b"
+NOTICE: truncate cascades to table "trunc_isi_b1"
+NOTICE: truncate cascades to table "trunc_isi_c"
+SELECT (SELECT count(*) FROM trunc_isi_a) + (SELECT count(*) FROM trunc_isi_b) +
+ (SELECT count(*) FROM trunc_isi_c) AS rows_left;
+ rows_left
+-----------
+ 0
+(1 row)
+
+\c -reuse-previous=on "options="
+SHOW ignore_system_indexes;
+ ignore_system_indexes
+-----------------------
+ off
+(1 row)
+
+DROP TABLE trunc_isi_a, trunc_isi_b, trunc_isi_c;
diff --git a/src/test/modules/unsafe_tests/meson.build b/src/test/modules/unsafe_tests/meson.build
index 8217bbe..0209399 100644
--- a/src/test/modules/unsafe_tests/meson.build
+++ b/src/test/modules/unsafe_tests/meson.build
@@ -10,6 +10,7 @@ tests += {
'setconfig',
'alter_system_table',
'guc_privs',
+ 'truncate_heapscan',
],
'regress_args': ['--create-role=regress_authenticated_user_db_sr',
'--create-role=regress_authenticated_user_db_ssa',
diff --git a/src/test/modules/unsafe_tests/sql/truncate_heapscan.sql b/src/test/modules/unsafe_tests/sql/truncate_heapscan.sql
new file mode 100644
index 0000000..618e5a2
--- /dev/null
+++ b/src/test/modules/unsafe_tests/sql/truncate_heapscan.sql
@@ -0,0 +1,26 @@
+--
+-- TRUNCATE foreign key lookups through the heap scan of pg_constraint
+-- (ignore_system_indexes), where systable_beginscan() has to check the
+-- confrelid = ANY key itself.
+--
+CREATE TABLE trunc_isi_a (id int PRIMARY KEY) PARTITION BY RANGE (id);
+CREATE TABLE trunc_isi_a1 PARTITION OF trunc_isi_a FOR VALUES FROM (0) TO (10);
+CREATE TABLE trunc_isi_b (id int PRIMARY KEY, a int REFERENCES trunc_isi_a)
+ PARTITION BY RANGE (id);
+CREATE TABLE trunc_isi_b1 PARTITION OF trunc_isi_b FOR VALUES FROM (0) TO (10);
+CREATE TABLE trunc_isi_c (b int REFERENCES trunc_isi_b);
+INSERT INTO trunc_isi_a VALUES (1);
+INSERT INTO trunc_isi_b VALUES (1, 1);
+INSERT INTO trunc_isi_c VALUES (1);
+-- ignore_system_indexes only takes effect at connection start. Only SHOW,
+-- the TRUNCATEs and a count run with it: DDL may use an index anyway and
+-- warn.
+\c -reuse-previous=on "options=-cignore_system_indexes=on"
+SHOW ignore_system_indexes;
+TRUNCATE trunc_isi_a1, trunc_isi_b1; -- fail
+TRUNCATE trunc_isi_a1 CASCADE;
+SELECT (SELECT count(*) FROM trunc_isi_a) + (SELECT count(*) FROM trunc_isi_b) +
+ (SELECT count(*) FROM trunc_isi_c) AS rows_left;
+\c -reuse-previous=on "options="
+SHOW ignore_system_indexes;
+DROP TABLE trunc_isi_a, trunc_isi_b, trunc_isi_c;
--
2.56.1
heap_truncate_find_FKs() with confrelid = ANY: measurements
===========================================================
CPU instructions in user space (perf stat) of a single-user backend,
fsync off; 3 runs per build in rotated order; median, and the min-max
of the runs (in M) at the right. Builds: gcc -O2 -g, no cassert.
m: 77bba54 doc: Fix link to TCL project
p: 871e054 Use the confrelid index in heap_truncate_find_FKs()
a: cd80160 Avoid repeated foreign key lookups in TRUNCATE CASCADE
n: 741ff54 MEASUREMENT ONLY: one confrelid index probe per relation in he
m = master; p = m + v1-0001..0003 ("patched"); a = m + v1-0001 only
("0001 only", the CASCADE change); n = m + v1-0001 + one confrelid
index probe per relation in heap_truncate_find_FKs() instead of
0002+0003 ("probes"; the alternative that needs no genam.c change,
not proposed, measured for comparison).
Every figure is net of a control: sections 1-2 subtract a run with
fewer repetitions or with FK-less tables (below); sections 3-4
subtract a session that runs SELECT 1 the same number of times
(backend start-up, stats flush and counter queries).
Scripts: build.sh.txt, counts.sh.txt (driver), fk-lookup-counts.sh.txt
(setups and measuring stages), mk_measurements.py.txt (this file);
drop the .txt suffix to run them.
1. Commit with ON COMMIT DELETE ROWS tables
-------------------------------------------
N temporary tables, each with a trigger (without one, the FK lookup
does not run at all); every commit truncates them. Per commit:
(100 commits - 10 commits) / 90. K = 0 is a fresh database (194
pg_constraint rows); with K, the catalog of section 2 (K + 2 FKs).
cell master patched change runs: master / patched
N=1 K=0 0.14M 0.10M -25.9% 0.13-0.14 / 0.10-0.10
N=100 K=0 3.48M 3.51M +1.0% 3.47-3.49 / 3.51-3.51
N=1000 K=0 33.90M 34.83M +2.7% 33.88-33.99 / 34.78-34.88
N=100 K=1000 4.21M 3.52M -16.5% 4.19-4.22 / 3.50-3.52
N=1000 K=1000 39.12M 34.83M -11.0% 39.02-39.23 / 34.73-34.85
N=100 K=10000 10.81M 3.53M -67.4% 10.81-10.82 / 3.52-3.54
N=1000 K=10000 86.25M 34.93M -59.5% 86.20-86.29 / 34.93-34.97
N=100 K=100000 76.69M 3.52M -95.4% 76.69-76.70 / 3.51-3.54
N=1000 K=100000 557.21M 34.91M -93.7% 557.20-557.22 / 34.91-34.97
cell master probes change runs: master / probes
N=1 K=0 0.14M 0.10M -26.7% 0.13-0.14 / 0.10-0.10
N=100 K=0 3.48M 4.12M +18.5% 3.47-3.49 / 4.11-4.12
N=1000 K=0 33.90M 41.31M +21.8% 33.88-33.99 / 41.09-41.99
N=100 K=1000 4.21M 4.08M -3.2% 4.19-4.22 / 4.06-4.08
N=1000 K=1000 39.12M 38.97M -0.4% 39.02-39.23 / 38.72-41.16
N=100 K=10000 10.81M 4.26M -60.6% 10.81-10.82 / 4.26-4.32
N=1000 K=10000 86.25M 41.35M -52.1% 86.20-86.29 / 40.40-42.45
N=100 K=100000 76.69M 4.31M -94.4% 76.69-76.70 / 4.28-4.33
N=1000 K=100000 557.21M 41.93M -92.5% 557.20-557.22 / 40.73-41.99
2. TRUNCATE in a catalog with many other FKs
--------------------------------------------
old_pk/old_fk, then K FKs between other tables, then new_pk/new_fk;
100 x TRUNCATE old_pk, old_fk, new_pk, new_fk, minus 100 x TRUNCATE
of four plain tables (no index, no trigger), per TRUNCATE. So it is
the FK lookup plus truncating two PK indexes; the lookup is what
changes.
cell master patched change runs: master / patched
K=1000 1.22M 0.94M -23.2% 1.21-1.22 / 0.93-0.94
K=10000 3.56M 0.99M -72.2% 3.56-3.56 / 0.99-0.99
K=100000 26.45M 1.02M -96.1% 26.44-26.45 / 1.02-1.03
cell master probes change runs: master / probes
K=1000 1.22M 0.95M -21.9% 1.21-1.22 / 0.95-0.96
K=10000 3.56M 1.00M -71.8% 3.56-3.56 / 1.00-1.01
K=100000 26.45M 1.04M -96.1% 26.44-26.45 / 1.04-1.04
3. TRUNCATE ... CASCADE
-----------------------
Fresh database, per TRUNCATE. chain: c1 <- c2 <- ... <- cN, TRUNCATE
c1 CASCADE. wide: N tables reference w0, TRUNCATE w0 CASCADE.
pp: partitioned table with 100 partitions, referenced by 10 tables;
TRUNCATE pp CASCADE, and TRUNCATE pp_1 CASCADE (one partition).
chain master patched change runs: master / patched
N=10 7.96M 7.66M -3.7% 7.96-7.99 / 7.62-7.78
N=100 71.06M 57.15M -19.6% 70.99-71.11 / 57.09-57.31
N=1000 3990.78M 637.02M -84.0% 3990.7-4056.0 / 599.58-663.40
chain master 0001 only change runs: master / 0001 only
N=10 7.96M 7.88M -1.0% 7.96-7.99 / 7.84-7.96
N=100 71.06M 68.46M -3.7% 70.99-71.11 / 68.41-73.53
N=1000 3990.78M 1486.45M -62.8% 3990.7-4056.0 / 1486.2-1523.0
wide master patched change runs: master / patched
N=1000 591.72M 612.02M +3.4% 583.58-632.56 / 585.36-634.61
wide master 0001 only change runs: master / 0001 only
N=1000 591.72M 589.12M -0.4% 583.58-632.56 / 588.99-626.43
pp master patched change runs: master / patched
P=100 Q=10 69.52M 69.51M -0.0% 69.31-69.64 / 69.19-69.53
pp master 0001 only change runs: master / 0001 only
P=100 Q=10 69.52M 68.50M -1.5% 69.31-69.64 / 68.40-72.78
pp_1 master patched change runs: master / patched
P=100 Q=10 6.15M 4.50M -26.8% 6.14-6.16 / 4.46-4.61
pp_1 master 0001 only change runs: master / 0001 only
P=100 Q=10 6.15M 5.63M -8.5% 6.14-6.16 / 5.58-5.67
4. Other shapes, fresh database, per statement
----------------------------------------------
list: TRUNCATE of N tables with a trigger in one statement.
err: TRUNCATE of 100 tables that fails on the last one (error path).
list master patched change runs: master / patched
N=1 0.56M 0.52M -6.4% 0.56-0.56 / 0.52-0.53
N=10 3.52M 3.49M -0.7% 3.51-3.52 / 3.49-3.51
N=100 25.20M 25.10M -0.4% 25.19-25.22 / 25.09-25.14
N=1000 251.23M 251.91M +0.3% 251.04-251.33 / 251.57-256.64
list master probes change runs: master / probes
N=1 0.56M 0.53M -5.5% 0.56-0.56 / 0.51-0.53
N=10 3.52M 3.55M +0.9% 3.51-3.52 / 3.55-3.55
N=100 25.20M 25.73M +2.1% 25.19-25.22 / 25.72-26.10
N=1000 251.23M 258.13M +2.7% 251.04-251.33 / 258.04-282.24
err master patched change runs: master / patched
N=100 13.54M 4.69M -65.4% 13.53-13.54 / 4.68-4.70
err master probes change runs: master / probes
N=100 13.54M 5.16M -61.8% 13.53-13.54 / 5.16-5.17
5. Run-to-run variation
-----------------------
Cells whose min-max ranges overlap with master, read as no change:
cell N=1000 K=1000 (probes), chain N=100 (0001 only), wide N=1000, wide
N=1000 (0001 only), pp P=100 Q=10, pp P=100 Q=10 (0001 only).
In every other cell the ranges do not overlap.
#!/usr/bin/env bash
# Production builds (-O2 -g, no cassert, gcc via configure) for counts.sh.
# build.sh <name>=<source tree> ... e.g. build.sh m=$HOME/src/master
p=$HOME/src/patched
# Each is built out of tree in $R/b-<name> and installed in $R/i-<name>.
# R=<dir> default ~/lab-pg/ctr
set -uo pipefail
R=${R:-$HOME/lab-pg/ctr}; mkdir -p "$R"
for arg in "$@"; do
n=${arg%%=*} src=$(realpath "${arg#*=}")
B=$R/b-$n I=$R/i-$n L=$R/log-$n
rm -rf "$B" "$I"; mkdir -p "$B"; cd "$B" || exit 1
"$src/configure" -q --prefix="$I" --without-icu --enable-debug CFLAGS='-O2
-g' \
>"$L.configure" 2>&1 || { echo "$n: configure failed"; exit 1; }
make -j8 >"$L.make" 2>&1 || { echo "$n: make failed"; exit 1; }
echo "$n: $(env GIT_CONFIG_GLOBAL=/dev/null git -C "$src" log --oneline -1 |
cut -c1-60)"
echo "$n: warnings=$(grep -c 'warning:' "$L.make")"
make -s install >/dev/null 2>&1 && echo "$n: installed $I"
done
#!/usr/bin/env bash
# Instruction counts of heap_truncate_find_FKs() callers, master (m) vs patched
(p).
# counts.sh <section>... sections: oc spread list cascade part err wide
# Needs perf and installs made by build.sh: $R/i-m (master), $R/i-p (patched)
and, if
# BUILDS includes q, $R/i-q (a partial series). They share catversion, so they
share
# each scratch catalog. 3 runs per cell, build order rotated each run.
# Output: <this dir>/../results/c-<section>.txt. The attachments are named
*.txt: drop
# that suffix (counts.sh calls fk-lookup-counts.sh next to it).
# R=<dir> installs and scratch space (default ~/lab-pg/ctr)
# BUILDS="m p n" builds to compare (default "m p")
# KS="1000 10000" catalog sizes for the spread section (default 1000 10000
100000)
# SRC_m, SRC_p... source trees, only to print their HEAD in the output
(optional)
set -euo pipefail
H=$(cd "$(dirname "$0")/.." && pwd); R=${R:-$HOME/lab-pg/ctr}; mkdir -p
"$H/results"
read -r -a V <<<"${BUILDS:-m p}"
BINS=""; CATS=""; for v in "${V[@]}"; do BINS+="$v=$R/i-$v/bin "; CATS+="$v=idx
"; done
export WORK=$R/w BINS CATS
C="bash $(dirname "$0")/fk-lookup-counts.sh"
rot() { local r=$1; shift; local a=("$@") n=$#; for i in $(seq 0 $((n-1))); do
echo "${a[$(( (i + r) % n ))]}"; done; }
head_of() { local d; eval "d=\${SRC_$1:-}"; [ -n "$d" ] && env
GIT_CONFIG_GLOBAL=/dev/null git -C "$d" log --oneline -1 | cut -c1-70 || echo
"?"; }
for SEC in "$@"; do
OUT=$H/results/c-$SEC.txt; [ "$SEC" = spread ] && [ -n "${KS:-}" ] &&
OUT=$H/results/c-spread-${KS// /-}.txt
{
echo "c $SEC builds: ${V[*]} $(date -Is)"
for v in "${V[@]}"; do echo " $v: $(head_of $v)"; done
case $SEC in
oc) $C oncommit-setup m
for N in 1 100 1000; do for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do
$C oncommit "$v" $N $r; done; done; done ;;
spread) for K in ${KS:-1000 10000 100000}; do $C spread-setup m $K
for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do $C spread "$v" $K $r;
done; done
for N in 100 1000; do for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do
$C oncommit "$v" $N $r $K; done; done; done
done ;;
list) for N in 1 10 100 1000; do $C list-setup m $N
for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do $C list "$v" $N $r;
done; done; done ;;
cascade) for N in 10 100 1000; do $C cascade-setup m $N
for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do $C cascade "$v" $N $r;
done; done; done ;;
part) $C part-setup m 100 10
for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do $C part "$v" 100 10 $r;
done; done ;;
err) $C errpath-setup m 100
for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do $C errpath "$v" 100 $r;
done; done ;;
wide) $C wide-setup m 1000
for r in 1 2 3; do for v in $(rot $r "${V[@]}"); do $C wide "$v" 1000 $r;
done; done ;;
*) echo "section?"; exit 2;;
esac
echo "END $(date -Is)"
} > "$OUT" 2>&1 || true
# a failing stage does not stop the { } group by itself, so judge the log
if grep -qE 'error|unbound|errors=' "$OUT" || ! tail -1 "$OUT" | grep -q
'^END'; then
echo "$SEC FAILED"; grep -m5 -E 'error|unbound|errors=' "$OUT"; exit 1; fi
echo "$SEC ok"
done
#!/usr/bin/env bash
# Counts, not times, for heap_truncate_find_FKs() and its callers: a single-user
# backend under perf stat (user-space instructions, event instructions:u), plus
# the pg_constraint seqscan counters and the confrelid index counter. Usually
# driven by counts.sh. Builds by name (counts.sh uses m and p, and q):
#
# BINS="m=<bindir> p=<bindir>" CATS="m=idx p=idx" (builds sharing a
catalog)
# WORK=<scratch dir>
# SBOPTS="-c ignore_system_indexes=on" (optional; counts.sh does not use
it)
#
# Every figure is net of a control: spread subtracts the same TRUNCATE on plain
# tables, oncommit takes (100 commits - 10 commits) / 90, and the other stages
# subtract a session that runs SELECT 1 as many times ("control"), so backend
# start-up, the stats flush and the counter queries cancel out.
#
# spread-setup <cat-build> <K> old table + FK, K FKs between, new table + FK
# spread <build> <K> <run> 100 x TRUNCATE old_pk, old_fk, new_pk, new_fk
# list-setup <cat-build> <N> N tables with a trigger
# list <build> <N> <run> TRUNCATE of the N tables in one statement
# cascade-setup/cascade <N> TRUNCATE c1 CASCADE down a chain of N tables
# wide-setup/wide <N> TRUNCATE w0 CASCADE, N tables reference w0
# part-setup/part <P> <Q> partitioned pp (P parts) referenced by Q
tables
# oncommit-setup <cat-build>
# oncommit <build> <N> <run> [<K>] N ON COMMIT DELETE ROWS temp tables
# with a trigger; with K, in the spread catalog of that K
# errpath-setup/errpath <N> TRUNCATE e1..eN that fails on eN
set -euo pipefail
: "${WORK:?}" "${BINS:?}" "${CATS:?}"
mkdir -p "$WORK"
lookup() { local k=$1 kv; shift; for kv in $*; do [ "${kv%%=*}" = "$k" ] && {
echo "${kv#*=}"; return; }; done
echo "unknown build $k" >&2; exit 2; }
bin() { lookup "$1" $BINS; }
cat_of() { lookup "$1" $CATS; }
instr() { awk -F, '$3 ~ /^instructions/ {print $1}' "$1"; }
val() { sed -n "s/^[[:space:]]*[0-9]*: $2 = \"\([^\"]*\)\".*/\1/p" "$1" | tail
-1; }
sb() { "$1/postgres" --single -j -D "$2" -c stats_fetch_consistency=none
${SBOPTS:-} postgres; }
newdb() {
rm -rf "$1"; "$2/initdb" -D "$1" -U postgres -A trust >/dev/null
printf 'fsync = off\nautovacuum = off\nmax_locks_per_transaction = 1024\n'
>>"$1/postgresql.conf"
}
COUNTERS="SELECT seq_scan AS SX, seq_tup_read AS TX,
coalesce((SELECT idx_tup_read FROM pg_stat_sys_indexes
WHERE indexrelname = 'pg_constraint_confrelid_index'), 0) AS IX
FROM pg_stat_sys_tables WHERE relname = 'pg_constraint';"
# measure <bin> <datadir> <out prefix> <reps> <statement> [<sql first>]:
# prints: instructions seq_scan seq_tup_read confrelid_idx_tup_read
# MEASURE_ERRORS=<n>: each statement is expected to fail, n errors in all
measure() {
local f=$3.sql c0 c1
c0=${COUNTERS//X/0}; c1=${COUNTERS//X/1}
{ [ -n "${6:-}" ] && printf '%s\n\n' "$6"
printf 'SELECT pg_stat_force_next_flush();\n\nSELECT 1;\n\n%s\n\n' "$c0"
for _ in $(seq "$4"); do printf '%s\n\n' "$5"; done
printf 'SELECT pg_stat_force_next_flush();\n\nSELECT 1;\n\n%s\n\n' "$c1"
} >"$f"
perf stat -x, -e instructions:u -o "$3.perf" -- \
"$1/postgres" --single -j -D "$2" -c stats_fetch_consistency=none
${SBOPTS:-} postgres \
<"$f" >"$3.out" 2>&1
local ne; ne=$(grep -c 'ERROR:' "$3.out" || true)
[ "$ne" = "${MEASURE_ERRORS:-0}" ] || { echo "errors=$ne"; grep -m3 'ERROR:'
"$3.out"; exit 1; }
echo "$(instr "$3.perf") $(( $(val "$3.out" s1) - $(val "$3.out" s0) ))" \
"$(( $(val "$3.out" t1) - $(val "$3.out" t0) )) $(( $(val "$3.out" i1) -
$(val "$3.out" i0) ))"
}
# control <bin> <datadir> <out prefix> <reps>: instructions of the same session
with
# SELECT 1 instead of the statement (backend start-up, stats flush, counter
queries)
control() { measure "$1" "$2" "$3-ctl" "$4" 'SELECT 1;' | cut -d' ' -f1; }
fkrows() { sb "$1" "$2" <<<"SELECT count(*) AS n, count(*) FILTER (WHERE
contype = 'f') AS f FROM pg_constraint;" 2>/dev/null |
sed -n 's/.* [nf] = "\([0-9]*\)".*/\1/p' | paste -sd/; }
case ${1:?stage} in
spread-setup)
C=${2:?}; K=${3:?}; B=$(bin "$C"); D=$WORK/spread-$(cat_of "$C")
if [ ! -d "$D" ]; then
newdb "$D" "$B"
sb "$B" "$D" >/dev/null <<'SQL'
CREATE TABLE old_pk (id int PRIMARY KEY);
CREATE TABLE old_fk (id int REFERENCES old_pk);
CREATE TABLE plain1 (id int);
CREATE TABLE plain2 (id int);
CREATE TABLE plain3 (id int);
CREATE TABLE plain4 (id int);
SQL
fi
have=$(sb "$B" "$D" <<<"SELECT count(*) AS n FROM pg_class WHERE relkind =
'r' AND relname LIKE 'mid\_%';" 2>/dev/null |
sed -n 's/.*n = "\([0-9]*\)".*/\1/p')
# one referenced table per 100 foreign keys; each gets 100 FKs from its own
table
for j in $(seq $((have + 1)) $((K / 100))); do
printf 'CREATE TABLE mid_%s (id int PRIMARY KEY);\n\n' "$j"
printf 'CREATE TABLE ref_%s (%s);\n\n' "$j" \
"$(seq -s, -f "c%g int REFERENCES mid_$j" 1 100 | sed 's/,$//')"
done | sb "$B" "$D" >/dev/null
sb "$B" "$D" >/dev/null <<'SQL'
DROP TABLE IF EXISTS new_fk, new_pk;
CREATE TABLE new_pk (id int PRIMARY KEY);
CREATE TABLE new_fk (id int REFERENCES new_pk);
SQL
echo "spread-setup $(cat_of "$C") K=$K pg_constraint rows/fk=$(fkrows "$B"
"$D")"
;;
spread)
S=${2:?}; K=${3:?}; R=${4:?}; B=$(bin "$S"); D=$WORK/spread-$(cat_of "$S");
O=$WORK/sp-$S-$K-$R
set -- $(measure "$B" "$D" "$O-fk" 100 'TRUNCATE old_pk, old_fk, new_pk,
new_fk;') \
$(measure "$B" "$D" "$O-plain" 100 'TRUNCATE plain1, plain2, plain3,
plain4;')
echo "spread $S K=$K run=$R x100 TRUNCATE old+new: instructions=$1
seq_scan=$2" \
"seq_tup_read=$3 confrelid_idx_tup_read=$4; control: instructions=$5;" \
"lookup per TRUNCATE=$(( ($1 - $5) / 100 ))"
;;
list-setup)
C=${2:?}; N=${3:?}; B=$(bin "$C"); D=$WORK/list-$(cat_of "$C")-$N
newdb "$D" "$B"
{ printf 'CREATE FUNCTION f() RETURNS trigger LANGUAGE plpgsql AS $$BEGIN
RETURN NEW; END$$;\n\n'
for i in $(seq "$N"); do
printf 'CREATE TABLE t%s (id int);\n\nCREATE TRIGGER g BEFORE INSERT ON
t%s FOR EACH ROW EXECUTE FUNCTION f();\n\n' "$i" "$i"
done; } | sb "$B" "$D" >/dev/null
echo "list-setup $(cat_of "$C") N=$N pg_constraint rows/fk=$(fkrows "$B"
"$D")"
;;
list)
S=${2:?}; N=${3:?}; R=${4:?}; B=$(bin "$S"); D=$WORK/list-$(cat_of "$S")-$N;
O=$WORK/li-$S-$N-$R
reps=100; [ "$N" -ge 1000 ] && reps=10
ctl=$(control "$B" "$D" "$O" $reps)
set -- $(measure "$B" "$D" "$O-trg" $reps "TRUNCATE $(seq -s, -f 't%g' 1 "$N"
| sed 's/,$//');")
echo "list $S N=$N run=$R x$reps TRUNCATE: instructions=$1 seq_tup_read=$3" \
"confrelid_idx_tup_read=$4; control: instructions=$ctl;" \
"net per TRUNCATE=$(( ($1 - ctl) / reps ))"
;;
cascade-setup)
C=${2:?}; N=${3:?}; B=$(bin "$C"); D=$WORK/cascade-$(cat_of "$C")-$N
newdb "$D" "$B"
{ printf 'CREATE TABLE c1 (id int PRIMARY KEY);\n\n'
for i in $(seq 2 "$N"); do
printf 'CREATE TABLE c%s (id int PRIMARY KEY, p int REFERENCES c%s);\n\n'
"$i" $((i - 1))
done; } | sb "$B" "$D" >/dev/null
echo "cascade-setup $(cat_of "$C") N=$N pg_constraint rows/fk=$(fkrows "$B"
"$D")"
;;
cascade)
S=${2:?}; N=${3:?}; R=${4:?}; B=$(bin "$S"); D=$WORK/cascade-$(cat_of
"$S")-$N; O=$WORK/ca-$S-$N-$R
ctl=$(control "$B" "$D" "$O" 3)
set -- $(measure "$B" "$D" "$O" 3 'TRUNCATE c1 CASCADE;')
left=$({ printf 'INSERT INTO c1 VALUES (1);\n\n'
for i in $(seq 2 "$N"); do printf 'INSERT INTO c%s VALUES (1,
1);\n\n' "$i"; done
printf 'TRUNCATE c1 CASCADE;\n\nSELECT %s AS left_rows;\n\n' \
"$(seq -s+ -f '(SELECT count(*) FROM c%g)' 1 "$N")"; } |
sb "$B" "$D" 2>/dev/null | sed -n 's/.*left_rows =
"\([0-9]*\)".*/\1/p')
echo "cascade $S N=$N run=$R x3 TRUNCATE c1 CASCADE (chain of $N tables):" \
"instructions=$1 seq_scan=$2 seq_tup_read=$3 confrelid_idx_tup_read=$4;"
\
"per TRUNCATE=$(( $1 / 3 )); control: instructions=$ctl;" \
"net per TRUNCATE=$(( ($1 - ctl) / 3 )); rows left after one more=$left"
;;
wide-setup)
C=${2:?}; N=${3:?}; B=$(bin "$C"); D=$WORK/wide-$(cat_of "$C")-$N
newdb "$D" "$B"
{ printf 'CREATE TABLE w0 (id int PRIMARY KEY);\n\n'
for i in $(seq "$N"); do
printf 'CREATE TABLE w%s (id int PRIMARY KEY, p int REFERENCES w0);\n\n'
"$i"
done; } | sb "$B" "$D" >/dev/null
echo "wide-setup $(cat_of "$C") N=$N pg_constraint rows/fk=$(fkrows "$B"
"$D")"
;;
wide)
S=${2:?}; N=${3:?}; R=${4:?}; B=$(bin "$S"); D=$WORK/wide-$(cat_of "$S")-$N;
O=$WORK/wi-$S-$N-$R
ctl=$(control "$B" "$D" "$O" 3)
set -- $(measure "$B" "$D" "$O" 3 'TRUNCATE w0 CASCADE;')
left=$({ printf 'INSERT INTO w0 VALUES (1);\n\n'
for i in $(seq "$N"); do printf 'INSERT INTO w%s VALUES (1, 1);\n\n'
"$i"; done
printf 'TRUNCATE w0 CASCADE;\n\nSELECT %s AS left_rows;\n\n' \
"$(seq -s+ -f '(SELECT count(*) FROM w%g)' 0 "$N")"; } |
sb "$B" "$D" 2>/dev/null | sed -n 's/.*left_rows =
"\([0-9]*\)".*/\1/p')
echo "wide $S N=$N run=$R x3 TRUNCATE w0 CASCADE ($N tables reference w0):" \
"instructions=$1 seq_scan=$2 seq_tup_read=$3 confrelid_idx_tup_read=$4;"
\
"per TRUNCATE=$(( $1 / 3 )); control: instructions=$ctl;" \
"net per TRUNCATE=$(( ($1 - ctl) / 3 )); rows left after one more=$left"
;;
part-setup)
# pp partitioned in P partitions, referenced by Q tables: every FK has a
# row per partition with conparentid set, which is what makes
# heap_truncate_find_FKs() climb to the parent and restart
C=${2:?}; P=${3:?}; Q=${4:?}; B=$(bin "$C"); D=$WORK/part-$(cat_of "$C")-$P-$Q
newdb "$D" "$B"
{ printf 'CREATE TABLE pp (id int PRIMARY KEY) PARTITION BY RANGE (id);\n\n'
for i in $(seq "$P"); do
printf 'CREATE TABLE pp_%s PARTITION OF pp FOR VALUES FROM (%s) TO
(%s);\n\n' \
"$i" $(( i * 10 )) $(( i * 10 + 10 ))
done
for j in $(seq "$Q"); do
printf 'CREATE TABLE pr_%s (id int, p int REFERENCES pp);\n\n' "$j"
done; } | sb "$B" "$D" >/dev/null
echo "part-setup $(cat_of "$C") P=$P Q=$Q pg_constraint rows/fk=$(fkrows "$B"
"$D")"
;;
part)
S=${2:?}; P=${3:?}; Q=${4:?}; R=${5:?}; B=$(bin "$S"); D=$WORK/part-$(cat_of
"$S")-$P-$Q
O=$WORK/pa-$S-$P-$Q-$R
ctl=$(control "$B" "$D" "$O" 3)
set -- $(measure "$B" "$D" "$O-all" 3 'TRUNCATE pp CASCADE;') \
$(measure "$B" "$D" "$O-one" 3 'TRUNCATE pp_1 CASCADE;')
left=$({ printf 'INSERT INTO pp VALUES (10);\n\n'
for j in $(seq "$Q"); do printf 'INSERT INTO pr_%s VALUES (1,
10);\n\n' "$j"; done
printf 'TRUNCATE pp_1 CASCADE;\n\nSELECT %s AS left_rows;\n\n' \
"(SELECT count(*) FROM pp)+$(seq -s+ -f '(SELECT count(*) FROM
pr_%g)' 1 "$Q")"; } |
sb "$B" "$D" 2>/dev/null | sed -n 's/.*left_rows =
"\([0-9]*\)".*/\1/p')
echo "part $S P=$P Q=$Q run=$R x3 TRUNCATE pp CASCADE: instructions=$1
seq_scan=$2" \
"seq_tup_read=$3 confrelid_idx_tup_read=$4; x3 TRUNCATE pp_1 CASCADE:" \
"instructions=$5 seq_scan=$6 seq_tup_read=$7 confrelid_idx_tup_read=$8;"
\
"control: instructions=$ctl; net per TRUNCATE pp=$(( ($1 - ctl) / 3 ))" \
"pp_1=$(( ($5 - ctl) / 3 )); rows left after one more=$left"
;;
oncommit-setup)
C=${2:?}; B=$(bin "$C"); D=$WORK/oc-$(cat_of "$C")
newdb "$D" "$B"
sb "$B" "$D" >/dev/null <<'SQL'
CREATE FUNCTION f() RETURNS trigger LANGUAGE plpgsql AS $$BEGIN RETURN NEW;
END$$;
SQL
echo "oncommit-setup $(cat_of "$C") pg_constraint rows/fk=$(fkrows "$B" "$D")"
;;
oncommit)
# N ON COMMIT DELETE ROWS temp tables with a trigger, all truncated at
# every commit that touches temp tables; per commit = (100 - 10) commits
S=${2:?}; N=${3:?}; R=${4:?}; K=${5:-}; B=$(bin "$S")
if [ -n "$K" ]; then D=$WORK/spread-$(cat_of "$S"); else D=$WORK/oc-$(cat_of
"$S"); fi
O=$WORK/oc-$S-$N-$R-${K:-0}
mk=$( [ -n "$K" ] && printf 'CREATE OR REPLACE FUNCTION f() RETURNS trigger
LANGUAGE plpgsql AS $$BEGIN RETURN NEW; END$$;\n\n'
for i in $(seq "$N"); do
printf 'CREATE TEMP TABLE tt%s (a int) ON COMMIT DELETE ROWS;\n\n' "$i"
printf 'CREATE TRIGGER g BEFORE INSERT ON tt%s FOR EACH ROW EXECUTE
FUNCTION f();\n\n' "$i"
done)
set -- $(measure "$B" "$D" "$O-100" 100 'INSERT INTO tt1 VALUES (1);' "$mk") \
$(measure "$B" "$D" "$O-10" 10 'INSERT INTO tt1 VALUES (1);' "$mk")
echo "oncommit $S N=$N K=${K:-0} run=$R: x100 instructions=$1 seq_scan=$2
seq_tup_read=$3" \
"confrelid_idx_tup_read=$4; x10 instructions=$5;" \
"per commit=$(( ($1 - $5) / 90 ))"
;;
errpath-setup)
# e1..eN with a trigger each; eN referenced by ex from outside the list
C=${2:?}; N=${3:?}; B=$(bin "$C"); D=$WORK/err-$(cat_of "$C")-$N
newdb "$D" "$B"
{ printf 'CREATE FUNCTION f() RETURNS trigger LANGUAGE plpgsql AS $$BEGIN
RETURN NEW; END$$;\n\n'
for i in $(seq "$N"); do
printf 'CREATE TABLE e%s (id int PRIMARY KEY);\n\nCREATE TRIGGER g BEFORE
INSERT ON e%s FOR EACH ROW EXECUTE FUNCTION f();\n\n' "$i" "$i"
done
printf 'CREATE TABLE ex (id int REFERENCES e%s);\n\n' "$N"; } | sb "$B"
"$D" >/dev/null
echo "errpath-setup $(cat_of "$C") N=$N pg_constraint rows/fk=$(fkrows "$B"
"$D")"
;;
errpath)
# TRUNCATE e1..eN fails on eN, the last one heap_truncate_check_FKs() tries
S=${2:?}; N=${3:?}; R=${4:?}; B=$(bin "$S"); D=$WORK/err-$(cat_of "$S")-$N;
O=$WORK/er-$S-$N-$R
ctl=$(control "$B" "$D" "$O" 10)
set -- $(MEASURE_ERRORS=10 measure "$B" "$D" "$O" 10 \
"TRUNCATE $(seq -s, -f 'e%g' 1 "$N" | sed 's/,$//');")
echo "errpath $S N=$N run=$R x10 failing TRUNCATE: instructions=$1
seq_scan=$2" \
"seq_tup_read=$3 confrelid_idx_tup_read=$4; per TRUNCATE=$(( $1 / 10
));" \
"control: instructions=$ctl; net per TRUNCATE=$(( ($1 - ctl) / 10 ))"
;;
*) echo "stage?"; exit 2;;
esac
#!/usr/bin/env python3
"""Write measurements.txt from results/c-*.txt (the output of counts.sh).
mk_measurements.py <output file>
Medians of the 3 runs per cell; every number comes from the result files."""
import glob, os, re, statistics as st, sys, textwrap
H = os.path.join(os.path.dirname(os.path.abspath(__file__)), '..')
R = os.path.join(H, 'results')
FILES = sorted(glob.glob(os.path.join(R, 'c-*.txt')))
TEXT = ''.join(open(f).read() for f in FILES)
OVERLAP = []
NAMES = {'p': 'patched', 'n': 'probes', 'a': '0001 only'}
def heads():
seen = {}
for f in FILES:
for l in open(f).read().splitlines()[1:5]:
m = re.match(r'\s+(\w): (.*)', l)
if m:
seen.setdefault(m.group(1), m.group(2))
return [f' {k}: {seen[k]}' for k in ('m', 'p', 'a', 'n') if k in seen]
def cells(kre, vre):
out = {}
for line in TEXT.splitlines():
k, v = re.search(kre, line), re.search(vre, line)
if k and v:
out.setdefault(k.group(2), {}).setdefault(k.group(1),
[]).append(int(v.group(1)))
return out
def mm(x):
return f'{x / 1e6:.2f}M'
def rr(x):
return f'{x / 1e6:.1f}' if x >= 1e9 else f'{x / 1e6:.2f}'
def block(title, desc, kre, vre, label, pb='p'):
pname = NAMES[pb]
o = ([title, '-' * len(title)] if title else []) + desc
o += ['', f'{label:16} {"master":>10} {pname:>10} {"change":>7} runs:
master / {pname}']
for cell, d in cells(kre, vre).items():
m, p = d['m'], d[pb]
assert len(m) == 3 and len(p) == 3, (title, cell, pb)
a, b = st.median(m), st.median(p)
if max(min(m), min(p)) <= min(max(m), max(p)):
OVERLAP.append(f'{label} {cell}' + ('' if pb == 'p' else f'
({pname})'))
o.append(f'{cell:16} {mm(a):>10} {mm(b):>10} {100 * (b - a) / a:+6.1f}%
'
f'{rr(min(m))}-{rr(max(m))} / {rr(min(p))}-{rr(max(p))}')
return o + ['']
OC = (r'^oncommit (\w) (N=\d+ K=\d+) run=\d', r'per commit=(\d+)')
SP = (r'^spread (\w) (K=\d+) run=\d', r'lookup per TRUNCATE=(\d+)')
L = ['heap_truncate_find_FKs() with confrelid = ANY: measurements', '=' * 59,
'',
'CPU instructions in user space (perf stat) of a single-user backend,',
'fsync off; 3 runs per build in rotated order; median, and the min-max',
'of the runs (in M) at the right. Builds: gcc -O2 -g, no cassert.'] +
heads() + [
'm = master; p = m + v1-0001..0003 ("patched"); a = m + v1-0001 only',
'("0001 only", the CASCADE change); n = m + v1-0001 + one confrelid',
'index probe per relation in heap_truncate_find_FKs() instead of',
'0002+0003 ("probes"; the alternative that needs no genam.c change,',
'not proposed, measured for comparison).',
'Every figure is net of a control: sections 1-2 subtract a run with',
'fewer repetitions or with FK-less tables (below); sections 3-4',
'subtract a session that runs SELECT 1 the same number of times',
'(backend start-up, stats flush and counter queries).',
'Scripts: build.sh.txt, counts.sh.txt (driver), fk-lookup-counts.sh.txt',
'(setups and measuring stages), mk_measurements.py.txt (this file);',
'drop the .txt suffix to run them.', '', '']
L += block('1. Commit with ON COMMIT DELETE ROWS tables', [
'N temporary tables, each with a trigger (without one, the FK lookup',
'does not run at all); every commit truncates them. Per commit:',
'(100 commits - 10 commits) / 90. K = 0 is a fresh database (194',
'pg_constraint rows); with K, the catalog of section 2 (K + 2 FKs).'], *OC,
'cell')
L += block('', [], *OC, 'cell', 'n') + ['']
L += block('2. TRUNCATE in a catalog with many other FKs', [
'old_pk/old_fk, then K FKs between other tables, then new_pk/new_fk;',
'100 x TRUNCATE old_pk, old_fk, new_pk, new_fk, minus 100 x TRUNCATE',
'of four plain tables (no index, no trigger), per TRUNCATE. So it is',
'the FK lookup plus truncating two PK indexes; the lookup is what',
'changes.'], *SP, 'cell')
L += block('', [], *SP, 'cell', 'n') + ['']
L += block('3. TRUNCATE ... CASCADE', [
'Fresh database, per TRUNCATE. chain: c1 <- c2 <- ... <- cN, TRUNCATE',
'c1 CASCADE. wide: N tables reference w0, TRUNCATE w0 CASCADE.',
'pp: partitioned table with 100 partitions, referenced by 10 tables;',
'TRUNCATE pp CASCADE, and TRUNCATE pp_1 CASCADE (one partition).'],
r'^cascade (\w) (N=\d+) run=\d', r'net per TRUNCATE=(\d+)', 'chain')
L += block('', [], r'^cascade (\w) (N=\d+) run=\d', r'net per TRUNCATE=(\d+)',
'chain', 'a')
for lab, kre, vre in (('wide', r'^wide (\w) (N=\d+) run=\d', r'net per
TRUNCATE=(\d+)'),
('pp', r'^part (\w) (P=\d+ Q=\d+) run=\d', r'net per
TRUNCATE pp=(\d+)'),
('pp_1', r'^part (\w) (P=\d+ Q=\d+) run=\d', r'
pp_1=(\d+)')):
L += block('', [], kre, vre, lab) + block('', [], kre, vre, lab, 'a')
L += ['']
L += block('4. Other shapes, fresh database, per statement', [
'list: TRUNCATE of N tables with a trigger in one statement.',
'err: TRUNCATE of 100 tables that fails on the last one (error path).'],
r'^list (\w) (N=\d+) run=\d', r'net per TRUNCATE=(\d+)', 'list')
L += block('', [], r'^list (\w) (N=\d+) run=\d', r'net per TRUNCATE=(\d+)',
'list', 'n')
L += block('', [], r'^errpath (\w) (N=\d+) run=\d', r'net per TRUNCATE=(\d+)',
'err')
L += block('', [], r'^errpath (\w) (N=\d+) run=\d', r'net per TRUNCATE=(\d+)',
'err', 'n') + ['']
L += ['5. Run-to-run variation', '-' * 23,
'Cells whose min-max ranges overlap with master, read as no change:',
*textwrap.wrap((', '.join(OVERLAP) if OVERLAP else 'none') + '.', 72),
'In every other cell the ranges do not overlap.']
out = '\n'.join(L).rstrip() + '\n'
while '\n\n\n' in out:
out = out.replace('\n\n\n', '\n\n')
out = re.sub(r'\n\n(\d\. )', r'\n\n\n\1', out)
open(sys.argv[1], 'w').write(out)