1/*-------------------------------------------------------------------------
4 * scan synchronization support
6 * When multiple backends run a sequential scan on the same table, we try
7 * to keep them synchronized to reduce the overall I/O needed. The goal is
8 * to read each page into shared buffer cache only once, and let all backends
9 * that take part in the shared scan process the page before it falls out of
12 * Since the "leader" in a pack of backends doing a seqscan will have to wait
13 * for I/O, while the "followers" don't, there is a strong self-synchronizing
14 * effect once we can get the backends examining approximately the same part
15 * of the table at the same time. Hence all that is really needed is to get
16 * a new backend beginning a seqscan to begin it close to where other backends
17 * are reading. We can scan the table circularly, from block X up to the
18 * end and then from block 0 to X-1, to ensure we visit all rows while still
19 * participating in the common scan.
21 * To accomplish that, we keep track of the scan position of each table, and
22 * start new scans close to where the previous scan(s) are. We don't try to
23 * do any extra synchronization to keep the scans together afterwards; some
24 * scans might progress much more slowly than others, for example if the
25 * results need to be transferred to the client over a slow network, and we
26 * don't want such queries to slow down others.
28 * There can realistically only be a few large sequential scans on different
29 * tables in progress at any time. Therefore we just keep the scan positions
30 * in a small LRU list which we scan every time we need to look up or update a
31 * scan position. The whole mechanism is only applied for tables exceeding
32 * a threshold size (but that is not the concern of this module).
35 * ss_get_location - return current scan location of a relation
36 * ss_report_location - update current scan location
39 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
40 * Portions Copyright (c) 1994, Regents of the University of California
43 * src/backend/access/common/syncscan.c
45 *-------------------------------------------------------------------------
58bool trace_syncscan =
false;
63 * Size of the LRU list.
65 * Note: the code assumes that SYNC_SCAN_NELEM > 1.
67 * XXX: What's a good value? It should be large enough to hold the
68 * maximum number of large tables scanned simultaneously. But a larger value
69 * means more traversing of the LRU list when starting a new scan.
71 #define SYNC_SCAN_NELEM 20
74 * Interval between reports of the location of the current scan, in pages.
76 * Note: This should be smaller than the ring size (see buffer/freelist.c)
77 * we use for bulk reads. Otherwise a scan joining other scans might start
78 * from a page that's no longer in the buffer cache. This is a bit fuzzy;
79 * there's no guarantee that the new scan will read the page before it leaves
80 * the buffer cache anyway, and on the other hand the page is most likely
81 * still in the OS cache.
83 #define SYNC_SCAN_REPORT_INTERVAL (128 * 1024 / BLCKSZ)
87 * The scan locations structure is essentially a doubly-linked LRU with head
88 * and tail pointer, but designed to hold a fixed maximum number of elements in
89 * fixed-size shared memory.
111 #define SizeOfScanLocations(N) \
112 (offsetof(ss_scan_locations_t, items) + (N) * sizeof(ss_lru_item_t))
114/* Pointer to struct in shared memory */
117/* prototypes for internal functions */
123 * SyncScanShmemSize --- report amount of shared memory space needed
132 * SyncScanShmemInit --- initialize this module's shared memory
147 /* Initialize shared memory area */
158 * Initialize all slots with invalid values. As scans are started,
159 * these invalid entries will fall off the LRU list and get
160 * replaced with real entries.
167 item->
prev = (
i > 0) ?
178 * ss_search --- search the scan_locations structure for an entry with the
179 * given relfilelocator.
181 * If "set" is true, the location is updated to the given location. If no
182 * entry for the given relfilelocator is found, it will be created at the head
183 * of the list with the given location, even if "set" is false.
185 * In any case, the location after possible update is returned.
187 * Caller is responsible for having acquired suitable lock on the shared
203 if (match || item->
next == NULL)
206 * If we reached the end of list and no match was found, take over
217 /* Move the entry to the front of the LRU list */
244 * ss_get_location --- get the optimal starting location for scan
246 * Returns the last-reported location of a sequential scan on the
247 * relation, or 0 if no valid location is found.
249 * We expect the caller has just done RelationGetNumberOfBlocks(), and
250 * so that number is passed in rather than computing it again. The result
251 * is guaranteed less than relnblocks (assuming that's > 0).
263 * If the location is not a valid block number for this scan, start at 0.
265 * This can happen if for instance a VACUUM truncated the table since the
266 * location was saved.
268 if (startloc >= relnblocks)
274 "SYNC_SCAN: start \"%s\" (size %u) at %u",
282 * ss_report_location --- update the current scan location
284 * Writes an entry into the shared Sync Scan state of the form
285 * (relfilelocator, blocknumber), overwriting any existing entry for the
286 * same relfilelocator.
294 if ((location % 1024) == 0)
296 "SYNC_SCAN: scanning \"%s\" at %u",
302 * To reduce lock contention, only report scan progress every N pages. For
303 * the same reason, don't block if the lock isn't immediately available.
304 * Missing a few updates isn't critical, it just means that a new scan
305 * that wants to join the pack will start a little bit behind the head of
306 * the scan. Hopefully the pages are still in OS cache and the scan
307 * catches up quickly.
317 else if (trace_syncscan)
319 "SYNC_SCAN: missed update for \"%s\" at %u",
#define InvalidBlockNumber
#define FLEXIBLE_ARRAY_MEMBER
Assert(PointerIsAligned(start, uint64))
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
void LWLockRelease(LWLock *lock)
bool LWLockConditionalAcquire(LWLock *lock, LWLockMode mode)
#define RelationGetRelationName(relation)
#define RelFileLocatorEquals(locator1, locator2)
#define InvalidRelFileNumber
void * ShmemInitStruct(const char *name, Size size, bool *foundPtr)
RelFileLocator rd_locator
ss_scan_location_t location
struct ss_lru_item_t * next
struct ss_lru_item_t * prev
RelFileLocator relfilelocator
ss_lru_item_t items[FLEXIBLE_ARRAY_MEMBER]
struct ss_lru_item_t ss_lru_item_t
void ss_report_location(Relation rel, BlockNumber location)
void SyncScanShmemInit(void)
static ss_scan_locations_t * scan_locations
BlockNumber ss_get_location(Relation rel, BlockNumber relnblocks)
struct ss_scan_locations_t ss_scan_locations_t
Size SyncScanShmemSize(void)
static BlockNumber ss_search(RelFileLocator relfilelocator, BlockNumber location, bool set)
struct ss_scan_location_t ss_scan_location_t
#define SizeOfScanLocations(N)
#define SYNC_SCAN_REPORT_INTERVAL