Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references. - Mailing list pgsql-hackers

From Tom Lane
Subject Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.
Date
Msg-id 14681.1443202990@sss.pgh.pa.us
Whole thread Raw
In response to Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.  (Alvaro Herrera <alvherre@2ndquadrant.com>)
Responses Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.  (Tom Lane <tgl@sss.pgh.pa.us>)
List pgsql-hackers
Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> Would it make sense to remove the only the few oldest entries, instead
> of all of them?  As is, I think this causes a storm of reloads every
> once in a while, if the number of FKs in the system is large enough.
> Maybe on a cache hit we could push the entry to the head of the list,
> and then remove N entries from the back of the list when the threshold
> is reached.

Sure, there's room for optimization of that sort, although I think we
could do with some evidence that it's actually helpful.  I believe that
under "production" workloads InvalidateConstraintCacheCallBack won't
get called much at all, so the problem's moot.

(FWIW, it might take less code to put the recently-used entries at the
back of the list.  Then the loop in InvalidateConstraintCacheCallBack
could just invalidate/delete entries if either they're targets, or
the current list length exceeds the threshold.)
        regards, tom lane



pgsql-hackers by date:

Previous
From: Jeff Janes
Date:
Subject: Re: No Issue Tracker - Say it Ain't So!
Next
From: Tom Lane
Date:
Subject: Re: [COMMITTERS] pgsql: Fix an O(N^2) problem in foreign key references.