Sort the dependent objects before recursing in findDependentObjects().

Historically, the notices output by DROP CASCADE tended to come out
in uncertain order, and in some cases you might get different claims
about which object depends on which other one.  This is because we
just traversed the dependency tree in the order in which pg_depend
entries are seen, and nbtree has never promised anything about the
order of equal-keyed index entries.  We've put up with that for years,
hacking regression tests when necessary to prevent them from emitting
unstable output.  However, it's a problem for pending work that will
change nbtree's behavior for equal keys, as that causes unexpected
changes in the regression test results.

Hence, adjust findDependentObjects to sort the results of each
indexscan before processing them.  The sort is on descending OID of
the dependent objects, hence more or less reverse creation order.
While this rule could still result in bogus regression test failures
if an OID wraparound occurred mid-test, that seems unlikely to happen
in any plausible development or packaging-test scenario.

This is enough to ensure output stability for ordinary DROP CASCADE
commands, but not for DROP OWNED BY, because that has a different
code path with the same problem.  We might later choose to sort in
the DROP OWNED BY code as well, but this patch doesn't do so.

I've also not done anything about reverting the existing hacks to
suppress unstable DROP CASCADE output in specific regression tests.
It might be worth undoing those, but it seems like a distinct question.

The first indexscan loop in findDependentObjects is not touched,
meaning there is a hazard of unstable error reports from that too.
However, said hazard is not the fault of that code: it was designed
on the assumption that there could be at most one "owning" object
to complain about, and that assumption does not seem unreasonable.
The recent patch that added the possibility of multiple
DEPENDENCY_INTERNAL_AUTO links broke that assumption, but we should
fix that situation not band-aid around it.  That's a matter for
another patch, though.

Discussion: https://postgr.es/m/12244.1547854440@sss.pgh.pa.us

1 files changed, 85 insertions, 15 deletions

diff --git a/src/backend/catalog/dependency.c b/src/backend/catalog/dependency.c
index 6b8c7357e1d..2e3579ddf33 100644
--- a/src/backend/catalog/dependency.c
+++ b/src/backend/catalog/dependency.c
@@ -124,6 +124,13 @@ typedef struct ObjectAddressStack
 	struct ObjectAddressStack *next;	/* next outer stack level */
 } ObjectAddressStack;
 
