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

Commit14e991d

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 parent5863bac commit14e991d

File tree

2 files changed

+125
-23
lines changed

2 files changed

+125
-23
lines changed

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

Lines changed: 120 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,8 @@ static void CatCachePrintStats(int code, Datum arg);
8989
#endif
9090
staticvoidCatCacheRemoveCTup(CatCache*cache,CatCTup*ct);
9191
staticvoidCatCacheRemoveCList(CatCache*cache,CatCList*cl);
92+
staticvoidRehashCatCache(CatCache*cp);
93+
staticvoidRehashCatCacheLists(CatCache*cp);
9294
staticvoidCatalogCacheInitializeCache(CatCache*cache);
9395
staticCatCTup*CatalogCacheCreateEntry(CatCache*cache,
9496
HeapTuplentp,SysScanDescscandesc,
@@ -393,6 +395,7 @@ CatCachePrintStats(int code, Datum arg)
393395
longcc_neg_hits=0;
394396
longcc_newloads=0;
395397
longcc_invals=0;
398+
longcc_nlists=0;
396399
longcc_lsearches=0;
397400
longcc_lhits=0;
398401

@@ -402,7 +405,7 @@ CatCachePrintStats(int code, Datum arg)
402405

403406
if (cache->cc_ntup==0&&cache->cc_searches==0)
404407
continue;/* don't print unused caches */
405-
elog(DEBUG2,"catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
408+
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",
406409
cache->cc_relname,
407410
cache->cc_indexoid,
408411
cache->cc_ntup,
@@ -414,17 +417,19 @@ CatCachePrintStats(int code, Datum arg)
414417
cache->cc_searches-cache->cc_hits-cache->cc_neg_hits-cache->cc_newloads,
415418
cache->cc_searches-cache->cc_hits-cache->cc_neg_hits,
416419
cache->cc_invals,
420+
cache->cc_nlist,
417421
cache->cc_lsearches,
418422
cache->cc_lhits);
419423
cc_searches+=cache->cc_searches;
420424
cc_hits+=cache->cc_hits;
421425
cc_neg_hits+=cache->cc_neg_hits;
422426
cc_newloads+=cache->cc_newloads;
423427
cc_invals+=cache->cc_invals;
428+
cc_nlists+=cache->cc_nlist;
424429
cc_lsearches+=cache->cc_lsearches;
425430
cc_lhits+=cache->cc_lhits;
426431
}
427-
elog(DEBUG2,"catcache totals: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
432+
elog(DEBUG2,"catcache totals: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ldlists, %ldlsrch, %ld lhits",
428433
CacheHdr->ch_ntup,
429434
cc_searches,
430435
cc_hits,
@@ -434,6 +439,7 @@ CatCachePrintStats(int code, Datum arg)
434439
cc_searches-cc_hits-cc_neg_hits-cc_newloads,
435440
cc_searches-cc_hits-cc_neg_hits,
436441
cc_invals,
442+
cc_nlists,
437443
cc_lsearches,
438444
cc_lhits);
439445
}
@@ -522,6 +528,8 @@ CatCacheRemoveCList(CatCache *cache, CatCList *cl)
522528
cache->cc_keyno,cl->keys);
523529

524530
pfree(cl);
531+
532+
--cache->cc_nlist;
525533
}
526534

527535

@@ -560,14 +568,19 @@ CatCacheInvalidate(CatCache *cache, uint32 hashValue)
560568
* Invalidate *all* CatCLists in this cache; it's too hard to tell which
561569
* searches might still be correct, so just zap 'em all.
562570
*/
563-
dlist_foreach_modify(iter,&cache->cc_lists)
571+
for (inti=0;i<cache->cc_nlbuckets;i++)
564572
{
565-
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
573+
dlist_head*bucket=&cache->cc_lbucket[i];
566574

567-
if (cl->refcount>0)
568-
cl->dead= true;
569-
else
570-
CatCacheRemoveCList(cache,cl);
575+
dlist_foreach_modify(iter,bucket)
576+
{
577+
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
578+
579+
if (cl->refcount>0)
580+
cl->dead= true;
581+
else
582+
CatCacheRemoveCList(cache,cl);
583+
}
571584
}
572585

