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

Commit473182c

Browse files
committed
Use a hash table for catcache.c's CatCList objects.
Up to now, all of the "catcache list" objects within a catalog cachewere just chained together on a single dlist, requiring O(N) time tosearch. Remarkably, we've not had serious performance problems withthat so far; but we got a complaint of a bad performance regressionfrom v15 in a case with a large number of roles in the system, whichtraced down to O(N^2) total time when we probed N catcache lists.Replace that data structure with a hashtable having an enlargeablenumber of dlists, in an exactly parallel way to the data structurewe've used for years for the plain CatCTup cache members. The extracost of maintaining a hash table seems negligible, since we werealready computing a hash value for list searches.Normally this'd be HEAD-only material, but in view of the performanceregression it seems advisable to back-patch into v16. In the v16version of the patch, leave the dead cc_lists field where it is andadd the new fields at the end of struct catcache, to avoid possibleABI breakage in case any external code is looking at these structs.(We assume no external code is actually allocating new catcachestructs.)Per report from alex work.Discussion:https://postgr.es/m/CAGvXd3OSMbJQwOSc-Tq-Ro1CAz=vggErdSG7pv2s6vmmTOLJSg@mail.gmail.com
1 parent6acb0a6 commit473182c

File tree

2 files changed

+124
-25
lines changed

2 files changed

+124
-25
lines changed

‎src/backend/utils/cache/catcache.c‎

Lines changed: 120 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,8 @@ static void CatCachePrintStats(int code, Datum arg);
8888
#endif
8989
staticvoidCatCacheRemoveCTup(CatCache*cache,CatCTup*ct);
9090
staticvoidCatCacheRemoveCList(CatCache*cache,CatCList*cl);
91+
staticvoidRehashCatCache(CatCache*cp);
92+
staticvoidRehashCatCacheLists(CatCache*cp);
9193
staticvoidCatalogCacheInitializeCache(CatCache*cache);
9294
staticCatCTup*CatalogCacheCreateEntry(CatCache*cache,
9395
HeapTuplentp,SysScanDescscandesc,
@@ -444,6 +446,7 @@ CatCachePrintStats(int code, Datum arg)
444446
longcc_neg_hits=0;
445447
longcc_newloads=0;
446448
longcc_invals=0;
449+
longcc_nlists=0;
447450
longcc_lsearches=0;
448451
longcc_lhits=0;
449452

@@ -453,7 +456,7 @@ CatCachePrintStats(int code, Datum arg)
453456

454457
if (cache->cc_ntup==0&&cache->cc_searches==0)
455458
continue;/* don't print unused caches */
456-
elog(DEBUG2,"catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
459+
elog(DEBUG2,"catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %d lists, %ld lsrch, %ld lhits",
457460
cache->cc_relname,
458461
cache->cc_indexoid,
459462
cache->cc_ntup,
@@ -465,17 +468,19 @@ CatCachePrintStats(int code, Datum arg)
465468
cache->cc_searches-cache->cc_hits-cache->cc_neg_hits-cache->cc_newloads,
466469
cache->cc_searches-cache->cc_hits-cache->cc_neg_hits,
467470
cache->cc_invals,
471+
cache->cc_nlist,
468472
cache->cc_lsearches,
469473
cache->cc_lhits);
470474
cc_searches+=cache->cc_searches;
471475
cc_hits+=cache->cc_hits;
472476
cc_neg_hits+=cache->cc_neg_hits;
473477
cc_newloads+=cache->cc_newloads;
474478
cc_invals+=cache->cc_invals;
479+
cc_nlists+=cache->cc_nlist;
475480
cc_lsearches+=cache->cc_lsearches;
476481
cc_lhits+=cache->cc_lhits;
477482
}
478-
elog(DEBUG2,"catcache totals: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
483+
elog(DEBUG2,"catcache totals: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ldlists, %ldlsrch, %ld lhits",
479484
CacheHdr->ch_ntup,
480485
cc_searches,
481486
cc_hits,
@@ -485,6 +490,7 @@ CatCachePrintStats(int code, Datum arg)
485490
cc_searches-cc_hits-cc_neg_hits-cc_newloads,
486491
cc_searches-cc_hits-cc_neg_hits,
487492
cc_invals,
493+
cc_nlists,
488494
cc_lsearches,
489495
cc_lhits);
490496
}
@@ -573,6 +579,8 @@ CatCacheRemoveCList(CatCache *cache, CatCList *cl)
573579
cache->cc_keyno,cl->keys);
574580

575581
pfree(cl);
582+
583+
--cache->cc_nlist;
576584
}
577585

578586

