type cache cleanup improvements

Hi Teodor,

I'd like to suggest two independent patches to improve performance of type cache
cleanup. I found a case where type cache cleanup was a reason for low
performance. In short, customer makes 100 thousand temporary tables in one
transaction.

1 mapRelType.patch
It just adds a local map between relation and its type as it was suggested in
comment above TypeCacheRelCallback(). Unfortunately, using syscache here was
impossible because this call back could be called outside transaction and it
makes impossible catalog lookups.

2 hash_seq_init_with_hash_value.patch
TypeCacheTypCallback() loop over type hash to find entry with given hash
value. Here there are two problems: 1) there isn't interface to dynahash to
search entry with given hash value and 2) hash value calculation algorithm is
differ from system cache. But coming hashvalue is came from system cache. Patch
is addressed to both issues. It suggests hash_seq_init_with_hash_value() call
which inits hash sequential scan over the single bucket which could contain
entry with given hash value, and hash_seq_search() will iterate only over such
entries. Anf patch changes hash algorithm to match syscache. Actually, patch
makes small refactoring of dynahash, it makes common function hash_do_lookup()
which does initial lookup in hash.

Some artificial performance test is in attachment, command to test is 'time psql
< custom_types_and_array.sql', here I show only last rollback time and total
execution time:
1) master 92d2ab7554f92b841ea71bcc72eaa8ab11aae662
Time: 33353,288 ms (00:33,353)
psql < custom_types_and_array.sql 0,82s user 0,71s system 1% cpu 1:28,36 total

2) mapRelType.patch
Time: 7455,581 ms (00:07,456)
psql < custom_types_and_array.sql 1,39s user 1,19s system 6% cpu 41,220 total

3) hash_seq_init_with_hash_value.patch
Time: 24975,886 ms (00:24,976)
psql < custom_types_and_array.sql 1,33s user 1,25s system 3% cpu 1:19,77 total

4) both
Time: 89,446 ms
psql < custom_types_and_array.sql 0,72s user 0,52s system 10% cpu 12,137 total

These changes look very promising. Unfortunately the proposed patches
conflict with each other regardless the order of applying:

```
error: patch failed: src/backend/utils/cache/typcache.c:356
error: src/backend/utils/cache/typcache.c: patch does not apply
```

So it's difficult to confirm case 4, not to mention the fact that we
are unable to test the patches on cfbot.

Could you please rebase the patches against the recent master branch
(in any order) and submit the result of `git format-patch` ?

--
Best regards,
Aleksander Alekseev

Hi!

Thank you for interesting in it!

These changes look very promising. Unfortunately the proposed patches
conflict with each other regardless the order of applying:

```
error: patch failed: src/backend/utils/cache/typcache.c:356
error: src/backend/utils/cache/typcache.c: patch does not apply
```

Try increase -F option of patch.

Anyway, union of both patches in attachment

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Hi,

Thank you for interesting in it!

These changes look very promising. Unfortunately the proposed patches
conflict with each other regardless the order of applying:

```
error: patch failed: src/backend/utils/cache/typcache.c:356
error: src/backend/utils/cache/typcache.c: patch does not apply
```

Try increase -F option of patch.

Anyway, union of both patches in attachment

Thanks for the quick update.

I tested the patch on an Intel MacBook. A release build was used with
my typical configuration, TWIMC see single-install-meson.sh [1]https://github.com/afiskon/pgscripts/. The
speedup I got on the provided benchmark is about 150 times. cfbot
seems to be happy with the patch.

I would like to tweak the patch a little bit - change some comments,
add some Asserts, etc. Don't you mind?

[1]: https://github.com/afiskon/pgscripts/

--
Best regards,
Aleksander Alekseev

I would like to tweak the patch a little bit - change some comments,
add some Asserts, etc. Don't you mind?

You are welcome!
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Hi,

I would like to tweak the patch a little bit - change some comments,
add some Asserts, etc. Don't you mind?

You are welcome!

Thanks. PFA the updated patch with some tweaks by me. I added the
commit message as well.

