From 3f38c7722deb260e5cc4ac003ab37cfe959b1954 Mon Sep 17 00:00:00 2001 From: Masahiko Sawada Date: Mon, 17 Apr 2023 17:54:49 +0900 Subject: [PATCH v32 12/18] tidstore: Use concept of off_upper and off_lower. The key is block number + the upper of offset number, whereas the value is the bitmap representation of the lower offset number. Updated function and variable names accordingly. --- src/backend/access/common/tidstore.c | 191 ++++++++++++++------------- 1 file changed, 99 insertions(+), 92 deletions(-) diff --git a/src/backend/access/common/tidstore.c b/src/backend/access/common/tidstore.c index 283a326d13..d9fe3d5f15 100644 --- a/src/backend/access/common/tidstore.c +++ b/src/backend/access/common/tidstore.c @@ -65,8 +65,10 @@ * * The maximum height of the radix tree is 5 in this case. */ -#define TIDSTORE_VALUE_NBITS 6 /* log(64, 2) */ -#define TIDSTORE_OFFSET_MASK ((1 << TIDSTORE_VALUE_NBITS) - 1) +typedef uint64 tidkey; +typedef uint64 offsetbm; +#define LOWER_OFFSET_NBITS 6 /* log(sizeof(offsetbm), 2) */ +#define LOWER_OFFSET_MASK ((1 << LOWER_OFFSET_NBITS) - 1) /* A magic value used to identify our TidStores. */ #define TIDSTORE_MAGIC 0x826f6a10 @@ -75,7 +77,7 @@ #define RT_SCOPE static #define RT_DECLARE #define RT_DEFINE -#define RT_VALUE_TYPE uint64 +#define RT_VALUE_TYPE tidkey #include "lib/radixtree.h" #define RT_PREFIX shared_rt @@ -83,7 +85,7 @@ #define RT_SCOPE static #define RT_DECLARE #define RT_DEFINE -#define RT_VALUE_TYPE uint64 +#define RT_VALUE_TYPE tidkey #include "lib/radixtree.h" /* The control object for a TidStore */ @@ -94,10 +96,10 @@ typedef struct TidStoreControl /* These values are never changed after creation */ size_t max_bytes; /* the maximum bytes a TidStore can use */ - int max_offset; /* the maximum offset number */ - int offset_nbits; /* the number of bits required for an offset - * number */ - int offset_key_nbits; /* the number of bits of an offset number + int max_off; /* the maximum offset number */ + int max_off_nbits; /* the number of bits required for offset + * numbers */ + int upper_off_nbits; /* the number of bits of offset numbers * used in a key */ /* The below fields are used only in shared case */ @@ -147,17 +149,18 @@ typedef struct TidStoreIter bool finished; /* save for the next iteration */ - uint64 next_key; - uint64 next_val; + tidkey next_tidkey; + offsetbm next_off_bitmap; /* output for the caller */ TidStoreIterResult result; } TidStoreIter; -static void tidstore_iter_extract_tids(TidStoreIter *iter, uint64 key, uint64 val); -static inline BlockNumber key_get_blkno(TidStore *ts, uint64 key); -static inline uint64 encode_key_off(TidStore *ts, BlockNumber block, uint32 offset, uint64 *off_bit); -static inline uint64 tid_to_key_off(TidStore *ts, ItemPointer tid, uint64 *off_bit); +static void iter_decode_key_off(TidStoreIter *iter, tidkey key, offsetbm off_bitmap); +static inline BlockNumber key_get_blkno(TidStore *ts, tidkey key); +static inline tidkey encode_blk_off(TidStore *ts, BlockNumber block, + OffsetNumber offset, offsetbm *off_bit); +static inline tidkey encode_tid(TidStore *ts, ItemPointer tid, offsetbm *off_bit); /* * Create a TidStore. The returned object is allocated in backend-local memory. @@ -218,14 +221,14 @@ TidStoreCreate(size_t max_bytes, int max_off, dsa_area *area) ts->control->max_bytes = max_bytes - (70 * 1024); } - ts->control->max_offset = max_offset; - ts->control->offset_nbits = pg_ceil_log2_32(max_offset); + ts->control->max_off = max_off; + ts->control->max_off_nbits = pg_ceil_log2_32(max_off); - if (ts->control->offset_nbits < TIDSTORE_VALUE_NBITS) - ts->control->offset_nbits = TIDSTORE_VALUE_NBITS; + if (ts->control->max_off_nbits < LOWER_OFFSET_NBITS) + ts->control->max_off_nbits = LOWER_OFFSET_NBITS; - ts->control->offset_key_nbits = - ts->control->offset_nbits - TIDSTORE_VALUE_NBITS; + ts->control->upper_off_nbits = + ts->control->max_off_nbits - LOWER_OFFSET_NBITS; return ts; } @@ -355,25 +358,25 @@ void TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, int num_offsets) { - uint64 *values; - uint64 key; - uint64 prev_key; - uint64 off_bitmap = 0; + offsetbm *bitmaps; + tidkey key; + tidkey prev_key; + offsetbm off_bitmap = 0; int idx; - const uint64 key_base = ((uint64) blkno) << ts->control->offset_key_nbits; - const int nkeys = UINT64CONST(1) << ts->control->offset_key_nbits; + const tidkey key_base = ((uint64) blkno) << ts->control->upper_off_nbits; + const int nkeys = UINT64CONST(1) << ts->control->upper_off_nbits; Assert(!TidStoreIsShared(ts) || ts->control->magic == TIDSTORE_MAGIC); - values = palloc(sizeof(uint64) * nkeys); + bitmaps = palloc(sizeof(offsetbm) * nkeys); key = prev_key = key_base; for (int i = 0; i < num_offsets; i++) { - uint64 off_bit; + offsetbm off_bit; /* encode the tid to a key and partial offset */ - key = encode_key_off(ts, blkno, offsets[i], &off_bit); + key = encode_blk_off(ts, blkno, offsets[i], &off_bit); /* make sure we scanned the line pointer array in order */ Assert(key >= prev_key); @@ -384,11 +387,11 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, Assert(idx >= 0 && idx < nkeys); /* write out offset bitmap for this key */ - values[idx] = off_bitmap; + bitmaps[idx] = off_bitmap; /* zero out any gaps up to the current key */ for (int empty_idx = idx + 1; empty_idx < key - key_base; empty_idx++) - values[empty_idx] = 0; + bitmaps[empty_idx] = 0; /* reset for current key -- the current offset will be handled below */ off_bitmap = 0; @@ -401,7 +404,7 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, /* save the final index for later */ idx = key - key_base; /* write out last offset bitmap */ - values[idx] = off_bitmap; + bitmaps[idx] = off_bitmap; if (TidStoreIsShared(ts)) LWLockAcquire(&ts->control->lock, LW_EXCLUSIVE); @@ -409,14 +412,14 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, /* insert the calculated key-values to the tree */ for (int i = 0; i <= idx; i++) { - if (values[i]) + if (bitmaps[i]) { key = key_base + i; if (TidStoreIsShared(ts)) - shared_rt_set(ts->tree.shared, key, &values[i]); + shared_rt_set(ts->tree.shared, key, &bitmaps[i]); else - local_rt_set(ts->tree.local, key, &values[i]); + local_rt_set(ts->tree.local, key, &bitmaps[i]); } } @@ -426,29 +429,29 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, if (TidStoreIsShared(ts)) LWLockRelease(&ts->control->lock); - pfree(values); + pfree(bitmaps); } /* Return true if the given tid is present in the TidStore */ bool TidStoreIsMember(TidStore *ts, ItemPointer tid) { - uint64 key; - uint64 val = 0; - uint64 off_bit; + tidkey key; + offsetbm off_bitmap = 0; + offsetbm off_bit; bool found; - key = tid_to_key_off(ts, tid, &off_bit); + key = encode_tid(ts, tid, &off_bit); if (TidStoreIsShared(ts)) - found = shared_rt_search(ts->tree.shared, key, &val); + found = shared_rt_search(ts->tree.shared, key, &off_bitmap); else - found = local_rt_search(ts->tree.local, key, &val); + found = local_rt_search(ts->tree.local, key, &off_bitmap); if (!found) return false; - return (val & off_bit) != 0; + return (off_bitmap & off_bit) != 0; } /* @@ -486,12 +489,12 @@ TidStoreBeginIterate(TidStore *ts) } static inline bool -tidstore_iter_kv(TidStoreIter *iter, uint64 *key, uint64 *val) +tidstore_iter(TidStoreIter *iter, tidkey *key, offsetbm *off_bitmap) { if (TidStoreIsShared(iter->ts)) - return shared_rt_iterate_next(iter->tree_iter.shared, key, val); + return shared_rt_iterate_next(iter->tree_iter.shared, key, off_bitmap); - return local_rt_iterate_next(iter->tree_iter.local, key, val); + return local_rt_iterate_next(iter->tree_iter.local, key, off_bitmap); } /* @@ -502,43 +505,46 @@ tidstore_iter_kv(TidStoreIter *iter, uint64 *key, uint64 *val) TidStoreIterResult * TidStoreIterateNext(TidStoreIter *iter) { - uint64 key; - uint64 val; - TidStoreIterResult *result = &(iter->result); + tidkey key; + offsetbm off_bitmap = 0; + TidStoreIterResult *output = &(iter->output); if (iter->finished) return NULL; - if (BlockNumberIsValid(result->blkno)) - { - /* Process the previously collected key-value */ - result->num_offsets = 0; - tidstore_iter_extract_tids(iter, iter->next_key, iter->next_val); - } + /* Initialize the outputs */ + output->blkno = InvalidBlockNumber; + output->num_offsets = 0; - while (tidstore_iter_kv(iter, &key, &val)) - { - BlockNumber blkno; + /* + * Decode the key and offset bitmap that are collected in the previous + * time, if exists. + */ + if (iter->next_off_bitmap > 0) + iter_decode_key_off(iter, iter->next_tidkey, iter->next_off_bitmap); - blkno = key_get_blkno(iter->ts, key); + while (tidstore_iter(iter, &key, &off_bitmap)) + { + BlockNumber blkno = key_get_blkno(iter->ts, key); - if (BlockNumberIsValid(result->blkno) && result->blkno != blkno) + if (BlockNumberIsValid(output->blkno) && output->blkno != blkno) { /* - * We got a key-value pair for a different block. So return the - * collected tids, and remember the key-value for the next iteration. + * We got tids for a different block. We return the collected + * tids so far, and remember the key-value for the next + * iteration. */ - iter->next_key = key; - iter->next_val = val; - return result; + iter->next_tidkey = key; + iter->next_off_bitmap = off_bitmap; + return output; } - /* Collect tids extracted from the key-value pair */ - tidstore_iter_extract_tids(iter, key, val); + /* Collect tids decoded from the key and offset bitmap */ + iter_decode_key_off(iter, key, off_bitmap); } iter->finished = true; - return result; + return output; } /* @@ -623,61 +629,62 @@ TidStoreGetHandle(TidStore *ts) /* Extract tids from the given key-value pair */ static void -tidstore_iter_extract_tids(TidStoreIter *iter, uint64 key, uint64 val) +iter_decode_key_off(TidStoreIter *iter, tidkey key, offsetbm off_bitmap) { TidStoreIterResult *result = (&iter->result); - while (val) + while (off_bitmap) { - uint64 tid_i; + uint64 compressed_tid; OffsetNumber off; - tid_i = key << TIDSTORE_VALUE_NBITS; - tid_i |= pg_rightmost_one_pos64(val); + compressed_tid = key << LOWER_OFFSET_NBITS; + compressed_tid |= pg_rightmost_one_pos64(off_bitmap); - off = tid_i & ((UINT64CONST(1) << iter->ts->control->offset_nbits) - 1); + off = compressed_tid & ((UINT64CONST(1) << iter->ts->control->max_off_nbits) - 1); - Assert(result->num_offsets < iter->ts->control->max_offset); - result->offsets[result->num_offsets++] = off; + Assert(output->num_offsets < iter->ts->control->max_off); + output->offsets[output->num_offsets++] = off; /* unset the rightmost bit */ - val &= ~pg_rightmost_one64(val); + off_bitmap &= ~pg_rightmost_one64(off_bitmap); } - result->blkno = key_get_blkno(iter->ts, key); + output->blkno = key_get_blkno(iter->ts, key); } /* Get block number from the given key */ static inline BlockNumber -key_get_blkno(TidStore *ts, uint64 key) +key_get_blkno(TidStore *ts, tidkey key) { - return (BlockNumber) (key >> ts->control->offset_key_nbits); + return (BlockNumber) (key >> ts->control->upper_off_nbits); } -/* Encode a tid to key and offset */ -static inline uint64 -tid_to_key_off(TidStore *ts, ItemPointer tid, uint64 *off_bit) +/* Encode a tid to key and partial offset */ +static inline tidkey +encode_tid(TidStore *ts, ItemPointer tid, offsetbm *off_bit) { uint32 offset = ItemPointerGetOffsetNumber(tid); BlockNumber block = ItemPointerGetBlockNumber(tid); - return encode_key_off(ts, block, offset, off_bit); + return encode_blk_off(ts, block, offset, off_bit); } /* encode a block and offset to a key and partial offset */ -static inline uint64 -encode_key_off(TidStore *ts, BlockNumber block, uint32 offset, uint64 *off_bit) +static inline tidkey +encode_blk_off(TidStore *ts, BlockNumber block, OffsetNumber offset, + offsetbm *off_bit) { - uint64 key; - uint64 tid_i; + tidkey key; + uint64 compressed_tid; uint32 off_lower; - off_lower = offset & TIDSTORE_OFFSET_MASK; - Assert(off_lower < (sizeof(uint64) * BITS_PER_BYTE)); + off_lower = offset & LOWER_OFFSET_MASK; + Assert(off_lower < (sizeof(offsetbm) * BITS_PER_BYTE)); *off_bit = UINT64CONST(1) << off_lower; - tid_i = offset | ((uint64) block << ts->control->offset_nbits); - key = tid_i >> TIDSTORE_VALUE_NBITS; + compressed_tid = offset | ((uint64) block << ts->control->max_off_nbits); + key = compressed_tid >> LOWER_OFFSET_NBITS; return key; } -- 2.31.1