Обсуждение: Syscaches should store negative entries, too

While fooling around some more with profiling of simple queries,
I noticed that in some scenarios there are lots of failing lookups in
the syscaches.  This happens, for example, when trying to resolve
ambiguous operators or functions: the parser will do a lot of
can_coerce_type calls, each of which probes using the syscache to see
if there is a matching type-coercion function.  Often there won't be.

Now, while the syscaches are very good at dealing with repetitive
successful lookups, they suck on repetitive unsuccessful ones: each
probe will do a whole new indexscan search on the underlying catalog.
It's not difficult to get into situations where the bulk of the catalog
searches are due to repetitive failing syscache probes.  For example,
I added some simple counters to current sources, and got these results
for a 100-transaction run of pgbench:

Catcache totals: 43 tup, 14519 srch, 13976 hits, 43 loads, 500 not found

That says the caches had 43 tuples by the end of the run, and were
searched 14519 times, of which 13976 searches were satisfied by an
existing entry and another 43 by a newly-loaded entry.  The remaining
500 searches failed.  The catcaches were therefore responsible for
543 catalog indexscans.  The 500 failed searches almost certainly
consisted of 100 sets of probes for the same five nonexistent tuples,
given the repetitive structure of the queries.  As we throw more
similar queries at the backend, no new cache entries will need to be
loaded ... but every failing search will have to be done again.

I suspect repetitive query structure is a common feature of most
applications, so these numbers suggest strongly that the catcaches
ought to cache negative results as well as positive ones.

AFAICS there's no logical difficulty in doing this: we simply make
a catcache entry that contains the probed-for key values but is
marked "no one home at this address".  If a probe hits one of these
things, it can return NULL without a trip to the catalog.  If someone
later comes along and creates a tuple that matches the key value,
the negative-result cache entry will be invalidated in the usual way
(this should work because insertion and update are treated identically
in the caches).

Negative and positive cache entries should compete on an equal basis for
space in the cache, since they are equally expensive to recreate.

Can anyone spot a flaw in this reasoning?
        regards, tom lane

... Interesting...

> Negative and positive cache entries should compete on an equal basis for
> space in the cache, since they are equally expensive to recreate.
> Can anyone spot a flaw in this reasoning?

Maybe not a flaw, but an observation: a backend running for an extended
period of time may tend to accumulate a large number of negative cache
entries and in principle they can grow indefinitely. The positive cache
entries have an upper limit of the number of actual tuples in the
catalog itself (or perhaps something smaller).

Presumably there is an upper limit to the physical cache size. Would
retaining negative entries tend to cause the cache to cycle or to grow
without bounds if there is no such limit? Or does it seem that things
would reach a reasonable steady state no matter what the query topology
tends to be?
                  - Thomas

Thomas Lockhart writes:

> Presumably there is an upper limit to the physical cache size. Would
> retaining negative entries tend to cause the cache to cycle or to grow
> without bounds if there is no such limit? Or does it seem that things
> would reach a reasonable steady state no matter what the query topology
> tends to be?

I think the key would be that you cache N-1 failed function lookups only
if you are actually successful finding a useful function in the Nth
attempt.  Then, if your logical cache size is C you would have quick
access to C/N function resolution paths, whereas right now the cache is
really quite useless for function resolution that requires unsuccessful
lookups along the way.  Note that if your queries are "well written" in
that they don't require any unsuccessful lookups, the cache behaviour
wouldn't change.  Since N is usually small in reasonable applications you
could also simply increase your cache size by a factor of N to compensate
for whatever you might be afraid of.

Perhaps Tom Lane was also thinking ahead in terms of schema lookups.  I
imagine this negative cache scheme would really be critical there.

However, what you probably wouldn't want to do is cache negative lookups
that don't end up producing results or are not part of a search chain at
all.  Those are user errors and not likely to be repeated and do not need
to be optimized.

-- 
Peter Eisentraut   peter_e@gmx.net

Peter Eisentraut <peter_e@gmx.net> writes:
> However, what you probably wouldn't want to do is cache negative lookups
> that don't end up producing results or are not part of a search chain at
> all.  Those are user errors and not likely to be repeated and do not need
> to be optimized.