573586
/*
@@ -640,14 +653,19 @@ ResetCatalogCache(CatCache *cache)
640653
inti;
641654

642655
/* Remove each list in this cache, or at least mark it dead */
643-
dlist_foreach_modify(iter,&cache->cc_lists)
656+
for (i=0;i<cache->cc_nlbuckets;i++)
644657
{
645-
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
658+
dlist_head*bucket=&cache->cc_lbucket[i];
646659

647-
if (cl->refcount>0)
648-
cl->dead= true;
649-
else
650-
CatCacheRemoveCList(cache,cl);
660+
dlist_foreach_modify(iter,bucket)
661+
{
662+
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
663+
664+
if (cl->refcount>0)
665+
cl->dead= true;
666+
else
667+
CatCacheRemoveCList(cache,cl);
668+
}
651669
}
652670

653671
/* Remove each tuple in this cache, or at least mark it dead */
@@ -811,6 +829,12 @@ InitCatCache(int id,
811829
MCXT_ALLOC_ZERO);
812830
cp->cc_bucket=palloc0(nbuckets*sizeof(dlist_head));
813831

832+
/*
833+
* Many catcaches never receive any list searches. Therefore, we don't
834+
* allocate the cc_lbuckets till we get a list search.
835+
*/
836+
cp->cc_lbucket=NULL;
837+
814838
/*
815839
* initialize the cache's relation information for the relation
816840
* corresponding to this cache, and initialize some of the new cache's
@@ -823,7 +847,9 @@ InitCatCache(int id,
823847
cp->cc_relisshared= false;/* temporary */
824848
cp->cc_tupdesc= (TupleDesc)NULL;
825849
cp->cc_ntup=0;
850+
cp->cc_nlist=0;
826851
cp->cc_nbuckets=nbuckets;
852+
cp->cc_nlbuckets=0;
827853
cp->cc_nkeys=nkeys;
828854
for (i=0;i<nkeys;++i)
829855
cp->cc_keyno[i]=key[i];
@@ -885,6 +911,44 @@ RehashCatCache(CatCache *cp)
885911
cp->cc_bucket=newbucket;
886912
}
887913

