hashjoin.h File Reference

#include "nodes/execnodes.h"
#include "port/atomics.h"
#include "storage/barrier.h"
#include "storage/buffile.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
#include "utils/sharedtuplestore.h"

Include dependency graph for hashjoin.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	HashJoinTupleData
struct	HashSkewBucket
struct	HashMemoryChunkData
struct	ParallelHashJoinBatch
struct	ParallelHashJoinBatchAccessor
struct	ParallelHashJoinState
struct	HashJoinTableData

Macros
#define	HJTUPLE_OVERHEAD   MAXALIGN(sizeof(HashJoinTupleData))
#define	HJTUPLE_MINTUPLE(hjtup)    ((MinimalTuple) ((char *) (hjtup) + HJTUPLE_OVERHEAD))
#define	SKEW_BUCKET_OVERHEAD   MAXALIGN(sizeof(HashSkewBucket))
#define	INVALID_SKEW_BUCKET_NO   (-1)
#define	SKEW_HASH_MEM_PERCENT   2
#define	SKEW_MIN_OUTER_FRACTION   0.01
#define	HASH_CHUNK_SIZE   ((Size) (32 * 1024))
#define	HASH_CHUNK_HEADER_SIZE   MAXALIGN(sizeof(HashMemoryChunkData))
#define	HASH_CHUNK_DATA(hc)   (((char *) (hc)) + HASH_CHUNK_HEADER_SIZE)
#define	HASH_CHUNK_THRESHOLD   (HASH_CHUNK_SIZE / 4)
#define	ParallelHashJoinBatchInner(batch)
#define	ParallelHashJoinBatchOuter(batch, nparticipants)
#define	EstimateParallelHashJoinBatch(hashtable)
#define	NthParallelHashJoinBatch(base, n)
#define	PHJ_BUILD_ELECT   0
#define	PHJ_BUILD_ALLOCATE   1
#define	PHJ_BUILD_HASH_INNER   2
#define	PHJ_BUILD_HASH_OUTER   3
#define	PHJ_BUILD_RUN   4
#define	PHJ_BUILD_FREE   5
#define	PHJ_BATCH_ELECT   0
#define	PHJ_BATCH_ALLOCATE   1
#define	PHJ_BATCH_LOAD   2
#define	PHJ_BATCH_PROBE   3
#define	PHJ_BATCH_SCAN   4
#define	PHJ_BATCH_FREE   5
#define	PHJ_GROW_BATCHES_ELECT   0
#define	PHJ_GROW_BATCHES_REALLOCATE   1
#define	PHJ_GROW_BATCHES_REPARTITION   2
#define	PHJ_GROW_BATCHES_DECIDE   3
#define	PHJ_GROW_BATCHES_FINISH   4
#define	PHJ_GROW_BATCHES_PHASE(n)   ((n) % 5) /* circular phases */
#define	PHJ_GROW_BUCKETS_ELECT   0
#define	PHJ_GROW_BUCKETS_REALLOCATE   1
#define	PHJ_GROW_BUCKETS_REINSERT   2
#define	PHJ_GROW_BUCKETS_PHASE(n)   ((n) % 3) /* circular phases */

Typedefs
typedef struct HashJoinTupleData	HashJoinTupleData
typedef struct HashSkewBucket	HashSkewBucket
typedef struct HashMemoryChunkData	HashMemoryChunkData
typedef struct HashMemoryChunkData *	HashMemoryChunk
typedef struct ParallelHashJoinBatch	ParallelHashJoinBatch
typedef struct ParallelHashJoinBatchAccessor	ParallelHashJoinBatchAccessor
typedef enum ParallelHashGrowth	ParallelHashGrowth
typedef struct ParallelHashJoinState	ParallelHashJoinState
typedef struct HashJoinTableData	HashJoinTableData

Enumerations
enum	ParallelHashGrowth { PHJ_GROWTH_OK , PHJ_GROWTH_NEED_MORE_BUCKETS , PHJ_GROWTH_NEED_MORE_BATCHES , PHJ_GROWTH_DISABLED }

Macro Definition Documentation

EstimateParallelHashJoinBatch

#define EstimateParallelHashJoinBatch

(

hashtable

)

Value:

    (MAXALIGN(sizeof(ParallelHashJoinBatch)) +                          \
	 MAXALIGN(sts_estimate((hashtable)->parallel_state->nparticipants)) * 2)

Definition at line 204 of file hashjoin.h.

{
    ParallelHashJoinBatch *shared;  /* pointer to shared state */
 
    /* Per-backend partial counters to reduce contention. */
    size_t      preallocated;   /* pre-allocated space for this backend */
    size_t      ntuples;        /* number of tuples */
    size_t      size;           /* size of partition in memory */
    size_t      estimated_size; /* size of partition on disk */
    size_t      old_ntuples;    /* how many tuples before repartitioning? */
    bool        at_least_one_chunk; /* has this backend allocated a chunk? */
    bool        outer_eof;      /* has this process hit end of batch? */
    bool        done;           /* flag to remember that a batch is done */
    SharedTuplestoreAccessor *inner_tuples;
    SharedTuplestoreAccessor *outer_tuples;
} ParallelHashJoinBatchAccessor;
 
/*
 * While hashing the inner relation, any participant might determine that it's
 * time to increase the number of buckets to reduce the load factor or batches
 * to reduce the memory size.  This is indicated by setting the growth flag to
 * these values.
 */
typedef enum ParallelHashGrowth
{
    /* The current dimensions are sufficient. */
    PHJ_GROWTH_OK,
    /* The load factor is too high, so we need to add buckets. */
    PHJ_GROWTH_NEED_MORE_BUCKETS,
    /* The memory budget would be exhausted, so we need to repartition. */
    PHJ_GROWTH_NEED_MORE_BATCHES,
    /* Repartitioning didn't help last time, so don't try to do that again. */
    PHJ_GROWTH_DISABLED,
} ParallelHashGrowth;
 
/*
 * The shared state used to coordinate a Parallel Hash Join.  This is stored
 * in the DSM segment.
 */
typedef struct ParallelHashJoinState
{
    dsa_pointer batches;        /* array of ParallelHashJoinBatch */
    dsa_pointer old_batches;    /* previous generation during repartition */
    int         nbatch;         /* number of batches now */
    int         old_nbatch;     /* previous number of batches */
    int         nbuckets;       /* number of buckets */
    ParallelHashGrowth growth;  /* control batch/bucket growth */
    dsa_pointer chunk_work_queue;   /* chunk work queue */
    int         nparticipants;
    size_t      space_allowed;
    size_t      total_tuples;   /* total number of inner tuples */
    LWLock      lock;           /* lock protecting the above */
 
    Barrier     build_barrier;  /* synchronization for the build phases */
    Barrier     grow_batches_barrier;
    Barrier     grow_buckets_barrier;
    pg_atomic_uint32 distributor;   /* counter for load balancing */
 
    SharedFileSet fileset;      /* space for shared temporary files */
} ParallelHashJoinState;
 
/* The phases for building batches, used by build_barrier. */
#define PHJ_BUILD_ELECT                 0
#define PHJ_BUILD_ALLOCATE              1
#define PHJ_BUILD_HASH_INNER            2
#define PHJ_BUILD_HASH_OUTER            3
#define PHJ_BUILD_RUN                   4
#define PHJ_BUILD_FREE                  5
 
/* The phases for probing each batch, used by for batch_barrier. */
#define PHJ_BATCH_ELECT                 0
#define PHJ_BATCH_ALLOCATE              1
#define PHJ_BATCH_LOAD                  2
#define PHJ_BATCH_PROBE                 3
#define PHJ_BATCH_SCAN                  4
#define PHJ_BATCH_FREE                  5
 
