Re: Syscaches should store negative entries, too

Peter Eisentraut <peter_e(at)gmx(dot)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.