@@ -611,14 +619,19 @@ CatCacheInvalidate(CatCache *cache, uint32 hashValue)
611619
* Invalidate *all* CatCLists in this cache; it's too hard to tell which
612620
* searches might still be correct, so just zap 'em all.
613621
*/
614-
dlist_foreach_modify(iter,&cache->cc_lists)
622+
for (inti=0;i<cache->cc_nlbuckets;i++)
615623
{
616-
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
624+
dlist_head*bucket=&cache->cc_lbucket[i];
617625

618-
if (cl->refcount>0)
619-
cl->dead= true;
620-
else
621-
CatCacheRemoveCList(cache,cl);
626+
dlist_foreach_modify(iter,bucket)
627+
{
628+
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
629+
630+
if (cl->refcount>0)
631+
cl->dead= true;
632+
else
633+
CatCacheRemoveCList(cache,cl);
634+
}
622635
}
623636

624637
/*
@@ -691,14 +704,19 @@ ResetCatalogCache(CatCache *cache)
691704
inti;
692705

693706
/* Remove each list in this cache, or at least mark it dead */
694-
dlist_foreach_modify(iter,&cache->cc_lists)
707+
for (i=0;i<cache->cc_nlbuckets;i++)
695708
{
696-
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
709+
dlist_head*bucket=&cache->cc_lbucket[i];
697710

698-
if (cl->refcount>0)
699-
cl->dead= true;
700-
else
701-
CatCacheRemoveCList(cache,cl);
711+
dlist_foreach_modify(iter,bucket)
712+
{
713+
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
714+
715+
if (cl->refcount>0)
716+
cl->dead= true;
717+
else
718+
CatCacheRemoveCList(cache,cl);
719+
}
702720
}
703721

704722
/* Remove each tuple in this cache, or at least mark it dead */
@@ -862,6 +880,12 @@ InitCatCache(int id,
862880
MCXT_ALLOC_ZERO);
863881
cp->cc_bucket=palloc0(nbuckets*sizeof(dlist_head));
864882

883+
/*
884+
* Many catcaches never receive any list searches. Therefore, we don't
885+
* allocate the cc_lbuckets till we get a list search.
886+
*/
887+
cp->cc_lbucket=NULL;
888+
865889
/*
866890
* initialize the cache's relation information for the relation
867891
* corresponding to this cache, and initialize some of the new cache's
@@ -874,7 +898,9 @@ InitCatCache(int id,
874898
cp->cc_relisshared= false;/* temporary */
875899
cp->cc_tupdesc= (TupleDesc)NULL;
876900
cp->cc_ntup=0;
901+
cp->cc_nlist=0;
877902
cp->cc_nbuckets=nbuckets;
903+
cp->cc_nlbuckets=0;
878904
cp->cc_nkeys=nkeys;
879905
for (i=0;i<nkeys;++i)
880906
{
@@ -939,6 +965,44 @@ RehashCatCache(CatCache *cp)
939965
cp->cc_bucket=newbucket;
940966
}
941967