I think the key point here is that cache entries that aren't repeatedly
referenced won't survive.  I don't see why it would matter whether they
are negative or positive.  If you make one reference to a table (and
then never touch it again in the session), is the cache supposed to
presciently know that the resulting positive entries are wasted?  No,
it ages them out on the same schedule as anything else.  If entering
those entries caused some other stuff to drop out, well it was stuff
that hadn't been referenced in quite a while anyhow.  AFAICS all this
reasoning holds equally well for negative entries.

It is true that the system generally makes many more successful searches
than unsuccessful ones --- but that just means that positive entries
will be more able to survive in the cache, if the cache gets full enough
for there to be competition.

FWIW, I believe that in typical scenarios there *is* no competition as
the syscache never gets full enough to have anything age out.  In the
regression tests my little stats addition shows no run with more than
266 cache entries accumulated; the average end-of-run cache population
is 75 entries.  Syscache is currently configured to allow 5000 entries
before it starts to drop stuff.

The regression tests are probably not representative, but if anything
I'd expect them to hit a wider variety of tables on an average run than
typical applications do.

Bottom line: it's not apparent to me why the cache policy should be
anything but straight LRU across both positive and negative entries.
        regards, tom lane

PS: Just in case anyone wants to see numbers, here are the end-of-run
stats for each of the regression tests.

