src/backend/access/heap/syncscan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * syncscan.c
   4  *        heap scan synchronization support
   5  *
   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
  10  * the cache.
  11  *
  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.
  20  *
  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.
  27  *
  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).
  33  *
  34  * INTERFACE ROUTINES
  35  *              ss_get_location         - return current scan location of a relation
  36  *              ss_report_location      - update current scan location
  37  *
  38  *
  39  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  40  * Portions Copyright (c) 1994, Regents of the University of California
  41  *
  42  * IDENTIFICATION
  43  *        $PostgreSQL$
  44  *
  45  *-------------------------------------------------------------------------
  46  */
  47 #include "postgres.h"
  48
  49 #include "access/heapam.h"
  50 #include "miscadmin.h"
  51 #include "storage/block.h"
  52 #include "storage/relfilenode.h"
  53 #include "utils/rel.h"
  54
  55
  56 /* GUC variables */
  57 #ifdef TRACE_SYNCSCAN
  58 bool            trace_syncscan = false;
  59 #endif
  60
  61
  62 /*
  63  * Size of the LRU list.
  64  *
  65  * Note: the code assumes that SYNC_SCAN_NELEM > 1.
  66  *
  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.
  70  */
  71 #define SYNC_SCAN_NELEM 20
  72
  73 /*
  74  * Interval between reports of the location of the current scan, in pages.
  75  *
  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.
  82  */
  83 #define SYNC_SCAN_REPORT_INTERVAL (128 * 1024 / BLCKSZ)
  84
  85
  86 /*
  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.
  90  */
  91 typedef struct ss_scan_location_t
  92 {
  93         RelFileNode relfilenode;        /* identity of a relation */
  94         BlockNumber location;           /* last-reported location in the relation */
  95 } ss_scan_location_t;
  96
  97 typedef struct ss_lru_item_t
  98 {
  99         struct ss_lru_item_t *prev;
 100         struct ss_lru_item_t *next;
 101         ss_scan_location_t location;
 102 } ss_lru_item_t;
 103
 104 typedef struct ss_scan_locations_t
 105 {
 106         ss_lru_item_t *head;
 107         ss_lru_item_t *tail;
 108         ss_lru_item_t items[1];         /* SYNC_SCAN_NELEM items */
 109 } ss_scan_locations_t;
 110
 111 #define SizeOfScanLocations(N) offsetof(ss_scan_locations_t, items[N])
 112
 113 /* Pointer to struct in shared memory */
 114 static ss_scan_locations_t *scan_locations;
 115
 116 /* prototypes for internal functions */
 117 static BlockNumber ss_search(RelFileNode relfilenode,
 118                   BlockNumber location, bool set);
 119
 120
 121 /*
 122  * SyncScanShmemSize --- report amount of shared memory space needed
 123  */
 124 Size
 125 SyncScanShmemSize(void)
 126 {
 127         return SizeOfScanLocations(SYNC_SCAN_NELEM);
 128 }
 129
 130 /*
 131  * SyncScanShmemInit --- initialize this module's shared memory
 132  */
 133 void
 134 SyncScanShmemInit(void)
 135 {
 136         int                     i;
 137         bool            found;
 138
 139         scan_locations = (ss_scan_locations_t *)
 140                 ShmemInitStruct("Sync Scan Locations List",
 141                                                 SizeOfScanLocations(SYNC_SCAN_NELEM),
 142                                                 &found);
 143
 144         if (!IsUnderPostmaster)
 145         {
 146                 /* Initialize shared memory area */
 147                 Assert(!found);
 148
 149                 scan_locations->head = &scan_locations->items[0];
 150                 scan_locations->tail = &scan_locations->items[SYNC_SCAN_NELEM - 1];
 151
 152                 for (i = 0; i < SYNC_SCAN_NELEM; i++)
 153                 {
 154                         ss_lru_item_t *item = &scan_locations->items[i];
 155
 156                         /*
 157                          * Initialize all slots with invalid values. As scans are started,
 158                          * these invalid entries will fall off the LRU list and get
 159                          * replaced with real entries.
 160                          */
 161                         item->location.relfilenode.spcNode = InvalidOid;
 162                         item->location.relfilenode.dbNode = InvalidOid;
 163                         item->location.relfilenode.relNode = InvalidOid;
 164                         item->location.location = InvalidBlockNumber;
 165
 166                         item->prev = (i > 0) ?
 167                                 (&scan_locations->items[i - 1]) : NULL;
 168                         item->next = (i < SYNC_SCAN_NELEM - 1) ?
 169                                 (&scan_locations->items[i + 1]) : NULL;
 170                 }
 171         }
 172         else
 173                 Assert(found);
 174 }
 175
 176 /*
 177  * ss_search --- search the scan_locations structure for an entry with the
 178  *              given relfilenode.
 179  *
 180  * If "set" is true, the location is updated to the given location.  If no
 181  * entry for the given relfilenode is found, it will be created at the head
 182  * of the list with the given location, even if "set" is false.
 183  *
 184  * In any case, the location after possible update is returned.
 185  *
 186  * Caller is responsible for having acquired suitable lock on the shared
 187  * data structure.
 188  */
 189 static BlockNumber
 190 ss_search(RelFileNode relfilenode, BlockNumber location, bool set)
 191 {
 192         ss_lru_item_t *item;
 193
 194         item = scan_locations->head;
 195         for (;;)
 196         {
 197                 bool            match;
 198
 199                 match = RelFileNodeEquals(item->location.relfilenode, relfilenode);
 200
 201                 if (match || item->next == NULL)
 202                 {
 203                         /*
 204                          * If we reached the end of list and no match was found, take over
 205                          * the last entry
 206                          */
 207                         if (!match)
 208                         {
 209                                 item->location.relfilenode = relfilenode;
 210                                 item->location.location = location;
 211                         }
 212                         else if (set)
 213                                 item->location.location = location;
 214
 215                         /* Move the entry to the front of the LRU list */
 216                         if (item != scan_locations->head)
 217                         {
 218                                 /* unlink */
 219                                 if (item == scan_locations->tail)
 220                                         scan_locations->tail = item->prev;
 221                                 item->prev->next = item->next;
 222                                 if (item->next)
 223                                         item->next->prev = item->prev;
 224
 225                                 /* link */
 226                                 item->prev = NULL;
 227                                 item->next = scan_locations->head;
 228                                 scan_locations->head->prev = item;
 229                                 scan_locations->head = item;
 230                         }
 231
 232                         return item->location.location;
 233                 }
 234
 235                 item = item->next;
 236         }
 237
 238         /* not reached */
 239 }
 240
 241 /*
 242  * ss_get_location --- get the optimal starting location for scan
 243  *
 244  * Returns the last-reported location of a sequential scan on the
 245  * relation, or 0 if no valid location is found.
 246  *
 247  * We expect the caller has just done RelationGetNumberOfBlocks(), and
 248  * so that number is passed in rather than computing it again.  The result
 249  * is guaranteed less than relnblocks (assuming that's > 0).
 250  */
 251 BlockNumber
 252 ss_get_location(Relation rel, BlockNumber relnblocks)
 253 {
 254         BlockNumber startloc;
 255
 256         LWLockAcquire(SyncScanLock, LW_EXCLUSIVE);
 257         startloc = ss_search(rel->rd_node, 0, false);
 258         LWLockRelease(SyncScanLock);
 259
 260         /*
 261          * If the location is not a valid block number for this scan, start at 0.
 262          *
 263          * This can happen if for instance a VACUUM truncated the table since the
 264          * location was saved.
 265          */
 266         if (startloc >= relnblocks)
 267                 startloc = 0;
 268
 269 #ifdef TRACE_SYNCSCAN
 270         if (trace_syncscan)
 271                 elog(LOG,
 272                          "SYNC_SCAN: start \"%s\" (size %u) at %u",
 273                          RelationGetRelationName(rel), relnblocks, startloc);
 274 #endif
 275
 276         return startloc;
 277 }
 278
 279 /*
 280  * ss_report_location --- update the current scan location
 281  *
 282  * Writes an entry into the shared Sync Scan state of the form
 283  * (relfilenode, blocknumber), overwriting any existing entry for the
 284  * same relfilenode.
 285  */
 286 void
 287 ss_report_location(Relation rel, BlockNumber location)
 288 {
 289 #ifdef TRACE_SYNCSCAN
 290         if (trace_syncscan)
 291         {
 292                 if ((location % 1024) == 0)
 293                         elog(LOG,
 294                                  "SYNC_SCAN: scanning \"%s\" at %u",
 295                                  RelationGetRelationName(rel), location);
 296         }
 297 #endif
 298
 299         /*
 300          * To reduce lock contention, only report scan progress every N pages. For
 301          * the same reason, don't block if the lock isn't immediately available.
 302          * Missing a few updates isn't critical, it just means that a new scan
 303          * that wants to join the pack will start a little bit behind the head of
 304          * the scan.  Hopefully the pages are still in OS cache and the scan
 305          * catches up quickly.
 306          */
 307         if ((location % SYNC_SCAN_REPORT_INTERVAL) == 0)
 308         {
 309                 if (LWLockConditionalAcquire(SyncScanLock, LW_EXCLUSIVE))
 310                 {
 311                         (void) ss_search(rel->rd_node, location, true);
 312                         LWLockRelease(SyncScanLock);
 313                 }
 314 #ifdef TRACE_SYNCSCAN
 315                 else if (trace_syncscan)
 316                         elog(LOG,
 317                                  "SYNC_SCAN: missed update for \"%s\" at %u",
 318                                  RelationGetRelationName(rel), location);
 319 #endif
 320         }
 321 }