One thing that I couldn't immediately figure out is why 0 hash value
is treated as a magic invalid value in TypeCacheTypCallback():

```
-       hash_seq_init(&status, TypeCacheHash);
+       if (hashvalue == 0)
+               hash_seq_init(&status, TypeCacheHash);
+       else
+               hash_seq_init_with_hash_value(&status, TypeCacheHash,
hashvalue);
```

Is there anything that prevents the actual hash value from being zero?
I don't think so, but maybe I missed something.

If zero is indeed an invalid hash value I would like to reference the
corresponding code. If zero is a correct hash value we should either
change this by adding something like `if(!hash) hash++` or use an
additional boolean argument here.

--
Best regards,
Aleksander Alekseev

Aleksander Alekseev <aleksander@timescale.com> writes:

One thing that I couldn't immediately figure out is why 0 hash value
is treated as a magic invalid value in TypeCacheTypCallback():

I've not read this patch, but IIRC in some places we have a convention
that hash value zero is passed for an sinval reset event (that is,
"flush all cache entries").

regards, tom lane

Yep, exacly. One time from 2^32 we reset whole cache instead of one (or several)
entry with hash value = 0.

On 08.03.2024 18:35, Tom Lane wrote:

Aleksander Alekseev <aleksander@timescale.com> writes:

One thing that I couldn't immediately figure out is why 0 hash value
is treated as a magic invalid value in TypeCacheTypCallback():

I've not read this patch, but IIRC in some places we have a convention
that hash value zero is passed for an sinval reset event (that is,
"flush all cache entries").

regards, tom lane

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Hi,

Yep, exacly. One time from 2^32 we reset whole cache instead of one (or several)
entry with hash value = 0.

Got it. Here is an updated patch where I added a corresponding comment.

Now the patch LGTM. I'm going to change its status to RfC unless
anyone wants to review it too.

--
Best regards,
Aleksander Alekseev

Got it. Here is an updated patch where I added a corresponding comment.

Thank you!

Playing around I found one more place which could easily modified with
hash_seq_init_with_hash_value() call.
--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

On Tue, Mar 12, 2024 at 06:55:41PM +0300, Teodor Sigaev wrote:

Playing around I found one more place which could easily modified with
hash_seq_init_with_hash_value() call.

I think that this patch should be split for clarity, as there are a
few things that are independently useful. I guess something like
that:
- Introduction of hash_initial_lookup(), that simplifies 3 places of
dynahash.c where the same code is used. The routine should be
inlined.
- The split in hash_seq_search to force a different type of search is
weird, complicating the dynahash interface by hiding what seems like a
search mode. Rather than hasHashvalue that's hidden in the middle of
HASH_SEQ_STATUS, could it be better to have an entirely different API
for the search? That should be a patch on its own, as well.
- The typcache changes.
--
Michael

I think that this patch should be split for clarity, as there are a
few things that are independently useful. I guess something like
that:

Done, all patches should be applied consequentially.

- The typcache changes.

01-map_rel_to_type.v5.patch adds map relation to its type

- Introduction of hash_initial_lookup(), that simplifies 3 places of
dynahash.c where the same code is used. The routine should be
inlined.
- The split in hash_seq_search to force a different type of search is
weird, complicating the dynahash interface by hiding what seems like a
search mode. Rather than hasHashvalue that's hidden in the middle of
HASH_SEQ_STATUS, could it be better to have an entirely different API
for the search? That should be a patch on its own, as well.

02-hash_seq_init_with_hash_value.v5.patch - introduces a
hash_seq_init_with_hash_value() method. hash_initial_lookup() is marked as
inline, but I suppose, modern compilers are smart enough to inline it automatically.

