Rethinking dependency traversal during DROP

I promise I won't expend any real effort on this until after the
commitfest is over, but ...

While working on the recently committed constraints patch, I got annoyed
by the way in which DROP CASCADE frequently emitted "noise" messages.
For instance:

regression=# create table p1 (f1 int);
CREATE TABLE
regression=# create table c1 (f2 int check (f2>0)) inherits (p1);
CREATE TABLE
regression=# drop table p1 cascade;
NOTICE: drop cascades to table c1
NOTICE: drop cascades to constraint c1_f2_check on table c1
DROP TABLE

The check constraint is auto-dependent on c1, so really the second
message shouldn't be there. The reason it is there is that the
constraint also has a normal dependency on c1.f2, and if this pg_depend
link is traversed first (which seems to almost always be the case)
then you get the message. The findAutoDeletableObjects() scan that is
supposed to prevent this behavior does not, because it only goes as far
as the objects that are directly auto- or internal-dependent on the
original target object (ie, p1).

I thought about fixing this by doing a new findAutoDeletableObjects()
scan whenever we recurse, adding-on new objects to not complain about.
This sort of works; I attach a test patch that does that, and the
regression test output changes it induces, which seem to be all to
the good. But it's a pretty ugly idea for a number of reasons:

1. With this patch, every single call to recursiveDeletion is preceded
by findAutoDeletableObjects, which at the very least cries out for
refactoring.

2. The above observation puts the final nail in the coffin of the
original design idea, which was to do one recursive traversal of
pg_depend links during DROP. It's indisputable that we now must
traverse the entire link tree twice (at least!), and the cost of
doing that seems annoying, especially when we are sitting there
building various lists of the objects in memory anyway.

3. We have got various open bug reports centered around the fact
that a cascaded DROP takes locks too late:
http://archives.postgresql.org/pgsql-hackers/2007-01/msg00937.php
http://archives.postgresql.org/pgsql-bugs/2007-03/msg00143.php
http://archives.postgresql.org/pgsql-bugs/2007-12/msg00188.php
If we are going to be forced into a two-pass approach, we really
ought to try to solve those issues at the same time.

So the idea I am toying with goes like this:

1. First, recursively scan the pg_depend tree to find every object that
would have to be deleted in order to drop the initial target object(s).
Take out locks on objects that are of lockable types before scanning for
their referencing objects, but don't do anything else yet. Build an
ObjectAddresses list in memory of the objects-to-drop, and annotate each
entry with flags showing how we got to it (ie, via normal, auto, or
internal dependency links).

2. Scan the ObjectAddresses list and issue notices about any objects
that are reachable only via normal dependencies. If there are any,
and it's not a CASCADE drop, error out. (This means we will fail in
such a case after expending quite a lot less work than we do now.)

3. Scan the ObjectAddresses list back-to-front and perform the
deletions. The back-to-front scan ensures dependent objects are deleted
before depended-on ones, which is critical in a number of cases.

I am not entirely certain that a back-to-front traversal is sufficient:
there may need to be some kind of sorting step, or maybe we should just
continue to drive the deletion pass off scans of pg_depend, seeing that
we'll have to do those anyway to delete the pg_depend entries. So this
is just a back-of-the-napkin sketch of how it might work.

Comments?

regards, tom lane