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

Jan Wieck <jan@wi3ck.info> writes:
> Would it be appropriate to use (Un)RegisterXactCallback() in case of 
> detecting excessive sequential scanning of that cache and remove all 
> invalid entries from it at that time?

Don't see how unregistering the callback would help?

In any case, I'm -1 on this entire concept of "let's zero out the cache at
randomly chosen moments".  That's far too hard to test the effects of, as
we've just seen.  It needs to be more predictable, and I think it ought to
be more selective too.

One idea is to limit the cache to say 1000 entries, and get rid of the
least-used one when the threshold is exceeded.  We could do that fairly
cheaply if we chain the cache entries together in a doubly-linked list
(see ilist.h) and move an entry to the front when referenced.  For
reasonably large cache sizes, that would pretty much guarantee that you
weren't destroying an actively-used entry.  However, it would still be
a bit hard to test, because you could not safely reduce the cache size
to just 1 as a test mechanism.

Another idea is that it's not the size of the cache that's the problem,
it's the cost of finding the entries that need to be invalidated.
So we could also consider adding list links that chain only the entries
that are currently marked valid.  If the list gets too long, we could mark
them all invalid and thereby reset the list to nil.  This doesn't do
anything for the cache's space consumption, but that wasn't what you were
worried about anyway was it?
        regards, tom lane