src/backend/executor/nodeBitmapHeapscan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeBitmapHeapscan.c
   4  *        Routines to support bitmapped scans of relations
   5  *
   6  * NOTE: it is critical that this plan type only be used with MVCC-compliant
   7  * snapshots (ie, regular snapshots, not SnapshotNow or one of the other
   8  * special snapshots).  The reason is that since index and heap scans are
   9  * decoupled, there can be no assurance that the index tuple prompting a
  10  * visit to a particular heap TID still exists when the visit is made.
  11  * Therefore the tuple might not exist anymore either (which is OK because
  12  * heap_fetch will cope) --- but worse, the tuple slot could have been
  13  * re-used for a newer tuple.  With an MVCC snapshot the newer tuple is
  14  * certain to fail the time qual and so it will not be mistakenly returned.
  15  * With SnapshotNow we might return a tuple that doesn't meet the required
  16  * index qual conditions.
  17  *
  18  *
  19  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  20  * Portions Copyright (c) 1994, Regents of the University of California
  21  *
  22  *
  23  * IDENTIFICATION
  24  *        $PostgreSQL$
  25  *
  26  *-------------------------------------------------------------------------
  27  */
  28 /*
  29  * INTERFACE ROUTINES
  30  *              ExecBitmapHeapScan                      scans a relation using bitmap info
  31  *              ExecBitmapHeapNext                      workhorse for above
  32  *              ExecInitBitmapHeapScan          creates and initializes state info.
  33  *              ExecBitmapHeapReScan            prepares to rescan the plan.
  34  *              ExecEndBitmapHeapScan           releases all storage.
  35  */
  36 #include "postgres.h"
  37
  38 #include "access/heapam.h"
  39 #include "access/relscan.h"
  40 #include "access/transam.h"
  41 #include "executor/execdebug.h"
  42 #include "executor/nodeBitmapHeapscan.h"
  43 #include "pgstat.h"
  44 #include "storage/bufmgr.h"
  45 #include "utils/memutils.h"
  46 #include "utils/snapmgr.h"
  47 #include "utils/tqual.h"
  48
  49
  50 static TupleTableSlot *BitmapHeapNext(BitmapHeapScanState *node);
  51 static void bitgetpage(HeapScanDesc scan, TBMIterateResult *tbmres);
  52
  53
  54 /* ----------------------------------------------------------------
  55  *              BitmapHeapNext
  56  *
  57  *              Retrieve next tuple from the BitmapHeapScan node's currentRelation
  58  * ----------------------------------------------------------------
  59  */
  60 static TupleTableSlot *
  61 BitmapHeapNext(BitmapHeapScanState *node)
  62 {
  63         EState     *estate;
  64         ExprContext *econtext;
  65         HeapScanDesc scan;
  66         Index           scanrelid;
  67         TIDBitmap  *tbm;
  68         TBMIterateResult *tbmres;
  69         OffsetNumber targoffset;
  70         TupleTableSlot *slot;
  71
  72         /*
  73          * extract necessary information from index scan node
  74          */
  75         estate = node->ss.ps.state;
  76         econtext = node->ss.ps.ps_ExprContext;
  77         slot = node->ss.ss_ScanTupleSlot;
  78         scan = node->ss.ss_currentScanDesc;
  79         scanrelid = ((BitmapHeapScan *) node->ss.ps.plan)->scan.scanrelid;
  80         tbm = node->tbm;
  81         tbmres = node->tbmres;
  82
  83         /*
  84          * Check if we are evaluating PlanQual for tuple of this relation.
  85          * Additional checking is not good, but no other way for now. We could
  86          * introduce new nodes for this case and handle IndexScan --> NewNode
  87          * switching in Init/ReScan plan...
  88          */
  89         if (estate->es_evTuple != NULL &&
  90                 estate->es_evTuple[scanrelid - 1] != NULL)
  91         {
  92                 if (estate->es_evTupleNull[scanrelid - 1])
  93                         return ExecClearTuple(slot);
  94
  95                 ExecStoreTuple(estate->es_evTuple[scanrelid - 1],
  96                                            slot, InvalidBuffer, false);
  97
  98                 /* Does the tuple meet the original qual conditions? */
  99                 econtext->ecxt_scantuple = slot;
 100
 101                 ResetExprContext(econtext);
 102
 103                 if (!ExecQual(node->bitmapqualorig, econtext, false))
 104                         ExecClearTuple(slot);           /* would not be returned by scan */
 105
 106                 /* Flag for the next call that no more tuples */
 107                 estate->es_evTupleNull[scanrelid - 1] = true;
 108
 109                 return slot;
 110         }
 111
 112         /*
 113          * If we haven't yet performed the underlying index scan, do it, and
 114          * prepare the bitmap to be iterated over.
 115          */
 116         if (tbm == NULL)
 117         {
 118                 tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));
 119
 120                 if (!tbm || !IsA(tbm, TIDBitmap))
 121                         elog(ERROR, "unrecognized result from subplan");
 122
 123                 node->tbm = tbm;
 124                 node->tbmres = tbmres = NULL;
 125
 126                 tbm_begin_iterate(tbm);
 127         }
 128
 129         for (;;)
 130         {
 131                 Page            dp;
 132                 ItemId          lp;
 133
 134                 /*
 135                  * Get next page of results if needed
 136                  */
 137                 if (tbmres == NULL)
 138                 {
 139                         node->tbmres = tbmres = tbm_iterate(tbm);
 140                         if (tbmres == NULL)
 141                         {
 142                                 /* no more entries in the bitmap */
 143                                 break;
 144                         }
 145
 146                         /*
 147                          * Ignore any claimed entries past what we think is the end of the
 148                          * relation.  (This is probably not necessary given that we got at
 149                          * least AccessShareLock on the table before performing any of the
 150                          * indexscans, but let's be safe.)
 151                          */
 152                         if (tbmres->blockno >= scan->rs_nblocks)
 153                         {
 154                                 node->tbmres = tbmres = NULL;
 155                                 continue;
 156                         }
 157
 158                         /*
 159                          * Fetch the current heap page and identify candidate tuples.
 160                          */
 161                         bitgetpage(scan, tbmres);
 162
 163                         /*
 164                          * Set rs_cindex to first slot to examine
 165                          */
 166                         scan->rs_cindex = 0;
 167                 }
 168                 else
 169                 {
 170                         /*
 171                          * Continuing in previously obtained page; advance rs_cindex
 172                          */
 173                         scan->rs_cindex++;
 174                 }
 175
 176                 /*
 177                  * Out of range?  If so, nothing more to look at on this page
 178                  */
 179                 if (scan->rs_cindex < 0 || scan->rs_cindex >= scan->rs_ntuples)
 180                 {
 181                         node->tbmres = tbmres = NULL;
 182                         continue;
 183                 }
 184
 185                 /*
 186                  * Okay to fetch the tuple
 187                  */
 188                 targoffset = scan->rs_vistuples[scan->rs_cindex];
 189                 dp = (Page) BufferGetPage(scan->rs_cbuf);
 190                 lp = PageGetItemId(dp, targoffset);
 191                 Assert(ItemIdIsNormal(lp));
 192
 193                 scan->rs_ctup.t_data = (HeapTupleHeader) PageGetItem((Page) dp, lp);
 194                 scan->rs_ctup.t_len = ItemIdGetLength(lp);
 195                 ItemPointerSet(&scan->rs_ctup.t_self, tbmres->blockno, targoffset);
 196
 197                 pgstat_count_heap_fetch(scan->rs_rd);
 198
 199                 /*
 200                  * Set up the result slot to point to this tuple. Note that the slot
 201                  * acquires a pin on the buffer.
 202                  */
 203                 ExecStoreTuple(&scan->rs_ctup,
 204                                            slot,
 205                                            scan->rs_cbuf,
 206                                            false);
 207
 208                 /*
 209                  * If we are using lossy info, we have to recheck the qual conditions
 210                  * at every tuple.
 211                  */
 212                 if (tbmres->recheck)
 213                 {
 214                         econtext->ecxt_scantuple = slot;
 215                         ResetExprContext(econtext);
 216
 217                         if (!ExecQual(node->bitmapqualorig, econtext, false))
 218                         {
 219                                 /* Fails recheck, so drop it and loop back for another */
 220                                 ExecClearTuple(slot);
 221                                 continue;
 222                         }
 223                 }
 224
 225                 /* OK to return this tuple */
 226                 return slot;
 227         }
 228
 229         /*
 230          * if we get here it means we are at the end of the scan..
 231          */
 232         return ExecClearTuple(slot);
 233 }
 234
 235 /*
 236  * bitgetpage - subroutine for BitmapHeapNext()
 237  *
 238  * This routine reads and pins the specified page of the relation, then
 239  * builds an array indicating which tuples on the page are both potentially
 240  * interesting according to the bitmap, and visible according to the snapshot.
 241  */
 242 static void
 243 bitgetpage(HeapScanDesc scan, TBMIterateResult *tbmres)
 244 {
 245         BlockNumber page = tbmres->blockno;
 246         Buffer          buffer;
 247         Snapshot        snapshot;
 248         int                     ntup;
 249
 250         /*
 251          * Acquire pin on the target heap page, trading in any pin we held before.
 252          */
 253         Assert(page < scan->rs_nblocks);
 254
 255         scan->rs_cbuf = ReleaseAndReadBuffer(scan->rs_cbuf,
 256                                                                                  scan->rs_rd,
 257                                                                                  page);
 258         buffer = scan->rs_cbuf;
 259         snapshot = scan->rs_snapshot;
 260
 261         ntup = 0;
 262
 263         /*
 264          * Prune and repair fragmentation for the whole page, if possible.
 265          */
 266         Assert(TransactionIdIsValid(RecentGlobalXmin));
 267         heap_page_prune_opt(scan->rs_rd, buffer, RecentGlobalXmin);
 268
 269         /*
 270          * We must hold share lock on the buffer content while examining tuple
 271          * visibility.  Afterwards, however, the tuples we have found to be
 272          * visible are guaranteed good as long as we hold the buffer pin.
 273          */
 274         LockBuffer(buffer, BUFFER_LOCK_SHARE);
 275
 276         /*
 277          * We need two separate strategies for lossy and non-lossy cases.
 278          */
 279         if (tbmres->ntuples >= 0)
 280         {
 281                 /*
 282                  * Bitmap is non-lossy, so we just look through the offsets listed in
 283                  * tbmres; but we have to follow any HOT chain starting at each such
 284                  * offset.
 285                  */
 286                 int                     curslot;
 287
 288                 for (curslot = 0; curslot < tbmres->ntuples; curslot++)
 289                 {
 290                         OffsetNumber offnum = tbmres->offsets[curslot];
 291                         ItemPointerData tid;
 292
 293                         ItemPointerSet(&tid, page, offnum);
 294                         if (heap_hot_search_buffer(&tid, buffer, snapshot, NULL))
 295                                 scan->rs_vistuples[ntup++] = ItemPointerGetOffsetNumber(&tid);
 296                 }
 297         }
 298         else
 299         {
 300                 /*
 301                  * Bitmap is lossy, so we must examine each item pointer on the page.
 302                  * But we can ignore HOT chains, since we'll check each tuple anyway.
 303                  */
 304                 Page            dp = (Page) BufferGetPage(buffer);
 305                 OffsetNumber maxoff = PageGetMaxOffsetNumber(dp);
 306                 OffsetNumber offnum;
 307
 308                 for (offnum = FirstOffsetNumber; offnum <= maxoff; offnum = OffsetNumberNext(offnum))
 309                 {
 310                         ItemId          lp;
 311                         HeapTupleData loctup;
 312
 313                         lp = PageGetItemId(dp, offnum);
 314                         if (!ItemIdIsNormal(lp))
 315                                 continue;
 316                         loctup.t_data = (HeapTupleHeader) PageGetItem((Page) dp, lp);
 317                         loctup.t_len = ItemIdGetLength(lp);
 318                         if (HeapTupleSatisfiesVisibility(&loctup, snapshot, buffer))
 319                                 scan->rs_vistuples[ntup++] = offnum;
 320                 }
 321         }
 322
 323         LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
 324
 325         Assert(ntup <= MaxHeapTuplesPerPage);
 326         scan->rs_ntuples = ntup;
 327 }
 328
 329 /* ----------------------------------------------------------------
 330  *              ExecBitmapHeapScan(node)
 331  * ----------------------------------------------------------------
 332  */
 333 TupleTableSlot *
 334 ExecBitmapHeapScan(BitmapHeapScanState *node)
 335 {
 336         /*
 337          * use BitmapHeapNext as access method
 338          */
 339         return ExecScan(&node->ss, (ExecScanAccessMtd) BitmapHeapNext);
 340 }
 341
 342 /* ----------------------------------------------------------------
 343  *              ExecBitmapHeapReScan(node)
 344  * ----------------------------------------------------------------
 345  */
 346 void
 347 ExecBitmapHeapReScan(BitmapHeapScanState *node, ExprContext *exprCtxt)
 348 {
 349         EState     *estate;
 350         Index           scanrelid;
 351
 352         estate = node->ss.ps.state;
 353         scanrelid = ((BitmapHeapScan *) node->ss.ps.plan)->scan.scanrelid;
 354
 355         node->ss.ps.ps_TupFromTlist = false;
 356
 357         /*
 358          * If we are being passed an outer tuple, link it into the "regular"
 359          * per-tuple econtext for possible qual eval.
 360          */
 361         if (exprCtxt != NULL)
 362         {
 363                 ExprContext *stdecontext;
 364
 365                 stdecontext = node->ss.ps.ps_ExprContext;
 366                 stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 367         }
 368
 369         /* If this is re-scanning of PlanQual ... */
 370         if (estate->es_evTuple != NULL &&
 371                 estate->es_evTuple[scanrelid - 1] != NULL)
 372         {
 373                 estate->es_evTupleNull[scanrelid - 1] = false;
 374         }
 375
 376         /* rescan to release any page pin */
 377         heap_rescan(node->ss.ss_currentScanDesc, NULL);
 378
 379         if (node->tbm)
 380                 tbm_free(node->tbm);
 381         node->tbm = NULL;
 382         node->tbmres = NULL;
 383
 384         /*
 385          * Always rescan the input immediately, to ensure we can pass down any
 386          * outer tuple that might be used in index quals.
 387          */
 388         ExecReScan(outerPlanState(node), exprCtxt);
 389 }
 390
 391 /* ----------------------------------------------------------------
 392  *              ExecEndBitmapHeapScan
 393  * ----------------------------------------------------------------
 394  */
 395 void
 396 ExecEndBitmapHeapScan(BitmapHeapScanState *node)
 397 {
 398         Relation        relation;
 399         HeapScanDesc scanDesc;
 400
 401         /*
 402          * extract information from the node
 403          */
 404         relation = node->ss.ss_currentRelation;
 405         scanDesc = node->ss.ss_currentScanDesc;
 406
 407         /*
 408          * Free the exprcontext
 409          */
 410         ExecFreeExprContext(&node->ss.ps);
 411
 412         /*
 413          * clear out tuple table slots
 414          */
 415         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 416         ExecClearTuple(node->ss.ss_ScanTupleSlot);
 417
 418         /*
 419          * close down subplans
 420          */
 421         ExecEndNode(outerPlanState(node));
 422
 423         /*
 424          * release bitmap if any
 425          */
 426         if (node->tbm)
 427                 tbm_free(node->tbm);
 428
 429         /*
 430          * close heap scan
 431          */
 432         heap_endscan(scanDesc);
 433
 434         /*
 435          * close the heap relation.
 436          */
 437         ExecCloseScanRelation(relation);
 438 }
 439
 440 /* ----------------------------------------------------------------
 441  *              ExecInitBitmapHeapScan
 442  *
 443  *              Initializes the scan's state information.
 444  * ----------------------------------------------------------------
 445  */
 446 BitmapHeapScanState *
 447 ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags)
 448 {
 449         BitmapHeapScanState *scanstate;
 450         Relation        currentRelation;
 451
 452         /* check for unsupported flags */
 453         Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
 454
 455         /*
 456          * Assert caller didn't ask for an unsafe snapshot --- see comments at
 457          * head of file.
 458          */
 459         Assert(IsMVCCSnapshot(estate->es_snapshot));
 460
 461         /*
 462          * create state structure
 463          */
 464         scanstate = makeNode(BitmapHeapScanState);
 465         scanstate->ss.ps.plan = (Plan *) node;
 466         scanstate->ss.ps.state = estate;
 467
 468         scanstate->tbm = NULL;
 469         scanstate->tbmres = NULL;
 470
 471         /*
 472          * Miscellaneous initialization
 473          *
 474          * create expression context for node
 475          */
 476         ExecAssignExprContext(estate, &scanstate->ss.ps);
 477
 478         scanstate->ss.ps.ps_TupFromTlist = false;
 479
 480         /*
 481          * initialize child expressions
 482          */
 483         scanstate->ss.ps.targetlist = (List *)
 484                 ExecInitExpr((Expr *) node->scan.plan.targetlist,
 485                                          (PlanState *) scanstate);
 486         scanstate->ss.ps.qual = (List *)
 487                 ExecInitExpr((Expr *) node->scan.plan.qual,
 488                                          (PlanState *) scanstate);
 489         scanstate->bitmapqualorig = (List *)
 490                 ExecInitExpr((Expr *) node->bitmapqualorig,
 491                                          (PlanState *) scanstate);
 492
 493 #define BITMAPHEAPSCAN_NSLOTS 2
 494
 495         /*
 496          * tuple table initialization
 497          */
 498         ExecInitResultTupleSlot(estate, &scanstate->ss.ps);
 499         ExecInitScanTupleSlot(estate, &scanstate->ss);
 500
 501         /*
 502          * open the base relation and acquire appropriate lock on it.
 503          */
 504         currentRelation = ExecOpenScanRelation(estate, node->scan.scanrelid);
 505
 506         scanstate->ss.ss_currentRelation = currentRelation;
 507
 508         /*
 509          * Even though we aren't going to do a conventional seqscan, it is useful
 510          * to create a HeapScanDesc --- most of the fields in it are usable.
 511          */
 512         scanstate->ss.ss_currentScanDesc = heap_beginscan_bm(currentRelation,
 513                                                                                                                  estate->es_snapshot,
 514                                                                                                                  0,
 515                                                                                                                  NULL);
 516
 517         /*
 518          * get the scan type from the relation descriptor.
 519          */
 520         ExecAssignScanType(&scanstate->ss, RelationGetDescr(currentRelation));
 521
 522         /*
 523          * Initialize result tuple type and projection info.
 524          */
 525         ExecAssignResultTypeFromTL(&scanstate->ss.ps);
 526         ExecAssignScanProjectionInfo(&scanstate->ss);
 527
 528         /*
 529          * initialize child nodes
 530          *
 531          * We do this last because the child nodes will open indexscans on our
 532          * relation's indexes, and we want to be sure we have acquired a lock on
 533          * the relation first.
 534          */
 535         outerPlanState(scanstate) = ExecInitNode(outerPlan(node), estate, eflags);
 536
 537         /*
 538          * all done.
 539          */
 540         return scanstate;
 541 }
 542
 543 int
 544 ExecCountSlotsBitmapHeapScan(BitmapHeapScan *node)
 545 {
 546         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
 547                 ExecCountSlotsNode(innerPlan((Plan *) node)) + BITMAPHEAPSCAN_NSLOTS;
 548 }