From: Kyotaro Horiguchi Date: Mon, 12 Mar 2018 15:52:18 +0900 Subject: [PATCH 2/3] introduce dynhash pruning --- src/backend/utils/hash/dynahash.c | 166 +++++++++++++++++++++++++++++++++----- src/include/utils/catcache.h | 12 +++ src/include/utils/hsearch.h | 21 ++++- 3 files changed, 179 insertions(+), 20 deletions(-) diff --git a/src/backend/utils/hash/dynahash.c b/src/backend/utils/hash/dynahash.c index 785e0faffb..261f8d9577 100644 --- a/src/backend/utils/hash/dynahash.c +++ b/src/backend/utils/hash/dynahash.c @@ -88,6 +88,7 @@ #include "access/xact.h" #include "storage/shmem.h" #include "storage/spin.h" +#include "utils/catcache.h" #include "utils/dynahash.h" #include "utils/memutils.h" @@ -184,6 +185,12 @@ struct HASHHDR long ssize; /* segment size --- must be power of 2 */ int sshift; /* segment shift = log2(ssize) */ int nelem_alloc; /* number of entries to allocate at once */ + bool prunable; /* true if prunable */ + HASH_PRUNE_CB prune_cb; /* function to call instead of just deleting */ + + /* These fields point to variables to control pruning */ + int *memory_target; /* pointer to memory target value in kB */ + int *prune_min_age; /* pointer to prune minimum age value in sec */ #ifdef HASH_STATISTICS @@ -227,16 +234,18 @@ struct HTAB int sshift; /* segment shift = log2(ssize) */ }; +#define HASHELEMENT_SIZE(ctlp) MAXALIGN(ctlp->prunable ? sizeof(PRUNABLE_HASHELEMENT) : sizeof(HASHELEMENT)) + /* * Key (also entry) part of a HASHELEMENT */ -#define ELEMENTKEY(helem) (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT))) +#define ELEMENTKEY(helem, ctlp) (((char *)(helem)) + HASHELEMENT_SIZE(ctlp)) /* * Obtain element pointer given pointer to key */ -#define ELEMENT_FROM_KEY(key) \ - ((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT)))) +#define ELEMENT_FROM_KEY(key, ctlp) \ + ((HASHELEMENT *) (((char *) (key)) - HASHELEMENT_SIZE(ctlp))) /* * Fast MOD arithmetic, assuming that y is a power of 2 ! @@ -257,6 +266,7 @@ static HASHSEGMENT seg_alloc(HTAB *hashp); static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx); static bool dir_realloc(HTAB *hashp); static bool expand_table(HTAB *hashp); +static bool prune_entries(HTAB *hashp); static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx); static void hdefault(HTAB *hashp); static int choose_nelem_alloc(Size entrysize); @@ -499,6 +509,29 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags) hctl->entrysize = info->entrysize; } + /* + * Set up pruning. + * + * We have two knobs to control pruning and a hash can share them of + * syscache. + * + */ + if (flags & HASH_PRUNABLE) + { + hctl->prunable = true; + hctl->prune_cb = info->prune_cb; + if (info->memory_target) + hctl->memory_target = info->memory_target; + else + hctl->memory_target = &cache_memory_target; + if (info->prune_min_age) + hctl->prune_min_age = info->prune_min_age; + else + hctl->prune_min_age = &cache_prune_min_age; + } + else + hctl->prunable = false; + /* make local copies of heavily-used constant fields */ hashp->keysize = hctl->keysize; hashp->ssize = hctl->ssize; @@ -984,7 +1017,7 @@ hash_search_with_hash_value(HTAB *hashp, while (currBucket != NULL) { if (currBucket->hashvalue == hashvalue && - match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0) + match(ELEMENTKEY(currBucket, hctl), keyPtr, keysize) == 0) break; prevBucketPtr = &(currBucket->link); currBucket = *prevBucketPtr; @@ -997,6 +1030,17 @@ hash_search_with_hash_value(HTAB *hashp, if (foundPtr) *foundPtr = (bool) (currBucket != NULL); + /* Update access counter if needed */ + if (hctl->prunable && currBucket && + (action == HASH_FIND || action == HASH_ENTER)) + { + PRUNABLE_HASHELEMENT *prunable_elm = + (PRUNABLE_HASHELEMENT *) currBucket; + if (prunable_elm->naccess < 2) + prunable_elm->naccess++; + prunable_elm->last_access = GetCatCacheClock(); + } + /* * OK, now what? */ @@ -1004,7 +1048,8 @@ hash_search_with_hash_value(HTAB *hashp, { case HASH_FIND: if (currBucket != NULL) - return (void *) ELEMENTKEY(currBucket); + return (void *) ELEMENTKEY(currBucket, hctl); + return NULL; case HASH_REMOVE: @@ -1033,7 +1078,7 @@ hash_search_with_hash_value(HTAB *hashp, * element, because someone else is going to reuse it the next * time something is added to the table */ - return (void *) ELEMENTKEY(currBucket); + return (void *) ELEMENTKEY(currBucket, hctl); } return NULL; @@ -1045,7 +1090,7 @@ hash_search_with_hash_value(HTAB *hashp, case HASH_ENTER: /* Return existing element if found, else create one */ if (currBucket != NULL) - return (void *) ELEMENTKEY(currBucket); + return (void *) ELEMENTKEY(currBucket, hctl); /* disallow inserts if frozen */ if (hashp->frozen) @@ -1075,8 +1120,18 @@ hash_search_with_hash_value(HTAB *hashp, /* copy key into record */ currBucket->hashvalue = hashvalue; - hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize); + hashp->keycopy(ELEMENTKEY(currBucket, hctl), keyPtr, keysize); + /* set access counter */ + if (hctl->prunable) + { + PRUNABLE_HASHELEMENT *prunable_elm = + (PRUNABLE_HASHELEMENT *) currBucket; + if (prunable_elm->naccess < 2) + prunable_elm->naccess++; + prunable_elm->last_access = GetCatCacheClock(); + } + /* * Caller is expected to fill the data field on return. DO NOT * insert any code that could possibly throw error here, as doing @@ -1084,7 +1139,7 @@ hash_search_with_hash_value(HTAB *hashp, * caller's data structure. */ - return (void *) ELEMENTKEY(currBucket); + return (void *) ELEMENTKEY(currBucket, hctl); } elog(ERROR, "unrecognized hash action code: %d", (int) action); @@ -1116,7 +1171,7 @@ hash_update_hash_key(HTAB *hashp, void *existingEntry, const void *newKeyPtr) { - HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry); + HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry, hashp->hctl); HASHHDR *hctl = hashp->hctl; uint32 newhashvalue; Size keysize; @@ -1200,7 +1255,7 @@ hash_update_hash_key(HTAB *hashp, while (currBucket != NULL) { if (currBucket->hashvalue == newhashvalue && - match(ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0) + match(ELEMENTKEY(currBucket, hctl), newKeyPtr, keysize) == 0) break; prevBucketPtr = &(currBucket->link); currBucket = *prevBucketPtr; @@ -1234,7 +1289,7 @@ hash_update_hash_key(HTAB *hashp, /* copy new key into record */ currBucket->hashvalue = newhashvalue; - hashp->keycopy(ELEMENTKEY(currBucket), newKeyPtr, keysize); + hashp->keycopy(ELEMENTKEY(currBucket, hctl), newKeyPtr, keysize); /* rest of record is untouched */ @@ -1388,8 +1443,8 @@ hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp) void * hash_seq_search(HASH_SEQ_STATUS *status) { - HTAB *hashp; - HASHHDR *hctl; + HTAB *hashp = status->hashp; + HASHHDR *hctl = hashp->hctl; uint32 max_bucket; long ssize; long segment_num; @@ -1404,15 +1459,13 @@ hash_seq_search(HASH_SEQ_STATUS *status) status->curEntry = curElem->link; if (status->curEntry == NULL) /* end of this bucket */ ++status->curBucket; - return (void *) ELEMENTKEY(curElem); + return (void *) ELEMENTKEY(curElem, hctl); } /* * Search for next nonempty bucket starting at curBucket. */ curBucket = status->curBucket; - hashp = status->hashp; - hctl = hashp->hctl; ssize = hashp->ssize; max_bucket = hctl->max_bucket; @@ -1458,7 +1511,7 @@ hash_seq_search(HASH_SEQ_STATUS *status) if (status->curEntry == NULL) /* end of this bucket */ ++curBucket; status->curBucket = curBucket; - return (void *) ELEMENTKEY(curElem); + return (void *) ELEMENTKEY(curElem, hctl); } void @@ -1552,6 +1605,10 @@ expand_table(HTAB *hashp) */ if ((uint32) new_bucket > hctl->high_mask) { + /* try pruning before expansion. return true on success */ + if (hctl->prunable && prune_entries(hashp)) + return true; + hctl->low_mask = hctl->high_mask; hctl->high_mask = (uint32) new_bucket | hctl->low_mask; } @@ -1594,6 +1651,77 @@ expand_table(HTAB *hashp) return true; } +static bool +prune_entries(HTAB *hashp) +{ + HASHHDR *hctl = hashp->hctl; + HASH_SEQ_STATUS status; + void *elm; + TimestampTz currclock = GetCatCacheClock(); + int nall = 0, + nremoved = 0; + + Assert(hctl->prunable); + + /* Return if pruning is currently disabled or not doable */ + if (*hctl->prune_min_age < 0 || hashp->frozen || has_seq_scans(hashp)) + return false; + + /* + * we don't prune before reaching this size. We only consider bucket array + * size since it is the significant part of memory usage. + */ + if (hctl->dsize * sizeof(HASHBUCKET) * hashp->ssize < + (Size) *hctl->memory_target * 1024L) + return false; + + /* Ok, start pruning. we can use seq scan here. */ + hash_seq_init(&status, hashp); + while ((elm = hash_seq_search(&status)) != NULL) + { + PRUNABLE_HASHELEMENT *helm = + (PRUNABLE_HASHELEMENT *)ELEMENT_FROM_KEY(elm, hctl); + long entry_age; + int us; + + nall++; + + TimestampDifference(helm->last_access, currclock, &entry_age, &us); + + /* + * consider pruning if this entry has not been accessed for a certain + * time + */ + if (entry_age > *hctl->prune_min_age) + { + /* Wait for the next chance if this is recently used */ + if (helm->naccess > 0) + helm->naccess--; + else + { + /* just call it if callback is provided, remove otherwise */ + if (hctl->prune_cb) + { + if (hctl->prune_cb(hashp, (void *)elm)) + nremoved++; + } + else + { + bool found; + + hash_search(hashp, elm, HASH_REMOVE, &found); + Assert(found); + nremoved++; + } + } + } + } + + elog(DEBUG1, "removed %d/%d entries from hash \"%s\"", + nremoved, nall, hashp->tabname); + + return nremoved > 0; +} static bool dir_realloc(HTAB *hashp) @@ -1667,7 +1795,7 @@ element_alloc(HTAB *hashp, int nelem, int freelist_idx) return false; /* Each element has a HASHELEMENT header plus user data. */ - elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize); + elementSize = HASHELEMENT_SIZE(hctl) + MAXALIGN(hctl->entrysize); CurrentDynaHashCxt = hashp->hcxt; firstElement = (HASHELEMENT *) hashp->alloc(nelem * elementSize); diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h index 599303be56..b3f73f53d2 100644 --- a/src/include/utils/catcache.h +++ b/src/include/utils/catcache.h @@ -208,6 +208,18 @@ SetCatCacheClock(TimestampTz ts) catcacheclock = ts; } +/* + * GetCatCacheClock - get timestamp for catcache access record + * + * This clock is basically provided for catcache usage, but dynahash has a + * similar pruning mechanism and wants to use the same clock. + */ +static inline TimestampTz +GetCatCacheClock(void) +{ + return catcacheclock; +} + extern void CreateCacheMemoryContext(void); extern CatCache *InitCatCache(int id, Oid reloid, Oid indexoid, diff --git a/src/include/utils/hsearch.h b/src/include/utils/hsearch.h index 8357faac5a..6e9fa74a4f 100644 --- a/src/include/utils/hsearch.h +++ b/src/include/utils/hsearch.h @@ -13,7 +13,7 @@ */ #ifndef HSEARCH_H #define HSEARCH_H - +#include "datatype/timestamp.h" /* * Hash functions must have this signature. @@ -47,6 +47,7 @@ typedef void *(*HashAllocFunc) (Size request); * HASHELEMENT is the private part of a hashtable entry. The caller's data * follows the HASHELEMENT structure (on a MAXALIGN'd boundary). The hash key * is expected to be at the start of the caller's hash entry data structure. + * If this hash is prunable, PRUNABLE_HASHELEMENT is used instead. */ typedef struct HASHELEMENT { @@ -54,12 +55,26 @@ typedef struct HASHELEMENT uint32 hashvalue; /* hash function result for this entry */ } HASHELEMENT; +typedef struct PRUNABLE_HASHELEMENT +{ + struct HASHELEMENT *link; /* link to next entry in same bucket */ + uint32 hashvalue; /* hash function result for this entry */ + TimestampTz last_access; /* timestamp of last usage */ + int naccess; /* takes 0 to 2, counted up when used */ +} PRUNABLE_HASHELEMENT; + /* Hash table header struct is an opaque type known only within dynahash.c */ typedef struct HASHHDR HASHHDR; /* Hash table control struct is an opaque type known only within dynahash.c */ typedef struct HTAB HTAB; +/* + * Hash pruning callback which is called for the entries which is about to be + * pruned and returns false if the entry shuold be kept. + */ +typedef bool (*HASH_PRUNE_CB)(HTAB *hashp, void *ent); + /* Parameter data structure for hash_create */ /* Only those fields indicated by hash_flags need be set */ typedef struct HASHCTL @@ -77,6 +92,9 @@ typedef struct HASHCTL HashAllocFunc alloc; /* memory allocator */ MemoryContext hcxt; /* memory context to use for allocations */ HASHHDR *hctl; /* location of header in shared mem */ + HASH_PRUNE_CB prune_cb; /* pruning callback. see above. */ + int *memory_target; /* pointer to memory target */ + int *prune_min_age; /* pointer to prune minimum age */ } HASHCTL; /* Flags to indicate which parameters are supplied */ @@ -94,6 +112,7 @@ typedef struct HASHCTL #define HASH_SHARED_MEM 0x0800 /* Hashtable is in shared memory */ #define HASH_ATTACH 0x1000 /* Do not initialize hctl */ #define HASH_FIXED_SIZE 0x2000 /* Initial size is a hard limit */ +#define HASH_PRUNABLE 0x4000 /* pruning setting */ /* max_dsize value to indicate expansible directory */ -- 2.16.3 ----Next_Part(Tue_Jun_26_18_00_03_2018_442)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v4-0001-Remove-entries-that-haven-t-been-used-for-a-certain-.patch"