DEBUG:  Catcache totals: 14 tup, 14 srch, 0 hits, 14 loads, 0 not found
DEBUG:  Catcache totals: 15 tup, 16 srch, 1 hits, 15 loads, 0 not found
DEBUG:  Catcache totals: 71 tup, 130 srch, 59 hits, 71 loads, 0 not found
DEBUG:  Catcache totals: 18 tup, 34 srch, 12 hits, 18 loads, 4 not found
DEBUG:  Catcache totals: 27 tup, 61 srch, 27 hits, 27 loads, 7 not found
DEBUG:  Catcache totals: 3 tup, 4 srch, 0 hits, 3 loads, 1 not found
DEBUG:  Catcache totals: 3 tup, 4 srch, 0 hits, 3 loads, 1 not found
DEBUG:  Catcache totals: 44 tup, 448 srch, 329 hits, 66 loads, 53 not found
DEBUG:  Catcache totals: 52 tup, 271 srch, 182 hits, 64 loads, 25 not found
DEBUG:  Catcache totals: 56 tup, 472 srch, 357 hits, 67 loads, 48 not found
DEBUG:  Catcache totals: 50 tup, 307 srch, 222 hits, 62 loads, 23 not found
DEBUG:  Catcache totals: 39 tup, 106 srch, 52 hits, 46 loads, 8 not found
DEBUG:  Catcache totals: 76 tup, 441 srch, 324 hits, 77 loads, 40 not found
DEBUG:  Catcache totals: 100 tup, 597 srch, 456 hits, 101 loads, 40 not found
DEBUG:  Catcache totals: 59 tup, 1352 srch, 1139 hits, 60 loads, 153 not found
DEBUG:  Catcache totals: 40 tup, 202 srch, 132 hits, 51 loads, 19 not found
DEBUG:  Catcache totals: 51 tup, 340 srch, 255 hits, 52 loads, 33 not found
DEBUG:  Catcache totals: 67 tup, 590 srch, 459 hits, 68 loads, 63 not found
DEBUG:  Catcache totals: 103 tup, 1536 srch, 1187 hits, 171 loads, 178 not found
DEBUG:  Catcache totals: 143 tup, 8319 srch, 7733 hits, 241 loads, 345 not found
DEBUG:  Catcache totals: 89 tup, 1351 srch, 1161 hits, 89 loads, 101 not found
DEBUG:  Catcache totals: 121 tup, 2279 srch, 1866 hits, 167 loads, 246 not found
DEBUG:  Catcache totals: 96 tup, 1223 srch, 1009 hits, 97 loads, 117 not found
DEBUG:  Catcache totals: 77 tup, 391 srch, 274 hits, 78 loads, 39 not found
DEBUG:  Catcache totals: 61 tup, 367 srch, 271 hits, 62 loads, 34 not found
DEBUG:  Catcache totals: 41 tup, 175 srch, 107 hits, 48 loads, 20 not found
DEBUG:  Catcache totals: 60 tup, 290 srch, 206 hits, 67 loads, 17 not found
DEBUG:  Catcache totals: 88 tup, 1050 srch, 845 hits, 89 loads, 116 not found
DEBUG:  Catcache totals: 37 tup, 226 srch, 175 hits, 38 loads, 13 not found
DEBUG:  Catcache totals: 56 tup, 374 srch, 274 hits, 57 loads, 43 not found
DEBUG:  Catcache totals: 55 tup, 383 srch, 280 hits, 56 loads, 47 not found
DEBUG:  Catcache totals: 67 tup, 2082 srch, 1850 hits, 68 loads, 164 not found
DEBUG:  Catcache totals: 67 tup, 2082 srch, 1850 hits, 68 loads, 164 not found
DEBUG:  Catcache totals: 44 tup, 272 srch, 205 hits, 45 loads, 22 not found
DEBUG:  Catcache totals: 65 tup, 593 srch, 468 hits, 66 loads, 59 not found
DEBUG:  Catcache totals: 40 tup, 207 srch, 146 hits, 41 loads, 20 not found
DEBUG:  Catcache totals: 54 tup, 325 srch, 241 hits, 55 loads, 29 not found
DEBUG:  Catcache totals: 127 tup, 2494 srch, 1887 hits, 142 loads, 465 not found
DEBUG:  Catcache totals: 22 tup, 51 srch, 25 hits, 22 loads, 4 not found
DEBUG:  Catcache totals: 224 tup, 16980 srch, 13307 hits, 224 loads, 3449 not found
DEBUG:  Catcache totals: 152 tup, 3879 srch, 2974 hits, 152 loads, 753 not found
DEBUG:  Catcache totals: 217 tup, 11008 srch, 8561 hits, 217 loads, 2230 not found
DEBUG:  Catcache totals: 151 tup, 1206 srch, 912 hits, 151 loads, 143 not found
DEBUG:  Catcache totals: 206 tup, 2496 srch, 2028 hits, 217 loads, 251 not found
DEBUG:  Catcache totals: 23 tup, 64 srch, 29 hits, 23 loads, 12 not found
DEBUG:  Catcache totals: 43 tup, 140 srch, 61 hits, 55 loads, 24 not found
DEBUG:  Catcache totals: 55 tup, 1011 srch, 723 hits, 201 loads, 87 not found
DEBUG:  Catcache totals: 46 tup, 131 srch, 66 hits, 46 loads, 19 not found
DEBUG:  Catcache totals: 31 tup, 283 srch, 247 hits, 31 loads, 5 not found
DEBUG:  Catcache totals: 93 tup, 2200 srch, 1552 hits, 430 loads, 218 not found
DEBUG:  Catcache totals: 76 tup, 1503 srch, 1048 hits, 287 loads, 168 not found
DEBUG:  Catcache totals: 95 tup, 1509 srch, 1254 hits, 127 loads, 128 not found
DEBUG:  Catcache totals: 28 tup, 54 srch, 18 hits, 28 loads, 8 not found
DEBUG:  Catcache totals: 24 tup, 44 srch, 16 hits, 24 loads, 4 not found
DEBUG:  Catcache totals: 112 tup, 561 srch, 239 hits, 288 loads, 34 not found
DEBUG:  Catcache totals: 67 tup, 3491 srch, 2632 hits, 102 loads, 757 not found
DEBUG:  Catcache totals: 46 tup, 111 srch, 52 hits, 49 loads, 10 not found
DEBUG:  Catcache totals: 65 tup, 845 srch, 411 hits, 425 loads, 9 not found
DEBUG:  Catcache totals: 93 tup, 217 srch, 108 hits, 94 loads, 15 not found
DEBUG:  Catcache totals: 95 tup, 879 srch, 689 hits, 97 loads, 93 not found
DEBUG:  Catcache totals: 64 tup, 272 srch, 129 hits, 116 loads, 27 not found
DEBUG:  Catcache totals: 43 tup, 151 srch, 94 hits, 43 loads, 14 not found
DEBUG:  Catcache totals: 34 tup, 102 srch, 58 hits, 34 loads, 10 not found
DEBUG:  Catcache totals: 60 tup, 1015 srch, 801 hits, 96 loads, 118 not found
DEBUG:  Catcache totals: 55 tup, 342 srch, 249 hits, 69 loads, 24 not found
DEBUG:  Catcache totals: 127 tup, 1174 srch, 903 hits, 128 loads, 143 not found
DEBUG:  Catcache totals: 73 tup, 1240 srch, 1052 hits, 73 loads, 115 not found
DEBUG:  Catcache totals: 119 tup, 2773 srch, 2271 hits, 143 loads, 359 not found
DEBUG:  Catcache totals: 43 tup, 1527 srch, 1183 hits, 89 loads, 255 not found
DEBUG:  Catcache totals: 82 tup, 702 srch, 586 hits, 82 loads, 34 not found
DEBUG:  Catcache totals: 42 tup, 163 srch, 96 hits, 44 loads, 23 not found
DEBUG:  Catcache totals: 53 tup, 225 srch, 157 hits, 54 loads, 14 not found
DEBUG:  Catcache totals: 34 tup, 2018 srch, 1612 hits, 34 loads, 372 not found
DEBUG:  Catcache totals: 78 tup, 750 srch, 558 hits, 85 loads, 107 not found
DEBUG:  Catcache totals: 78 tup, 364 srch, 222 hits, 78 loads, 64 not found
DEBUG:  Catcache totals: 55 tup, 612 srch, 465 hits, 55 loads, 92 not found
DEBUG:  Catcache totals: 151 tup, 2521 srch, 1958 hits, 179 loads, 384 not found
DEBUG:  Catcache totals: 44 tup, 1680 srch, 1434 hits, 44 loads, 202 not found
DEBUG:  Catcache totals: 27 tup, 159 srch, 32 hits, 111 loads, 16 not found
DEBUG:  Catcache totals: 167 tup, 5601 srch, 4777 hits, 392 loads, 432 not found
DEBUG:  Catcache totals: 64 tup, 191 srch, 106 hits, 64 loads, 21 not found
DEBUG:  Catcache totals: 180 tup, 5935 srch, 4106 hits, 1077 loads, 752 not found
DEBUG:  Catcache totals: 61 tup, 1128 srch, 854 hits, 61 loads, 213 not found
DEBUG:  Catcache totals: 266 tup, 9834 srch, 8013 hits, 617 loads, 1204 not found
DEBUG:  Catcache totals: 160 tup, 16136 srch, 12750 hits, 1341 loads, 2045 not found
DEBUG:  Catcache totals: 46 tup, 437 srch, 333 hits, 46 loads, 58 not found