/* The phases of batch growth while hashing, for grow_batches_barrier. */
#define PHJ_GROW_BATCHES_ELECT          0
#define PHJ_GROW_BATCHES_REALLOCATE     1
#define PHJ_GROW_BATCHES_REPARTITION    2
#define PHJ_GROW_BATCHES_DECIDE         3
#define PHJ_GROW_BATCHES_FINISH         4
#define PHJ_GROW_BATCHES_PHASE(n)       ((n) % 5)   /* circular phases */
 
/* The phases of bucket growth while hashing, for grow_buckets_barrier. */
#define PHJ_GROW_BUCKETS_ELECT          0
#define PHJ_GROW_BUCKETS_REALLOCATE     1
#define PHJ_GROW_BUCKETS_REINSERT       2
#define PHJ_GROW_BUCKETS_PHASE(n)       ((n) % 3)   /* circular phases */
 
typedef struct HashJoinTableData
{
    int         nbuckets;       /* # buckets in the in-memory hash table */
    int         log2_nbuckets;  /* its log2 (nbuckets must be a power of 2) */
 
    int         nbuckets_original;  /* # buckets when starting the first hash */
    int         nbuckets_optimal;   /* optimal # buckets (per batch) */
    int         log2_nbuckets_optimal;  /* log2(nbuckets_optimal) */
 
    /* buckets[i] is head of list of tuples in i'th in-memory bucket */
    union
    {
        /* unshared array is per-batch storage, as are all the tuples */
        struct HashJoinTupleData **unshared;
        /* shared array is per-query DSA area, as are all the tuples */
        dsa_pointer_atomic *shared;
    }           buckets;
 
    bool        skewEnabled;    /* are we using skew optimization? */
    HashSkewBucket **skewBucket;    /* hashtable of skew buckets */
    int         skewBucketLen;  /* size of skewBucket array (a power of 2!) */
    int         nSkewBuckets;   /* number of active skew buckets */
    int        *skewBucketNums; /* array indexes of active skew buckets */
 
    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 */
 
    /*
     * totalTuples is the running total of tuples inserted into either the
     * main or skew hash tables.  reportTuples is the number of tuples that we
     * want EXPLAIN to show as output from the Hash node (this includes saved
     * null-keyed tuples as well as those inserted into the hash tables).
     * skewTuples is the number of tuples present in the skew hash table.
     */
    double      totalTuples;
    double      reportTuples;
    double      skewTuples;
 
    /*
     * 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.
     */
    BufFile   **innerBatchFile; /* buffered virtual temp file per batch */
    BufFile   **outerBatchFile; /* buffered virtual temp file per batch */
 
    Size        spaceUsed;      /* memory space currently used by tuples */
    Size        spaceAllowed;   /* upper limit for space used */
    Size        spacePeak;      /* peak space used */
    Size        spaceUsedSkew;  /* skew hash table's current space usage */
    Size        spaceAllowedSkew;   /* upper limit for skew hashtable */
 
    MemoryContext hashCxt;      /* context for whole-hash-join storage */
    MemoryContext batchCxt;     /* context for this-batch-only storage */
    MemoryContext spillCxt;     /* context for spilling to temp files */
 
    /* used for dense allocation of tuples (into linked chunks) */
    HashMemoryChunk chunks;     /* one list for the whole batch */
 
    /* Shared and private state for Parallel Hash. */
    HashMemoryChunk current_chunk;  /* this backend's current chunk */
    dsa_area   *area;           /* DSA area to allocate memory from */
    ParallelHashJoinState *parallel_state;
    ParallelHashJoinBatchAccessor *batches;
    dsa_pointer current_chunk_shared;
} HashJoinTableData;
 
#endif                          /* HASHJOIN_H */

HASH_CHUNK_DATA

#define HASH_CHUNK_DATA

(

hc

)

(((char *) (hc)) + HASH_CHUNK_HEADER_SIZE)

Definition at line 163 of file hashjoin.h.

HASH_CHUNK_HEADER_SIZE

#define HASH_CHUNK_HEADER_SIZE   MAXALIGN(sizeof(HashMemoryChunkData))

Definition at line 162 of file hashjoin.h.

HASH_CHUNK_SIZE

#define HASH_CHUNK_SIZE   ((Size) (32 * 1024))

Definition at line 161 of file hashjoin.h.

HASH_CHUNK_THRESHOLD

#define HASH_CHUNK_THRESHOLD   (HASH_CHUNK_SIZE / 4)

Definition at line 165 of file hashjoin.h.

HJTUPLE_MINTUPLE

#define HJTUPLE_MINTUPLE

(

hjtup

)

((MinimalTuple) ((char *) (hjtup) + HJTUPLE_OVERHEAD))

Definition at line 102 of file hashjoin.h.

HJTUPLE_OVERHEAD

#define HJTUPLE_OVERHEAD   MAXALIGN(sizeof(HashJoinTupleData))

Definition at line 101 of file hashjoin.h.

INVALID_SKEW_BUCKET_NO

#define INVALID_SKEW_BUCKET_NO   (-1)

Definition at line 131 of file hashjoin.h.

NthParallelHashJoinBatch

#define NthParallelHashJoinBatch	(		base,
			n
	)

Value:

    ((ParallelHashJoinBatch *)                                          \
     ((char *) (base) +                                                 \
      EstimateParallelHashJoinBatch(hashtable) *  (n)))

Definition at line 209 of file hashjoin.h.

ParallelHashJoinBatchInner

#define ParallelHashJoinBatchInner

(

batch

)

Value:

    ((SharedTuplestore *)                                           \
     ((char *) (batch) + MAXALIGN(sizeof(ParallelHashJoinBatch))))

Definition at line 193 of file hashjoin.h.

ParallelHashJoinBatchOuter

#define ParallelHashJoinBatchOuter	(		batch,
			nparticipants
	)

Value:

    ((SharedTuplestore *)                                               \
     ((char *) ParallelHashJoinBatchInner(batch) +                      \
	  MAXALIGN(sts_estimate(nparticipants))))

Definition at line 198 of file hashjoin.h.

PHJ_BATCH_ALLOCATE

#define PHJ_BATCH_ALLOCATE   1

Definition at line 289 of file hashjoin.h.

PHJ_BATCH_ELECT

#define PHJ_BATCH_ELECT   0

Definition at line 288 of file hashjoin.h.

PHJ_BATCH_FREE

#define PHJ_BATCH_FREE   5

Definition at line 293 of file hashjoin.h.

PHJ_BATCH_LOAD

#define PHJ_BATCH_LOAD   2

Definition at line 290 of file hashjoin.h.

PHJ_BATCH_PROBE

#define PHJ_BATCH_PROBE   3

Definition at line 291 of file hashjoin.h.

PHJ_BATCH_SCAN

#define PHJ_BATCH_SCAN   4

Definition at line 292 of file hashjoin.h.

PHJ_BUILD_ALLOCATE

#define PHJ_BUILD_ALLOCATE   1

Definition at line 281 of file hashjoin.h.

PHJ_BUILD_ELECT

#define PHJ_BUILD_ELECT   0

Definition at line 280 of file hashjoin.h.

PHJ_BUILD_FREE

#define PHJ_BUILD_FREE   5

Definition at line 285 of file hashjoin.h.

PHJ_BUILD_HASH_INNER

#define PHJ_BUILD_HASH_INNER   2

Definition at line 282 of file hashjoin.h.

PHJ_BUILD_HASH_OUTER

#define PHJ_BUILD_HASH_OUTER   3

Definition at line 283 of file hashjoin.h.

PHJ_BUILD_RUN

#define PHJ_BUILD_RUN   4

Definition at line 284 of file hashjoin.h.

PHJ_GROW_BATCHES_DECIDE

#define PHJ_GROW_BATCHES_DECIDE   3

