Re: Fixing findDependentObjects()'s dependency on scan order (regressions in DROP diagnostic messages)

Peter Geoghegan <pg@bowt.ie> writes:
> On Thu, Jan 17, 2019 at 4:40 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> We're going to stick all these items into an ObjectAddress array anyway,
>> so at worst it'd be 2X growth, most likely a lot less since we'd only
>> be sorting one level of dependency at a time.

> It sounds like we don't have a good reason to not just sort them
> explicitly, then. I'm happy to go that way. I mostly just wanted to be
> sure that you were aware that we could add a tie-breaker column
> without any storage overhead.

I think the tiebreaker idea is just a hack, because it'd only be stable
to the extent that the added tiebreaker values are stable, and they
wouldn't be very much so if the counter state is only kept per-backend.

Attached is a draft patch to sort objects before the recursion step
in findDependentObjects.  I found that sorting by descending OID is
really the right thing; if we sort by increasing OID then we get a
whole lot more diffs in the DROP CASCADE output.  As shown, there
are just a few such diffs, and many of them seem to be for the better
anyway.

I repurposed object_address_comparator for this, which means this
has a side-effect of changing the order in which pg_depend entries
for a new object are inserted into that catalog.  I don't think
this is an issue.

I did not do anything here about reverting the various hacks to
suppress DROP CASCADE printouts in specific regression tests.
I'm not very sure whether doing so would be useful or not.

Testing this under ignore_system_indexes, it fixes most of the
cases where the output changes, but there are still two categories
it doesn't fix:

* Objects-to-drop output from DROP ROLE is still unstable.  I suppose
this would be fixed by also doing sorting in that code path, but
I've not looked into it.

* There is still instability in which object you get told to drop
when attempting to drop an index partition or trigger, as a consequence
of there being two possible DEPENDENCY_INTERNAL_AUTO targets.  I still
feel that the right fix there involves changing the design for what
dependency types we store, but I've not worked on it yet.

Comments?

            regards, tom lane