Using separate interface for scanning hash with hash value will make scan code
more ugly in case when we need to use special value of hash value as it is done
in cache's scans. Look, instead of this simplified code:
if (hashvalue == 0)
hash_seq_init(&status, TypeCacheHash);
else
hash_seq_init_with_hash_value(&status, TypeCacheHash, hashvalue);
while ((typentry = hash_seq_search(&status)) != NULL) {
...
}
we will need to code something like that:
if (hashvalue == 0)
{
hash_seq_init(&status, TypeCacheHash);

while ((typentry = hash_seq_search(&status)) != NULL) {
...
}
}
else
{
hash_seq_init_with_hash_value(&status, TypeCacheHash, hashvalue);
while ((typentry = hash_seq_search_with_hash_value(&status)) != NULL) {
...
}
}
Or I didn't understand you.

I thought about integrate check inside existing loop in hash_seq_search() :
+ rerun:
if ((curElem = status->curEntry) != NULL)
{
/* Continuing scan of curBucket... */
status->curEntry = curElem->link;
if (status->curEntry == NULL) /* end of this bucket */
+ {
+ if (status->hasHashvalue)
+ hash_seq_term(status);

             ++status->curBucket;
+	}
+	else if (status->hasHashvalue && status->hashvalue !=
+                curElem->hashvalue)
+		goto rerun;
         return (void *) ELEMENTKEY(curElem);
     }

But for me it looks weird and adds some checks which will takes some CPU time.

03-att_with_hash_value.v5.patch - adds usage of previous patch.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

On Wed, Mar 13, 2024 at 04:40:38PM +0300, Teodor Sigaev wrote:

Done, all patches should be applied consequentially.

One thing that first pops out to me is that we can do the refactor of
hash_initial_lookup() as an independent piece, without the extra paths
introduced. But rather than returning the bucket hash and have the
bucket number as an in/out argument of hash_initial_lookup(), there is
an argument for reversing them: hash_search_with_hash_value() does not
care about the bucket number.

02-hash_seq_init_with_hash_value.v5.patch - introduces a
hash_seq_init_with_hash_value() method. hash_initial_lookup() is marked as
inline, but I suppose, modern compilers are smart enough to inline it
automatically.

Likely so, though that does not hurt to show the intention to the
reader.

So I would like to suggest the attached patch for this first piece.
What do you think?

It may also be an idea to use `git format-patch` when generating a
series of patches. That makes for easier reviews.
--
Michael

One thing that first pops out to me is that we can do the refactor of
hash_initial_lookup() as an independent piece, without the extra paths
introduced. But rather than returning the bucket hash and have the
bucket number as an in/out argument of hash_initial_lookup(), there is
an argument for reversing them: hash_search_with_hash_value() does not
care about the bucket number.

Ok, no problem

02-hash_seq_init_with_hash_value.v5.patch - introduces a
hash_seq_init_with_hash_value() method. hash_initial_lookup() is marked as
inline, but I suppose, modern compilers are smart enough to inline it
automatically.

Likely so, though that does not hurt to show the intention to the
reader.

Agree

So I would like to suggest the attached patch for this first piece.
What do you think?

I have not any objections

It may also be an idea to use `git format-patch` when generating a
series of patches. That makes for easier reviews.

Thanks, will try

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

On Thu, Mar 14, 2024 at 04:27:43PM +0300, Teodor Sigaev wrote:

So I would like to suggest the attached patch for this first piece.
What do you think?

I have not any objections

Okay, I've applied this piece for now. Not sure I'll have much room
to look at the rest.
--
Michael

Okay, I've applied this piece for now. Not sure I'll have much room
to look at the rest.

Thank you very much!

Rest of patches, rebased.

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Rest of patches, rebased.

Hello,
I read and tested only the first patch so far. Creation of temp
tables and rollback in your script work 3-4 times faster with
0001-type-cache.patch on my windows laptop.

In the patch I found a copy of the comment "If it's domain over
composite, reset flags...". Can we move the reset flags operation
and its comment into the invalidateCompositeTypeCacheEntry()
function? This simplify the TypeCacheRelCallback() func, but
adds two more IF statements when we need to clean up a cache
entry for a specific relation. (diff attached).
--
Roman Zharkov

On 3/15/24 17:57, Teodor Sigaev wrote:

