src/backend/executor/nodeIndexscan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeIndexscan.c
   4  *        Routines to support indexed 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/nodeIndexscan.c,v 1.106 2005/11/25 04:24:48 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 /*
  16  * INTERFACE ROUTINES
  17  *              ExecIndexScan                   scans a relation using indices
  18  *              ExecIndexNext                   using index to retrieve next tuple
  19  *              ExecInitIndexScan               creates and initializes state info.
  20  *              ExecIndexReScan                 rescans the indexed relation.
  21  *              ExecEndIndexScan                releases all storage.
  22  *              ExecIndexMarkPos                marks scan position.
  23  *              ExecIndexRestrPos               restores scan position.
  24  */
  25 #include "postgres.h"
  26
  27 #include "access/genam.h"
  28 #include "access/heapam.h"
  29 #include "executor/execdebug.h"
  30 #include "executor/nodeIndexscan.h"
  31 #include "miscadmin.h"
  32 #include "nodes/nodeFuncs.h"
  33 #include "optimizer/clauses.h"
  34 #include "parser/parsetree.h"
  35 #include "utils/memutils.h"
  36
  37
  38 static TupleTableSlot *IndexNext(IndexScanState *node);
  39
  40
  41 /* ----------------------------------------------------------------
  42  *              IndexNext
  43  *
  44  *              Retrieve a tuple from the IndexScan node's currentRelation
  45  *              using the index specified in the IndexScanState information.
  46  * ----------------------------------------------------------------
  47  */
  48 static TupleTableSlot *
  49 IndexNext(IndexScanState *node)
  50 {
  51         EState     *estate;
  52         ExprContext *econtext;
  53         ScanDirection direction;
  54         IndexScanDesc scandesc;
  55         Index           scanrelid;
  56         HeapTuple       tuple;
  57         TupleTableSlot *slot;
  58
  59         /*
  60          * extract necessary information from index scan node
  61          */
  62         estate = node->ss.ps.state;
  63         direction = estate->es_direction;
  64         /* flip direction if this is an overall backward scan */
  65         if (ScanDirectionIsBackward(((IndexScan *) node->ss.ps.plan)->indexorderdir))
  66         {
  67                 if (ScanDirectionIsForward(direction))
  68                         direction = BackwardScanDirection;
  69                 else if (ScanDirectionIsBackward(direction))
  70                         direction = ForwardScanDirection;
  71         }
  72         scandesc = node->iss_ScanDesc;
  73         econtext = node->ss.ps.ps_ExprContext;
  74         slot = node->ss.ss_ScanTupleSlot;
  75         scanrelid = ((IndexScan *) node->ss.ps.plan)->scan.scanrelid;
  76
  77         /*
  78          * Check if we are evaluating PlanQual for tuple of this relation.
  79          * Additional checking is not good, but no other way for now. We could
  80          * introduce new nodes for this case and handle IndexScan --> NewNode
  81          * switching in Init/ReScan plan...
  82          */
  83         if (estate->es_evTuple != NULL &&
  84                 estate->es_evTuple[scanrelid - 1] != NULL)
  85         {
  86                 if (estate->es_evTupleNull[scanrelid - 1])
  87                         return ExecClearTuple(slot);
  88
  89                 ExecStoreTuple(estate->es_evTuple[scanrelid - 1],
  90                                            slot, InvalidBuffer, false);
  91
  92                 /* Does the tuple meet the indexqual condition? */
  93                 econtext->ecxt_scantuple = slot;
  94
  95                 ResetExprContext(econtext);
  96
  97                 if (!ExecQual(node->indexqualorig, econtext, false))
  98                         ExecClearTuple(slot);           /* would not be returned by scan */
  99
 100                 /* Flag for the next call that no more tuples */
 101                 estate->es_evTupleNull[scanrelid - 1] = true;
 102
 103                 return slot;
 104         }
 105
 106         /*
 107          * ok, now that we have what we need, fetch the next tuple.
 108          */
 109         if ((tuple = index_getnext(scandesc, direction)) != NULL)
 110         {
 111                 /*
 112                  * Store the scanned tuple in the scan tuple slot of the scan state.
 113                  * Note: we pass 'false' because tuples returned by amgetnext are
 114                  * pointers onto disk pages and must not be pfree()'d.
 115                  */
 116                 ExecStoreTuple(tuple,   /* tuple to store */
 117                                            slot,        /* slot to store in */
 118                                            scandesc->xs_cbuf,           /* buffer containing tuple */
 119                                            false);      /* don't pfree */
 120
 121                 return slot;
 122         }
 123
 124         /*
 125          * if we get here it means the index scan failed so we are at the end of
 126          * the scan..
 127          */
 128         return ExecClearTuple(slot);
 129 }
 130
 131 /* ----------------------------------------------------------------
 132  *              ExecIndexScan(node)
 133  * ----------------------------------------------------------------
 134  */
 135 TupleTableSlot *
 136 ExecIndexScan(IndexScanState *node)
 137 {
 138         /*
 139          * If we have runtime keys and they've not already been set up, do it now.
 140          */
 141         if (node->iss_RuntimeKeyInfo && !node->iss_RuntimeKeysReady)
 142                 ExecReScan((PlanState *) node, NULL);
 143
 144         /*
 145          * use IndexNext as access method
 146          */
 147         return ExecScan(&node->ss, (ExecScanAccessMtd) IndexNext);
 148 }
 149
 150 /* ----------------------------------------------------------------
 151  *              ExecIndexReScan(node)
 152  *
 153  *              Recalculates the value of the scan keys whose value depends on
 154  *              information known at runtime and rescans the indexed relation.
 155  *              Updating the scan key was formerly done separately in
 156  *              ExecUpdateIndexScanKeys. Integrating it into ReScan makes
 157  *              rescans of indices and relations/general streams more uniform.
 158  * ----------------------------------------------------------------
 159  */
 160 void
 161 ExecIndexReScan(IndexScanState *node, ExprContext *exprCtxt)
 162 {
 163         EState     *estate;
 164         ExprContext *econtext;
 165         ScanKey         scanKeys;
 166         ExprState **runtimeKeyInfo;
 167         int                     numScanKeys;
 168         Index           scanrelid;
 169
 170         estate = node->ss.ps.state;
 171         econtext = node->iss_RuntimeContext;            /* context for runtime keys */
 172         scanKeys = node->iss_ScanKeys;
 173         runtimeKeyInfo = node->iss_RuntimeKeyInfo;
 174         numScanKeys = node->iss_NumScanKeys;
 175         scanrelid = ((IndexScan *) node->ss.ps.plan)->scan.scanrelid;
 176
 177         if (econtext)
 178         {
 179                 /*
 180                  * If we are being passed an outer tuple, save it for runtime key
 181                  * calc.  We also need to link it into the "regular" per-tuple
 182                  * econtext, so it can be used during indexqualorig evaluations.
 183                  */
 184                 if (exprCtxt != NULL)
 185                 {
 186                         ExprContext *stdecontext;
 187
 188                         econtext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 189                         stdecontext = node->ss.ps.ps_ExprContext;
 190                         stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 191                 }
 192
 193                 /*
 194                  * Reset the runtime-key context so we don't leak memory as each outer
 195                  * tuple is scanned.  Note this assumes that we will recalculate *all*
 196                  * runtime keys on each call.
 197                  */
 198                 ResetExprContext(econtext);
 199         }
 200
 201         /*
 202          * If we are doing runtime key calculations (ie, the index keys depend on
 203          * data from an outer scan), compute the new key values
 204          */
 205         if (runtimeKeyInfo)
 206         {
 207                 ExecIndexEvalRuntimeKeys(econtext,
 208                                                                  runtimeKeyInfo,
 209                                                                  scanKeys,
 210                                                                  numScanKeys);
 211                 node->iss_RuntimeKeysReady = true;
 212         }
 213
 214         /* If this is re-scanning of PlanQual ... */
 215         if (estate->es_evTuple != NULL &&
 216                 estate->es_evTuple[scanrelid - 1] != NULL)
 217         {
 218                 estate->es_evTupleNull[scanrelid - 1] = false;
 219                 return;
 220         }
 221
 222         /* reset index scan */
 223         index_rescan(node->iss_ScanDesc, scanKeys);
 224 }
 225
 226
 227 /*
 228  * ExecIndexEvalRuntimeKeys
 229  *              Evaluate any runtime key values, and update the scankeys.
 230  */
 231 void
 232 ExecIndexEvalRuntimeKeys(ExprContext *econtext,
 233                                                  ExprState **run_keys,
 234                                                  ScanKey scan_keys,
 235                                                  int n_keys)
 236 {
 237         int                     j;
 238
 239         for (j = 0; j < n_keys; j++)
 240         {
 241                 /*
 242                  * If we have a run-time key, then extract the run-time expression and
 243                  * evaluate it with respect to the current outer tuple.  We then stick
 244                  * the result into the scan key.
 245                  *
 246                  * Note: the result of the eval could be a pass-by-ref value that's
 247                  * stored in the outer scan's tuple, not in
 248                  * econtext->ecxt_per_tuple_memory.  We assume that the outer tuple
 249                  * will stay put throughout our scan.  If this is wrong, we could copy
 250                  * the result into our context explicitly, but I think that's not
 251                  * necessary...
 252                  */
 253                 if (run_keys[j] != NULL)
 254                 {
 255                         Datum           scanvalue;
 256                         bool            isNull;
 257
 258                         scanvalue = ExecEvalExprSwitchContext(run_keys[j],
 259                                                                                                   econtext,
 260                                                                                                   &isNull,
 261                                                                                                   NULL);
 262                         scan_keys[j].sk_argument = scanvalue;
 263                         if (isNull)
 264                                 scan_keys[j].sk_flags |= SK_ISNULL;
 265                         else
 266                                 scan_keys[j].sk_flags &= ~SK_ISNULL;
 267                 }
 268         }
 269 }
 270
 271 /* ----------------------------------------------------------------
 272  *              ExecEndIndexScan
 273  * ----------------------------------------------------------------
 274  */
 275 void
 276 ExecEndIndexScan(IndexScanState *node)
 277 {
 278         Relation        indexRelationDesc;
 279         IndexScanDesc indexScanDesc;
 280         Relation        relation;
 281
 282         /*
 283          * extract information from the node
 284          */
 285         indexRelationDesc = node->iss_RelationDesc;
 286         indexScanDesc = node->iss_ScanDesc;
 287         relation = node->ss.ss_currentRelation;
 288
 289         /*
 290          * Free the exprcontext(s) ... now dead code, see ExecFreeExprContext
 291          */
 292 #ifdef NOT_USED
 293         ExecFreeExprContext(&node->ss.ps);
 294         if (node->iss_RuntimeContext)
 295                 FreeExprContext(node->iss_RuntimeContext);
 296 #endif
 297
 298         /*
 299          * clear out tuple table slots
 300          */
 301         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 302         ExecClearTuple(node->ss.ss_ScanTupleSlot);
 303
 304         /*
 305          * close the index relation
 306          */
 307         index_endscan(indexScanDesc);
 308         index_close(indexRelationDesc);
 309
 310         /*
 311          * close the heap relation.
 312          *
 313          * Currently, we do not release the AccessShareLock acquired by
 314          * ExecInitIndexScan.  This lock should be held till end of transaction.
 315          * (There is a faction that considers this too much locking, however.)
 316          */
 317         heap_close(relation, NoLock);
 318 }
 319
 320 /* ----------------------------------------------------------------
 321  *              ExecIndexMarkPos
 322  * ----------------------------------------------------------------
 323  */
 324 void
 325 ExecIndexMarkPos(IndexScanState *node)
 326 {
 327         index_markpos(node->iss_ScanDesc);
 328 }
 329
 330 /* ----------------------------------------------------------------
 331  *              ExecIndexRestrPos
 332  * ----------------------------------------------------------------
 333  */
 334 void
 335 ExecIndexRestrPos(IndexScanState *node)
 336 {
 337         index_restrpos(node->iss_ScanDesc);
 338 }
 339
 340 /* ----------------------------------------------------------------
 341  *              ExecInitIndexScan
 342  *
 343  *              Initializes the index scan's state information, creates
 344  *              scan keys, and opens the base and index relations.
 345  *
 346  *              Note: index scans have 2 sets of state information because
 347  *                        we have to keep track of the base relation and the
 348  *                        index relation.
 349  * ----------------------------------------------------------------
 350  */
 351 IndexScanState *
 352 ExecInitIndexScan(IndexScan *node, EState *estate)
 353 {
 354         IndexScanState *indexstate;
 355         ScanKey         scanKeys;
 356         int                     numScanKeys;
 357         ExprState **runtimeKeyInfo;
 358         bool            have_runtime_keys;
 359         RangeTblEntry *rtentry;
 360         Index           relid;
 361         Oid                     reloid;
 362         Relation        currentRelation;
 363
 364         /*
 365          * create state structure
 366          */
 367         indexstate = makeNode(IndexScanState);
 368         indexstate->ss.ps.plan = (Plan *) node;
 369         indexstate->ss.ps.state = estate;
 370
 371         /*
 372          * Miscellaneous initialization
 373          *
 374          * create expression context for node
 375          */
 376         ExecAssignExprContext(estate, &indexstate->ss.ps);
 377
 378         /*
 379          * initialize child expressions
 380          *
 381          * Note: we don't initialize all of the indexqual expression, only the
 382          * sub-parts corresponding to runtime keys (see below).  The indexqualorig
 383          * expression is always initialized even though it will only be used in
 384          * some uncommon cases --- would be nice to improve that.  (Problem is
 385          * that any SubPlans present in the expression must be found now...)
 386          */
 387         indexstate->ss.ps.targetlist = (List *)
 388                 ExecInitExpr((Expr *) node->scan.plan.targetlist,
 389                                          (PlanState *) indexstate);
 390         indexstate->ss.ps.qual = (List *)
 391                 ExecInitExpr((Expr *) node->scan.plan.qual,
 392                                          (PlanState *) indexstate);
 393         indexstate->indexqualorig = (List *)
 394                 ExecInitExpr((Expr *) node->indexqualorig,
 395                                          (PlanState *) indexstate);
 396
 397 #define INDEXSCAN_NSLOTS 2
 398
 399         /*
 400          * tuple table initialization
 401          */
 402         ExecInitResultTupleSlot(estate, &indexstate->ss.ps);
 403         ExecInitScanTupleSlot(estate, &indexstate->ss);
 404
 405         /*
 406          * Initialize index-specific scan state
 407          */
 408         indexstate->iss_RuntimeKeysReady = false;
 409
 410         CXT1_printf("ExecInitIndexScan: context is %d\n", CurrentMemoryContext);
 411
 412         /*
 413          * build the index scan keys from the index qualification
 414          */
 415         have_runtime_keys =
 416                 ExecIndexBuildScanKeys((PlanState *) indexstate,
 417                                                            node->indexqual,
 418                                                            node->indexstrategy,
 419                                                            node->indexsubtype,
 420                                                            &runtimeKeyInfo,
 421                                                            &scanKeys,
 422                                                            &numScanKeys);
 423
 424         indexstate->iss_RuntimeKeyInfo = runtimeKeyInfo;
 425         indexstate->iss_ScanKeys = scanKeys;
 426         indexstate->iss_NumScanKeys = numScanKeys;
 427
 428         /*
 429          * If we have runtime keys, we need an ExprContext to evaluate them. The
 430          * node's standard context won't do because we want to reset that context
 431          * for every tuple.  So, build another context just like the other one...
 432          * -tgl 7/11/00
 433          */
 434         if (have_runtime_keys)
 435         {
 436                 ExprContext *stdecontext = indexstate->ss.ps.ps_ExprContext;
 437
 438                 ExecAssignExprContext(estate, &indexstate->ss.ps);
 439                 indexstate->iss_RuntimeContext = indexstate->ss.ps.ps_ExprContext;
 440                 indexstate->ss.ps.ps_ExprContext = stdecontext;
 441         }
 442         else
 443         {
 444                 indexstate->iss_RuntimeContext = NULL;
 445         }
 446
 447         /*
 448          * open the base relation and acquire AccessShareLock on it.
 449          */
 450         relid = node->scan.scanrelid;
 451         rtentry = rt_fetch(relid, estate->es_range_table);
 452         reloid = rtentry->relid;
 453
 454         currentRelation = heap_open(reloid, AccessShareLock);
 455
 456         indexstate->ss.ss_currentRelation = currentRelation;
 457         indexstate->ss.ss_currentScanDesc = NULL;       /* no heap scan here */
 458
 459         /*
 460          * get the scan type from the relation descriptor.
 461          */
 462         ExecAssignScanType(&indexstate->ss, RelationGetDescr(currentRelation), false);
 463
 464         /*
 465          * open the index relation and initialize relation and scan descriptors.
 466          * Note we acquire no locks here; the index machinery does its own locks
 467          * and unlocks.  (We rely on having AccessShareLock on the parent table to
 468          * ensure the index won't go away!)
 469          */
 470         indexstate->iss_RelationDesc = index_open(node->indexid);
 471         indexstate->iss_ScanDesc = index_beginscan(currentRelation,
 472                                                                                            indexstate->iss_RelationDesc,
 473                                                                                            estate->es_snapshot,
 474                                                                                            numScanKeys,
 475                                                                                            scanKeys);
 476
 477         /*
 478          * Initialize result tuple type and projection info.
 479          */
 480         ExecAssignResultTypeFromTL(&indexstate->ss.ps);
 481         ExecAssignScanProjectionInfo(&indexstate->ss);
 482
 483         /*
 484          * all done.
 485          */
 486         return indexstate;
 487 }
 488
 489
 490 /*
 491  * ExecIndexBuildScanKeys
 492  *              Build the index scan keys from the index qualification
 493  *
 494  * Input params are:
 495  *
 496  * planstate: executor state node we are working for
 497  * quals: indexquals expressions
 498  * strategies: associated operator strategy numbers
 499  * subtypes: associated operator subtype OIDs
 500  *
 501  * Output params are:
 502  *
 503  * *runtimeKeyInfo: receives ptr to array of runtime key exprstates
 504  *              (NULL if no runtime keys)
 505  * *scanKeys: receives ptr to array of ScanKeys
 506  * *numScanKeys: receives number of scankeys/runtime keys
 507  *
 508  * Return value is TRUE if any runtime key expressions were found, else FALSE.
 509  */
 510 bool
 511 ExecIndexBuildScanKeys(PlanState *planstate, List *quals,
 512                                            List *strategies, List *subtypes,
 513                                            ExprState ***runtimeKeyInfo,
 514                                            ScanKey *scanKeys, int *numScanKeys)
 515 {
 516         bool            have_runtime_keys = false;
 517         ListCell   *qual_cell;
 518         ListCell   *strategy_cell;
 519         ListCell   *subtype_cell;
 520         int                     n_keys;
 521         ScanKey         scan_keys;
 522         ExprState **run_keys;
 523         int                     j;
 524
 525         n_keys = list_length(quals);
 526         scan_keys = (n_keys <= 0) ? NULL :
 527                 (ScanKey) palloc(n_keys * sizeof(ScanKeyData));
 528         run_keys = (n_keys <= 0) ? NULL :
 529                 (ExprState **) palloc(n_keys * sizeof(ExprState *));
 530
 531         /*
 532          * for each opclause in the given qual, convert each qual's opclause into
 533          * a single scan key
 534          */
 535         qual_cell = list_head(quals);
 536         strategy_cell = list_head(strategies);
 537         subtype_cell = list_head(subtypes);
 538
 539         for (j = 0; j < n_keys; j++)
 540         {
 541                 OpExpr     *clause;             /* one clause of index qual */
 542                 Expr       *leftop;             /* expr on lhs of operator */
 543                 Expr       *rightop;    /* expr on rhs ... */
 544                 int                     flags = 0;
 545                 AttrNumber      varattno;       /* att number used in scan */
 546                 StrategyNumber strategy;        /* op's strategy number */
 547                 Oid                     subtype;        /* op's strategy subtype */
 548                 RegProcedure opfuncid;  /* operator proc id used in scan */
 549                 Datum           scanvalue;      /* value used in scan (if const) */
 550
 551                 /*
 552                  * extract clause information from the qualification
 553                  */
 554                 clause = (OpExpr *) lfirst(qual_cell);
 555                 qual_cell = lnext(qual_cell);
 556                 strategy = lfirst_int(strategy_cell);
 557                 strategy_cell = lnext(strategy_cell);
 558                 subtype = lfirst_oid(subtype_cell);
 559                 subtype_cell = lnext(subtype_cell);
 560
 561                 if (!IsA(clause, OpExpr))
 562                         elog(ERROR, "indexqual is not an OpExpr");
 563
 564                 opfuncid = clause->opfuncid;
 565
 566                 /*
 567                  * Here we figure out the contents of the index qual. The usual case
 568                  * is (var op const) which means we form a scan key for the attribute
 569                  * listed in the var node and use the value of the const as comparison
 570                  * data.
 571                  *
 572                  * If we don't have a const node, it means our scan key is a function
 573                  * of information obtained during the execution of the plan, in which
 574                  * case we need to recalculate the index scan key at run time.  Hence,
 575                  * we set have_runtime_keys to true and place the appropriate
 576                  * subexpression in run_keys. The corresponding scan key values are
 577                  * recomputed at run time.
 578                  */
 579                 run_keys[j] = NULL;
 580
 581                 /*
 582                  * determine information in leftop
 583                  */
 584                 leftop = (Expr *) get_leftop((Expr *) clause);
 585
 586                 if (leftop && IsA(leftop, RelabelType))
 587                         leftop = ((RelabelType *) leftop)->arg;
 588
 589                 Assert(leftop != NULL);
 590
 591                 if (!(IsA(leftop, Var) &&
 592                           var_is_rel((Var *) leftop)))
 593                         elog(ERROR, "indexqual doesn't have key on left side");
 594
 595                 varattno = ((Var *) leftop)->varattno;
 596
 597                 /*
 598                  * now determine information in rightop
 599                  */
 600                 rightop = (Expr *) get_rightop((Expr *) clause);
 601
 602                 if (rightop && IsA(rightop, RelabelType))
 603                         rightop = ((RelabelType *) rightop)->arg;
 604
 605                 Assert(rightop != NULL);
 606
 607                 if (IsA(rightop, Const))
 608                 {
 609                         /*
 610                          * if the rightop is a const node then it means it identifies the
 611                          * value to place in our scan key.
 612                          */
 613                         scanvalue = ((Const *) rightop)->constvalue;
 614                         if (((Const *) rightop)->constisnull)
 615                                 flags |= SK_ISNULL;
 616                 }
 617                 else
 618                 {
 619                         /*
 620                          * otherwise, the rightop contains an expression evaluable at
 621                          * runtime to figure out the value to place in our scan key.
 622                          */
 623                         have_runtime_keys = true;
 624                         run_keys[j] = ExecInitExpr(rightop, planstate);
 625                         scanvalue = (Datum) 0;
 626                 }
 627
 628                 /*
 629                  * initialize the scan key's fields appropriately
 630                  */
 631                 ScanKeyEntryInitialize(&scan_keys[j],
 632                                                            flags,
 633                                                            varattno,            /* attribute number to scan */
 634                                                            strategy,            /* op's strategy */
 635                                                            subtype, /* strategy subtype */
 636                                                            opfuncid,            /* reg proc to use */
 637                                                            scanvalue);          /* constant */
 638         }
 639
 640         /* If no runtime keys, get rid of speculatively-allocated array */
 641         if (run_keys && !have_runtime_keys)
 642         {
 643                 pfree(run_keys);
 644                 run_keys = NULL;
 645         }
 646
 647         /*
 648          * Return the info to our caller.
 649          */
 650         *numScanKeys = n_keys;
 651         *scanKeys = scan_keys;
 652         *runtimeKeyInfo = run_keys;
 653
 654         return have_runtime_keys;
 655 }
 656
 657 int
 658 ExecCountSlotsIndexScan(IndexScan *node)
 659 {
 660         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
 661                 ExecCountSlotsNode(innerPlan((Plan *) node)) + INDEXSCAN_NSLOTS;
 662 }