Обсуждение: SearchCatCacheList()/SearchSysCacheList() is O(n)

Hi,

When working on the shared memory stats patch I needed to manufacture
having a lot of stats entries. It seemed cheaper to create functions
than relations, for fairly obvious reasons. That required calling the
functions too get those entries.

My first attempt ran into the following issue:

-- create 100k functions
DO $d$BEGIN FOR i IN 1..100000 LOOP EXECUTE format('CREATE OR REPLACE FUNCTION func_%1$s() RETURNS VOID LANGUAGE SQL AS
$f$SELECT1$f$;', i);END LOOP;END;$d$;
 
Time: 14853.428 ms (00:14.853)

-- call them to create stats
DO $d$BEGIN FOR i IN 1..100000 LOOP EXECUTE format('SELECT func_%1$s();', i);END LOOP;END;$d$;
Time: 106291.238 ms (01:46.291)

I had started with 1M functions, but the calls never finished.

It turns out to work more normally if you create *and* call the
functions after each other:

DO $d$BEGIN FOR i IN 1..100000 LOOP EXECUTE format('CREATE OR REPLACE FUNCTION func_%1$s() RETURNS VOID LANGUAGE SQL AS
$f$SELECT1$f$; SELECT func_%1$s();', i);END LOOP;END;$d$;
 
Time: 20043.375 ms (00:20.043)

The problem is that SearchCatCacheList() is not actually a hash table -
there are no buckets, in contrast to SearchCatCacheList(). The hash
values SearchCatCacheList() computes are only used to make the
comparison cheaper.

The only reason that the combined creation / call works out OK
performance wise, is that CatCacheInvalidate() destroys *all* lists, so
there only ever is one entry to match against.


This seems like a pretty large trap?

It's been that way since SearchCatCacheList() was introduced:

commit 0332d65ac4a1c843e1812755db1afc1b1109d0ea
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   2002-04-06 06:59:25 +0000

    Implement partial-key searching of syscaches, per recent suggestion
    to pghackers.  Use this to do searching for ambiguous functions ---
    it will get more uses soon.

Tom, any chance you remember if this was an oversight, or whether you
just considered this to be OK, given the likely numbers of objects?


I mainly wrote this email because I just remembered this by accident as
part of another discussion, and thought it'd be good to have a record of
the problem...

Greetings,

Andres Freund

Andres Freund <andres@anarazel.de> writes:
> The problem is that SearchCatCacheList() is not actually a hash table -
> there are no buckets, in contrast to SearchCatCacheList().

Uh, what did you mean to compare to there?

> Tom, any chance you remember if this was an oversight, or whether you
> just considered this to be OK, given the likely numbers of objects?

I'm pretty sure I didn't think the lists would get large enough to be
a problem.  I'm not quite sure which list is a problem here, actually,
seeing that the functions all have distinct names.

I have a vague recollection that some callers depend on the lists
being ordered by key.  I'm also fairly sure that most callers need
to look at all entries of whichever list they've requested.  So
I have doubts that "use a hash table" is really going to be a
productive idea.

            regards, tom lane

Hi,

On 2021-05-12 17:26:28 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > The problem is that SearchCatCacheList() is not actually a hash table -
> > there are no buckets, in contrast to SearchCatCacheList().
>
> Uh, what did you mean to compare to there?

Oops, copy-and-paste failure. I was trying to reference
SearchCatCacheInternal().


> > Tom, any chance you remember if this was an oversight, or whether you
> > just considered this to be OK, given the likely numbers of objects?
>
> I'm pretty sure I didn't think the lists would get large enough to be
> a problem.  I'm not quite sure which list is a problem here, actually,
> seeing that the functions all have distinct names.

It's not an individual "result" list that's the issue. In my example
they're all exactly one element long. The problem is that CatCache->list
has one element for each cached SearchCatCacheList() result, and that
for every SearchCatCacheList() we linearly search through CatCache->list
to find a match.

This is the profile:

-   88.21%  postgres  postgres            [.] SearchCatCacheList
   - 88.21% SearchCatCacheList
      - 88.21% SearchSysCacheList
           FuncnameGetCandidates
           func_get_detail
           ParseFuncOrColumn
           transformFuncCall
+    0.65%  postgres  postgres            [.] AllocSetAlloc

IOW, a single SearchCatCacheInternal() is O(N). With a fairly small
constant, but obviously that's still not great for a cache.


> I have a vague recollection that some callers depend on the lists
> being ordered by key.  I'm also fairly sure that most callers need
> to look at all entries of whichever list they've requested.  So
> I have doubts that "use a hash table" is really going to be a
> productive idea.

I was only thinking of a hashtable to identify the relvant CatCList, not
within a CatCList or anything. The cache search code between
SearchCatCacheInternal() and SearchCatCacheList() is pretty similar, but
crucially the former uses buckets, the latter doesn't:

static inline HeapTuple
SearchCatCacheInternal(CatCache *cache,
                       int nkeys,
                       Datum v1,
                       Datum v2,
                       Datum v3,
                       Datum v4)
...

    /*
     * find the hash bucket in which to look for the tuple
     */
    hashValue = CatalogCacheComputeHashValue(cache, nkeys, v1, v2, v3, v4);
    hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets);

    /*
     * scan the hash bucket until we find a match or exhaust our tuples
     *
     * Note: it's okay to use dlist_foreach here, even though we modify the
     * dlist within the loop, because we don't continue the loop afterwards.
     */
    bucket = &cache->cc_bucket[hashIndex];
    dlist_foreach(iter, bucket)
        {
...

SearchCatCacheList(CatCache *cache,
                   int nkeys,
                   Datum v1,
                   Datum v2,
                   Datum v3)
...
    /*
     * compute a hash value of the given keys for faster search.  We don't
     * presently divide the CatCList items into buckets, but this still lets
     * us skip non-matching items quickly most of the time.
     */
    lHashValue = CatalogCacheComputeHashValue(cache, nkeys, v1, v2, v3, v4);

    /*
     * scan the items until we find a match or exhaust our list
     *
     * Note: it's okay to use dlist_foreach here, even though we modify the
     * dlist within the loop, because we don't continue the loop afterwards.
     */
    dlist_foreach(iter, &cache->cc_lists)
    {



Greetings,

Andres Freund

Andres Freund <andres@anarazel.de> writes:
> It's not an individual "result" list that's the issue. In my example
> they're all exactly one element long. The problem is that CatCache->list
> has one element for each cached SearchCatCacheList() result, and that
> for every SearchCatCacheList() we linearly search through CatCache->list
> to find a match.

Ah, now I understand.  Yeah, replacing that list with a hash table might
be a good idea.

            regards, tom lane