+/* temporary storage in findDependentObjects */
+typedef struct
+{
+	ObjectAddress obj;			/* object to be deleted --- MUST BE FIRST */
+	int			subflags;		/* flags to pass down when recursing to obj */
+} ObjectAddressAndFlags;
+
 /* for find_expr_references_walker */
 typedef struct
 {
@@ -472,6 +479,9 @@ findDependentObjects(const ObjectAddress *object,
 	SysScanDesc scan;
 	HeapTuple	tup;
 	ObjectAddress otherObject;
+	ObjectAddressAndFlags *dependentObjects;
+	int			numDependentObjects;
+	int			maxDependentObjects;
 	ObjectAddressStack mystack;
 	ObjectAddressExtra extra;
 
@@ -704,12 +714,17 @@ findDependentObjects(const ObjectAddress *object,
 	systable_endscan(scan);
 
 	/*
-	 * Now recurse to any dependent objects.  We must visit them first since
-	 * they have to be deleted before the current object.
+	 * Next, identify all objects that directly depend on the current object.
+	 * To ensure predictable deletion order, we collect them up in
+	 * dependentObjects and sort the list before actually recursing.  (The
+	 * deletion order would be valid in any case, but doing this ensures
+	 * consistent output from DROP CASCADE commands, which is helpful for
+	 * regression testing.)
 	 */
-	mystack.object = object;	/* set up a new stack level */
-	mystack.flags = objflags;
-	mystack.next = stack;
+	maxDependentObjects = 128;	/* arbitrary initial allocation */
+	dependentObjects = (ObjectAddressAndFlags *)
+		palloc(maxDependentObjects * sizeof(ObjectAddressAndFlags));
+	numDependentObjects = 0;
 
 	ScanKeyInit(&key[0],
 				Anum_pg_depend_refclassid,
@@ -762,7 +777,10 @@ findDependentObjects(const ObjectAddress *object,
 			continue;
 		}
 
-		/* Recurse, passing objflags indicating the dependency type */
+		/*
+		 * We do need to delete it, so identify objflags to be passed down,
+		 * which depend on the dependency type.
+		 */
 		switch (foundDep->deptype)
 		{
 			case DEPENDENCY_NORMAL:
@@ -798,8 +816,47 @@ findDependentObjects(const ObjectAddress *object,
 				break;
 		}
 
-		findDependentObjects(&otherObject,
-							 subflags,
+		/* And add it to the pending-objects list */
+		if (numDependentObjects >= maxDependentObjects)
+		{
+			/* enlarge array if needed */
+			maxDependentObjects *= 2;
+			dependentObjects = (ObjectAddressAndFlags *)
+				repalloc(dependentObjects,
+						 maxDependentObjects * sizeof(ObjectAddressAndFlags));
+		}
+
+		dependentObjects[numDependentObjects].obj = otherObject;
+		dependentObjects[numDependentObjects].subflags = subflags;
+		numDependentObjects++;
+	}
+
+	systable_endscan(scan);
+
+	/*
+	 * Now we can sort the dependent objects into a stable visitation order.
+	 * It's safe to use object_address_comparator here since the obj field is
+	 * first within ObjectAddressAndFlags.
+	 */
+	if (numDependentObjects > 1)
+		qsort((void *) dependentObjects, numDependentObjects,
+			  sizeof(ObjectAddressAndFlags),
+			  object_address_comparator);
+
+	/*
+	 * Now recurse to the dependent objects.  We must visit them first since
+	 * they have to be deleted before the current object.
+	 */
+	mystack.object = object;	/* set up a new stack level */
+	mystack.flags = objflags;
+	mystack.next = stack;
+
+	for (int i = 0; i < numDependentObjects; i++)
+	{
+		ObjectAddressAndFlags *depObj = dependentObjects + i;
+
+		findDependentObjects(&depObj->obj,
+							 depObj->subflags,
 							 flags,
 							 &mystack,
 							 targetObjects,
@@ -807,7 +864,7 @@ findDependentObjects(const ObjectAddress *object,
 							 depRel);
 	}
 
-	systable_endscan(scan);
+	pfree(dependentObjects);
 
 	/*
 	 * Finally, we can add the target object to targetObjects.  Be careful to
@@ -2109,18 +2166,31 @@ object_address_comparator(const void *a, const void *b)
 	const ObjectAddress *obja = (const ObjectAddress *) a;
 	const ObjectAddress *objb = (const ObjectAddress *) b;
 
-	if (obja->classId < objb->classId)
+	/*
+	 * Primary sort key is OID descending.  Most of the time, this will result
+	 * in putting newer objects before older ones, which is likely to be the
+	 * right order to delete in.
+	 */
+	if (obja->objectId > objb->objectId)
 		return -1;
-	if (obja->classId > objb->classId)
-		return 1;
 	if (obja->objectId < objb->objectId)
+		return 1;
+
+	/*
+	 * Next sort on catalog ID, in case identical OIDs appear in different
+	 * catalogs.  Sort direction is pretty arbitrary here.
+	 */
+	if (obja->classId < objb->classId)
 		return -1;
-	if (obja->objectId > objb->objectId)
+	if (obja->classId > objb->classId)
 		return 1;
 
 	/*
-	 * We sort the subId as an unsigned int so that 0 will come first. See
-	 * logic in eliminate_duplicate_dependencies.
+	 * Last, sort on object subId.
+	 *
+	 * We sort the subId as an unsigned int so that 0 (the whole object) will
+	 * come first.  This is essential for eliminate_duplicate_dependencies,
+	 * and is also the best order for findDependentObjects.
 	 */
 	if ((unsigned int) obja->objectSubId < (unsigned int) objb->objectSubId)
 		return -1;