Okay, I've applied this piece for now.  Not sure I'll have much room
to look at the rest.

Thank you very much!

I have spent some time reviewing this feature. I think we can discuss
and apply it step-by-step. So, the 0001-* patch is at this moment.
The feature addresses the issue of TypCache being bloated by intensive
usage of non-standard types and domains. It adds significant overhead
during relcache invalidation by thoroughly scanning this hash table.
IMO, this feature will be handy soon, as we already see some patches
where TypCache is intensively used for storing composite types—for
example, look into solutions proposed in [1]/messages/by-id/CAKcux6ktu-8tefLWtQuuZBYFaZA83vUzuRd7c1YHC-yEWyYFpg@mail.gmail.com.
One of my main concerns with this feature is the possibility of lost
entries, which could be mistakenly used by relations with the same oid
in the future. This seems particularly possible in cases with multiple
temporary tables. The author has attempted to address this by replacing
the typrelid and type_id fields in the mapRelType on each call of
lookup_type_cache. However, I believe we could further improve this by
removing the entry from mapRelType on invalidation, thus avoiding this
potential issue.
While reviewing the patch, I made some minor changes (see attachment)
that you're free to adopt or reject. However, it's crucial that the
patch includes a detailed explanation, not just a single sentence, to
ensure everyone understands the changes.
Upon closer inspection, I noticed that the current implementation only
invalidates the cache entry. While this is acceptable for standard
types, it may not be sufficient to maintain numerous custom types (as in
the example in the initial letter) or in cases where whole-row vars are
heavily used. In such scenarios, removing the entry and reducing the
hash table's size might be more efficient.
In toto, the 0001-* patch looks good, and I would be glad to see it in
the core.

[1]: /messages/by-id/CAKcux6ktu-8tefLWtQuuZBYFaZA83vUzuRd7c1YHC-yEWyYFpg@mail.gmail.com
/messages/by-id/CAKcux6ktu-8tefLWtQuuZBYFaZA83vUzuRd7c1YHC-yEWyYFpg@mail.gmail.com

--
regards,
Andrei Lepikhov
Postgres Professional

Hi!

On Wed, Apr 3, 2024 at 9:07 AM Andrei Lepikhov
<a.lepikhov@postgrespro.ru> wrote:

On 3/15/24 17:57, Teodor Sigaev wrote:

Okay, I've applied this piece for now. Not sure I'll have much room
to look at the rest.

Thank you very much!

I have spent some time reviewing this feature. I think we can discuss
and apply it step-by-step. So, the 0001-* patch is at this moment.
The feature addresses the issue of TypCache being bloated by intensive
usage of non-standard types and domains. It adds significant overhead
during relcache invalidation by thoroughly scanning this hash table.
IMO, this feature will be handy soon, as we already see some patches
where TypCache is intensively used for storing composite types—for
example, look into solutions proposed in [1].
One of my main concerns with this feature is the possibility of lost
entries, which could be mistakenly used by relations with the same oid
in the future. This seems particularly possible in cases with multiple
temporary tables. The author has attempted to address this by replacing
the typrelid and type_id fields in the mapRelType on each call of
lookup_type_cache. However, I believe we could further improve this by
removing the entry from mapRelType on invalidation, thus avoiding this
potential issue.
While reviewing the patch, I made some minor changes (see attachment)
that you're free to adopt or reject. However, it's crucial that the
patch includes a detailed explanation, not just a single sentence, to
ensure everyone understands the changes.
Upon closer inspection, I noticed that the current implementation only
invalidates the cache entry. While this is acceptable for standard
types, it may not be sufficient to maintain numerous custom types (as in
the example in the initial letter) or in cases where whole-row vars are
heavily used. In such scenarios, removing the entry and reducing the
hash table's size might be more efficient.
In toto, the 0001-* patch looks good, and I would be glad to see it in
the core.

I've revised the patchset. First of all, I've re-ordered the patches.

