Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc9645f7

Browse files
committed
Second try at fixing O(N^2) problem in foreign key references.
This replaces ill-fated commit5ddc728,which was reverted because it broke active uses of FK cache entries. Inthis patch, we still do nothing more to invalidatable cache entries thanmark them as needing revalidation, so we won't break active uses. To keepdown the overhead of InvalidateConstraintCacheCallBack(), keep a list ofjust the currently-valid cache entries. (The entries are large enough thatsome added space for list links doesn't seem like a big problem.) Thiswould still be O(N^2) when there are many valid entries, though, so whenthe list gets too long, just force the "sinval reset" behavior to removeeverything from the list. I set the threshold at 1000 entries, somewhatarbitrarily. Possibly that could be fine-tuned later. Another item forfuture study is whether it's worth adding reference counting so that wecould safely remove invalidated entries. As-is, problem cases are likelyto end up with large and mostly invalid FK caches.Like the previous attempt, backpatch to 9.3.Jan Wieck and Tom Lane
1 parent5eb7024 commitc9645f7

File tree

1 file changed

+38
-7
lines changed

1 file changed

+38
-7
lines changed

‎src/backend/utils/adt/ri_triggers.c

Lines changed: 38 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
#include"commands/trigger.h"
4141
#include"executor/executor.h"
4242
#include"executor/spi.h"
43+
#include"lib/ilist.h"
4344
#include"parser/parse_coerce.h"
4445
#include"parser/parse_relation.h"
4546
#include"miscadmin.h"
@@ -125,6 +126,7 @@ typedef struct RI_ConstraintInfo
125126
* PK) */
126127
Oidff_eq_oprs[RI_MAX_NUMKEYS];/* equality operators (FK =
127128
* FK) */
129+
dlist_nodevalid_link;/* Link in list of valid entries */
128130
}RI_ConstraintInfo;
129131

130132

@@ -185,6 +187,8 @@ typedef struct RI_CompareHashEntry
185187
staticHTAB*ri_constraint_cache=NULL;
186188
staticHTAB*ri_query_cache=NULL;
187189
staticHTAB*ri_compare_cache=NULL;
190+
staticdlist_headri_constraint_cache_valid_list;
191+
staticintri_constraint_cache_valid_count=0;
188192

189193

190194
/* ----------
@@ -2924,6 +2928,13 @@ ri_LoadConstraintInfo(Oid constraintOid)
29242928

29252929
ReleaseSysCache(tup);
29262930

2931+
/*
2932+
* For efficient processing of invalidation messages below, we keep a
2933+
* doubly-linked list, and a count, of all currently valid entries.
2934+
*/
2935+
dlist_push_tail(&ri_constraint_cache_valid_list,&riinfo->valid_link);
2936+
ri_constraint_cache_valid_count++;
2937+
29272938
riinfo->valid= true;
29282939

29292940
returnriinfo;
@@ -2936,21 +2947,41 @@ ri_LoadConstraintInfo(Oid constraintOid)
29362947
* gets enough update traffic that it's probably worth being smarter.
29372948
* Invalidate any ri_constraint_cache entry associated with the syscache
29382949
* entry with the specified hash value, or all entries if hashvalue == 0.
2950+
*
2951+
* Note: at the time a cache invalidation message is processed there may be
2952+
* active references to the cache. Because of this we never remove entries
2953+
* from the cache, but only mark them invalid, which is harmless to active
2954+
* uses. (Any query using an entry should hold a lock sufficient to keep that
2955+
* data from changing under it --- but we may get cache flushes anyway.)
29392956
*/
29402957
staticvoid
29412958
InvalidateConstraintCacheCallBack(Datumarg,intcacheid,uint32hashvalue)
29422959
{
2943-
HASH_SEQ_STATUSstatus;
2944-
RI_ConstraintInfo*hentry;
2960+
dlist_mutable_iteriter;
29452961

29462962
Assert(ri_constraint_cache!=NULL);
29472963

2948-
hash_seq_init(&status,ri_constraint_cache);
2949-
while ((hentry= (RI_ConstraintInfo*)hash_seq_search(&status))!=NULL)
2964+
/*
2965+
* If the list of currently valid entries gets excessively large, we mark
2966+
* them all invalid so we can empty the list. This arrangement avoids
2967+
* O(N^2) behavior in situations where a session touches many foreign keys
2968+
* and also does many ALTER TABLEs, such as a restore from pg_dump.
2969+
*/
2970+
if (ri_constraint_cache_valid_count>1000)
2971+
hashvalue=0;/* pretend it's a cache reset */
2972+
2973+
dlist_foreach_modify(iter,&ri_constraint_cache_valid_list)
29502974
{
2951-
if (hentry->valid&&
2952-
(hashvalue==0||hentry->oidHashValue==hashvalue))
2953-
hentry->valid= false;
2975+
RI_ConstraintInfo*riinfo=dlist_container(RI_ConstraintInfo,
2976+
valid_link,iter.cur);
2977+
2978+
if (hashvalue==0||riinfo->oidHashValue==hashvalue)
2979+
{
2980+
riinfo->valid= false;
2981+
/* Remove invalidated entries from the list, too */
2982+
dlist_delete(iter.cur);
2983+
ri_constraint_cache_valid_count--;
2984+
}
29542985
}
29552986
}
29562987

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp