hashjoin.h 4.92 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * hashjoin.h
4
 *	  internal structures for hash joins
5 6
 *
 *
7
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
8
 * Portions Copyright (c) 1994, Regents of the University of California
9
 *
10
 * $PostgreSQL: pgsql/src/include/executor/hashjoin.h,v 1.35 2005/03/06 22:15:05 tgl Exp $
11 12 13
 *
 *-------------------------------------------------------------------------
 */
14
#ifndef HASHJOIN_H
15 16
#define HASHJOIN_H

17
#include "access/htup.h"
18
#include "storage/buffile.h"
19

20 21 22
/* ----------------------------------------------------------------
 *				hash-join hash table structures
 *
23
 * Each active hashjoin has a HashJoinTable control block, which is
24 25
 * palloc'd in the executor's per-query context.  All other storage needed
 * for the hashjoin is kept in private memory contexts, two for each hashjoin.
26
 * This makes it easy and fast to release the storage when we don't need it
27 28
 * anymore.  (Exception: data associated with the temp files lives in the
 * per-query context too, since we always call buffile.c in that context.)
29
 *
30
 * The hashtable contexts are made children of the per-query context, ensuring
31
 * that they will be discarded at end of statement even if the join is
32 33
 * aborted early by an error.  (Likewise, any temporary files we make will
 * be cleaned up by the virtual file manager in event of an error.)
34
 *
35
 * Storage that should live through the entire join is allocated from the
36 37 38
 * "hashCxt", while storage that is only wanted for the current batch is
 * allocated in the "batchCxt".  By resetting the batchCxt at the end of
 * each batch, we free all the per-batch storage reliably and without tedium.
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
 *
 * During first scan of inner relation, we get its tuples from executor.
 * If nbatch > 1 then tuples that don't belong in first batch get saved
 * into inner-batch temp files. The same statements apply for the
 * first scan of the outer relation, except we write tuples to outer-batch
 * temp files.  After finishing the first scan, we do the following for
 * each remaining batch:
 *	1. Read tuples from inner batch file, load into hash buckets.
 *	2. Read tuples from outer batch file, match to hash buckets and output.
 *
 * It is possible to increase nbatch on the fly if the in-memory hash table
 * gets too big.  The hash-value-to-batch computation is arranged so that this
 * can only cause a tuple to go into a later batch than previously thought,
 * never into an earlier batch.  When we increase nbatch, we rescan the hash
 * table and dump out any tuples that are now of a later batch to the correct
 * inner batch file.  Subsequently, while reading either inner or outer batch
 * files, we might find tuples that no longer belong to the current batch;
 * if so, we just dump them out to the correct batch file.
57
 * ----------------------------------------------------------------
58 59
 */

60 61 62 63
/* these are in nodes/execnodes.h: */
/* typedef struct HashJoinTupleData *HashJoinTuple; */
/* typedef struct HashJoinTableData *HashJoinTable; */

64 65
typedef struct HashJoinTupleData
{
66 67
	struct HashJoinTupleData *next;	/* link to next tuple in same bucket */
	uint32		hashvalue;		/* tuple's hash code */
Bruce Momjian's avatar
Bruce Momjian committed
68
	HeapTupleData htup;			/* tuple header */
69
} HashJoinTupleData;
70

71
typedef struct HashJoinTableData
72
{
73 74 75
	int			nbuckets;		/* # buckets in the in-memory hash table */
	/* buckets[i] is head of list of tuples in i'th in-memory bucket */
	struct HashJoinTupleData **buckets;
76
	/* buckets array is per-batch storage, as are all the tuples */
77

78 79 80 81 82 83 84
	int			nbatch;			/* number of batches */
	int			curbatch;		/* current batch #; 0 during 1st pass */

	int			nbatch_original;	/* nbatch when we started inner scan */
	int			nbatch_outstart;	/* nbatch when we started outer scan */

	bool		growEnabled;	/* flag to shut off nbatch increases */
85

86 87
	bool		hashNonEmpty;	/* did inner plan produce any rows? */

Bruce Momjian's avatar
Bruce Momjian committed
88
	/*
89 90 91 92 93
	 * These arrays are allocated for the life of the hash join, but
	 * only if nbatch > 1.  A file is opened only when we first write
	 * a tuple into it (otherwise its pointer remains NULL).  Note that
	 * the zero'th array elements never get used, since we will process
	 * rather than dump out any tuples of batch zero.
94
	 */
Bruce Momjian's avatar
Bruce Momjian committed
95 96
	BufFile   **innerBatchFile; /* buffered virtual temp file per batch */
	BufFile   **outerBatchFile; /* buffered virtual temp file per batch */
97

98
	/*
99 100
	 * Info about the datatype-specific hash functions for the datatypes
	 * being hashed.  We assume that the inner and outer sides of each
Bruce Momjian's avatar
Bruce Momjian committed
101 102 103
	 * hashclause are the same type, or at least share the same hash
	 * function. This is an array of the same length as the number of hash
	 * keys.
104
	 */
105
	FmgrInfo   *hashfunctions;	/* lookup data for hash functions */
106

107 108
	Size		spaceUsed;		/* memory space currently used by tuples */
	Size		spaceAllowed;	/* upper limit for space used */
109

Bruce Momjian's avatar
Bruce Momjian committed
110 111
	MemoryContext hashCxt;		/* context for whole-hash-join storage */
	MemoryContext batchCxt;		/* context for this-batch-only storage */
112
} HashJoinTableData;
113

114
#endif   /* HASHJOIN_H */