On Tue, 17 Jul 2001, Tom Lane wrote:
> Bill Studenmund <wrstuden@zembu.com> writes:
> > I think it's actually O(N^M) where there are N system objects and a chain
> > of M dependencies (A depends on B which depends on C => M = 3).
>
> It's probably not *that* bad. It's reasonable to assume that only a
> small number of objects actually depend directly on any one object you
> might want to delete. (Performance of deleting, say, the int4 datatype
> is probably not of major interest ;-) ...) Only for those objects, not
> for all N, would you need to descend to the next level of search.
Ah yes. It'll be O(ND) where D is the number of dependers (the number of
leaves in the dependency tree).
> Nonetheless, a properly indexed pg_depend table would allow you to find
> these objects directly, and again to find their dependents directly,
> etc. The brute force approach would require a rather expensive scan
> over all the system catalogs, plus nontrivial analysis for some types
> of system objects such as functions. Repeating that for each cascaded
> delete is even less appetizing than doing it once.
Indeed.
Take care,
Bill