0001-0002 (former 0002-0003)
Comprises hash_search_with_hash_value() function and its application
to avoid full hash iteration in InvalidateAttoptCacheCallback() and
TypeCacheTypCallback(). I think this is quite straightforward
optimization without negative side effects. I've revised comments,
commit message and did some code beautification. I'm going to push
this if no objections.

0003 (former 0001)
I've revised this patch. I think main concerns expressed in the
thread about this path is that we don't have invalidation mechanism
for relid => typid map. Finally due to oid wraparound same relids
could get reused. That could lead to invalid entries in the map about
existing relids and typeids. This is rather messy, but I don't think
this could cause a material bug. The maps items are used only for
cache invalidation. Extra invalidation doesn't cause a bug. If type
with same relid will be cached, then correspoding map item will be
overridden, so no missing invalidation. However, I see the following
reasons for keeping consistent state of relid => typid map.

1) As the main use-case for this optimization is flood of temporary
tables, it would be nice not let relid => typid map bloat in this
case. I see that TypeCacheHash would get bloated, because its entries
are never deleted. However, I would prefer to not get this situation
even worse.
2) In future we may find some more use-cases for relid => typid map
besides cache invalidation. Keeping that in consistent state could be
advantage then.

In the attached patch, I'm keeping relid => typid map when
corresponding typentry have either TCFLAGS_HAVE_PG_TYPE_DATA, or
TCFLAGS_OPERATOR_FLAGS, or tupdesc. Thus, when temporary table gets
deleted, we would invalidate the map item.

It will be also nice to get rid of iteration over all the cached
domain types in TypeCacheRelCallback(). However, this typically
shouldn't be a problem since domain types are less tended to bloat.
Domain types are created manually, unlike composite types which are
automatically created for every temporary table. We will probably
need to optimize this in future, but I don't feel this to be necessary
in present patch.

I think the revised 0003 requires review.

------
Regards,
Alexander Korotkov
Supabase

On Mon, Aug 5, 2024 at 4:16 AM Alexander Korotkov <aekorotkov@gmail.com> wrote:

I've revised the patchset. First of all, I've re-ordered the patches.

0001-0002 (former 0002-0003)
Comprises hash_search_with_hash_value() function and its application
to avoid full hash iteration in InvalidateAttoptCacheCallback() and
TypeCacheTypCallback(). I think this is quite straightforward
optimization without negative side effects. I've revised comments,
commit message and did some code beautification. I'm going to push
this if no objections.

0003 (former 0001)
I've revised this patch. I think main concerns expressed in the
thread about this path is that we don't have invalidation mechanism
for relid => typid map. Finally due to oid wraparound same relids
could get reused. That could lead to invalid entries in the map about
existing relids and typeids. This is rather messy, but I don't think
this could cause a material bug. The maps items are used only for
cache invalidation. Extra invalidation doesn't cause a bug. If type
with same relid will be cached, then correspoding map item will be
overridden, so no missing invalidation. However, I see the following
reasons for keeping consistent state of relid => typid map.

1) As the main use-case for this optimization is flood of temporary
tables, it would be nice not let relid => typid map bloat in this
case. I see that TypeCacheHash would get bloated, because its entries
are never deleted. However, I would prefer to not get this situation
even worse.
2) In future we may find some more use-cases for relid => typid map
besides cache invalidation. Keeping that in consistent state could be
advantage then.

In the attached patch, I'm keeping relid => typid map when
corresponding typentry have either TCFLAGS_HAVE_PG_TYPE_DATA, or
TCFLAGS_OPERATOR_FLAGS, or tupdesc. Thus, when temporary table gets
deleted, we would invalidate the map item.

It will be also nice to get rid of iteration over all the cached
domain types in TypeCacheRelCallback(). However, this typically
shouldn't be a problem since domain types are less tended to bloat.
Domain types are created manually, unlike composite types which are
automatically created for every temporary table. We will probably
need to optimize this in future, but I don't feel this to be necessary
in present patch.

I think the revised 0003 requires review.

The rebased remaining patch is attached.

------
Regards,
Alexander Korotkov
Supabase