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