968+
/*
969+
* Enlarge a catcache's list storage, doubling the number of buckets.
970+
*/
971+
staticvoid
972+
RehashCatCacheLists(CatCache*cp)
973+
{
974+
dlist_head*newbucket;
975+
intnewnbuckets;
976+
inti;
977+
978+
elog(DEBUG1,"rehashing catalog cache id %d for %s; %d lists, %d buckets",
979+
cp->id,cp->cc_relname,cp->cc_nlist,cp->cc_nlbuckets);
980+
981+
/* Allocate a new, larger, hash table. */
982+
newnbuckets=cp->cc_nlbuckets*2;
983+
newbucket= (dlist_head*)MemoryContextAllocZero(CacheMemoryContext,newnbuckets*sizeof(dlist_head));
984+
985+
/* Move all entries from old hash table to new. */
986+
for (i=0;i<cp->cc_nlbuckets;i++)
987+
{
988+
dlist_mutable_iteriter;
989+
990+
dlist_foreach_modify(iter,&cp->cc_lbucket[i])
991+
{
992+
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
993+
inthashIndex=HASH_INDEX(cl->hash_value,newnbuckets);
994+
995+
dlist_delete(iter.cur);
996+
dlist_push_head(&newbucket[hashIndex],&cl->cache_elem);
997+
}
998+
}
999+
1000+
/* Switch to the new array. */
1001+
pfree(cp->cc_lbucket);
1002+
cp->cc_nlbuckets=newnbuckets;
1003+
cp->cc_lbucket=newbucket;
1004+
}
1005+
9421006
/*
9431007
*CatalogCacheInitializeCache
9441008
*
@@ -1588,7 +1652,9 @@ SearchCatCacheList(CatCache *cache,
15881652
Datumv4=0;/* dummy last-column value */
15891653
Datumarguments[CATCACHE_MAXKEYS];
15901654
uint32lHashValue;
1655+
IndexlHashIndex;
15911656
dlist_iteriter;
1657+
dlist_head*lbucket;
15921658
CatCList*cl;
15931659
CatCTup*ct;
15941660
List*volatilectlist;
@@ -1602,7 +1668,7 @@ SearchCatCacheList(CatCache *cache,
16021668
/*
16031669
* one-time startup overhead for each cache
16041670
*/
1605-
if (cache->cc_tupdesc==NULL)
1671+
if (unlikely(cache->cc_tupdesc==NULL))
16061672
CatalogCacheInitializeCache(cache);
16071673

16081674
Assert(nkeys>0&&nkeys<cache->cc_nkeys);
@@ -1618,19 +1684,45 @@ SearchCatCacheList(CatCache *cache,
16181684
arguments[3]=v4;
16191685

16201686
/*
1621-
* compute a hash value of the given keys for faster search. We don't
1622-
* presently divide the CatCList items into buckets, but this still lets
1623-
* us skip non-matching items quickly most of the time.
1687+
* If we haven't previously done a list search in this cache, create the
1688+
* bucket header array; otherwise, consider whether it's time to enlarge
1689+
* it.
1690+
*/
1691+
if (cache->cc_lbucket==NULL)
1692+
{
1693+
/* Arbitrary initial size --- must be a power of 2 */
1694+
intnbuckets=16;
1695+
1696+
cache->cc_lbucket= (dlist_head*)
1697+
MemoryContextAllocZero(CacheMemoryContext,
1698+
nbuckets*sizeof(dlist_head));
1699+
/* Don't set cc_nlbuckets if we get OOM allocating cc_lbucket */
1700+
cache->cc_nlbuckets=nbuckets;
1701+
}
1702+
else
1703+
{
1704+
/*
1705+
* If the hash table has become too full, enlarge the buckets array.
1706+
* Quite arbitrarily, we enlarge when fill factor > 2.
1707+
*/
1708+
if (cache->cc_nlist>cache->cc_nlbuckets*2)
1709+
RehashCatCacheLists(cache);
1710+
}
1711+
1712+
/*
1713+
* Find the hash bucket in which to look for the CatCList.
16241714
*/
16251715
lHashValue=CatalogCacheComputeHashValue(cache,nkeys,v1,v2,v3,v4);
1716+
lHashIndex=HASH_INDEX(lHashValue,cache->cc_nlbuckets);
16261717

16271718
/*
16281719
* scan the items until we find a match or exhaust our list
16291720
*
16301721
* Note: it's okay to use dlist_foreach here, even though we modify the
16311722
* dlist within the loop, because we don't continue the loop afterwards.
16321723
*/
1633-
dlist_foreach(iter,&cache->cc_lists)
1724+
lbucket=&cache->cc_lbucket[lHashIndex];
1725+
dlist_foreach(iter,lbucket)
16341726
{
16351727
cl=dlist_container(CatCList,cache_elem,iter.cur);
16361728

@@ -1650,13 +1742,13 @@ SearchCatCacheList(CatCache *cache,
16501742
continue;
16511743

16521744
/*
1653-
* We found a matching list. Move the list to the front of the
1654-
*cache's list-of-lists, to speed subsequent searches. (We do not
1745+
* We found a matching list. Move the list to the front of the list
1746+
*for its hashbucket, so as to speed subsequent searches. (We do not
16551747
* move the members to the fronts of their hashbucket lists, however,
16561748
* since there's no point in that unless they are searched for
16571749
* individually.)
16581750
*/
1659-
dlist_move_head(&cache->cc_lists,&cl->cache_elem);
1751+
dlist_move_head(lbucket,&cl->cache_elem);
16601752

16611753
/* Bump the list's refcount and return it */
16621754
ResourceOwnerEnlarge(CurrentResourceOwner);
@@ -1868,7 +1960,12 @@ SearchCatCacheList(CatCache *cache,
18681960
}
18691961
Assert(i==nmembers);
18701962

1871-
dlist_push_head(&cache->cc_lists,&cl->cache_elem);
1963+
/*
1964+
* Add the CatCList to the appropriate bucket, and count it.
1965+
*/
1966+
dlist_push_head(lbucket,&cl->cache_elem);
1967+
1968+
cache->cc_nlist++;
18721969

18731970
/* Finally, bump the list's refcount and return it */
18741971
cl->refcount++;

‎src/include/utils/catcache.h‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -51,9 +51,11 @@ typedef struct catcache
5151
CCFastEqualFNcc_fastequal[CATCACHE_MAXKEYS];/* fast equal function for
5252
* each key */
5353
intcc_keyno[CATCACHE_MAXKEYS];/* AttrNumber of each key */
54-
dlist_headcc_lists;/* list of CatCList structs */
55-
intcc_ntup;/* # of tuples currently in this cache */
5654
intcc_nkeys;/* # of keys (1..CATCACHE_MAXKEYS) */
55+
intcc_ntup;/* # of tuples currently in this cache */
56+
intcc_nlist;/* # of CatCLists currently in this cache */
57+
intcc_nlbuckets;/* # of CatCList hash buckets in this cache */
58+
dlist_head*cc_lbucket;/* hash buckets for CatCLists */
5759
constchar*cc_relname;/* name of relation the tuples come from */
5860
Oidcc_reloid;/* OID of relation the tuples come from */
5961
Oidcc_indexoid;/* OID of index matching cache keys */

0 commit comments

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