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)

Reply via email to