914+
/*
915+
* Enlarge a catcache's list storage, doubling the number of buckets.
916+
*/
917+
staticvoid
918+
RehashCatCacheLists(CatCache*cp)
919+
{
920+
dlist_head*newbucket;
921+
intnewnbuckets;
922+
inti;
923+
924+
elog(DEBUG1,"rehashing catalog cache id %d for %s; %d lists, %d buckets",
925+
cp->id,cp->cc_relname,cp->cc_nlist,cp->cc_nlbuckets);
926+
927+
/* Allocate a new, larger, hash table. */
928+
newnbuckets=cp->cc_nlbuckets*2;
929+
newbucket= (dlist_head*)MemoryContextAllocZero(CacheMemoryContext,newnbuckets*sizeof(dlist_head));
930+
931+
/* Move all entries from old hash table to new. */
932+
for (i=0;i<cp->cc_nlbuckets;i++)
933+
{
934+
dlist_mutable_iteriter;
935+
936+
dlist_foreach_modify(iter,&cp->cc_lbucket[i])
937+
{
938+
CatCList*cl=dlist_container(CatCList,cache_elem,iter.cur);
939+
inthashIndex=HASH_INDEX(cl->hash_value,newnbuckets);
940+
941+
dlist_delete(iter.cur);
942+
dlist_push_head(&newbucket[hashIndex],&cl->cache_elem);
943+
}
944+
}
945+
946+
/* Switch to the new array. */
947+
pfree(cp->cc_lbucket);
948+
cp->cc_nlbuckets=newnbuckets;
949+
cp->cc_lbucket=newbucket;
950+
}
951+
888952
/*
889953
*CatalogCacheInitializeCache
890954
*
@@ -1527,7 +1591,9 @@ SearchCatCacheList(CatCache *cache,
15271591
Datumv4=0;/* dummy last-column value */
15281592
Datumarguments[CATCACHE_MAXKEYS];
15291593
uint32lHashValue;
1594+
IndexlHashIndex;
15301595
dlist_iteriter;
1596+
dlist_head*lbucket;
15311597
CatCList*cl;
15321598
CatCTup*ct;
15331599
List*volatilectlist;
@@ -1541,7 +1607,7 @@ SearchCatCacheList(CatCache *cache,
15411607
/*
15421608
* one-time startup overhead for each cache
15431609
*/
1544-
if (cache->cc_tupdesc==NULL)
1610+
if (unlikely(cache->cc_tupdesc==NULL))
15451611
CatalogCacheInitializeCache(cache);
15461612

15471613
Assert(nkeys>0&&nkeys<cache->cc_nkeys);
@@ -1557,19 +1623,45 @@ SearchCatCacheList(CatCache *cache,
15571623
arguments[3]=v4;
15581624

15591625
/*
1560-
* compute a hash value of the given keys for faster search. We don't
1561-
* presently divide the CatCList items into buckets, but this still lets
1562-
* us skip non-matching items quickly most of the time.
1626+
* If we haven't previously done a list search in this cache, create the
1627+
* bucket header array; otherwise, consider whether it's time to enlarge
1628+
* it.
1629+
*/
1630+
if (cache->cc_lbucket==NULL)
1631+
{
1632+
/* Arbitrary initial size --- must be a power of 2 */
1633+
intnbuckets=16;
1634+
1635+
cache->cc_lbucket= (dlist_head*)
1636+
MemoryContextAllocZero(CacheMemoryContext,
1637+
nbuckets*sizeof(dlist_head));
1638+
/* Don't set cc_nlbuckets if we get OOM allocating cc_lbucket */
1639+
cache->cc_nlbuckets=nbuckets;
1640+
}
1641+
else
1642+
{
1643+
/*
1644+
* If the hash table has become too full, enlarge the buckets array.
1645+
* Quite arbitrarily, we enlarge when fill factor > 2.
1646+
*/
1647+
if (cache->cc_nlist>cache->cc_nlbuckets*2)
1648+
RehashCatCacheLists(cache);
1649+
}
1650+
1651+
/*
1652+
* Find the hash bucket in which to look for the CatCList.
15631653
*/
15641654
lHashValue=CatalogCacheComputeHashValue(cache,nkeys,v1,v2,v3,v4);
1655+
lHashIndex=HASH_INDEX(lHashValue,cache->cc_nlbuckets);
15651656

15661657
/*
15671658
* scan the items until we find a match or exhaust our list
15681659
*
15691660
* Note: it's okay to use dlist_foreach here, even though we modify the
15701661
* dlist within the loop, because we don't continue the loop afterwards.
15711662
*/
1572-
dlist_foreach(iter,&cache->cc_lists)
1663+
lbucket=&cache->cc_lbucket[lHashIndex];
1664+
dlist_foreach(iter,lbucket)
15731665
{
15741666
cl=dlist_container(CatCList,cache_elem,iter.cur);
15751667

@@ -1589,13 +1681,13 @@ SearchCatCacheList(CatCache *cache,
15891681
continue;
15901682

15911683
/*
1592-
* We found a matching list. Move the list to the front of the
1593-
*cache's list-of-lists, to speed subsequent searches. (We do not
1684+
* We found a matching list. Move the list to the front of the list
1685+
*for its hashbucket, so as to speed subsequent searches. (We do not
15941686
* move the members to the fronts of their hashbucket lists, however,
15951687
* since there's no point in that unless they are searched for
15961688
* individually.)
15971689
*/
1598-
dlist_move_head(&cache->cc_lists,&cl->cache_elem);
1690+
dlist_move_head(lbucket,&cl->cache_elem);
15991691

16001692
/* Bump the list's refcount and return it */
16011693
ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner);
@@ -1806,7 +1898,12 @@ SearchCatCacheList(CatCache *cache,
18061898
}
18071899
Assert(i==nmembers);
18081900

1809-
dlist_push_head(&cache->cc_lists,&cl->cache_elem);
1901+
/*
1902+
* Add the CatCList to the appropriate bucket, and count it.
1903+
*/
1904+
dlist_push_head(lbucket,&cl->cache_elem);
1905+
1906+
cache->cc_nlist++;
18101907

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

‎src/include/utils/catcache.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -62,6 +62,11 @@ typedef struct catcache
6262
ScanKeyDatacc_skey[CATCACHE_MAXKEYS];/* precomputed key info for heap
6363
* scans */
6464

65+
/* These fields are placed here to avoid ABI breakage in v16 */
66+
intcc_nlist;/* # of CatCLists currently in this cache */
67+
intcc_nlbuckets;/* # of CatCList hash buckets in this cache */
68+
dlist_head*cc_lbucket;/* hash buckets for CatCLists */
69+
6570
/*
6671
* Keep these at the end, so that compiling catcache.c with CATCACHE_STATS
6772
* doesn't break ABI for other modules

0 commit comments

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