The grand totals are 137123 searches, 107792 hits, 11055 successful
loads and 18276 not-found searches... of course these numbers do not
say how many of the not-found searches would be eliminated by negative
cache entries, but it sure looks worth trying.

> However, what you probably wouldn't want to do is cache negative lookups
> that don't end up producing results or are not part of a search chain at
> all.  Those are user errors and not likely to be repeated and do not need
> to be optimized.

But this also is resolved by the LRU mechanism, no ?
People are not going to issue the same errors repeatedly,
but if they do, we are still interested in minimizing the 
resource consumption.

Andreas

Hannu Krosing <hannu@krosing.net> writes:
> Are there _any_ tests where it does start to drop stuff ?

> In other words - is the stuff-dropping part tested reasonably recently
> (or at all) ?

Good point.  The drop mechanism is exercised well enough as driven by
shared-cache-invalidation cases, but the case where it's driven by cache
entry count isn't getting tested.

> In other words we should cache Frequently Asked Questions and not
> Frequently Found Answers ;)

Right ;-)
        regards, tom lane

I wrote:
> AFAICS there's no logical difficulty in doing this: we simply make
> a catcache entry that contains the probed-for key values but is
> marked "no one home at this address".  If a probe hits one of these
> things, it can return NULL without a trip to the catalog.  If someone
> later comes along and creates a tuple that matches the key value,
> the negative-result cache entry will be invalidated in the usual way
> (this should work because insertion and update are treated identically
> in the caches).

That last claim is false, unfortunately.  Shared cache invalidation
treats inserts differently from updates and deletes (see the comments
at the top of src/backend/utils/cache/inval.c).

