granicus.if.org Git - postgresql/blob - src/backend/executor/nodeBitmapIndexscan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeBitmapIndexscan.c
   4  *        Routines to support bitmapped index scans of relations
   5  *
   6  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.1 2005/04/19 22:35:12 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 /*
  16  * INTERFACE ROUTINES
  17  *              MultiExecBitmapIndexScan        scans a relation using index.
  18  *              ExecInitBitmapIndexScan         creates and initializes state info.
  19  *              ExecBitmapIndexReScan           prepares to rescan the plan.
  20  *              ExecEndBitmapIndexScan          releases all storage.
  21  */
  22 #include "postgres.h"
  23
  24 #include "access/genam.h"
  25 #include "access/heapam.h"
  26 #include "executor/execdebug.h"
  27 #include "executor/instrument.h"
  28 #include "executor/nodeBitmapIndexscan.h"
  29 #include "miscadmin.h"
  30 #include "nodes/nodeFuncs.h"
  31 #include "optimizer/clauses.h"
  32 #include "parser/parsetree.h"
  33
  34
  35 /* ----------------------------------------------------------------
  36  *              MultiExecBitmapIndexScan(node)
  37  * ----------------------------------------------------------------
  38  */
  39 Node *
  40 MultiExecBitmapIndexScan(BitmapIndexScanState *node)
  41 {
  42 #define MAX_TIDS        1024
  43         TIDBitmap  *tbm;
  44         IndexScanDesc scandesc;
  45         ItemPointerData tids[MAX_TIDS];
  46         int32           ntids;
  47         double          nTuples = 0;
  48
  49         /* must provide our own instrumentation support */
  50         if (node->ss.ps.instrument)
  51                 InstrStartNode(node->ss.ps.instrument);
  52
  53         /*
  54          * If we have runtime keys and they've not already been set up, do it
  55          * now.
  56          */
  57         if (node->biss_RuntimeKeyInfo && !node->biss_RuntimeKeysReady)
  58                 ExecReScan((PlanState *) node, NULL);
  59
  60         /*
  61          * extract necessary information from index scan node
  62          */
  63         scandesc = node->biss_ScanDesc;
  64
  65         /*
  66          * Prepare result bitmap
  67          */
  68         tbm = tbm_create(work_mem * 1024L);
  69
  70         /*
  71          * Get TIDs from index and insert into bitmap
  72          */
  73         for (;;)
  74         {
  75                 bool    more = index_getmulti(scandesc, tids, MAX_TIDS, &ntids);
  76
  77                 if (ntids > 0)
  78                 {
  79                         tbm_add_tuples(tbm, tids, ntids);
  80                         nTuples += ntids;
  81                 }
  82
  83                 if (!more)
  84                         break;
  85
  86                 CHECK_FOR_INTERRUPTS();
  87         }
  88
  89         /* must provide our own instrumentation support */
  90         if (node->ss.ps.instrument)
  91                 InstrStopNodeMulti(node->ss.ps.instrument, nTuples);
  92
  93         return (Node *) tbm;
  94 }
  95
  96 /* ----------------------------------------------------------------
  97  *              ExecBitmapIndexReScan(node)
  98  *
  99  *              Recalculates the value of the scan keys whose value depends on
 100  *              information known at runtime and rescans the indexed relation.
 101  *              Updating the scan key was formerly done separately in
 102  *              ExecUpdateIndexScanKeys. Integrating it into ReScan makes
 103  *              rescans of indices and relations/general streams more uniform.
 104  *
 105  * ----------------------------------------------------------------
 106  */
 107 void
 108 ExecBitmapIndexReScan(BitmapIndexScanState *node, ExprContext *exprCtxt)
 109 {
 110         ExprContext *econtext;
 111         ExprState **runtimeKeyInfo;
 112         Index           scanrelid;
 113
 114         econtext = node->biss_RuntimeContext;           /* context for runtime
 115                                                                                                  * keys */
 116         runtimeKeyInfo = node->biss_RuntimeKeyInfo;
 117         scanrelid = ((BitmapIndexScan *) node->ss.ps.plan)->scan.scanrelid;
 118
 119         if (econtext)
 120         {
 121                 /*
 122                  * If we are being passed an outer tuple, save it for runtime key
 123                  * calc.  We also need to link it into the "regular" per-tuple
 124                  * econtext.
 125                  */
 126                 if (exprCtxt != NULL)
 127                 {
 128                         ExprContext *stdecontext;
 129
 130                         econtext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 131                         stdecontext = node->ss.ps.ps_ExprContext;
 132                         stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 133                 }
 134
 135                 /*
 136                  * Reset the runtime-key context so we don't leak memory as each
 137                  * outer tuple is scanned.      Note this assumes that we will
 138                  * recalculate *all* runtime keys on each call.
 139                  */
 140                 ResetExprContext(econtext);
 141         }
 142
 143         /*
 144          * If we are doing runtime key calculations (ie, the index keys depend
 145          * on data from an outer scan), compute the new key values
 146          */
 147         if (runtimeKeyInfo)
 148         {
 149                 int                     n_keys;
 150                 ScanKey         scan_keys;
 151                 ExprState **run_keys;
 152                 int                     j;
 153
 154                 n_keys = node->biss_NumScanKeys;
 155                 scan_keys = node->biss_ScanKeys;
 156                 run_keys = runtimeKeyInfo;
 157
 158                 for (j = 0; j < n_keys; j++)
 159                 {
 160                         /*
 161                          * If we have a run-time key, then extract the run-time
 162                          * expression and evaluate it with respect to the current
 163                          * outer tuple.  We then stick the result into the scan
 164                          * key.
 165                          *
 166                          * Note: the result of the eval could be a pass-by-ref value
 167                          * that's stored in the outer scan's tuple, not in
 168                          * econtext->ecxt_per_tuple_memory.  We assume that the
 169                          * outer tuple will stay put throughout our scan.  If this
 170                          * is wrong, we could copy the result into our context
 171                          * explicitly, but I think that's not necessary...
 172                          */
 173                         if (run_keys[j] != NULL)
 174                         {
 175                                 Datum           scanvalue;
 176                                 bool            isNull;
 177
 178                                 scanvalue = ExecEvalExprSwitchContext(run_keys[j],
 179                                                                                                           econtext,
 180                                                                                                           &isNull,
 181                                                                                                           NULL);
 182                                 scan_keys[j].sk_argument = scanvalue;
 183                                 if (isNull)
 184                                         scan_keys[j].sk_flags |= SK_ISNULL;
 185                                 else
 186                                         scan_keys[j].sk_flags &= ~SK_ISNULL;
 187                         }
 188                 }
 189
 190                 node->biss_RuntimeKeysReady = true;
 191         }
 192
 193         index_rescan(node->biss_ScanDesc, node->biss_ScanKeys);
 194 }
 195
 196 /* ----------------------------------------------------------------
 197  *              ExecEndBitmapIndexScan
 198  * ----------------------------------------------------------------
 199  */
 200 void
 201 ExecEndBitmapIndexScan(BitmapIndexScanState *node)
 202 {
 203         Relation        relation;
 204
 205         /*
 206          * extract information from the node
 207          */
 208         relation = node->ss.ss_currentRelation;
 209
 210         /*
 211          * Free the exprcontext(s)
 212          */
 213         ExecFreeExprContext(&node->ss.ps);
 214         if (node->biss_RuntimeContext)
 215                 FreeExprContext(node->biss_RuntimeContext);
 216
 217         /*
 218          * close the index relation
 219          */
 220         if (node->biss_ScanDesc != NULL)
 221                 index_endscan(node->biss_ScanDesc);
 222
 223         if (node->biss_RelationDesc != NULL)
 224                 index_close(node->biss_RelationDesc);
 225
 226         /*
 227          * close the heap relation.
 228          *
 229          * Currently, we do not release the AccessShareLock acquired by
 230          * ExecInitBitmapIndexScan.  This lock should be held till end of
 231          * transaction. (There is a faction that considers this too much
 232          * locking, however.)
 233          */
 234         heap_close(relation, NoLock);
 235 }
 236
 237 /* ----------------------------------------------------------------
 238  *              ExecInitBitmapIndexScan
 239  *
 240  *              Initializes the index scan's state information, creates
 241  *              scan keys, and opens the base and index relations.
 242  *
 243  *              Note: index scans have 2 sets of state information because
 244  *                        we have to keep track of the base relation and the
 245  *                        index relations.
 246  *
 247  * old comments
 248  *              Creates the run-time state information for the node and
 249  *              sets the relation id to contain relevant descriptors.
 250  *
 251  *              Parameters:
 252  *                node: BitmapIndexNode node produced by the planner.
 253  *                estate: the execution state initialized in InitPlan.
 254  * ----------------------------------------------------------------
 255  */
 256 BitmapIndexScanState *
 257 ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate)
 258 {
 259         BitmapIndexScanState *indexstate;
 260         ExprState **runtimeKeyInfo;
 261         bool            have_runtime_keys;
 262         RangeTblEntry *rtentry;
 263         Index           relid;
 264         Oid                     reloid;
 265         Relation        currentRelation;
 266
 267         /*
 268          * create state structure
 269          */
 270         indexstate = makeNode(BitmapIndexScanState);
 271         indexstate->ss.ps.plan = (Plan *) node;
 272         indexstate->ss.ps.state = estate;
 273
 274         /*
 275          * Miscellaneous initialization
 276          *
 277          * create expression context for node
 278          */
 279         ExecAssignExprContext(estate, &indexstate->ss.ps);
 280
 281         /*
 282          * initialize child expressions
 283          *
 284          * We don't need to initialize targetlist or qual since neither are used.
 285          *
 286          * Note: we don't initialize all of the indxqual expression, only the
 287          * sub-parts corresponding to runtime keys (see below).
 288          */
 289
 290 #define BITMAPINDEXSCAN_NSLOTS 0
 291
 292         /*
 293          * Initialize index-specific scan state
 294          */
 295         indexstate->biss_ScanKeys = NULL;
 296         indexstate->biss_NumScanKeys = 0;
 297         indexstate->biss_RuntimeKeyInfo = NULL;
 298         indexstate->biss_RuntimeContext = NULL;
 299         indexstate->biss_RuntimeKeysReady = false;
 300         indexstate->biss_RelationDesc = NULL;
 301         indexstate->biss_ScanDesc = NULL;
 302
 303         CXT1_printf("ExecInitBitmapIndexScan: context is %d\n", CurrentMemoryContext);
 304
 305         /*
 306          * initialize space for runtime key info (may not be needed)
 307          */
 308         have_runtime_keys = false;
 309
 310         /*
 311          * build the index scan keys from the index qualification
 312          */
 313         {
 314                 List       *quals;
 315                 List       *strategies;
 316                 List       *subtypes;
 317                 ListCell   *qual_cell;
 318                 ListCell   *strategy_cell;
 319                 ListCell   *subtype_cell;
 320                 int                     n_keys;
 321                 ScanKey         scan_keys;
 322                 ExprState **run_keys;
 323                 int                     j;
 324
 325                 quals = node->indxqual;
 326                 strategies = node->indxstrategy;
 327                 subtypes = node->indxsubtype;
 328                 n_keys = list_length(quals);
 329                 scan_keys = (n_keys <= 0) ? NULL :
 330                         (ScanKey) palloc(n_keys * sizeof(ScanKeyData));
 331                 run_keys = (n_keys <= 0) ? NULL :
 332                         (ExprState **) palloc(n_keys * sizeof(ExprState *));
 333
 334                 /*
 335                  * for each opclause in the given qual, convert each qual's
 336                  * opclause into a single scan key
 337                  */
 338                 qual_cell = list_head(quals);
 339                 strategy_cell = list_head(strategies);
 340                 subtype_cell = list_head(subtypes);
 341                 for (j = 0; j < n_keys; j++)
 342                 {
 343                         OpExpr     *clause; /* one clause of index qual */
 344                         Expr       *leftop; /* expr on lhs of operator */
 345                         Expr       *rightop;    /* expr on rhs ... */
 346                         int                     flags = 0;
 347                         AttrNumber      varattno;               /* att number used in scan */
 348                         StrategyNumber strategy;        /* op's strategy number */
 349                         Oid                     subtype;        /* op's strategy subtype */
 350                         RegProcedure opfuncid;          /* operator proc id used in scan */
 351                         Datum           scanvalue;              /* value used in scan (if const) */
 352
 353                         /*
 354                          * extract clause information from the qualification
 355                          */
 356                         clause = (OpExpr *) lfirst(qual_cell);
 357                         qual_cell = lnext(qual_cell);
 358                         strategy = lfirst_int(strategy_cell);
 359                         strategy_cell = lnext(strategy_cell);
 360                         subtype = lfirst_oid(subtype_cell);
 361                         subtype_cell = lnext(subtype_cell);
 362
 363                         if (!IsA(clause, OpExpr))
 364                                 elog(ERROR, "indxqual is not an OpExpr");
 365
 366                         opfuncid = clause->opfuncid;
 367
 368                         /*
 369                          * Here we figure out the contents of the index qual. The
 370                          * usual case is (var op const) which means we form a scan key
 371                          * for the attribute listed in the var node and use the value
 372                          * of the const as comparison data.
 373                          *
 374                          * If we don't have a const node, it means our scan key is a
 375                          * function of information obtained during the execution of
 376                          * the plan, in which case we need to recalculate the index
 377                          * scan key at run time.  Hence, we set have_runtime_keys to
 378                          * true and place the appropriate subexpression in run_keys.
 379                          * The corresponding scan key values are recomputed at run
 380                          * time.
 381                          */
 382                         run_keys[j] = NULL;
 383
 384                         /*
 385                          * determine information in leftop
 386                          */
 387                         leftop = (Expr *) get_leftop((Expr *) clause);
 388
 389                         if (leftop && IsA(leftop, RelabelType))
 390                                 leftop = ((RelabelType *) leftop)->arg;
 391
 392                         Assert(leftop != NULL);
 393
 394                         if (!(IsA(leftop, Var) &&
 395                                   var_is_rel((Var *) leftop)))
 396                                 elog(ERROR, "indxqual doesn't have key on left side");
 397
 398                         varattno = ((Var *) leftop)->varattno;
 399
 400                         /*
 401                          * now determine information in rightop
 402                          */
 403                         rightop = (Expr *) get_rightop((Expr *) clause);
 404
 405                         if (rightop && IsA(rightop, RelabelType))
 406                                 rightop = ((RelabelType *) rightop)->arg;
 407
 408                         Assert(rightop != NULL);
 409
 410                         if (IsA(rightop, Const))
 411                         {
 412                                 /*
 413                                  * if the rightop is a const node then it means it
 414                                  * identifies the value to place in our scan key.
 415                                  */
 416                                 scanvalue = ((Const *) rightop)->constvalue;
 417                                 if (((Const *) rightop)->constisnull)
 418                                         flags |= SK_ISNULL;
 419                         }
 420                         else
 421                         {
 422                                 /*
 423                                  * otherwise, the rightop contains an expression evaluable
 424                                  * at runtime to figure out the value to place in our scan
 425                                  * key.
 426                                  */
 427                                 have_runtime_keys = true;
 428                                 run_keys[j] = ExecInitExpr(rightop, (PlanState *) indexstate);
 429                                 scanvalue = (Datum) 0;
 430                         }
 431
 432                         /*
 433                          * initialize the scan key's fields appropriately
 434                          */
 435                         ScanKeyEntryInitialize(&scan_keys[j],
 436                                                                    flags,
 437                                                                    varattno,    /* attribute number to
 438                                                                                                  * scan */
 439                                                                    strategy,    /* op's strategy */
 440                                                                    subtype,             /* strategy subtype */
 441                                                                    opfuncid,    /* reg proc to use */
 442                                                                    scanvalue);  /* constant */
 443                 }
 444
 445                 /*
 446                  * store the key information into the node.
 447                  */
 448                 indexstate->biss_NumScanKeys = n_keys;
 449                 indexstate->biss_ScanKeys = scan_keys;
 450                 runtimeKeyInfo = run_keys;
 451         }
 452
 453
 454         /*
 455          * If all of our keys have the form (var op const), then we have no
 456          * runtime keys so we store NULL in the runtime key info. Otherwise
 457          * runtime key info contains an array of pointers (one for each index)
 458          * to arrays of flags (one for each key) which indicate that the qual
 459          * needs to be evaluated at runtime. -cim 10/24/89
 460          *
 461          * If we do have runtime keys, we need an ExprContext to evaluate them;
 462          * the node's standard context won't do because we want to reset that
 463          * context for every tuple.  So, build another context just like the
 464          * other one... -tgl 7/11/00
 465          */
 466         if (have_runtime_keys)
 467         {
 468                 ExprContext *stdecontext = indexstate->ss.ps.ps_ExprContext;
 469
 470                 ExecAssignExprContext(estate, &indexstate->ss.ps);
 471                 indexstate->biss_RuntimeKeyInfo = runtimeKeyInfo;
 472                 indexstate->biss_RuntimeContext = indexstate->ss.ps.ps_ExprContext;
 473                 indexstate->ss.ps.ps_ExprContext = stdecontext;
 474         }
 475         else
 476         {
 477                 indexstate->biss_RuntimeKeyInfo = NULL;
 478                 indexstate->biss_RuntimeContext = NULL;
 479                 /* Get rid of the speculatively-allocated flag array, too */
 480                 pfree(runtimeKeyInfo);
 481         }
 482
 483         /*
 484          * open the base relation and acquire AccessShareLock on it.
 485          */
 486         relid = node->scan.scanrelid;
 487         rtentry = rt_fetch(relid, estate->es_range_table);
 488         reloid = rtentry->relid;
 489
 490         currentRelation = heap_open(reloid, AccessShareLock);
 491
 492         indexstate->ss.ss_currentRelation = currentRelation;
 493         indexstate->ss.ss_currentScanDesc = NULL;       /* no heap scan here */
 494
 495         /*
 496          * open the index relation and initialize relation and scan
 497          * descriptors.  Note we acquire no locks here; the index machinery
 498          * does its own locks and unlocks.      (We rely on having AccessShareLock
 499          * on the parent table to ensure the index won't go away!)
 500          */
 501         indexstate->biss_RelationDesc = index_open(node->indxid);
 502         indexstate->biss_ScanDesc =
 503                 index_beginscan_multi(indexstate->biss_RelationDesc,
 504                                                           estate->es_snapshot,
 505                                                           indexstate->biss_NumScanKeys,
 506                                                           indexstate->biss_ScanKeys);
 507
 508         /*
 509          * all done.
 510          */
 511         return indexstate;
 512 }
 513
 514 int
 515 ExecCountSlotsBitmapIndexScan(BitmapIndexScan *node)
 516 {
 517         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
 518                 ExecCountSlotsNode(innerPlan((Plan *) node)) + BITMAPINDEXSCAN_NSLOTS;
 519 }