nodeIndexscan.c

/*-------------------------------------------------------------------------
 *
 * nodeIndexscan.c
 *	  Routines to support indexes and indexed scans of relations
 *
 * Portions Copyright (c) 1996-2004, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/executor/nodeIndexscan.c,v 1.97 2004/08/29 05:06:42 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
/*
 * INTERFACE ROUTINES
 *		ExecIndexScan			scans a relation using indices
 *		ExecIndexNext			using index to retrieve next tuple
 *		ExecInitIndexScan		creates and initializes state info.
 *		ExecIndexReScan			rescans the indexed relation.
 *		ExecEndIndexScan		releases all storage.
 *		ExecIndexMarkPos		marks scan position.
 *		ExecIndexRestrPos		restores scan position.
 */
#include "postgres.h"

#include "access/genam.h"
#include "access/heapam.h"
#include "executor/execdebug.h"
#include "executor/nodeIndexscan.h"
#include "miscadmin.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "parser/parsetree.h"


/*
 * In a multiple-index plan, we must take care to return any given tuple
 * only once, even if it matches conditions of several index scans.  Our
 * preferred way to do this is to record already-returned tuples in a hash
 * table (using the TID as unique identifier).	However, in a very large
 * scan this could conceivably run out of memory.  We limit the hash table
 * to no more than work_mem KB; if it grows past that, we fall back to the
 * pre-7.4 technique: evaluate the prior-scan index quals again for each
 * tuple (which is space-efficient, but slow).
 *
 * When scanning backwards, we use scannum to determine when to emit the
 * tuple --- we have to re-emit a tuple in the same scan as it was first
 * encountered.
 *
 * Note: this code would break if the planner were ever to create a multiple
 * index plan with overall backwards direction, because the hashtable code
 * will emit a tuple the first time it is encountered (which would be the
 * highest scan in which it matches the index), but the evaluate-the-quals
 * code will emit a tuple in the lowest-numbered scan in which it's valid.
 * This could be fixed at need by making the evaluate-the-quals case more
 * complex.  Currently the planner will never create such a plan (since it
 * considers multi-index plans unordered anyway), so there's no need for
 * more complexity.
 */
typedef struct
{
	/* tid is the hash key and so must be first! */
	ItemPointerData tid;		/* TID of a tuple we've returned */
	int			scannum;		/* number of scan we returned it in */
} DupHashTabEntry;


static TupleTableSlot *IndexNext(IndexScanState *node);
static void create_duphash(IndexScanState *node);