To make negative cache entries work correctly, we'd have to issue
cross-backend SI messages for inserts into the system catalogs, not
only for updates and deletes.  This would mean more SI traffic than
there is now.  I think it'd still be a win, but the case for negative
cache entries isn't quite as airtight as I thought.  There could be
scenarios where the extra SI traffic outweighs the savings from avoiding
failing catalog searches.

Comments anyone?
        regards, tom lane

On Wed, 2002-01-30 at 10:56, Tom Lane wrote:
>
> FWIW, I believe that in typical scenarios there *is* no competition as
> the syscache never gets full enough to have anything age out.  In the
> regression tests my little stats addition shows no run with more than
> 266 cache entries accumulated; the average end-of-run cache population
> is 75 entries.  Syscache is currently configured to allow 5000 entries
> before it starts to drop stuff.

Are there _any_ tests where it does start to drop stuff ?

In other words - is the stuff-dropping part tested reasonably recently
(or at all) ?

> The regression tests are probably not representative, but if anything
> I'd expect them to hit a wider variety of tables on an average run than
> typical applications do.
> 
> Bottom line: it's not apparent to me why the cache policy should be
> anything but straight LRU across both positive and negative entries.

In other words we should cache Frequently Asked Questions and not
Frequently Found Answers ;)

-------------
Hannu

On Thu, 2002-01-31 at 00:00, Tom Lane wrote:
> 
> To make negative cache entries work correctly, we'd have to issue
> cross-backend SI messages for inserts into the system catalogs, not
> only for updates and deletes.  This would mean more SI traffic than
> there is now.  I think it'd still be a win, but the case for negative
> cache entries isn't quite as airtight as I thought.  There could be
> scenarios where the extra SI traffic outweighs the savings from avoiding
> failing catalog searches.
> 
> Comments anyone?

The standard one - if not sure, make it an option ;)

------------
Hannu

Hannu Krosing wrote:
> On Thu, 2002-01-31 at 00:00, Tom Lane wrote:
> > 
> > To make negative cache entries work correctly, we'd have to issue
> > cross-backend SI messages for inserts into the system catalogs, not
> > only for updates and deletes.  This would mean more SI traffic than
> > there is now.  I think it'd still be a win, but the case for negative
> > cache entries isn't quite as airtight as I thought.  There could be
> > scenarios where the extra SI traffic outweighs the savings from avoiding
> > failing catalog searches.
> > 
> > Comments anyone?
> 
> The standard one - if not sure, make it an option ;)

Actually, that is not our standard comment.  We want to give people a
limited set of meaningful options.  If then want billions of options,
they should use Oracle.  :-)

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
853-3000+  If your life is a hard drive,     |  830 Blythe Avenue +  Christ can be your backup.        |  Drexel Hill,
Pennsylvania19026
 

> > Actually, that is not our standard comment.  We want to give people a
> > limited set of meaningful options.  If then want billions of options,
> > they should use Oracle.  :-)
> 
> In that case we have to decide for the user for which case we optimize
> and give user suboptimal performanse for the _other_ case.

If we can't decide, and it is significant, we have to give any option,
but only if both are true.

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
853-3000+  If your life is a hard drive,     |  830 Blythe Avenue +  Christ can be your backup.        |  Drexel Hill,
Pennsylvania19026
 

Hannu Krosing <hannu@krosing.net> writes:
> In that case we have to decide for the user for which case we optimize
> and give user suboptimal performanse for the _other_ case.

If we're gonna do it, I'd just do it; that code is hairy enough already
without trying to support multiple, fundamentally different operating
modes.

An advantage of switching is that the insert, update, and delete cases
would all become truly alike to inval.c, thus making that module simpler
instea of more complex.  I find this attractive.

One thing I realized after my last message on the subject is that the
cross-backend SI messages do not carry the actual key values of the
tuple being inserted/deleted/updated.  What they do carry is a hash
index, which is presently used only to speed up the search for matching
cache entries to be purged.  What we'd have to do with negative cache
entries is (for an insert) purge *all* negative cache entries on that
hash chain, since we couldn't tell exactly which if any correspond to
the keys of the inserted tuple.  I don't think this is a big problem;
hopefully each individual hash chain is short and so not very many
negative entries would become collateral casualties.  But it is another
potential source of inefficiency.
        regards, tom lane