Re: pgsql: Make heap TID a tiebreaker nbtree index column.

I wrote:
> Yeah.  My opinion is that we should just qsort the list of targets
> during DROP OWNED and be done with this.  I'll post a patch shortly.

Here's one way we could do this: add a flag to performMultipleDeletions
to invoke the sort.  A small problem with it is that if we sort the
ObjectAddresses in-place as this does, we really oughta remove the
"const" from that argument.  (I believe compilers would probably not
realize we were cheating if we didn't, but it'd still be cheating.)
That doesn't affect any existing callers, but in future it might
prevent const-ifying something or other.  Another way we could handle
this is to make dependency.c expose a separate function
"void sortObjectAddresses(ObjectAddresses *objects)", and then have
callers call that as a separate action.  Not sure which I like better
... any opinions?

A preliminary check-world run finds no places where the output changes,
but I've not tried this with SELinux yet.

            regards, tom lane

diff --git a/src/backend/catalog/dependency.c b/src/backend/catalog/dependency.c
index 2048d71..7a969d1 100644
--- a/src/backend/catalog/dependency.c
+++ b/src/backend/catalog/dependency.c
@@ -365,9 +365,17 @@ performDeletion(const ObjectAddress *object,
  * list of objects that would be implicitly dropped, for each object to be
  * dropped, is the union of the implicit-object list for all objects.  This
  * makes each check be more relaxed.
+ *
+ * Also, this honors one additional flags bit:
+ *
+ * PERFORM_DELETION_SORTEDLY: sort the objects before beginning deletion.
+ * The major sort key is OID-descending, so that newer objects will be deleted
+ * first in most cases.  This is primarily useful for ensuring stable outputs
+ * from regression tests; it's not recommended if the order of the objects is
+ * determined by user input, such as the order of targets in a DROP command.
  */
 void
-performMultipleDeletions(const ObjectAddresses *objects,
+performMultipleDeletions(ObjectAddresses *objects,
                          DropBehavior behavior, int flags)
 {
     Relation    depRel;
@@ -378,6 +386,12 @@ performMultipleDeletions(const ObjectAddresses *objects,
     if (objects->numrefs <= 0)
         return;

+    /* Presort objects if requested */
+    if ((flags & PERFORM_DELETION_SORTEDLY) && objects->numrefs > 1)
+        qsort((void *) objects->refs, objects->numrefs,
+              sizeof(ObjectAddress),
+              object_address_comparator);
+
     /*
      * We save some cycles by opening pg_depend just once and passing the
      * Relation pointer down to all the recursive deletion steps.
diff --git a/src/backend/catalog/pg_shdepend.c b/src/backend/catalog/pg_shdepend.c
index 1619c1c..dbd1d4b 100644
--- a/src/backend/catalog/pg_shdepend.c
+++ b/src/backend/catalog/pg_shdepend.c
@@ -1266,8 +1266,12 @@ shdepDropOwned(List *roleids, DropBehavior behavior)
         systable_endscan(scan);
     }

-    /* the dependency mechanism does the actual work */
-    performMultipleDeletions(deleteobjs, behavior, 0);
+    /*
+     * The dependency mechanism does the actual work.  For stability of
+     * output, sort the objects into approximate reverse creation order
+     * beforehand.
+     */
+    performMultipleDeletions(deleteobjs, behavior, PERFORM_DELETION_SORTEDLY);

     table_close(sdepRel, RowExclusiveLock);

diff --git a/src/include/catalog/dependency.h b/src/include/catalog/dependency.h
index b235a23..47a4f73 100644
--- a/src/include/catalog/dependency.h
+++ b/src/include/catalog/dependency.h
@@ -136,6 +136,7 @@ typedef enum ObjectClass
 #define PERFORM_DELETION_QUIETLY            0x0004    /* suppress notices */
 #define PERFORM_DELETION_SKIP_ORIGINAL        0x0008    /* keep original obj */
 #define PERFORM_DELETION_SKIP_EXTENSIONS    0x0010    /* keep extensions */
+#define PERFORM_DELETION_SORTEDLY            0x0020    /* presort objects */


 /* in dependency.c */
@@ -143,7 +144,7 @@ typedef enum ObjectClass
 extern void performDeletion(const ObjectAddress *object,
                 DropBehavior behavior, int flags);

-extern void performMultipleDeletions(const ObjectAddresses *objects,
+extern void performMultipleDeletions(ObjectAddresses *objects,
                          DropBehavior behavior, int flags);

 extern void recordDependencyOnExpr(const ObjectAddress *depender,