diff --git a/src/backend/catalog/dependency.c b/src/backend/catalog/dependency.c
index 6b8c735..aae30b5 100644
*** a/src/backend/catalog/dependency.c
--- b/src/backend/catalog/dependency.c
*************** typedef struct ObjectAddressStack
*** 124,129 ****
--- 124,136 ----
      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
  {
*************** findDependentObjects(const ObjectAddress
*** 472,477 ****
--- 479,487 ----
      SysScanDesc scan;
      HeapTuple    tup;
      ObjectAddress otherObject;
+     ObjectAddressAndFlags *dependentObjects;
+     int            numDependentObjects;
+     int            maxDependentObjects;
      ObjectAddressStack mystack;
      ObjectAddressExtra extra;

*************** findDependentObjects(const ObjectAddress
*** 704,715 ****
      systable_endscan(scan);

      /*
!      * Now recurse to any 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;

      ScanKeyInit(&key[0],
                  Anum_pg_depend_refclassid,
--- 714,727 ----
      systable_endscan(scan);

      /*
!      * Next, identify all objects dependent on the current object.  To ensure
!      * predictable deletion order, we collect them up in dependentObjects and
!      * sort the list before actually recursing.
       */
!     maxDependentObjects = 128;    /* arbitrary initial allocation */
!     dependentObjects = (ObjectAddressAndFlags *)
!         palloc(maxDependentObjects * sizeof(ObjectAddressAndFlags));
!     numDependentObjects = 0;

      ScanKeyInit(&key[0],
                  Anum_pg_depend_refclassid,
*************** findDependentObjects(const ObjectAddress
*** 762,768 ****
              continue;
          }

!         /* Recurse, passing objflags indicating the dependency type */
          switch (foundDep->deptype)
          {
              case DEPENDENCY_NORMAL:
--- 774,783 ----
              continue;
          }

!         /*
!          * 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:
*************** findDependentObjects(const ObjectAddress
*** 798,805 ****
                  break;
          }

!         findDependentObjects(&otherObject,
!                              subflags,
                               flags,
                               &mystack,
                               targetObjects,
--- 813,859 ----
                  break;
          }

!         /* 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 any 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,
*************** findDependentObjects(const ObjectAddress
*** 807,813 ****
                               depRel);
      }

!     systable_endscan(scan);

      /*
       * Finally, we can add the target object to targetObjects.  Be careful to
--- 861,867 ----
                               depRel);
      }

!     pfree(dependentObjects);

      /*
       * Finally, we can add the target object to targetObjects.  Be careful to
*************** object_address_comparator(const void *a,
*** 2109,2126 ****
      const ObjectAddress *obja = (const ObjectAddress *) a;
      const ObjectAddress *objb = (const ObjectAddress *) b;

!     if (obja->classId < objb->classId)
          return -1;
-     if (obja->classId > objb->classId)
-         return 1;
      if (obja->objectId < objb->objectId)
          return -1;
!     if (obja->objectId > objb->objectId)
          return 1;

      /*
!      * We sort the subId as an unsigned int so that 0 will come first. See
!      * logic in eliminate_duplicate_dependencies.
       */
      if ((unsigned int) obja->objectSubId < (unsigned int) objb->objectSubId)
          return -1;
--- 2163,2193 ----
      const ObjectAddress *obja = (const ObjectAddress *) a;
      const ObjectAddress *objb = (const ObjectAddress *) b;

!     /*
!      * 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->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->classId > objb->classId)
          return 1;

      /*
!      * 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;
diff --git a/src/test/regress/expected/alter_table.out b/src/test/regress/expected/alter_table.out
index 27cf550..7bb8ca9 100644
*** a/src/test/regress/expected/alter_table.out
--- b/src/test/regress/expected/alter_table.out
*************** DETAIL:  drop cascades to table alter2.t
*** 2583,2592 ****
  drop cascades to view alter2.v1
  drop cascades to function alter2.plus1(integer)
  drop cascades to type alter2.posint
- drop cascades to operator family alter2.ctype_hash_ops for access method hash
  drop cascades to type alter2.ctype
  drop cascades to function alter2.same(alter2.ctype,alter2.ctype)
  drop cascades to operator alter2.=(alter2.ctype,alter2.ctype)
  drop cascades to conversion alter2.ascii_to_utf8
  drop cascades to text search parser alter2.prs
  drop cascades to text search configuration alter2.cfg
--- 2583,2592 ----
  drop cascades to view alter2.v1
  drop cascades to function alter2.plus1(integer)
  drop cascades to type alter2.posint
  drop cascades to type alter2.ctype
  drop cascades to function alter2.same(alter2.ctype,alter2.ctype)
  drop cascades to operator alter2.=(alter2.ctype,alter2.ctype)
+ drop cascades to operator family alter2.ctype_hash_ops for access method hash
  drop cascades to conversion alter2.ascii_to_utf8
  drop cascades to text search parser alter2.prs
  drop cascades to text search configuration alter2.cfg
diff --git a/src/test/regress/expected/create_type.out b/src/test/regress/expected/create_type.out
index 2f7d5f9..8309756 100644
*** a/src/test/regress/expected/create_type.out
--- b/src/test/regress/expected/create_type.out
*************** DROP FUNCTION base_fn_out(opaque); -- er
*** 161,173 ****
  ERROR:  function base_fn_out(opaque) does not exist
  DROP TYPE base_type; -- error
  ERROR:  cannot drop type base_type because other objects depend on it
! DETAIL:  function base_fn_out(base_type) depends on type base_type
! function base_fn_in(cstring) depends on type base_type
  HINT:  Use DROP ... CASCADE to drop the dependent objects too.
  DROP TYPE base_type CASCADE;
  NOTICE:  drop cascades to 2 other objects
! DETAIL:  drop cascades to function base_fn_out(base_type)
! drop cascades to function base_fn_in(cstring)
  -- Check usage of typmod with a user-defined type
  -- (we have borrowed numeric's typmod functions)
  CREATE TEMP TABLE mytab (foo widget(42,13,7));     -- should fail
--- 161,173 ----
  ERROR:  function base_fn_out(opaque) does not exist
  DROP TYPE base_type; -- error
  ERROR:  cannot drop type base_type because other objects depend on it
! DETAIL:  function base_fn_in(cstring) depends on type base_type
! function base_fn_out(base_type) depends on type base_type
  HINT:  Use DROP ... CASCADE to drop the dependent objects too.
  DROP TYPE base_type CASCADE;
  NOTICE:  drop cascades to 2 other objects
! DETAIL:  drop cascades to function base_fn_in(cstring)
! drop cascades to function base_fn_out(base_type)
  -- Check usage of typmod with a user-defined type
  -- (we have borrowed numeric's typmod functions)
  CREATE TEMP TABLE mytab (foo widget(42,13,7));     -- should fail
diff --git a/src/test/regress/expected/domain.out b/src/test/regress/expected/domain.out
index 11bc772..4ff1b4a 100644
*** a/src/test/regress/expected/domain.out
--- b/src/test/regress/expected/domain.out
*************** alter domain dnotnulltest drop not null;
*** 645,652 ****
  update domnotnull set col1 = null;
  drop domain dnotnulltest cascade;
  NOTICE:  drop cascades to 2 other objects
! DETAIL:  drop cascades to column col1 of table domnotnull
! drop cascades to column col2 of table domnotnull
  -- Test ALTER DOMAIN .. DEFAULT ..
  create table domdeftest (col1 ddef1);
  insert into domdeftest default values;
--- 645,652 ----
  update domnotnull set col1 = null;
  drop domain dnotnulltest cascade;
  NOTICE:  drop cascades to 2 other objects
! DETAIL:  drop cascades to column col2 of table domnotnull
! drop cascades to column col1 of table domnotnull
  -- Test ALTER DOMAIN .. DEFAULT ..
  create table domdeftest (col1 ddef1);
  insert into domdeftest default values;
diff --git a/src/test/regress/expected/matview.out b/src/test/regress/expected/matview.out
index 08cd4be..d0121a7 100644
*** a/src/test/regress/expected/matview.out
--- b/src/test/regress/expected/matview.out
*************** SELECT type, m.totamt AS mtot, v.totamt
*** 311,322 ****
  DROP TABLE mvtest_t;
  ERROR:  cannot drop table mvtest_t because other objects depend on it
  DETAIL:  view mvtest_tv depends on table mvtest_t
  view mvtest_tvv depends on view mvtest_tv
  materialized view mvtest_tvvm depends on view mvtest_tvv
  view mvtest_tvvmv depends on materialized view mvtest_tvvm
  materialized view mvtest_bb depends on view mvtest_tvvmv
- materialized view mvtest_mvschema.mvtest_tvm depends on view mvtest_tv
- materialized view mvtest_tvmm depends on materialized view mvtest_mvschema.mvtest_tvm
  materialized view mvtest_tm depends on table mvtest_t
  materialized view mvtest_tmm depends on materialized view mvtest_tm
  HINT:  Use DROP ... CASCADE to drop the dependent objects too.
--- 311,322 ----
  DROP TABLE mvtest_t;
  ERROR:  cannot drop table mvtest_t because other objects depend on it
  DETAIL:  view mvtest_tv depends on table mvtest_t
+ materialized view mvtest_mvschema.mvtest_tvm depends on view mvtest_tv
+ materialized view mvtest_tvmm depends on materialized view mvtest_mvschema.mvtest_tvm
  view mvtest_tvv depends on view mvtest_tv
  materialized view mvtest_tvvm depends on view mvtest_tvv
  view mvtest_tvvmv depends on materialized view mvtest_tvvm
  materialized view mvtest_bb depends on view mvtest_tvvmv
  materialized view mvtest_tm depends on table mvtest_t
  materialized view mvtest_tmm depends on materialized view mvtest_tm
  HINT:  Use DROP ... CASCADE to drop the dependent objects too.
*************** BEGIN;
*** 327,338 ****
  DROP TABLE mvtest_t CASCADE;
  NOTICE:  drop cascades to 9 other objects
  DETAIL:  drop cascades to view mvtest_tv
  drop cascades to view mvtest_tvv
  drop cascades to materialized view mvtest_tvvm
  drop cascades to view mvtest_tvvmv
  drop cascades to materialized view mvtest_bb
- drop cascades to materialized view mvtest_mvschema.mvtest_tvm
- drop cascades to materialized view mvtest_tvmm
  drop cascades to materialized view mvtest_tm
  drop cascades to materialized view mvtest_tmm
  ROLLBACK;
--- 327,338 ----
  DROP TABLE mvtest_t CASCADE;
  NOTICE:  drop cascades to 9 other objects
  DETAIL:  drop cascades to view mvtest_tv
+ drop cascades to materialized view mvtest_mvschema.mvtest_tvm
+ drop cascades to materialized view mvtest_tvmm
  drop cascades to view mvtest_tvv
  drop cascades to materialized view mvtest_tvvm
  drop cascades to view mvtest_tvvmv
  drop cascades to materialized view mvtest_bb
  drop cascades to materialized view mvtest_tm
  drop cascades to materialized view mvtest_tmm
  ROLLBACK;
diff --git a/src/test/regress/expected/updatable_views.out b/src/test/regress/expected/updatable_views.out
index 0ac08ca..420c5a5 100644
*** a/src/test/regress/expected/updatable_views.out
--- b/src/test/regress/expected/updatable_views.out
*************** DETAIL:  drop cascades to view ro_view1
*** 334,339 ****
--- 334,340 ----
  drop cascades to view ro_view17
  drop cascades to view ro_view2
  drop cascades to view ro_view3
+ drop cascades to view ro_view4
  drop cascades to view ro_view5
  drop cascades to view ro_view6
  drop cascades to view ro_view7
*************** drop cascades to view ro_view8
*** 341,351 ****
  drop cascades to view ro_view9
  drop cascades to view ro_view11
  drop cascades to view ro_view13
  drop cascades to view rw_view15
  drop cascades to view rw_view16
  drop cascades to view ro_view20
- drop cascades to view ro_view4
- drop cascades to view rw_view14
  DROP VIEW ro_view10, ro_view12, ro_view18;
  DROP SEQUENCE uv_seq CASCADE;
  NOTICE:  drop cascades to view ro_view19
--- 342,351 ----
  drop cascades to view ro_view9
  drop cascades to view ro_view11
  drop cascades to view ro_view13
+ drop cascades to view rw_view14
  drop cascades to view rw_view15
  drop cascades to view rw_view16
  drop cascades to view ro_view20
  DROP VIEW ro_view10, ro_view12, ro_view18;
  DROP SEQUENCE uv_seq CASCADE;
  NOTICE:  drop cascades to view ro_view19