From a5a897a6b77b9db99186092060d55b34491acbf2 Mon Sep 17 00:00:00 2001 From: Tomas Vondra Date: Sat, 18 Nov 2023 00:32:33 +0100 Subject: [PATCH v20231124 2/7] rely on PrefetchBuffer instead of custom cache Instead of maintaining a custom cache of recently prefetched blocks, rely on PrefetchBuffer doing the right thing. This only checks shared buffers, though, there's no attempt to determine if block is in page cache. However, it's a shared cache, not restricted to a single process. --- src/backend/access/index/indexam.c | 400 +++-------------------- src/backend/executor/nodeIndexonlyscan.c | 8 +- src/include/access/genam.h | 53 --- src/include/access/relscan.h | 1 + 4 files changed, 52 insertions(+), 410 deletions(-) diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c index 51feece527a..54a704338f1 100644 --- a/src/backend/access/index/indexam.c +++ b/src/backend/access/index/indexam.c @@ -112,6 +112,8 @@ static IndexScanDesc index_beginscan_internal(Relation indexRelation, ParallelIndexScanDesc pscan, bool temp_snap, int prefetch_max); +static void index_prefetch_tids(IndexScanDesc scan, ScanDirection direction); +static ItemPointer index_prefetch_get_tid(IndexScanDesc scan, ScanDirection direction); static void index_prefetch(IndexScanDesc scan, ItemPointer tid, bool skip_all_visible); @@ -313,6 +315,7 @@ index_beginscan_internal(Relation indexRelation, /* Initialize information for parallel scan. */ scan->parallel_scan = pscan; scan->xs_temp_snap = temp_snap; + scan->indexonly = false; /* * With prefetching requested, initialize the prefetcher state. @@ -608,8 +611,8 @@ index_beginscan_parallel(Relation heaprel, Relation indexrel, int nkeys, * or NULL if no more matching tuples exist. * ---------------- */ -ItemPointer -index_getnext_tid(IndexScanDesc scan, ScanDirection direction) +static ItemPointer +index_getnext_tid_internal(IndexScanDesc scan, ScanDirection direction) { bool found; @@ -710,95 +713,23 @@ index_fetch_heap(IndexScanDesc scan, TupleTableSlot *slot) bool index_getnext_slot(IndexScanDesc scan, ScanDirection direction, TupleTableSlot *slot) { - IndexPrefetch prefetch = scan->xs_prefetch; /* for convenience */ - for (;;) { - /* - * If the prefetching is still active (i.e. enabled and we still - * haven't finished reading TIDs from the scan), read enough TIDs into - * the queue until we hit the current target. - */ - if (PREFETCH_ACTIVE(prefetch)) - { - /* - * Ramp up the prefetch distance incrementally. - * - * Intentionally done as first, before reading the TIDs into the - * queue, so that there's always at least one item. Otherwise we - * might get into a situation where we start with target=0 and no - * TIDs loaded. - */ - prefetch->prefetchTarget = Min(prefetch->prefetchTarget + 1, - prefetch->prefetchMaxTarget); - - /* - * Now read TIDs from the index until the queue is full (with - * respect to the current prefetch target). - */ - while (!PREFETCH_FULL(prefetch)) - { - ItemPointer tid; - - /* Time to fetch the next TID from the index */ - tid = index_getnext_tid(scan, direction); - - /* - * If we're out of index entries, we're done (and we mark the - * the prefetcher as inactive). - */ - if (tid == NULL) - { - prefetch->prefetchDone = true; - break; - } - - Assert(ItemPointerEquals(tid, &scan->xs_heaptid)); - - prefetch->queueItems[PREFETCH_QUEUE_INDEX(prefetch->queueEnd)] = *tid; - prefetch->queueEnd++; - - /* - * Issue the actuall prefetch requests for the new TID. - * - * FIXME For IOS, this should prefetch only pages that are not - * fully visible. - */ - index_prefetch(scan, tid, false); - } - } + /* Do prefetching (if requested/enabled). */ + index_prefetch_tids(scan, direction); if (!scan->xs_heap_continue) { - /* - * With prefetching enabled (even if we already finished reading - * all TIDs from the index scan), we need to return a TID from the - * queue. Otherwise, we just get the next TID from the scan - * directly. - */ - if (PREFETCH_ENABLED(prefetch)) - { - /* Did we reach the end of the scan and the queue is empty? */ - if (PREFETCH_DONE(prefetch)) - break; - - scan->xs_heaptid = prefetch->queueItems[PREFETCH_QUEUE_INDEX(prefetch->queueIndex)]; - prefetch->queueIndex++; - } - else /* not prefetching, just do the regular work */ - { - ItemPointer tid; - - /* Time to fetch the next TID from the index */ - tid = index_getnext_tid(scan, direction); + ItemPointer tid; - /* If we're out of index entries, we're done */ - if (tid == NULL) - break; + /* Time to fetch the next TID from the index */ + tid = index_prefetch_get_tid(scan, direction); - Assert(ItemPointerEquals(tid, &scan->xs_heaptid)); - } + /* If we're out of index entries, we're done */ + if (tid == NULL) + break; + Assert(ItemPointerEquals(tid, &scan->xs_heaptid)); } /* @@ -1151,267 +1082,6 @@ index_opclass_options(Relation indrel, AttrNumber attnum, Datum attoptions, return build_local_reloptions(&relopts, attoptions, validate); } -/* - * index_prefetch_is_sequential - * Track the block number and check if the I/O pattern is sequential, - * or if the same block was just prefetched. - * - * Prefetching is cheap, but for some access patterns the benefits are small - * compared to the extra overhead. In particular, for sequential access the - * read-ahead performed by the OS is very effective/efficient. Doing more - * prefetching is just increasing the costs. - * - * This tries to identify simple sequential patterns, so that we can skip - * the prefetching request. This is implemented by having a small queue - * of block numbers, and checking it before prefetching another block. - * - * We look at the preceding PREFETCH_SEQ_PATTERN_BLOCKS blocks, and see if - * they are sequential. We also check if the block is the same as the last - * request (which is not sequential). - * - * Note that the main prefetch queue is not really useful for this, as it - * stores TIDs while we care about block numbers. Consider a sorted table, - * with a perfectly sequential pattern when accessed through an index. Each - * heap page may have dozens of TIDs, but we need to check block numbers. - * We could keep enough TIDs to cover enough blocks, but then we also need - * to walk those when checking the pattern (in hot path). - * - * So instead, we maintain a small separate queue of block numbers, and we use - * this instead. - * - * Returns true if the block is in a sequential pattern (and so should not be - * prefetched), or false (not sequential, should be prefetched). - * - * XXX The name is a bit misleading, as it also adds the block number to the - * block queue and checks if the block is the same as the last one (which - * does not require a sequential pattern). - */ -static bool -index_prefetch_is_sequential(IndexPrefetch prefetch, BlockNumber block) -{ - int idx; - - /* - * If the block queue is empty, just store the block and we're done (it's - * neither a sequential pattern, neither recently prefetched block). - */ - if (prefetch->blockIndex == 0) - { - prefetch->blockItems[PREFETCH_BLOCK_INDEX(prefetch->blockIndex)] = block; - prefetch->blockIndex++; - return false; - } - - /* - * Check if it's the same as the immediately preceding block. We don't - * want to prefetch the same block over and over (which would happen for - * well correlated indexes). - * - * In principle we could rely on index_prefetch_add_cache doing this using - * the full cache, but this check is much cheaper and we need to look at - * the preceding block anyway, so we just do it. - * - * XXX Notice we haven't added the block to the block queue yet, and there - * is a preceding block (i.e. blockIndex-1 is valid). - */ - if (prefetch->blockItems[PREFETCH_BLOCK_INDEX(prefetch->blockIndex - 1)] == block) - return true; - - /* - * Add the block number to the queue. - * - * We do this before checking if the pattern, because we want to know - * about the block even if we end up skipping the prefetch. Otherwise we'd - * not be able to detect longer sequential pattens - we'd skip one block - * but then fail to skip the next couple blocks even in a perfect - * sequential pattern. This ocillation might even prevent the OS - * read-ahead from kicking in. - */ - prefetch->blockItems[PREFETCH_BLOCK_INDEX(prefetch->blockIndex)] = block; - prefetch->blockIndex++; - - /* - * Check if the last couple blocks are in a sequential pattern. We look - * for a sequential pattern of PREFETCH_SEQ_PATTERN_BLOCKS (4 by default), - * so we look for patterns of 5 pages (40kB) including the new block. - * - * XXX Perhaps this should be tied to effective_io_concurrency somehow? - * - * XXX Could it be harmful that we read the queue backwards? Maybe memory - * prefetching works better for the forward direction? - */ - for (int i = 1; i < PREFETCH_SEQ_PATTERN_BLOCKS; i++) - { - /* - * Are there enough requests to confirm a sequential pattern? We only - * consider something to be sequential after finding a sequence of - * PREFETCH_SEQ_PATTERN_BLOCKS blocks. - * - * FIXME Better to move this outside the loop. - */ - if (prefetch->blockIndex < i) - return false; - - /* - * Calculate index of the earlier block (we need to do -1 as we - * already incremented the index when adding the new block to the - * queue). - */ - idx = PREFETCH_BLOCK_INDEX(prefetch->blockIndex - i - 1); - - /* - * For a sequential pattern, blocks "k" step ago needs to have block - * number by "k" smaller compared to the current block. - */ - if (prefetch->blockItems[idx] != (block - i)) - return false; - } - - return true; -} - -/* - * index_prefetch_add_cache - * Add a block to the cache, check if it was recently prefetched. - * - * We don't want to prefetch blocks that we already prefetched recently. It's - * cheap but not free, and the overhead may have measurable impact. - * - * This check needs to be very cheap, even with fairly large caches (hundreds - * of entries, see PREFETCH_CACHE_SIZE). - * - * A simple queue would allow expiring the requests, but checking if it - * contains a particular block prefetched would be expensive (linear search). - * Another option would be a simple hash table, which has fast lookup but - * does not allow expiring entries cheaply. - * - * The cache does not need to be perfect, we can accept false - * positives/negatives, as long as the rate is reasonably low. We also need - * to expire entries, so that only "recent" requests are remembered. - * - * We use a hybrid cache that is organized as many small LRU caches. Each - * block is mapped to a particular LRU by hashing (so it's a bit like a - * hash table). The LRU caches are tiny (e.g. 8 entries), and the expiration - * happens at the level of a single LRU (by tracking only the 8 most recent requests). - * - * This allows quick searches and expiration, but with false negatives (when a - * particular LRU has too many collisions, we may evict entries that are more - * recent than some other LRU). - * - * For example, imagine 128 LRU caches, each with 8 entries - that's 1024 - * prefetch request in total (these are the default parameters.) - * - * The recency is determined using a prefetch counter, incremented every - * time we end up prefetching a block. The counter is uint64, so it should - * not wrap (125 zebibytes, would take ~4 million years at 1GB/s). - * - * To check if a block was prefetched recently, we calculate hash(block), - * and then linearly search if the tiny LRU has entry for the same block - * and request less than PREFETCH_CACHE_SIZE ago. - * - * At the same time, we either update the entry (for the queried block) if - * found, or replace the oldest/empty entry. - * - * If the block was not recently prefetched (i.e. we want to prefetch it), - * we increment the counter. - * - * Returns true if the block was recently prefetched (and thus we don't - * need to prefetch it again), or false (should do a prefetch). - * - * XXX It's a bit confusing these return values are inverse compared to - * what index_prefetch_is_sequential does. - */ -static bool -index_prefetch_add_cache(IndexPrefetch prefetch, BlockNumber block) -{ - PrefetchCacheEntry *entry; - - /* map the block number the the LRU */ - int lru = hash_uint32(block) % PREFETCH_LRU_COUNT; - - /* age/index of the oldest entry in the LRU, to maybe use */ - uint64 oldestRequest = PG_UINT64_MAX; - int oldestIndex = -1; - - /* - * First add the block to the (tiny) top-level LRU cache and see if it's - * part of a sequential pattern. In this case we just ignore the block and - * don't prefetch it - we expect read-ahead to do a better job. - * - * XXX Maybe we should still add the block to the hybrid cache, in case we - * happen to access it later? That might help if we first scan a lot of - * the table sequentially, and then randomly. Not sure that's very likely - * with index access, though. - */ - if (index_prefetch_is_sequential(prefetch, block)) - { - prefetch->countSkipSequential++; - return true; - } - - /* - * See if we recently prefetched this block - we simply scan the LRU - * linearly. While doing that, we also track the oldest entry, so that we - * know where to put the block if we don't find a matching entry. - */ - for (int i = 0; i < PREFETCH_LRU_SIZE; i++) - { - entry = &prefetch->prefetchCache[lru * PREFETCH_LRU_SIZE + i]; - - /* Is this the oldest prefetch request in this LRU? */ - if (entry->request < oldestRequest) - { - oldestRequest = entry->request; - oldestIndex = i; - } - - /* - * If the entry is unused (identified by request being set to 0), - * we're done. Notice the field is uint64, so empty entry is - * guaranteed to be the oldest one. - */ - if (entry->request == 0) - continue; - - /* Is this entry for the same block as the current request? */ - if (entry->block == block) - { - bool prefetched; - - /* - * Is the old request sufficiently recent? If yes, we treat the - * block as already prefetched. - * - * XXX We do add the cache size to the request in order not to - * have issues with uint64 underflows. - */ - prefetched = ((entry->request + PREFETCH_CACHE_SIZE) >= prefetch->prefetchReqNumber); - - /* Update the request number. */ - entry->request = ++prefetch->prefetchReqNumber; - - prefetch->countSkipCached += (prefetched) ? 1 : 0; - - return prefetched; - } - } - - /* - * We didn't find the block in the LRU, so store it either in an empty - * entry, or in the "oldest" prefetch request in this LRU. - */ - Assert((oldestIndex >= 0) && (oldestIndex < PREFETCH_LRU_SIZE)); - - /* FIXME do a nice macro */ - entry = &prefetch->prefetchCache[lru * PREFETCH_LRU_SIZE + oldestIndex]; - - entry->block = block; - entry->request = ++prefetch->prefetchReqNumber; - - /* not in the prefetch cache */ - return false; -} - /* * index_prefetch * Prefetch the TID, unless it's sequential or recently prefetched. @@ -1452,6 +1122,7 @@ index_prefetch(IndexScanDesc scan, ItemPointer tid, bool skip_all_visible) { IndexPrefetch prefetch = scan->xs_prefetch; BlockNumber block; + PrefetchBufferResult result; /* * No heap relation means bitmap index scan, which does prefetching at the @@ -1501,6 +1172,10 @@ index_prefetch(IndexScanDesc scan, ItemPointer tid, bool skip_all_visible) return; } + prefetch->countAll++; + + result = PrefetchBuffer(scan->heapRelation, MAIN_FORKNUM, block); + /* * Do not prefetch the same block over and over again, * @@ -1508,19 +1183,15 @@ index_prefetch(IndexScanDesc scan, ItemPointer tid, bool skip_all_visible) * to a sequence ID). It's not expensive (the block is in page cache * already, so no I/O), but it's not free either. */ - if (!index_prefetch_add_cache(prefetch, block)) + if (result.initiated_io) { prefetch->countPrefetch++; - - PrefetchBuffer(scan->heapRelation, MAIN_FORKNUM, block); pgBufferUsage.blks_prefetches++; } - - prefetch->countAll++; } /* ---------------- - * index_getnext_tid_prefetch - get the next TID from a scan + * index_getnext_tid - get the next TID from a scan * * The result is the next TID satisfying the scan keys, * or NULL if no more matching tuples exist. @@ -1529,9 +1200,20 @@ index_prefetch(IndexScanDesc scan, ItemPointer tid, bool skip_all_visible) * ---------------- */ ItemPointer -index_getnext_tid_prefetch(IndexScanDesc scan, ScanDirection direction) +index_getnext_tid(IndexScanDesc scan, ScanDirection direction) +{ + /* Do prefetching (if requested/enabled). */ + index_prefetch_tids(scan, direction); + + /* Read the TID from the queue (or directly from the index). */ + return index_prefetch_get_tid(scan, direction); +} + +static void +index_prefetch_tids(IndexScanDesc scan, ScanDirection direction) { - IndexPrefetch prefetch = scan->xs_prefetch; /* for convenience */ + /* for convenience */ + IndexPrefetch prefetch = scan->xs_prefetch; /* * If the prefetching is still active (i.e. enabled and we still @@ -1560,7 +1242,7 @@ index_getnext_tid_prefetch(IndexScanDesc scan, ScanDirection direction) ItemPointer tid; /* Time to fetch the next TID from the index */ - tid = index_getnext_tid(scan, direction); + tid = index_getnext_tid_internal(scan, direction); /* * If we're out of index entries, we're done (and we mark the @@ -1583,9 +1265,16 @@ index_getnext_tid_prefetch(IndexScanDesc scan, ScanDirection direction) * XXX index_getnext_tid_prefetch is only called for IOS (for now), * so skip prefetching of all-visible pages. */ - index_prefetch(scan, tid, true); + index_prefetch(scan, tid, scan->indexonly); } } +} + +static ItemPointer +index_prefetch_get_tid(IndexScanDesc scan, ScanDirection direction) +{ + /* for convenience */ + IndexPrefetch prefetch = scan->xs_prefetch; /* * With prefetching enabled (even if we already finished reading @@ -1607,7 +1296,7 @@ index_getnext_tid_prefetch(IndexScanDesc scan, ScanDirection direction) ItemPointer tid; /* Time to fetch the next TID from the index */ - tid = index_getnext_tid(scan, direction); + tid = index_getnext_tid_internal(scan, direction); /* If we're out of index entries, we're done */ if (tid == NULL) @@ -1616,6 +1305,5 @@ index_getnext_tid_prefetch(IndexScanDesc scan, ScanDirection direction) Assert(ItemPointerEquals(tid, &scan->xs_heaptid)); } - /* Return the TID of the tuple we found. */ return &scan->xs_heaptid; } diff --git a/src/backend/executor/nodeIndexonlyscan.c b/src/backend/executor/nodeIndexonlyscan.c index 855afd5ba76..545046e98ad 100644 --- a/src/backend/executor/nodeIndexonlyscan.c +++ b/src/backend/executor/nodeIndexonlyscan.c @@ -120,6 +120,12 @@ IndexOnlyNext(IndexOnlyScanState *node) node->ioss_NumOrderByKeys, prefetch_max); + /* + * Remember this is index-only scan, because of prefetching. Not the most + * elegant way to pass this info. + */ + scandesc->indexonly = true; + node->ioss_ScanDesc = scandesc; @@ -142,7 +148,7 @@ IndexOnlyNext(IndexOnlyScanState *node) /* * OK, now that we have what we need, fetch the next tuple. */ - while ((tid = index_getnext_tid_prefetch(scandesc, direction)) != NULL) + while ((tid = index_getnext_tid(scandesc, direction)) != NULL) { bool tuple_from_heap = false; diff --git a/src/include/access/genam.h b/src/include/access/genam.h index e7b915d6ce7..9f33796fd29 100644 --- a/src/include/access/genam.h +++ b/src/include/access/genam.h @@ -235,38 +235,6 @@ extern HeapTuple systable_getnext_ordered(SysScanDesc sysscan, ScanDirection direction); extern void systable_endscan_ordered(SysScanDesc sysscan); -/* - * Cache of recently prefetched blocks, organized as a hash table of - * small LRU caches. Doesn't need to be perfectly accurate, but we - * aim to make false positives/negatives reasonably low. - */ -typedef struct PrefetchCacheEntry { - BlockNumber block; - uint64 request; -} PrefetchCacheEntry; - -/* - * Size of the cache of recently prefetched blocks - shouldn't be too - * small or too large. 1024 seems about right, it covers ~8MB of data. - * It's somewhat arbitrary, there's no particular formula saying it - * should not be higher/lower. - * - * The cache is structured as an array of small LRU caches, so the total - * size needs to be a multiple of LRU size. The LRU should be tiny to - * keep linear search cheap enough. - * - * XXX Maybe we could consider effective_cache_size or something? - */ -#define PREFETCH_LRU_SIZE 8 -#define PREFETCH_LRU_COUNT 128 -#define PREFETCH_CACHE_SIZE (PREFETCH_LRU_SIZE * PREFETCH_LRU_COUNT) - -/* - * Used to detect sequential patterns (and disable prefetching). - */ -#define PREFETCH_QUEUE_HISTORY 8 -#define PREFETCH_SEQ_PATTERN_BLOCKS 4 - typedef struct IndexPrefetchData { @@ -296,27 +264,6 @@ typedef struct IndexPrefetchData uint64 queueIndex; /* next TID to prefetch */ uint64 queueStart; /* first valid TID in queue */ uint64 queueEnd; /* first invalid (empty) TID in queue */ - - /* - * A couple of last prefetched blocks, used to check for certain access - * pattern and skip prefetching - e.g. for sequential access). - * - * XXX Separate from the main queue, because we only want to compare the - * block numbers, not the whole TID. In sequential access it's likely we - * read many items from each page, and we don't want to check many items - * (as that is much more expensive). - */ - BlockNumber blockItems[PREFETCH_QUEUE_HISTORY]; - uint64 blockIndex; /* index in the block (points to the first - * empty entry)*/ - - /* - * Cache of recently prefetched blocks, organized as a hash table of - * small LRU caches. - */ - uint64 prefetchReqNumber; - PrefetchCacheEntry prefetchCache[PREFETCH_CACHE_SIZE]; - } IndexPrefetchData; #define PREFETCH_QUEUE_INDEX(a) ((a) % (MAX_IO_CONCURRENCY)) diff --git a/src/include/access/relscan.h b/src/include/access/relscan.h index 231a30ecc46..d5903492c6e 100644 --- a/src/include/access/relscan.h +++ b/src/include/access/relscan.h @@ -135,6 +135,7 @@ typedef struct IndexScanDescData bool ignore_killed_tuples; /* do not return killed entries */ bool xactStartedInRecovery; /* prevents killing/seeing killed * tuples */ + bool indexonly; /* is this index-only scan? */ /* index access method's private state */ void *opaque; /* access-method-specific info */ -- 2.42.0