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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeIndexscan.c
   4  *        Routines to support indexes and indexed scans of relations
   5  *
   6  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/executor/nodeIndexscan.c,v 1.85 2003/11/09 21:30:36 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/parse_expr.h"
  35 #include "parser/parsetree.h"
  36
  37
  38 /*
  39  * In a multiple-index plan, we must take care to return any given tuple
  40  * only once, even if it matches conditions of several index scans.  Our
  41  * preferred way to do this is to record already-returned tuples in a hash
  42  * table (using the TID as unique identifier).  However, in a very large
  43  * scan this could conceivably run out of memory.  We limit the hash table
  44  * to no more than SortMem KB; if it grows past that, we fall back to the
  45  * pre-7.4 technique: evaluate the prior-scan index quals again for each
  46  * tuple (which is space-efficient, but slow).
  47  *
  48  * When scanning backwards, we use scannum to determine when to emit the
  49  * tuple --- we have to re-emit a tuple in the same scan as it was first
  50  * encountered.
  51  *
  52  * Note: this code would break if the planner were ever to create a multiple
  53  * index plan with overall backwards direction, because the hashtable code
  54  * will emit a tuple the first time it is encountered (which would be the
  55  * highest scan in which it matches the index), but the evaluate-the-quals
  56  * code will emit a tuple in the lowest-numbered scan in which it's valid.
  57  * This could be fixed at need by making the evaluate-the-quals case more
  58  * complex.  Currently the planner will never create such a plan (since it
  59  * considers multi-index plans unordered anyway), so there's no need for
  60  * more complexity.
  61  */
  62 typedef struct
  63 {
  64         /* tid is the hash key and so must be first! */
  65         ItemPointerData tid;            /* TID of a tuple we've returned */
  66         int                     scannum;                /* number of scan we returned it in */
  67 } DupHashTabEntry;
  68
  69
  70 static TupleTableSlot *IndexNext(IndexScanState *node);
  71 static void create_duphash(IndexScanState *node);
  72
  73
  74 /* ----------------------------------------------------------------
  75  *              IndexNext
  76  *
  77  *              Retrieve a tuple from the IndexScan node's currentRelation
  78  *              using the indices in the IndexScanState information.
  79  *
  80  *              note: the old code mentions 'Primary indices'.  to my knowledge
  81  *              we only support a single secondary index. -cim 9/11/89
  82  *
  83  * old comments:
  84  *              retrieve a tuple from relation using the indices given.
  85  *              The indices are used in the order they appear in 'indices'.
  86  *              The indices may be primary or secondary indices:
  87  *                * primary index --    scan the relation 'relID' using keys supplied.
  88  *                * secondary index --  scan the index relation to get the 'tid' for
  89  *                                                              a tuple in the relation 'relID'.
  90  *              If the current index(pointed by 'indexPtr') fails to return a
  91  *              tuple, the next index in the indices is used.
  92  *
  93  *                bug fix so that it should retrieve on a null scan key.
  94  * ----------------------------------------------------------------
  95  */
  96 static TupleTableSlot *
  97 IndexNext(IndexScanState *node)
  98 {
  99         EState     *estate;
 100         ExprContext *econtext;
 101         ScanDirection direction;
 102         IndexScanDescPtr scanDescs;
 103         IndexScanDesc scandesc;
 104         Index           scanrelid;
 105         HeapTuple       tuple;
 106         TupleTableSlot *slot;
 107         int                     numIndices;
 108         bool            bBackward;
 109         int                     indexNumber;
 110
 111         /*
 112          * extract necessary information from index scan node
 113          */
 114         estate = node->ss.ps.state;
 115         direction = estate->es_direction;
 116         if (ScanDirectionIsBackward(((IndexScan *) node->ss.ps.plan)->indxorderdir))
 117         {
 118                 if (ScanDirectionIsForward(direction))
 119                         direction = BackwardScanDirection;
 120                 else if (ScanDirectionIsBackward(direction))
 121                         direction = ForwardScanDirection;
 122         }
 123         scanDescs = node->iss_ScanDescs;
 124         numIndices = node->iss_NumIndices;
 125         econtext = node->ss.ps.ps_ExprContext;
 126         slot = node->ss.ss_ScanTupleSlot;
 127         scanrelid = ((IndexScan *) node->ss.ps.plan)->scan.scanrelid;
 128
 129         /*
 130          * Check if we are evaluating PlanQual for tuple of this relation.
 131          * Additional checking is not good, but no other way for now. We could
 132          * introduce new nodes for this case and handle IndexScan --> NewNode
 133          * switching in Init/ReScan plan...
 134          */
 135         if (estate->es_evTuple != NULL &&
 136                 estate->es_evTuple[scanrelid - 1] != NULL)
 137         {
 138                 List       *qual;
 139
 140                 ExecClearTuple(slot);
 141                 if (estate->es_evTupleNull[scanrelid - 1])
 142                         return slot;            /* return empty slot */
 143
 144                 ExecStoreTuple(estate->es_evTuple[scanrelid - 1],
 145                                            slot, InvalidBuffer, false);
 146
 147                 /* Does the tuple meet any of the OR'd indxqual conditions? */
 148                 econtext->ecxt_scantuple = slot;
 149
 150                 ResetExprContext(econtext);
 151
 152                 foreach(qual, node->indxqualorig)
 153                 {
 154                         if (ExecQual((List *) lfirst(qual), econtext, false))
 155                                 break;
 156                 }
 157                 if (qual == NIL)                /* would not be returned by indices */
 158                         slot->val = NULL;
 159
 160                 /* Flag for the next call that no more tuples */
 161                 estate->es_evTupleNull[scanrelid - 1] = true;
 162
 163                 return slot;
 164         }
 165
 166         /*
 167          * ok, now that we have what we need, fetch an index tuple. if
 168          * scanning this index succeeded then return the appropriate heap
 169          * tuple.. else return NULL.
 170          */
 171         bBackward = ScanDirectionIsBackward(direction);
 172         if (bBackward)
 173         {
 174                 indexNumber = numIndices - node->iss_IndexPtr - 1;
 175                 if (indexNumber < 0)
 176                 {
 177                         indexNumber = 0;
 178                         node->iss_IndexPtr = numIndices - 1;
 179                 }
 180         }
 181         else
 182         {
 183                 if ((indexNumber = node->iss_IndexPtr) < 0)
 184                 {
 185                         indexNumber = 0;
 186                         node->iss_IndexPtr = 0;
 187                 }
 188         }
 189         while (indexNumber < numIndices)
 190         {
 191                 scandesc = scanDescs[node->iss_IndexPtr];
 192                 while ((tuple = index_getnext(scandesc, direction)) != NULL)
 193                 {
 194                         /*
 195                          * Store the scanned tuple in the scan tuple slot of the scan
 196                          * state.  Note: we pass 'false' because tuples returned by
 197                          * amgetnext are pointers onto disk pages and must not be
 198                          * pfree()'d.
 199                          */
 200                         ExecStoreTuple(tuple,           /* tuple to store */
 201                                                    slot,        /* slot to store in */
 202                                                    scandesc->xs_cbuf,   /* buffer containing tuple */
 203                                                    false);              /* don't pfree */
 204
 205                         /*
 206                          * If it's a multiple-index scan, make sure not to double-report
 207                          * a tuple matched by more than one index.  (See notes above.)
 208                          */
 209                         if (numIndices > 1)
 210                         {
 211                                 /* First try the hash table */
 212                                 if (node->iss_DupHash)
 213                                 {
 214                                         DupHashTabEntry *entry;
 215                                         bool    found;
 216
 217                                         entry = (DupHashTabEntry *)
 218                                                 hash_search(node->iss_DupHash,
 219                                                                         &tuple->t_data->t_ctid,
 220                                                                         HASH_ENTER,
 221                                                                         &found);
 222                                         if (entry == NULL ||
 223                                                 node->iss_DupHash->hctl->nentries > node->iss_MaxHash)
 224                                         {
 225                                                 /* out of memory (either hard or soft limit) */
 226                                                 /* release hash table and fall thru to old code */
 227                                                 hash_destroy(node->iss_DupHash);
 228                                                 node->iss_DupHash = NULL;
 229                                         }
 230                                         else if (found)
 231                                         {
 232                                                 /* pre-existing entry */
 233
 234                                                 /*
 235                                                  * It's duplicate if first emitted in a different
 236                                                  * scan.  If same scan, we must be backing up, so
 237                                                  * okay to emit again.
 238                                                  */
 239                                                 if (entry->scannum != node->iss_IndexPtr)
 240                                                 {
 241                                                         /* Dup, so drop it and loop back for another */
 242                                                         ExecClearTuple(slot);
 243                                                         continue;
 244                                                 }
 245                                         }
 246                                         else
 247                                         {
 248                                                 /* new entry, finish filling it in */
 249                                                 entry->scannum = node->iss_IndexPtr;
 250                                         }
 251                                 }
 252                                 /* If hash table has overflowed, do it the hard way */
 253                                 if (node->iss_DupHash == NULL &&
 254                                         node->iss_IndexPtr > 0)
 255                                 {
 256                                         bool            prev_matches = false;
 257                                         int                     prev_index;
 258                                         List       *qual;
 259
 260                                         econtext->ecxt_scantuple = slot;
 261                                         ResetExprContext(econtext);
 262                                         qual = node->indxqualorig;
 263                                         for (prev_index = 0;
 264                                                  prev_index < node->iss_IndexPtr;
 265                                                  prev_index++)
 266                                         {
 267                                                 if (ExecQual((List *) lfirst(qual), econtext, false))
 268                                                 {
 269                                                         prev_matches = true;
 270                                                         break;
 271                                                 }
 272                                                 qual = lnext(qual);
 273                                         }
 274                                         if (prev_matches)
 275                                         {
 276                                                 /* Dup, so drop it and loop back for another */
 277                                                 ExecClearTuple(slot);
 278                                                 continue;
 279                                         }
 280                                 }
 281                         }
 282
 283                         return slot;            /* OK to return tuple */
 284                 }
 285
 286                 if (indexNumber < numIndices)
 287                 {
 288                         indexNumber++;
 289                         if (bBackward)
 290                                 node->iss_IndexPtr--;
 291                         else
 292                                 node->iss_IndexPtr++;
 293                 }
 294         }
 295
 296         /*
 297          * if we get here it means the index scan failed so we are at the end
 298          * of the scan..
 299          */
 300         return ExecClearTuple(slot);
 301 }
 302
 303 /* ----------------------------------------------------------------
 304  *              ExecIndexScan(node)
 305  *
 306  * old comments:
 307  *              Scans the relation using primary or secondary indices and returns
 308  *                 the next qualifying tuple in the direction specified.
 309  *              It calls ExecScan() and passes it the access methods which returns
 310  *              the next tuple using the indices.
 311  *
 312  *              Conditions:
 313  *                -- the "cursor" maintained by the AMI is positioned at the tuple
 314  *                       returned previously.
 315  *
 316  *              Initial States:
 317  *                -- the relation indicated is opened for scanning so that the
 318  *                       "cursor" is positioned before the first qualifying tuple.
 319  *                -- all index realtions are opened for scanning.
 320  *                -- indexPtr points to the first index.
 321  *                -- state variable ruleFlag = nil.
 322  * ----------------------------------------------------------------
 323  */
 324 TupleTableSlot *
 325 ExecIndexScan(IndexScanState *node)
 326 {
 327         /*
 328          * If we have runtime keys and they've not already been set up, do it
 329          * now.
 330          */
 331         if (node->iss_RuntimeKeyInfo && !node->iss_RuntimeKeysReady)
 332                 ExecReScan((PlanState *) node, NULL);
 333
 334         /*
 335          * use IndexNext as access method
 336          */
 337         return ExecScan(&node->ss, (ExecScanAccessMtd) IndexNext);
 338 }
 339
 340 /* ----------------------------------------------------------------
 341  *              ExecIndexReScan(node)
 342  *
 343  *              Recalculates the value of the scan keys whose value depends on
 344  *              information known at runtime and rescans the indexed relation.
 345  *              Updating the scan key was formerly done separately in
 346  *              ExecUpdateIndexScanKeys. Integrating it into ReScan makes
 347  *              rescans of indices and relations/general streams more uniform.
 348  *
 349  * ----------------------------------------------------------------
 350  */
 351 void
 352 ExecIndexReScan(IndexScanState *node, ExprContext *exprCtxt)
 353 {
 354         EState     *estate;
 355         ExprContext *econtext;
 356         int                     numIndices;
 357         IndexScanDescPtr scanDescs;
 358         ScanKey    *scanKeys;
 359         ExprState ***runtimeKeyInfo;
 360         int                *numScanKeys;
 361         Index           scanrelid;
 362         int                     i;
 363         int                     j;
 364
 365         estate = node->ss.ps.state;
 366         econtext = node->iss_RuntimeContext;            /* context for runtime
 367                                                                                                  * keys */
 368         numIndices = node->iss_NumIndices;
 369         scanDescs = node->iss_ScanDescs;
 370         scanKeys = node->iss_ScanKeys;
 371         runtimeKeyInfo = node->iss_RuntimeKeyInfo;
 372         numScanKeys = node->iss_NumScanKeys;
 373         scanrelid = ((IndexScan *) node->ss.ps.plan)->scan.scanrelid;
 374
 375         if (econtext)
 376         {
 377                 /*
 378                  * If we are being passed an outer tuple, save it for runtime key
 379                  * calc.  We also need to link it into the "regular" per-tuple
 380                  * econtext, so it can be used during indexqualorig evaluations.
 381                  */
 382                 if (exprCtxt != NULL)
 383                 {
 384                         ExprContext *stdecontext;
 385
 386                         econtext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 387                         stdecontext = node->ss.ps.ps_ExprContext;
 388                         stdecontext->ecxt_outertuple = exprCtxt->ecxt_outertuple;
 389                 }
 390
 391                 /*
 392                  * Reset the runtime-key context so we don't leak memory as each
 393                  * outer tuple is scanned.      Note this assumes that we will
 394                  * recalculate *all* runtime keys on each call.
 395                  */
 396                 ResetExprContext(econtext);
 397         }
 398
 399         /*
 400          * If we are doing runtime key calculations (ie, the index keys depend
 401          * on data from an outer scan), compute the new key values
 402          */
 403         if (runtimeKeyInfo)
 404         {
 405                 for (i = 0; i < numIndices; i++)
 406                 {
 407                         int                     n_keys;
 408                         ScanKey         scan_keys;
 409                         ExprState **run_keys;
 410
 411                         n_keys = numScanKeys[i];
 412                         scan_keys = scanKeys[i];
 413                         run_keys = runtimeKeyInfo[i];
 414
 415                         for (j = 0; j < n_keys; j++)
 416                         {
 417                                 /*
 418                                  * If we have a run-time key, then extract the run-time
 419                                  * expression and evaluate it with respect to the current
 420                                  * outer tuple.  We then stick the result into the scan
 421                                  * key.
 422                                  *
 423                                  * Note: the result of the eval could be a pass-by-ref value
 424                                  * that's stored in the outer scan's tuple, not in
 425                                  * econtext->ecxt_per_tuple_memory.  We assume that the
 426                                  * outer tuple will stay put throughout our scan.  If this
 427                                  * is wrong, we could copy the result into our context
 428                                  * explicitly, but I think that's not necessary...
 429                                  */
 430                                 if (run_keys[j] != NULL)
 431                                 {
 432                                         Datum           scanvalue;
 433                                         bool            isNull;
 434
 435                                         scanvalue = ExecEvalExprSwitchContext(run_keys[j],
 436                                                                                                                   econtext,
 437                                                                                                                   &isNull,
 438                                                                                                                   NULL);
 439                                         scan_keys[j].sk_argument = scanvalue;
 440                                         if (isNull)
 441                                                 scan_keys[j].sk_flags |= SK_ISNULL;
 442                                         else
 443                                                 scan_keys[j].sk_flags &= ~SK_ISNULL;
 444                                 }
 445                         }
 446                 }
 447
 448                 node->iss_RuntimeKeysReady = true;
 449         }
 450
 451         /* If this is re-scanning of PlanQual ... */
 452         if (estate->es_evTuple != NULL &&
 453                 estate->es_evTuple[scanrelid - 1] != NULL)
 454         {
 455                 estate->es_evTupleNull[scanrelid - 1] = false;
 456                 return;
 457         }
 458
 459         /* reset hash table */
 460         if (numIndices > 1)
 461         {
 462                 if (node->iss_DupHash)
 463                         hash_destroy(node->iss_DupHash);
 464                 create_duphash(node);
 465         }
 466
 467         /* reset index scans */
 468         if (ScanDirectionIsBackward(((IndexScan *) node->ss.ps.plan)->indxorderdir))
 469                 node->iss_IndexPtr = numIndices;
 470         else
 471                 node->iss_IndexPtr = -1;
 472
 473         for (i = 0; i < numIndices; i++)
 474         {
 475                 IndexScanDesc scan = scanDescs[i];
 476                 ScanKey         skey = scanKeys[i];
 477
 478                 index_rescan(scan, skey);
 479         }
 480 }
 481
 482 /* ----------------------------------------------------------------
 483  *              ExecEndIndexScan
 484  * ----------------------------------------------------------------
 485  */
 486 void
 487 ExecEndIndexScan(IndexScanState *node)
 488 {
 489         int                     numIndices;
 490         RelationPtr indexRelationDescs;
 491         IndexScanDescPtr indexScanDescs;
 492         Relation        relation;
 493         int                     i;
 494
 495         /*
 496          * extract information from the node
 497          */
 498         numIndices = node->iss_NumIndices;
 499         indexRelationDescs = node->iss_RelationDescs;
 500         indexScanDescs = node->iss_ScanDescs;
 501         relation = node->ss.ss_currentRelation;
 502
 503         /*
 504          * Free the exprcontext(s)
 505          */
 506         ExecFreeExprContext(&node->ss.ps);
 507         if (node->iss_RuntimeContext)
 508                 FreeExprContext(node->iss_RuntimeContext);
 509
 510         /*
 511          * clear out tuple table slots
 512          */
 513         ExecClearTuple(node->ss.ps.ps_ResultTupleSlot);
 514         ExecClearTuple(node->ss.ss_ScanTupleSlot);
 515
 516         /* drop hash table */
 517         if (node->iss_DupHash)
 518                 hash_destroy(node->iss_DupHash);
 519
 520         /*
 521          * close the index relations
 522          */
 523         for (i = 0; i < numIndices; i++)
 524         {
 525                 if (indexScanDescs[i] != NULL)
 526                         index_endscan(indexScanDescs[i]);
 527
 528                 if (indexRelationDescs[i] != NULL)
 529                         index_close(indexRelationDescs[i]);
 530         }
 531
 532         /*
 533          * close the heap relation.
 534          *
 535          * Currently, we do not release the AccessShareLock acquired by
 536          * ExecInitIndexScan.  This lock should be held till end of
 537          * transaction. (There is a faction that considers this too much
 538          * locking, however.)
 539          */
 540         heap_close(relation, NoLock);
 541 }
 542
 543 /* ----------------------------------------------------------------
 544  *              ExecIndexMarkPos
 545  *
 546  * old comments
 547  *              Marks scan position by marking the current index.
 548  *              Returns nothing.
 549  * ----------------------------------------------------------------
 550  */
 551 void
 552 ExecIndexMarkPos(IndexScanState *node)
 553 {
 554         IndexScanDescPtr indexScanDescs;
 555         IndexScanDesc scanDesc;
 556         int                     indexPtr;
 557
 558         indexPtr = node->iss_MarkIndexPtr = node->iss_IndexPtr;
 559         if (indexPtr >= 0 && indexPtr < node->iss_NumIndices)
 560         {
 561                 indexScanDescs = node->iss_ScanDescs;
 562                 scanDesc = indexScanDescs[indexPtr];
 563
 564                 index_markpos(scanDesc);
 565         }
 566 }
 567
 568 /* ----------------------------------------------------------------
 569  *              ExecIndexRestrPos
 570  *
 571  * old comments
 572  *              Restores scan position by restoring the current index.
 573  *              Returns nothing.
 574  * ----------------------------------------------------------------
 575  */
 576 void
 577 ExecIndexRestrPos(IndexScanState *node)
 578 {
 579         IndexScanDescPtr indexScanDescs;
 580         IndexScanDesc scanDesc;
 581         int                     indexPtr;
 582
 583         indexPtr = node->iss_IndexPtr = node->iss_MarkIndexPtr;
 584         if (indexPtr >= 0 && indexPtr < node->iss_NumIndices)
 585         {
 586                 indexScanDescs = node->iss_ScanDescs;
 587                 scanDesc = indexScanDescs[indexPtr];
 588
 589                 index_restrpos(scanDesc);
 590         }
 591 }
 592
 593 /* ----------------------------------------------------------------
 594  *              ExecInitIndexScan
 595  *
 596  *              Initializes the index scan's state information, creates
 597  *              scan keys, and opens the base and index relations.
 598  *
 599  *              Note: index scans have 2 sets of state information because
 600  *                        we have to keep track of the base relation and the
 601  *                        index relations.
 602  *
 603  * old comments
 604  *              Creates the run-time state information for the node and
 605  *              sets the relation id to contain relevant descriptors.
 606  *
 607  *              Parameters:
 608  *                node: IndexNode node produced by the planner.
 609  *                estate: the execution state initialized in InitPlan.
 610  * ----------------------------------------------------------------
 611  */
 612 IndexScanState *
 613 ExecInitIndexScan(IndexScan *node, EState *estate)
 614 {
 615         IndexScanState *indexstate;
 616         List       *indxqual;
 617         List       *indxstrategy;
 618         List       *indxid;
 619         int                     i;
 620         int                     numIndices;
 621         int                     indexPtr;
 622         ScanKey    *scanKeys;
 623         int                *numScanKeys;
 624         RelationPtr indexDescs;
 625         IndexScanDescPtr scanDescs;
 626         ExprState ***runtimeKeyInfo;
 627         bool            have_runtime_keys;
 628         RangeTblEntry *rtentry;
 629         Index           relid;
 630         Oid                     reloid;
 631         Relation        currentRelation;
 632
 633         /*
 634          * create state structure
 635          */
 636         indexstate = makeNode(IndexScanState);
 637         indexstate->ss.ps.plan = (Plan *) node;
 638         indexstate->ss.ps.state = estate;
 639
 640         /*
 641          * Miscellaneous initialization
 642          *
 643          * create expression context for node
 644          */
 645         ExecAssignExprContext(estate, &indexstate->ss.ps);
 646
 647         /*
 648          * initialize child expressions
 649          */
 650         indexstate->ss.ps.targetlist = (List *)
 651                 ExecInitExpr((Expr *) node->scan.plan.targetlist,
 652                                          (PlanState *) indexstate);
 653         indexstate->ss.ps.qual = (List *)
 654                 ExecInitExpr((Expr *) node->scan.plan.qual,
 655                                          (PlanState *) indexstate);
 656         indexstate->indxqual = (List *)
 657                 ExecInitExpr((Expr *) node->indxqual,
 658                                          (PlanState *) indexstate);
 659         indexstate->indxqualorig = (List *)
 660                 ExecInitExpr((Expr *) node->indxqualorig,
 661                                          (PlanState *) indexstate);
 662
 663 #define INDEXSCAN_NSLOTS 2
 664
 665         /*
 666          * tuple table initialization
 667          */
 668         ExecInitResultTupleSlot(estate, &indexstate->ss.ps);
 669         ExecInitScanTupleSlot(estate, &indexstate->ss);
 670
 671         /*
 672          * Initialize index-specific scan state
 673          */
 674         indexstate->iss_NumIndices = 0;
 675         indexstate->iss_IndexPtr = -1;
 676         indexstate->iss_ScanKeys = NULL;
 677         indexstate->iss_NumScanKeys = NULL;
 678         indexstate->iss_RuntimeKeyInfo = NULL;
 679         indexstate->iss_RuntimeContext = NULL;
 680         indexstate->iss_RuntimeKeysReady = false;
 681         indexstate->iss_RelationDescs = NULL;
 682         indexstate->iss_ScanDescs = NULL;
 683
 684         /*
 685          * get the index node information
 686          */
 687         indxid = node->indxid;
 688         numIndices = length(indxid);
 689         indexPtr = -1;
 690
 691         CXT1_printf("ExecInitIndexScan: context is %d\n", CurrentMemoryContext);
 692
 693         /*
 694          * scanKeys is used to keep track of the ScanKey's. This is needed
 695          * because a single scan may use several indices and each index has
 696          * its own ScanKey.
 697          */
 698         numScanKeys = (int *) palloc(numIndices * sizeof(int));
 699         scanKeys = (ScanKey *) palloc(numIndices * sizeof(ScanKey));
 700         indexDescs = (RelationPtr) palloc(numIndices * sizeof(Relation));
 701         scanDescs = (IndexScanDescPtr) palloc(numIndices * sizeof(IndexScanDesc));
 702
 703         /*
 704          * initialize space for runtime key info (may not be needed)
 705          */
 706         have_runtime_keys = false;
 707         runtimeKeyInfo = (ExprState ***) palloc0(numIndices * sizeof(ExprState **));
 708
 709         /*
 710          * build the index scan keys from the index qualification
 711          */
 712         indxqual = node->indxqual;
 713         indxstrategy = node->indxstrategy;
 714         for (i = 0; i < numIndices; i++)
 715         {
 716                 List       *quals;
 717                 List       *strategies;
 718                 int                     n_keys;
 719                 ScanKey         scan_keys;
 720                 ExprState **run_keys;
 721                 int                     j;
 722
 723                 quals = lfirst(indxqual);
 724                 indxqual = lnext(indxqual);
 725                 strategies = lfirst(indxstrategy);
 726                 indxstrategy = lnext(indxstrategy);
 727                 n_keys = length(quals);
 728                 scan_keys = (n_keys <= 0) ? (ScanKey) NULL :
 729                         (ScanKey) palloc(n_keys * sizeof(ScanKeyData));
 730                 run_keys = (n_keys <= 0) ? (ExprState **) NULL :
 731                         (ExprState **) palloc(n_keys * sizeof(ExprState *));
 732
 733                 /*
 734                  * for each opclause in the given qual, convert each qual's
 735                  * opclause into a single scan key
 736                  */
 737                 for (j = 0; j < n_keys; j++)
 738                 {
 739                         OpExpr     *clause;                     /* one clause of index qual */
 740                         Expr       *leftop;                     /* expr on lhs of operator */
 741                         Expr       *rightop;            /* expr on rhs ... */
 742                         int                     flags = 0;
 743                         AttrNumber      varattno;               /* att number used in scan */
 744                         StrategyNumber strategy;        /* op's strategy number */
 745                         RegProcedure opfuncid;          /* operator proc id used in scan */
 746                         Datum           scanvalue;              /* value used in scan (if const) */
 747                         Oid                     rhstype;                /* datatype of comparison value */
 748
 749                         /*
 750                          * extract clause information from the qualification
 751                          */
 752                         clause = (OpExpr *) lfirst(quals);
 753                         quals = lnext(quals);
 754                         strategy = lfirsti(strategies);
 755                         strategies = lnext(strategies);
 756
 757                         if (!IsA(clause, OpExpr))
 758                                 elog(ERROR, "indxqual is not an OpExpr");
 759
 760                         opfuncid = clause->opfuncid;
 761
 762                         /*
 763                          * Here we figure out the contents of the index qual. The
 764                          * usual case is (var op const) which means we form a scan key
 765                          * for the attribute listed in the var node and use the value of
 766                          * the const as comparison data.
 767                          *
 768                          * If we don't have a const node, it means our scan key is a
 769                          * function of information obtained during the execution of the
 770                          * plan, in which case we need to recalculate the index scan key
 771                          * at run time.  Hence, we set have_runtime_keys to true and place
 772                          * the appropriate subexpression in run_keys. The corresponding
 773                          * scan key values are recomputed at run time.
 774                          */
 775                         run_keys[j] = NULL;
 776
 777                         /*
 778                          * determine information in leftop
 779                          */
 780                         leftop = (Expr *) get_leftop((Expr *) clause);
 781
 782                         if (leftop && IsA(leftop, RelabelType))
 783                                 leftop = ((RelabelType *) leftop)->arg;
 784
 785                         Assert(leftop != NULL);
 786
 787                         if (!(IsA(leftop, Var) &&
 788                                   var_is_rel((Var *) leftop)))
 789                                 elog(ERROR, "indxqual doesn't have key on left side");
 790
 791                         varattno = ((Var *) leftop)->varattno;
 792
 793                         /*
 794                          * now determine information in rightop
 795                          */
 796                         rightop = (Expr *) get_rightop((Expr *) clause);
 797
 798                         rhstype = exprType((Node *) rightop);
 799
 800                         if (rightop && IsA(rightop, RelabelType))
 801                                 rightop = ((RelabelType *) rightop)->arg;
 802
 803                         Assert(rightop != NULL);
 804
 805                         if (IsA(rightop, Const))
 806                         {
 807                                 /*
 808                                  * if the rightop is a const node then it means it
 809                                  * identifies the value to place in our scan key.
 810                                  */
 811                                 scanvalue = ((Const *) rightop)->constvalue;
 812                                 if (((Const *) rightop)->constisnull)
 813                                         flags |= SK_ISNULL;
 814                         }
 815                         else
 816                         {
 817                                 /*
 818                                  * otherwise, the rightop contains an expression evaluable
 819                                  * at runtime to figure out the value to place in our scan
 820                                  * key.
 821                                  */
 822                                 have_runtime_keys = true;
 823                                 run_keys[j] = ExecInitExpr(rightop, (PlanState *) indexstate);
 824                                 scanvalue = (Datum) 0;
 825                         }
 826
 827                         /*
 828                          * initialize the scan key's fields appropriately
 829                          */
 830                         ScanKeyEntryInitialize(&scan_keys[j],
 831                                                                    flags,
 832                                                                    varattno,    /* attribute number to
 833                                                                                                  * scan */
 834                                                                    strategy,    /* op's strategy */
 835                                                                    opfuncid,    /* reg proc to use */
 836                                                                    scanvalue,   /* constant */
 837                                                                    rhstype);    /* constant's type */
 838                 }
 839
 840                 /*
 841                  * store the key information into our arrays.
 842                  */
 843                 numScanKeys[i] = n_keys;
 844                 scanKeys[i] = scan_keys;
 845                 runtimeKeyInfo[i] = run_keys;
 846         }
 847
 848         indexstate->iss_NumIndices = numIndices;
 849         if (ScanDirectionIsBackward(node->indxorderdir))
 850                 indexPtr = numIndices;
 851         indexstate->iss_IndexPtr = indexPtr;
 852         indexstate->iss_ScanKeys = scanKeys;
 853         indexstate->iss_NumScanKeys = numScanKeys;
 854
 855         /*
 856          * If all of our keys have the form (var op const), then we have no
 857          * runtime keys so we store NULL in the runtime key info. Otherwise
 858          * runtime key info contains an array of pointers (one for each index)
 859          * to arrays of flags (one for each key) which indicate that the qual
 860          * needs to be evaluated at runtime. -cim 10/24/89
 861          *
 862          * If we do have runtime keys, we need an ExprContext to evaluate them;
 863          * the node's standard context won't do because we want to reset that
 864          * context for every tuple.  So, build another context just like the
 865          * other one... -tgl 7/11/00
 866          */
 867         if (have_runtime_keys)
 868         {
 869                 ExprContext *stdecontext = indexstate->ss.ps.ps_ExprContext;
 870
 871                 ExecAssignExprContext(estate, &indexstate->ss.ps);
 872                 indexstate->iss_RuntimeKeyInfo = runtimeKeyInfo;
 873                 indexstate->iss_RuntimeContext = indexstate->ss.ps.ps_ExprContext;
 874                 indexstate->ss.ps.ps_ExprContext = stdecontext;
 875         }
 876         else
 877         {
 878                 indexstate->iss_RuntimeKeyInfo = NULL;
 879                 indexstate->iss_RuntimeContext = NULL;
 880                 /* Get rid of the speculatively-allocated flag arrays, too */
 881                 for (i = 0; i < numIndices; i++)
 882                 {
 883                         if (runtimeKeyInfo[i] != NULL)
 884                                 pfree(runtimeKeyInfo[i]);
 885                 }
 886                 pfree(runtimeKeyInfo);
 887         }
 888
 889         /*
 890          * open the base relation and acquire AccessShareLock on it.
 891          */
 892         relid = node->scan.scanrelid;
 893         rtentry = rt_fetch(relid, estate->es_range_table);
 894         reloid = rtentry->relid;
 895
 896         currentRelation = heap_open(reloid, AccessShareLock);
 897
 898         indexstate->ss.ss_currentRelation = currentRelation;
 899         indexstate->ss.ss_currentScanDesc = NULL;       /* no heap scan here */
 900
 901         /*
 902          * get the scan type from the relation descriptor.
 903          */
 904         ExecAssignScanType(&indexstate->ss, RelationGetDescr(currentRelation), false);
 905
 906         /*
 907          * open the index relations and initialize relation and scan
 908          * descriptors.  Note we acquire no locks here; the index machinery
 909          * does its own locks and unlocks.      (We rely on having AccessShareLock
 910          * on the parent table to ensure the index won't go away!)
 911          */
 912         for (i = 0; i < numIndices; i++)
 913         {
 914                 Oid                     indexOid = lfirsto(indxid);
 915
 916                 indexDescs[i] = index_open(indexOid);
 917                 scanDescs[i] = index_beginscan(currentRelation,
 918                                                                            indexDescs[i],
 919                                                                            estate->es_snapshot,
 920                                                                            numScanKeys[i],
 921                                                                            scanKeys[i]);
 922                 indxid = lnext(indxid);
 923         }
 924
 925         indexstate->iss_RelationDescs = indexDescs;
 926         indexstate->iss_ScanDescs = scanDescs;
 927
 928         /*
 929          * Initialize result tuple type and projection info.
 930          */
 931         ExecAssignResultTypeFromTL(&indexstate->ss.ps);
 932         ExecAssignScanProjectionInfo(&indexstate->ss);
 933
 934         /*
 935          * Initialize hash table if needed.
 936          */
 937         if (numIndices > 1)
 938                 create_duphash(indexstate);
 939         else
 940                 indexstate->iss_DupHash = NULL;
 941
 942         /*
 943          * all done.
 944          */
 945         return indexstate;
 946 }
 947
 948 static void
 949 create_duphash(IndexScanState *node)
 950 {
 951         HASHCTL         hash_ctl;
 952
 953         MemSet(&hash_ctl, 0, sizeof(hash_ctl));
 954         hash_ctl.keysize = SizeOfIptrData;
 955         hash_ctl.entrysize = sizeof(DupHashTabEntry);
 956         hash_ctl.hash = tag_hash;
 957         hash_ctl.hcxt = CurrentMemoryContext;
 958         node->iss_DupHash = hash_create("DupHashTable",
 959                                                                         (long) ceil(node->ss.ps.plan->plan_rows),
 960                                                                         &hash_ctl,
 961                                                                         HASH_ELEM | HASH_FUNCTION | HASH_CONTEXT);
 962         if (node->iss_DupHash == NULL)
 963                 ereport(ERROR,
 964                                 (errcode(ERRCODE_OUT_OF_MEMORY),
 965                                  errmsg("out of memory")));
 966         node->iss_MaxHash = (SortMem * 1024L) /
 967                 (MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(sizeof(DupHashTabEntry)));
 968 }
 969
 970 int
 971 ExecCountSlotsIndexScan(IndexScan *node)
 972 {
 973         return ExecCountSlotsNode(outerPlan((Plan *) node)) +
 974                 ExecCountSlotsNode(innerPlan((Plan *) node)) + INDEXSCAN_NSLOTS;
 975 }