Definition at line 299 of file hashjoin.h.

PHJ_GROW_BATCHES_ELECT

#define PHJ_GROW_BATCHES_ELECT   0

Definition at line 296 of file hashjoin.h.

PHJ_GROW_BATCHES_FINISH

#define PHJ_GROW_BATCHES_FINISH   4

Definition at line 300 of file hashjoin.h.

PHJ_GROW_BATCHES_PHASE

#define PHJ_GROW_BATCHES_PHASE

(

n

)

((n) % 5) /* circular phases */

Definition at line 301 of file hashjoin.h.

PHJ_GROW_BATCHES_REALLOCATE

#define PHJ_GROW_BATCHES_REALLOCATE   1

Definition at line 297 of file hashjoin.h.

PHJ_GROW_BATCHES_REPARTITION

#define PHJ_GROW_BATCHES_REPARTITION   2

Definition at line 298 of file hashjoin.h.

PHJ_GROW_BUCKETS_ELECT

#define PHJ_GROW_BUCKETS_ELECT   0

Definition at line 304 of file hashjoin.h.

PHJ_GROW_BUCKETS_PHASE

#define PHJ_GROW_BUCKETS_PHASE

(

n

)

((n) % 3) /* circular phases */

Definition at line 307 of file hashjoin.h.

PHJ_GROW_BUCKETS_REALLOCATE

#define PHJ_GROW_BUCKETS_REALLOCATE   1

Definition at line 305 of file hashjoin.h.

PHJ_GROW_BUCKETS_REINSERT

#define PHJ_GROW_BUCKETS_REINSERT   2

Definition at line 306 of file hashjoin.h.

SKEW_BUCKET_OVERHEAD

#define SKEW_BUCKET_OVERHEAD   MAXALIGN(sizeof(HashSkewBucket))

Definition at line 130 of file hashjoin.h.

SKEW_HASH_MEM_PERCENT

#define SKEW_HASH_MEM_PERCENT   2

Definition at line 132 of file hashjoin.h.

SKEW_MIN_OUTER_FRACTION

#define SKEW_MIN_OUTER_FRACTION   0.01

Definition at line 133 of file hashjoin.h.

Typedef Documentation

HashJoinTableData

typedef struct HashJoinTableData HashJoinTableData

HashJoinTupleData

typedef struct HashJoinTupleData HashJoinTupleData

HashMemoryChunk

typedef struct HashMemoryChunkData* HashMemoryChunk

Definition at line 159 of file hashjoin.h.

HashMemoryChunkData

typedef struct HashMemoryChunkData HashMemoryChunkData

HashSkewBucket

typedef struct HashSkewBucket HashSkewBucket

ParallelHashGrowth

typedef enum ParallelHashGrowth ParallelHashGrowth

ParallelHashJoinBatch

typedef struct ParallelHashJoinBatch ParallelHashJoinBatch

ParallelHashJoinBatchAccessor

typedef struct ParallelHashJoinBatchAccessor ParallelHashJoinBatchAccessor

ParallelHashJoinState

typedef struct ParallelHashJoinState ParallelHashJoinState

Enumeration Type Documentation

ParallelHashGrowth

enum ParallelHashGrowth

Enumerator
PHJ_GROWTH_OK
PHJ_GROWTH_NEED_MORE_BUCKETS
PHJ_GROWTH_NEED_MORE_BATCHES
PHJ_GROWTH_DISABLED

Definition at line 241 of file hashjoin.h.

{
    /* The current dimensions are sufficient. */
    PHJ_GROWTH_OK,
    /* The load factor is too high, so we need to add buckets. */
    PHJ_GROWTH_NEED_MORE_BUCKETS,
    /* The memory budget would be exhausted, so we need to repartition. */
    PHJ_GROWTH_NEED_MORE_BATCHES,
    /* Repartitioning didn't help last time, so don't try to do that again. */
    PHJ_GROWTH_DISABLED,
} ParallelHashGrowth;