hash.h File Reference

#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "fmgr.h"
#include "lib/stringinfo.h"
#include "storage/bufmgr.h"
#include "storage/lockdefs.h"
#include "utils/hsearch.h"
#include "utils/relcache.h"

Include dependency graph for hash.h:

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

Go to the source code of this file.

Data Structures
struct	HashPageOpaqueData
struct	HashScanPosItem
struct	HashScanPosData
struct	HashScanOpaqueData
struct	HashMetaPageData

Macros
#define	InvalidBucket   ((Bucket) 0xFFFFFFFF)
#define	BUCKET_TO_BLKNO(metap, B)   ((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_spareindex((B)+1)-1] : 0)) + 1)
#define	ROTATE_HIGH_AND_LOW_32BITS(v)
#define	LH_UNUSED_PAGE   (0)
#define	LH_OVERFLOW_PAGE   (1 << 0)
#define	LH_BUCKET_PAGE   (1 << 1)
#define	LH_BITMAP_PAGE   (1 << 2)
#define	LH_META_PAGE   (1 << 3)
#define	LH_BUCKET_BEING_POPULATED   (1 << 4)
#define	LH_BUCKET_BEING_SPLIT   (1 << 5)
#define	LH_BUCKET_NEEDS_SPLIT_CLEANUP   (1 << 6)
#define	LH_PAGE_HAS_DEAD_TUPLES   (1 << 7)
#define	LH_PAGE_TYPE   (LH_OVERFLOW_PAGE | LH_BUCKET_PAGE | LH_BITMAP_PAGE | LH_META_PAGE)
#define	H_NEEDS_SPLIT_CLEANUP(opaque)   (((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)
#define	H_BUCKET_BEING_SPLIT(opaque)   (((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)
#define	H_BUCKET_BEING_POPULATED(opaque)   (((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)
#define	H_HAS_DEAD_TUPLES(opaque)   (((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)
#define	HASHO_PAGE_ID   0xFF80
#define	HashScanPosIsPinned(scanpos)
#define	HashScanPosIsValid(scanpos)
#define	HashScanPosInvalidate(scanpos)
#define	HASH_METAPAGE   0 /* metapage is always block 0 */
#define	HASH_MAGIC   0x6440640
#define	HASH_VERSION   4
#define	HASH_MAX_BITMAPS   1024
#define	HASH_SPLITPOINT_PHASE_BITS   2
#define	HASH_SPLITPOINT_PHASES_PER_GRP   (1 << HASH_SPLITPOINT_PHASE_BITS)
#define	HASH_SPLITPOINT_PHASE_MASK   (HASH_SPLITPOINT_PHASES_PER_GRP - 1)
#define	HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE   10
#define	HASH_MAX_SPLITPOINT_GROUP   32
#define	HASH_MAX_SPLITPOINTS
#define	HashMaxItemSize(page)
#define	INDEX_MOVED_BY_SPLIT_MASK   0x2000
#define	HASH_MIN_FILLFACTOR   10
#define	HASH_DEFAULT_FILLFACTOR   75
#define	BYTE_TO_BIT   3 /* 2^3 bits/byte */
#define	ALL_SET   ((uint32) ~0)
#define	BMPGSZ_BYTE(metap)   ((metap)->hashm_bmsize)
#define	BMPGSZ_BIT(metap)   ((metap)->hashm_bmsize << BYTE_TO_BIT)
#define	BMPG_SHIFT(metap)   ((metap)->hashm_bmshift)
#define	BMPG_MASK(metap)   (BMPGSZ_BIT(metap) - 1)
#define	HashPageGetBitmap(page)   ((uint32 *) PageGetContents(page))
#define	HashGetMaxBitmapSize(page)
#define	HashPageGetMeta(page)   ((HashMetaPage) PageGetContents(page))
#define	BITS_PER_MAP   32 /* Number of bits in uint32 */
#define	CLRBIT(A, N)   ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
#define	SETBIT(A, N)   ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
#define	ISSET(A, N)   ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
#define	HASH_READ   BUFFER_LOCK_SHARE
#define	HASH_WRITE   BUFFER_LOCK_EXCLUSIVE
#define	HASH_NOLOCK   (-1)
#define	HTEqualStrategyNumber   1
#define	HTMaxStrategyNumber   1
#define	HASHSTANDARD_PROC   1
#define	HASHEXTENDED_PROC   2
#define	HASHNProcs   2

Typedefs
typedef uint32	Bucket
typedef struct HashPageOpaqueData	HashPageOpaqueData
typedef HashPageOpaqueData *	HashPageOpaque
typedef struct HashScanPosItem	HashScanPosItem
typedef struct HashScanPosData	HashScanPosData
typedef struct HashScanOpaqueData	HashScanOpaqueData
typedef HashScanOpaqueData *	HashScanOpaque
typedef struct HashMetaPageData	HashMetaPageData
typedef HashMetaPageData *	HashMetaPage
typedef struct HSpool	HSpool

Functions
IndexBuildResult *	hashbuild (Relation heap, Relation index, struct IndexInfo *indexInfo)
void	hashbuildempty (Relation index)
bool	hashinsert (Relation rel, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, struct IndexInfo *indexInfo)
bool	hashgettuple (IndexScanDesc scan, ScanDirection dir)
int64	hashgetbitmap (IndexScanDesc scan, TIDBitmap *tbm)
IndexScanDesc	hashbeginscan (Relation rel, int nkeys, int norderbys)
void	hashrescan (IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
void	hashendscan (IndexScanDesc scan)
IndexBulkDeleteResult *	hashbulkdelete (IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
IndexBulkDeleteResult *	hashvacuumcleanup (IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
bytea *	hashoptions (Datum reloptions, bool validate)
bool	hashvalidate (Oid opclassoid)
Datum	hash_any (register const unsigned char *k, register int keylen)
Datum	hash_any_extended (register const unsigned char *k, register int keylen, uint64 seed)
Datum	hash_uint32 (uint32 k)
Datum	hash_uint32_extended (uint32 k, uint64 seed)
void	_hash_doinsert (Relation rel, IndexTuple itup, Relation heapRel)
OffsetNumber	_hash_pgaddtup (Relation rel, Buffer buf, Size itemsize, IndexTuple itup)
void	_hash_pgaddmultitup (Relation rel, Buffer buf, IndexTuple *itups, OffsetNumber *itup_offsets, uint16 nitups)
Buffer	_hash_addovflpage (Relation rel, Buffer metabuf, Buffer buf, bool retain_pin)
BlockNumber	_hash_freeovflpage (Relation rel, Buffer bucketbuf, Buffer ovflbuf, Buffer wbuf, IndexTuple *itups, OffsetNumber *itup_offsets, Size *tups_size, uint16 nitups, BufferAccessStrategy bstrategy)
void	_hash_initbitmapbuffer (Buffer buf, uint16 bmsize, bool initpage)
void	_hash_squeezebucket (Relation rel, Bucket bucket, BlockNumber bucket_blkno, Buffer bucket_buf, BufferAccessStrategy bstrategy)
uint32	_hash_ovflblkno_to_bitno (HashMetaPage metap, BlockNumber ovflblkno)
Buffer	_hash_getbuf (Relation rel, BlockNumber blkno, int access, int flags)
Buffer	_hash_getbuf_with_condlock_cleanup (Relation rel, BlockNumber blkno, int flags)
HashMetaPage	_hash_getcachedmetap (Relation rel, Buffer *metabuf, bool force_refresh)
Buffer	_hash_getbucketbuf_from_hashkey (Relation rel, uint32 hashkey, int access, HashMetaPage *cachedmetap)
Buffer	_hash_getinitbuf (Relation rel, BlockNumber blkno)
void	_hash_initbuf (Buffer buf, uint32 max_bucket, uint32 num_bucket, uint32 flag, bool initpage)
Buffer	_hash_getnewbuf (Relation rel, BlockNumber blkno, ForkNumber forkNum)
Buffer	_hash_getbuf_with_strategy (Relation rel, BlockNumber blkno, int access, int flags, BufferAccessStrategy bstrategy)
void	_hash_relbuf (Relation rel, Buffer buf)
void	_hash_dropbuf (Relation rel, Buffer buf)
void	_hash_dropscanbuf (Relation rel, HashScanOpaque so)
uint32	_hash_init (Relation rel, double num_tuples, ForkNumber forkNum)
void	_hash_init_metabuffer (Buffer buf, double num_tuples, RegProcedure procid, uint16 ffactor, bool initpage)
void	_hash_pageinit (Page page, Size size)
void	_hash_expandtable (Relation rel, Buffer metabuf)
void	_hash_finish_split (Relation rel, Buffer metabuf, Buffer obuf, Bucket obucket, uint32 maxbucket, uint32 highmask, uint32 lowmask)
bool	_hash_next (IndexScanDesc scan, ScanDirection dir)
bool	_hash_first (IndexScanDesc scan, ScanDirection dir)
HSpool *	_h_spoolinit (Relation heap, Relation index, uint32 num_buckets)
void	_h_spooldestroy (HSpool *hspool)
void	_h_spool (HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
void	_h_indexbuild (HSpool *hspool, Relation heapRel)
bool	_hash_checkqual (IndexScanDesc scan, IndexTuple itup)
uint32	_hash_datum2hashkey (Relation rel, Datum key)
uint32	_hash_datum2hashkey_type (Relation rel, Datum key, Oid keytype)
Bucket	_hash_hashkey2bucket (uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
uint32	_hash_log2 (uint32 num)
uint32	_hash_spareindex (uint32 num_bucket)
uint32	_hash_get_totalbuckets (uint32 splitpoint_phase)
void	_hash_checkpage (Relation rel, Buffer buf, int flags)
uint32	_hash_get_indextuple_hashkey (IndexTuple itup)
bool	_hash_convert_tuple (Relation index, Datum *user_values, bool *user_isnull, Datum *index_values, bool *index_isnull)
OffsetNumber	_hash_binsearch (Page page, uint32 hash_value)
OffsetNumber	_hash_binsearch_last (Page page, uint32 hash_value)
BlockNumber	_hash_get_oldblock_from_newbucket (Relation rel, Bucket new_bucket)
BlockNumber	_hash_get_newblock_from_oldbucket (Relation rel, Bucket old_bucket)
Bucket	_hash_get_newbucket_from_oldbucket (Relation rel, Bucket old_bucket, uint32 lowmask, uint32 maxbucket)
void	_hash_kill_items (IndexScanDesc scan)
void	hashbucketcleanup (Relation rel, Bucket cur_bucket, Buffer bucket_buf, BlockNumber bucket_blkno, BufferAccessStrategy bstrategy, uint32 maxbucket, uint32 highmask, uint32 lowmask, double *tuples_removed, double *num_index_tuples, bool bucket_has_garbage, IndexBulkDeleteCallback callback, void *callback_state)

Macro Definition Documentation

#define ALL_SET   ((uint32) ~0)

Definition at line 292 of file hash.h.

Referenced by _hash_addovflpage().

#define BITS_PER_MAP   32 /* Number of bits in uint32 */

Definition at line 319 of file hash.h.

Referenced by _hash_addovflpage(), and _hash_firstfreebit().

#define BMPG_MASK

(

metap

)

(BMPGSZ_BIT(metap) - 1)

Definition at line 304 of file hash.h.

Referenced by _hash_addovflpage(), _hash_freeovflpage(), _hash_init_metabuffer(), and hash_bitmap_info().

#define BMPG_SHIFT

(

metap

)

((metap)->hashm_bmshift)

Definition at line 303 of file hash.h.

Referenced by _hash_addovflpage(), _hash_freeovflpage(), _hash_init_metabuffer(), and hash_bitmap_info().

#define BMPGSZ_BIT

(

metap

)

((metap)->hashm_bmsize << BYTE_TO_BIT)

Definition at line 302 of file hash.h.

Referenced by _hash_addovflpage().

#define BMPGSZ_BYTE

(

metap

)

((metap)->hashm_bmsize)

Definition at line 301 of file hash.h.

#define BUCKET_TO_BLKNO	(		metap,
			B
	)		((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_spareindex((B)+1)-1] : 0)) + 1)

Definition at line 38 of file hash.h.

Referenced by _hash_expandtable(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_init(), and hashbulkdelete().

#define BYTE_TO_BIT   3 /* 2^3 bits/byte */

Definition at line 291 of file hash.h.

Referenced by _hash_init_metabuffer().

#define CLRBIT	(		A,
			N
	)		((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))

Definition at line 322 of file hash.h.

#define H_BUCKET_BEING_POPULATED

(

opaque

)

(((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)

Definition at line 100 of file hash.h.

Referenced by _hash_first().

#define H_BUCKET_BEING_SPLIT

(

opaque

)

(((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)

Definition at line 99 of file hash.h.

Referenced by _hash_doinsert(), _hash_expandtable(), and hashbulkdelete().

#define H_HAS_DEAD_TUPLES

(

opaque

)

(((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)

Definition at line 101 of file hash.h.

Referenced by _hash_doinsert(), and hashbucketcleanup().

#define H_NEEDS_SPLIT_CLEANUP

(

opaque

)

(((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)

Definition at line 98 of file hash.h.

Referenced by _hash_expandtable(), and hashbulkdelete().

#define HASH_DEFAULT_FILLFACTOR   75

Definition at line 286 of file hash.h.

Referenced by _hash_init().

#define HASH_MAGIC   0x6440640

Definition at line 208 of file hash.h.

Referenced by _hash_checkpage(), _hash_init_metabuffer(), and verify_hash_page().

#define HASH_MAX_BITMAPS   1024

Definition at line 235 of file hash.h.

Referenced by _hash_addovflpage(), _hash_init(), and hash_metapage_info().

#define HASH_MAX_SPLITPOINT_GROUP   32

Definition at line 243 of file hash.h.

#define HASH_MAX_SPLITPOINTS

Value:

(((HASH_MAX_SPLITPOINT_GROUP - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) * \
      HASH_SPLITPOINT_PHASES_PER_GRP) + \
	 HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)

Definition at line 244 of file hash.h.

Referenced by _hash_init_metabuffer(), and hash_metapage_info().

#define HASH_METAPAGE   0 /* metapage is always block 0 */

Definition at line 206 of file hash.h.

Referenced by _hash_doinsert(), _hash_freeovflpage(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getcachedmetap(), _hash_init(), hash_bitmap_info(), hashbulkdelete(), pgstat_relation(), and pgstathashindex().

#define HASH_MIN_FILLFACTOR   10

Definition at line 285 of file hash.h.

#define HASH_NOLOCK   (-1)

Definition at line 331 of file hash.h.

Referenced by _hash_doinsert(), _hash_getbuf(), _hash_getbuf_with_strategy(), and hashbulkdelete().

#define HASH_READ   BUFFER_LOCK_SHARE

Definition at line 329 of file hash.h.

Referenced by _hash_finish_split(), _hash_first(), _hash_freeovflpage(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_getcachedmetap(), _hash_kill_items(), _hash_next(), _hash_readnext(), _hash_readprev(), _hash_splitbucket(), hash_bitmap_info(), hash_xlog_vacuum_get_latestRemovedXid(), pgstat_hash_page(), and pgstathashindex().

#define HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE   10

Definition at line 240 of file hash.h.

Referenced by _hash_get_totalbuckets(), and _hash_spareindex().

#define HASH_SPLITPOINT_PHASE_BITS   2

Definition at line 237 of file hash.h.

Referenced by _hash_get_totalbuckets(), and _hash_spareindex().

#define HASH_SPLITPOINT_PHASE_MASK   (HASH_SPLITPOINT_PHASES_PER_GRP - 1)

Definition at line 239 of file hash.h.

Referenced by _hash_get_totalbuckets(), and _hash_spareindex().

#define HASH_SPLITPOINT_PHASES_PER_GRP   (1 << HASH_SPLITPOINT_PHASE_BITS)

Definition at line 238 of file hash.h.

#define HASH_VERSION   4

Definition at line 209 of file hash.h.

Referenced by _hash_checkpage(), _hash_init_metabuffer(), and verify_hash_page().

#define HASH_WRITE   BUFFER_LOCK_EXCLUSIVE

Definition at line 330 of file hash.h.

Referenced by _hash_addovflpage(), _hash_doinsert(), _hash_freeovflpage(), _hash_getbucketbuf_from_hashkey(), _hash_getnewbuf(), _hash_squeezebucket(), and hashbucketcleanup().

#define HASHEXTENDED_PROC   2

Definition at line 352 of file hash.h.

Referenced by assignProcTypes(), check_hash_func_signature(), hashvalidate(), and lookup_type_cache().

#define HashGetMaxBitmapSize

(

page

)

Value:

(PageGetPageSize((Page) page) - \
     (MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(HashPageOpaqueData))))

Definition at line 309 of file hash.h.

Referenced by _hash_init_metabuffer().

#define HashMaxItemSize

(

page

)

Value:

MAXALIGN_DOWN(PageGetPageSize(page) - \
                  SizeOfPageHeaderData - \
                  sizeof(ItemIdData) - \
                  MAXALIGN(sizeof(HashPageOpaqueData)))

Definition at line 277 of file hash.h.

Referenced by _hash_doinsert().

#define HASHNProcs   2

Definition at line 353 of file hash.h.

Referenced by hashhandler().

#define HASHO_PAGE_ID   0xFF80

Definition at line 109 of file hash.h.

Referenced by _hash_addovflpage(), _hash_alloc_buckets(), _hash_expandtable(), _hash_freeovflpage(), _hash_init_metabuffer(), _hash_initbitmapbuffer(), _hash_initbuf(), hash_xlog_squeeze_page(), and verify_hash_page().

#define HashPageGetBitmap

(

page

)

((uint32 *) PageGetContents(page))

Definition at line 306 of file hash.h.

Referenced by _hash_addovflpage(), _hash_freeovflpage(), _hash_initbitmapbuffer(), hash_bitmap_info(), hash_xlog_add_ovfl_page(), and hash_xlog_squeeze_page().

#define HashPageGetMeta

(

page

)

((HashMetaPage) PageGetContents(page))

Definition at line 313 of file hash.h.

Referenced by _hash_addovflpage(), _hash_checkpage(), _hash_doinsert(), _hash_expandtable(), _hash_freeovflpage(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getcachedmetap(), _hash_init(), _hash_init_metabuffer(), _hash_vacuum_one_page(), hash_bitmap_info(), hash_metapage_info(), hash_xlog_add_ovfl_page(), hash_xlog_init_bitmap_page(), hash_xlog_insert(), hash_xlog_split_allocate_page(), hash_xlog_squeeze_page(), hash_xlog_update_meta_page(), hash_xlog_vacuum_one_page(), hashbulkdelete(), pgstathashindex(), and verify_hash_page().

#define HashScanPosInvalidate

(

scanpos

)

Value:

do { \
        (scanpos).buf = InvalidBuffer; \
        (scanpos).currPage = InvalidBlockNumber; \
        (scanpos).nextPage = InvalidBlockNumber; \
        (scanpos).prevPage = InvalidBlockNumber; \
        (scanpos).firstItem = 0; \
        (scanpos).lastItem = 0; \
        (scanpos).itemIndex = 0; \
    } while (0);

Definition at line 152 of file hash.h.

Referenced by _hash_next(), hashbeginscan(), and hashrescan().

#define HashScanPosIsPinned

(

scanpos

)

Value:

( \
	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
                !BufferIsValid((scanpos).buf)), \
	BufferIsValid((scanpos).buf) \
)

Definition at line 138 of file hash.h.

Referenced by _hash_kill_items().

#define HashScanPosIsValid

(

scanpos

)

Value:

( \
	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
                !BufferIsValid((scanpos).buf)), \
	BlockNumberIsValid((scanpos).currPage) \
)

Definition at line 145 of file hash.h.

Referenced by _hash_kill_items(), hashendscan(), hashgettuple(), and hashrescan().

#define HASHSTANDARD_PROC   1

Definition at line 351 of file hash.h.

Referenced by _hash_datum2hashkey(), _hash_datum2hashkey_type(), _hash_init(), assignProcTypes(), check_hash_func_signature(), get_op_hash_functions(), hashvalidate(), and lookup_type_cache().

#define HTEqualStrategyNumber   1

Definition at line 336 of file hash.h.

Referenced by _hash_first(), get_compatible_hash_operators(), get_op_hash_functions(), hashvalidate(), and lookup_type_cache().

#define HTMaxStrategyNumber   1

Definition at line 337 of file hash.h.

Referenced by hashhandler(), and hashvalidate().

#define INDEX_MOVED_BY_SPLIT_MASK   0x2000

Definition at line 283 of file hash.h.

Referenced by _hash_load_qualified_items(), and _hash_splitbucket().

#define InvalidBucket   ((Bucket) 0xFFFFFFFF)

Definition at line 36 of file hash.h.

Referenced by hashbucketcleanup().

#define ISSET	(		A,
			N
	)		((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))

Definition at line 324 of file hash.h.

Referenced by _hash_freeovflpage(), and hash_bitmap_info().

#define LH_BITMAP_PAGE   (1 << 2)

Definition at line 66 of file hash.h.

Referenced by _hash_addovflpage(), _hash_freeovflpage(), _hash_initbitmapbuffer(), hash_bitmap_info(), hash_page_type(), pgstat_hash_page(), pgstathashindex(), and verify_hash_page().

#define LH_BUCKET_BEING_POPULATED   (1 << 4)

Definition at line 68 of file hash.h.

Referenced by _hash_expandtable(), and _hash_splitbucket().

#define LH_BUCKET_BEING_SPLIT   (1 << 5)

Definition at line 69 of file hash.h.

Referenced by _hash_expandtable(), and _hash_splitbucket().

#define LH_BUCKET_NEEDS_SPLIT_CLEANUP   (1 << 6)

Definition at line 70 of file hash.h.

Referenced by _hash_splitbucket(), hash_xlog_split_cleanup(), and hashbucketcleanup().

#define LH_BUCKET_PAGE   (1 << 1)

Definition at line 65 of file hash.h.

Referenced by _hash_addovflpage(), _hash_expandtable(), _hash_finish_split(), _hash_first(), _hash_freeovflpage(), _hash_getbucketbuf_from_hashkey(), _hash_init(), _hash_next(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_readpage(), _hash_readprev(), hash_mask(), hash_page_items(), hash_page_stats(), hash_page_type(), hashbulkdelete(), pgstat_hash_page(), pgstathashindex(), and verify_hash_page().

#define LH_META_PAGE   (1 << 3)

Definition at line 67 of file hash.h.

Referenced by _hash_addovflpage(), _hash_checkpage(), _hash_doinsert(), _hash_expandtable(), _hash_freeovflpage(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getcachedmetap(), _hash_init_metabuffer(), hash_bitmap_info(), hash_metapage_info(), hash_page_type(), hashbulkdelete(), pgstat_hash_page(), pgstathashindex(), and verify_hash_page().

#define LH_OVERFLOW_PAGE   (1 << 0)

Definition at line 64 of file hash.h.

Referenced by _hash_addovflpage(), _hash_doinsert(), _hash_finish_split(), _hash_freeovflpage(), _hash_kill_items(), _hash_next(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_readnext(), _hash_readpage(), _hash_readprev(), _hash_splitbucket(), _hash_squeezebucket(), hash_mask(), hash_page_items(), hash_page_stats(), hash_page_type(), hash_xlog_add_ovfl_page(), hashbucketcleanup(), pgstat_hash_page(), pgstathashindex(), and verify_hash_page().

#define LH_PAGE_HAS_DEAD_TUPLES   (1 << 7)

Definition at line 71 of file hash.h.

Referenced by _hash_kill_items(), _hash_vacuum_one_page(), hash_mask(), hash_xlog_delete(), hash_xlog_vacuum_one_page(), and hashbucketcleanup().

#define LH_PAGE_TYPE   (LH_OVERFLOW_PAGE | LH_BUCKET_PAGE | LH_BITMAP_PAGE | LH_META_PAGE)

Definition at line 73 of file hash.h.

Referenced by _hash_addovflpage(), _hash_doinsert(), hash_mask(), hash_page_type(), pgstat_hash_page(), pgstathashindex(), and verify_hash_page().

#define LH_UNUSED_PAGE   (0)

Definition at line 63 of file hash.h.

Referenced by _hash_alloc_buckets(), _hash_freeovflpage(), hash_mask(), hash_xlog_squeeze_page(), pgstat_hash_page(), pgstathashindex(), and verify_hash_page().

#define ROTATE_HIGH_AND_LOW_32BITS

(

v

)

Value:

((((v) << 1) & UINT64CONST(0xfffffffefffffffe)) | \
    (((v) >> 31) & UINT64CONST(0x100000001)))

Definition at line 48 of file hash.h.

Referenced by hash_range_extended(), and JsonbHashScalarValueExtended().

#define SETBIT	(		A,
			N
	)		((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))

Definition at line 323 of file hash.h.

Typedef Documentation

typedef uint32 Bucket

Definition at line 34 of file hash.h.

typedef HashMetaPageData* HashMetaPage

Definition at line 272 of file hash.h.

typedef struct HashMetaPageData HashMetaPageData

typedef HashPageOpaqueData* HashPageOpaque

Definition at line 96 of file hash.h.

typedef struct HashPageOpaqueData HashPageOpaqueData

typedef HashScanOpaqueData* HashScanOpaque

Definition at line 200 of file hash.h.

typedef struct HashScanOpaqueData HashScanOpaqueData

typedef struct HashScanPosData HashScanPosData

typedef struct HashScanPosItem HashScanPosItem

typedef struct HSpool HSpool

Definition at line 443 of file hash.h.

Function Documentation

void _h_indexbuild	(	HSpool *	hspool,
		Relation	heapRel
	)

Definition at line 115 of file hashsort.c.

References _hash_doinsert(), _hash_get_indextuple_hashkey(), _hash_hashkey2bucket(), Assert, HSpool::high_mask, HSpool::index, HSpool::low_mask, HSpool::max_buckets, HSpool::sortstate, tuplesort_getindextuple(), and tuplesort_performsort().

Referenced by hashbuild().

{
    IndexTuple  itup;
#ifdef USE_ASSERT_CHECKING
    uint32      hashkey = 0;
#endif

    tuplesort_performsort(hspool->sortstate);

    while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
    {
        /*
         * Technically, it isn't critical that hash keys be found in sorted
         * order, since this sorting is only used to increase locality of
         * access as a performance optimization.  It still seems like a good
         * idea to test tuplesort.c's handling of hash index tuple sorts
         * through an assertion, though.
         */
#ifdef USE_ASSERT_CHECKING
        uint32      lasthashkey = hashkey;

        hashkey = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
                                       hspool->max_buckets, hspool->high_mask,
                                       hspool->low_mask);
        Assert(hashkey >= lasthashkey);
#endif

        _hash_doinsert(hspool->index, itup, heapRel);
    }
}

void _h_spool	(	HSpool *	hspool,
		ItemPointer	self,
		Datum *	values,
		bool *	isnull
	)

Definition at line 104 of file hashsort.c.

References HSpool::index, HSpool::sortstate, and tuplesort_putindextuplevalues().

Referenced by hashbuildCallback().

{
    tuplesort_putindextuplevalues(hspool->sortstate, hspool->index,
                                  self, values, isnull);
}

void _h_spooldestroy

(

HSpool *

hspool

)

Definition at line 94 of file hashsort.c.

References pfree(), HSpool::sortstate, and tuplesort_end().

Referenced by hashbuild().

{
    tuplesort_end(hspool->sortstate);
    pfree(hspool);
}

HSpool* _h_spoolinit	(	Relation	heap,
		Relation	index,
		uint32	num_buckets
	)

Definition at line 56 of file hashsort.c.

References _hash_log2(), HSpool::high_mask, HSpool::index, HSpool::low_mask, maintenance_work_mem, HSpool::max_buckets, palloc0(), HSpool::sortstate, and tuplesort_begin_index_hash().

Referenced by hashbuild().

{
    HSpool     *hspool = (HSpool *) palloc0(sizeof(HSpool));

    hspool->index = index;

    /*
     * Determine the bitmask for hash code values.  Since there are currently
     * num_buckets buckets in the index, the appropriate mask can be computed
     * as follows.
     *
     * NOTE : This hash mask calculation should be in sync with similar
     * calculation in _hash_init_metabuffer.
     */
    hspool->high_mask = (((uint32) 1) << _hash_log2(num_buckets + 1)) - 1;
    hspool->low_mask = (hspool->high_mask >> 1);
    hspool->max_buckets = num_buckets - 1;

    /*
     * We size the sort area as maintenance_work_mem rather than work_mem to
     * speed index creation.  This should be OK since a single backend can't
     * run multiple index creations in parallel.
     */
    hspool->sortstate = tuplesort_begin_index_hash(heap,
                                                   index,
                                                   hspool->high_mask,
                                                   hspool->low_mask,
                                                   hspool->max_buckets,
                                                   maintenance_work_mem,
                                                   false);

    return hspool;
}

Buffer _hash_addovflpage	(	Relation	rel,
		Buffer	metabuf,
		Buffer	buf,
		bool	retain_pin
	)

Definition at line 111 of file hashovfl.c.

References _hash_checkpage(), _hash_firstfreebit(), _hash_getbuf(), _hash_getinitbuf(), _hash_getnewbuf(), _hash_initbitmapbuffer(), _hash_relbuf(), ALL_SET, Assert, bit(), bitno_to_blkno(), BITS_PER_MAP, BlockNumberIsValid, xl_hash_add_ovfl_page::bmpage_found, BMPG_MASK, BMPG_SHIFT, BMPGSZ_BIT, xl_hash_add_ovfl_page::bmsize, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, BufferIsValid, END_CRIT_SECTION, ereport, errcode(), errmsg(), ERROR, HASH_MAX_BITMAPS, HASH_WRITE, HashMetaPageData::hashm_bmsize, HashMetaPageData::hashm_firstfree, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_nmaps, HashMetaPageData::hashm_ovflpoint, HashMetaPageData::hashm_spares, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, HashPageGetBitmap, HashPageGetMeta, i, InvalidBlockNumber, InvalidBuffer, LH_BITMAP_PAGE, LH_BUCKET_PAGE, LH_META_PAGE, LH_OVERFLOW_PAGE, LH_PAGE_TYPE, LockBuffer(), MAIN_FORKNUM, MarkBufferDirty(), PageGetSpecialPointer, PageSetLSN, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationGetRelationName, RelationNeedsWAL, SETBIT, SizeOfHashAddOvflPage, START_CRIT_SECTION, XLOG_HASH_ADD_OVFL_PAGE, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _hash_doinsert(), and _hash_splitbucket().

{
    Buffer      ovflbuf;
    Page        page;
    Page        ovflpage;
    HashPageOpaque pageopaque;
    HashPageOpaque ovflopaque;
    HashMetaPage metap;
    Buffer      mapbuf = InvalidBuffer;
    Buffer      newmapbuf = InvalidBuffer;
    BlockNumber blkno;
    uint32      orig_firstfree;
    uint32      splitnum;
    uint32     *freep = NULL;
    uint32      max_ovflpg;
    uint32      bit;
    uint32      bitmap_page_bit;
    uint32      first_page;
    uint32      last_bit;
    uint32      last_page;
    uint32      i,
                j;
    bool        page_found = false;

    /*
     * Write-lock the tail page.  Here, we need to maintain locking order such
     * that, first acquire the lock on tail page of bucket, then on meta page
     * to find and lock the bitmap page and if it is found, then lock on meta
     * page is released, then finally acquire the lock on new overflow buffer.
     * We need this locking order to avoid deadlock with backends that are
     * doing inserts.
     *
     * Note: We could have avoided locking many buffers here if we made two
     * WAL records for acquiring an overflow page (one to allocate an overflow
     * page and another to add it to overflow bucket chain).  However, doing
     * so can leak an overflow page, if the system crashes after allocation.
     * Needless to say, it is better to have a single record from a
     * performance point of view as well.
     */
    LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);

    /* probably redundant... */
    _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);

    /* loop to find current tail page, in case someone else inserted too */
    for (;;)
    {
        BlockNumber nextblkno;

        page = BufferGetPage(buf);
        pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
        nextblkno = pageopaque->hasho_nextblkno;

        if (!BlockNumberIsValid(nextblkno))
            break;

        /* we assume we do not need to write the unmodified page */
        if (retain_pin)
        {
            /* pin will be retained only for the primary bucket page */
            Assert((pageopaque->hasho_flag & LH_PAGE_TYPE) == LH_BUCKET_PAGE);
            LockBuffer(buf, BUFFER_LOCK_UNLOCK);
        }
        else
            _hash_relbuf(rel, buf);

        retain_pin = false;

        buf = _hash_getbuf(rel, nextblkno, HASH_WRITE, LH_OVERFLOW_PAGE);
    }

    /* Get exclusive lock on the meta page */
    LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);

    _hash_checkpage(rel, metabuf, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));

    /* start search at hashm_firstfree */
    orig_firstfree = metap->hashm_firstfree;
    first_page = orig_firstfree >> BMPG_SHIFT(metap);
    bit = orig_firstfree & BMPG_MASK(metap);
    i = first_page;
    j = bit / BITS_PER_MAP;
    bit &= ~(BITS_PER_MAP - 1);

    /* outer loop iterates once per bitmap page */
    for (;;)
    {
        BlockNumber mapblkno;
        Page        mappage;
        uint32      last_inpage;

        /* want to end search with the last existing overflow page */
        splitnum = metap->hashm_ovflpoint;
        max_ovflpg = metap->hashm_spares[splitnum] - 1;
        last_page = max_ovflpg >> BMPG_SHIFT(metap);
        last_bit = max_ovflpg & BMPG_MASK(metap);

        if (i > last_page)
            break;

        Assert(i < metap->hashm_nmaps);
        mapblkno = metap->hashm_mapp[i];

        if (i == last_page)
            last_inpage = last_bit;
        else
            last_inpage = BMPGSZ_BIT(metap) - 1;

        /* Release exclusive lock on metapage while reading bitmap page */
        LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

        mapbuf = _hash_getbuf(rel, mapblkno, HASH_WRITE, LH_BITMAP_PAGE);
        mappage = BufferGetPage(mapbuf);
        freep = HashPageGetBitmap(mappage);

        for (; bit <= last_inpage; j++, bit += BITS_PER_MAP)
        {
            if (freep[j] != ALL_SET)
            {
                page_found = true;

                /* Reacquire exclusive lock on the meta page */
                LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);

                /* convert bit to bit number within page */
                bit += _hash_firstfreebit(freep[j]);
                bitmap_page_bit = bit;

                /* convert bit to absolute bit number */
                bit += (i << BMPG_SHIFT(metap));
                /* Calculate address of the recycled overflow page */
                blkno = bitno_to_blkno(metap, bit);

                /* Fetch and init the recycled page */
                ovflbuf = _hash_getinitbuf(rel, blkno);

                goto found;
            }
        }

        /* No free space here, try to advance to next map page */
        _hash_relbuf(rel, mapbuf);
        mapbuf = InvalidBuffer;
        i++;
        j = 0;                  /* scan from start of next map page */
        bit = 0;

        /* Reacquire exclusive lock on the meta page */
        LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
    }

    /*
     * No free pages --- have to extend the relation to add an overflow page.
     * First, check to see if we have to add a new bitmap page too.
     */
    if (last_bit == (uint32) (BMPGSZ_BIT(metap) - 1))
    {
        /*
         * We create the new bitmap page with all pages marked "in use".
         * Actually two pages in the new bitmap's range will exist
         * immediately: the bitmap page itself, and the following page which
         * is the one we return to the caller.  Both of these are correctly
         * marked "in use".  Subsequent pages do not exist yet, but it is
         * convenient to pre-mark them as "in use" too.
         */
        bit = metap->hashm_spares[splitnum];

        /* metapage already has a write lock */
        if (metap->hashm_nmaps >= HASH_MAX_BITMAPS)
            ereport(ERROR,
                    (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                     errmsg("out of overflow pages in hash index \"%s\"",
                            RelationGetRelationName(rel))));

        newmapbuf = _hash_getnewbuf(rel, bitno_to_blkno(metap, bit), MAIN_FORKNUM);
    }
    else
    {
        /*
         * Nothing to do here; since the page will be past the last used page,
         * we know its bitmap bit was preinitialized to "in use".
         */
    }

    /* Calculate address of the new overflow page */
    bit = BufferIsValid(newmapbuf) ?
        metap->hashm_spares[splitnum] + 1 : metap->hashm_spares[splitnum];
    blkno = bitno_to_blkno(metap, bit);

    /*
     * Fetch the page with _hash_getnewbuf to ensure smgr's idea of the
     * relation length stays in sync with ours.  XXX It's annoying to do this
     * with metapage write lock held; would be better to use a lock that
     * doesn't block incoming searches.
     *
     * It is okay to hold two buffer locks here (one on tail page of bucket
     * and other on new overflow page) since there cannot be anyone else
     * contending for access to ovflbuf.
     */
    ovflbuf = _hash_getnewbuf(rel, blkno, MAIN_FORKNUM);

found:

    /*
     * Do the update.  No ereport(ERROR) until changes are logged. We want to
     * log the changes for bitmap page and overflow page together to avoid
     * loss of pages in case the new page is added.
     */
    START_CRIT_SECTION();

    if (page_found)
    {
        Assert(BufferIsValid(mapbuf));

        /* mark page "in use" in the bitmap */
        SETBIT(freep, bitmap_page_bit);
        MarkBufferDirty(mapbuf);
    }
    else
    {
        /* update the count to indicate new overflow page is added */
        metap->hashm_spares[splitnum]++;

        if (BufferIsValid(newmapbuf))
        {
            _hash_initbitmapbuffer(newmapbuf, metap->hashm_bmsize, false);
            MarkBufferDirty(newmapbuf);

            /* add the new bitmap page to the metapage's list of bitmaps */
            metap->hashm_mapp[metap->hashm_nmaps] = BufferGetBlockNumber(newmapbuf);
            metap->hashm_nmaps++;
            metap->hashm_spares[splitnum]++;
            MarkBufferDirty(metabuf);
        }

        /*
         * for new overflow page, we don't need to explicitly set the bit in
         * bitmap page, as by default that will be set to "in use".
         */
    }

    /*
     * Adjust hashm_firstfree to avoid redundant searches.  But don't risk
     * changing it if someone moved it while we were searching bitmap pages.
     */
    if (metap->hashm_firstfree == orig_firstfree)
    {
        metap->hashm_firstfree = bit + 1;
        MarkBufferDirty(metabuf);
    }

    /* initialize new overflow page */
    ovflpage = BufferGetPage(ovflbuf);
    ovflopaque = (HashPageOpaque) PageGetSpecialPointer(ovflpage);
    ovflopaque->hasho_prevblkno = BufferGetBlockNumber(buf);
    ovflopaque->hasho_nextblkno = InvalidBlockNumber;
    ovflopaque->hasho_bucket = pageopaque->hasho_bucket;
    ovflopaque->hasho_flag = LH_OVERFLOW_PAGE;
    ovflopaque->hasho_page_id = HASHO_PAGE_ID;

    MarkBufferDirty(ovflbuf);

    /* logically chain overflow page to previous page */
    pageopaque->hasho_nextblkno = BufferGetBlockNumber(ovflbuf);

    MarkBufferDirty(buf);

    /* XLOG stuff */
    if (RelationNeedsWAL(rel))
    {
        XLogRecPtr  recptr;
        xl_hash_add_ovfl_page xlrec;

        xlrec.bmpage_found = page_found;
        xlrec.bmsize = metap->hashm_bmsize;

        XLogBeginInsert();
        XLogRegisterData((char *) &xlrec, SizeOfHashAddOvflPage);

        XLogRegisterBuffer(0, ovflbuf, REGBUF_WILL_INIT);
        XLogRegisterBufData(0, (char *) &pageopaque->hasho_bucket, sizeof(Bucket));

        XLogRegisterBuffer(1, buf, REGBUF_STANDARD);

        if (BufferIsValid(mapbuf))
        {
            XLogRegisterBuffer(2, mapbuf, REGBUF_STANDARD);
            XLogRegisterBufData(2, (char *) &bitmap_page_bit, sizeof(uint32));
        }

        if (BufferIsValid(newmapbuf))
            XLogRegisterBuffer(3, newmapbuf, REGBUF_WILL_INIT);

        XLogRegisterBuffer(4, metabuf, REGBUF_STANDARD);
        XLogRegisterBufData(4, (char *) &metap->hashm_firstfree, sizeof(uint32));

        recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_ADD_OVFL_PAGE);

        PageSetLSN(BufferGetPage(ovflbuf), recptr);
        PageSetLSN(BufferGetPage(buf), recptr);

        if (BufferIsValid(mapbuf))
            PageSetLSN(BufferGetPage(mapbuf), recptr);

        if (BufferIsValid(newmapbuf))
            PageSetLSN(BufferGetPage(newmapbuf), recptr);

        PageSetLSN(BufferGetPage(metabuf), recptr);
    }

    END_CRIT_SECTION();

    if (retain_pin)
        LockBuffer(buf, BUFFER_LOCK_UNLOCK);
    else
        _hash_relbuf(rel, buf);

    if (BufferIsValid(mapbuf))
        _hash_relbuf(rel, mapbuf);

    LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

    if (BufferIsValid(newmapbuf))
        _hash_relbuf(rel, newmapbuf);

    return ovflbuf;
}

OffsetNumber _hash_binsearch	(	Page	page,
		uint32	hash_value
	)

Definition at line 358 of file hashutil.c.

References _hash_get_indextuple_hashkey(), Assert, FirstOffsetNumber, lower(), OffsetNumberIsValid, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and upper().

Referenced by _hash_pgaddmultitup(), _hash_pgaddtup(), and _hash_readpage().

{
    OffsetNumber upper;
    OffsetNumber lower;

    /* Loop invariant: lower <= desired place <= upper */
    upper = PageGetMaxOffsetNumber(page) + 1;
    lower = FirstOffsetNumber;

    while (upper > lower)
    {
        OffsetNumber off;
        IndexTuple  itup;
        uint32      hashkey;

        off = (upper + lower) / 2;
        Assert(OffsetNumberIsValid(off));

        itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
        hashkey = _hash_get_indextuple_hashkey(itup);
        if (hashkey < hash_value)
            lower = off + 1;
        else
            upper = off;
    }

    return lower;
}

OffsetNumber _hash_binsearch_last	(	Page	page,
		uint32	hash_value
	)

Definition at line 396 of file hashutil.c.

References _hash_get_indextuple_hashkey(), Assert, FirstOffsetNumber, lower(), OffsetNumberIsValid, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and upper().

Referenced by _hash_readpage().

{
    OffsetNumber upper;
    OffsetNumber lower;

    /* Loop invariant: lower <= desired place <= upper */
    upper = PageGetMaxOffsetNumber(page);
    lower = FirstOffsetNumber - 1;

    while (upper > lower)
    {
        IndexTuple  itup;
        OffsetNumber off;
        uint32      hashkey;

        off = (upper + lower + 1) / 2;
        Assert(OffsetNumberIsValid(off));

        itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
        hashkey = _hash_get_indextuple_hashkey(itup);
        if (hashkey > hash_value)
            upper = off - 1;
        else
            lower = off;
    }

    return lower;
}

void _hash_checkpage	(	Relation	rel,
		Buffer	buf,
		int	flags
	)

Definition at line 225 of file hashutil.c.

References BufferGetBlockNumber(), BufferGetPage, ereport, errcode(), errhint(), errmsg(), ERROR, HASH_MAGIC, HASH_VERSION, HashMetaPageData::hashm_magic, HashMetaPageData::hashm_version, HashPageOpaqueData::hasho_flag, HashPageGetMeta, LH_META_PAGE, MAXALIGN, PageGetSpecialPointer, PageGetSpecialSize, PageIsNew, and RelationGetRelationName.

Referenced by _hash_addovflpage(), _hash_expandtable(), _hash_freeovflpage(), _hash_getbuf(), _hash_getbuf_with_condlock_cleanup(), _hash_getbuf_with_strategy(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_readpage(), and hashbulkdelete().

{
    Page        page = BufferGetPage(buf);

    /*
     * ReadBuffer verifies that every newly-read page passes
     * PageHeaderIsValid, which means it either contains a reasonably sane
     * page header or is all-zero.  We have to defend against the all-zero
     * case, however.
     */
    if (PageIsNew(page))
        ereport(ERROR,
                (errcode(ERRCODE_INDEX_CORRUPTED),
                 errmsg("index \"%s\" contains unexpected zero page at block %u",
                        RelationGetRelationName(rel),
                        BufferGetBlockNumber(buf)),
                 errhint("Please REINDEX it.")));

    /*
     * Additionally check that the special area looks sane.
     */
    if (PageGetSpecialSize(page) != MAXALIGN(sizeof(HashPageOpaqueData)))
        ereport(ERROR,
                (errcode(ERRCODE_INDEX_CORRUPTED),
                 errmsg("index \"%s\" contains corrupted page at block %u",
                        RelationGetRelationName(rel),
                        BufferGetBlockNumber(buf)),
                 errhint("Please REINDEX it.")));

    if (flags)
    {
        HashPageOpaque opaque = (HashPageOpaque) PageGetSpecialPointer(page);

        if ((opaque->hasho_flag & flags) == 0)
            ereport(ERROR,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg("index \"%s\" contains corrupted page at block %u",
                            RelationGetRelationName(rel),
                            BufferGetBlockNumber(buf)),
                     errhint("Please REINDEX it.")));
    }

    /*
     * When checking the metapage, also verify magic number and version.
     */
    if (flags == LH_META_PAGE)
    {
        HashMetaPage metap = HashPageGetMeta(page);

        if (metap->hashm_magic != HASH_MAGIC)
            ereport(ERROR,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg("index \"%s\" is not a hash index",
                            RelationGetRelationName(rel))));

        if (metap->hashm_version != HASH_VERSION)
            ereport(ERROR,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg("index \"%s\" has wrong hash version",
                            RelationGetRelationName(rel)),
                     errhint("Please REINDEX it.")));
    }
}

bool _hash_checkqual	(	IndexScanDesc	scan,
		IndexTuple	itup
	)

Definition at line 31 of file hashutil.c.

References DatumGetBool, FunctionCall2Coll(), index_getattr, IndexScanDescData::indexRelation, IndexScanDescData::keyData, IndexScanDescData::numberOfKeys, RelationGetDescr, ScanKeyData::sk_argument, ScanKeyData::sk_attno, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, SK_ISNULL, and test().

Referenced by _hash_load_qualified_items().

{
    /*
     * Currently, we can't check any of the scan conditions since we do not
     * have the original index entry value to supply to the sk_func. Always
     * return true; we expect that hashgettuple already set the recheck flag
     * to make the main indexscan code do it.
     */
#ifdef NOT_USED
    TupleDesc   tupdesc = RelationGetDescr(scan->indexRelation);
    ScanKey     key = scan->keyData;
    int         scanKeySize = scan->numberOfKeys;

    while (scanKeySize > 0)
    {
        Datum       datum;
        bool        isNull;
        Datum       test;

        datum = index_getattr(itup,
                              key->sk_attno,
                              tupdesc,
                              &isNull);

        /* assume sk_func is strict */
        if (isNull)
            return false;
        if (key->sk_flags & SK_ISNULL)
            return false;

        test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
                                 datum, key->sk_argument);

        if (!DatumGetBool(test))
            return false;

        key++;
        scanKeySize--;
    }
#endif

    return true;
}

bool _hash_convert_tuple	(	Relation	index,
		Datum *	user_values,
		bool *	user_isnull,
		Datum *	index_values,
		bool *	index_isnull
	)

Definition at line 326 of file hashutil.c.

References _hash_datum2hashkey(), and UInt32GetDatum.

Referenced by hashbuildCallback(), and hashinsert().

{
    uint32      hashkey;

    /*
     * We do not insert null values into hash indexes.  This is okay because
     * the only supported search operator is '=', and we assume it is strict.
     */
    if (user_isnull[0])
        return false;

    hashkey = _hash_datum2hashkey(index, user_values[0]);
    index_values[0] = UInt32GetDatum(hashkey);
    index_isnull[0] = false;
    return true;
}

uint32 _hash_datum2hashkey	(	Relation	rel,
		Datum	key
	)

Definition at line 82 of file hashutil.c.

References DatumGetUInt32, FunctionCall1Coll(), HASHSTANDARD_PROC, index_getprocinfo(), and RelationData::rd_indcollation.

Referenced by _hash_convert_tuple(), and _hash_first().

{
    FmgrInfo   *procinfo;
    Oid         collation;

    /* XXX assumes index has only one attribute */
    procinfo = index_getprocinfo(rel, 1, HASHSTANDARD_PROC);
    collation = rel->rd_indcollation[0];

    return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
}

uint32 _hash_datum2hashkey_type	(	Relation	rel,
		Datum	key,
		Oid	keytype
	)

Definition at line 102 of file hashutil.c.

References DatumGetUInt32, elog, ERROR, get_opfamily_proc(), HASHSTANDARD_PROC, OidFunctionCall1Coll(), RelationData::rd_indcollation, RelationData::rd_opfamily, RegProcedureIsValid, and RelationGetRelationName.

Referenced by _hash_first().

{
    RegProcedure hash_proc;
    Oid         collation;

    /* XXX assumes index has only one attribute */
    hash_proc = get_opfamily_proc(rel->rd_opfamily[0],
                                  keytype,
                                  keytype,
                                  HASHSTANDARD_PROC);
    if (!RegProcedureIsValid(hash_proc))
        elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
             HASHSTANDARD_PROC, keytype, keytype,
             RelationGetRelationName(rel));
    collation = rel->rd_indcollation[0];

    return DatumGetUInt32(OidFunctionCall1Coll(hash_proc, collation, key));
}

void _hash_doinsert	(	Relation	rel,
		IndexTuple	itup,
		Relation	heapRel
	)

Definition at line 36 of file hashinsert.c.

References _hash_addovflpage(), _hash_dropbuf(), _hash_expandtable(), _hash_finish_split(), _hash_get_indextuple_hashkey(), _hash_getbucketbuf_from_hashkey(), _hash_getbuf(), _hash_pgaddtup(), _hash_relbuf(), _hash_vacuum_one_page(), Assert, BlockNumberIsValid, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, END_CRIT_SECTION, ereport, errcode(), errhint(), errmsg(), ERROR, H_BUCKET_BEING_SPLIT, H_HAS_DEAD_TUPLES, HASH_METAPAGE, HASH_NOLOCK, HASH_WRITE, HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_ntuples, HashMaxItemSize, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageGetMeta, IndexTupleDSize, InvalidBuffer, IsBufferCleanupOK(), LH_META_PAGE, LH_OVERFLOW_PAGE, LH_PAGE_TYPE, LockBuffer(), MarkBufferDirty(), MAXALIGN, xl_hash_insert::offnum, PageGetFreeSpace(), PageGetSpecialPointer, PageSetLSN, RelationData::rd_node, REGBUF_STANDARD, RelationNeedsWAL, SizeOfHashInsert, START_CRIT_SECTION, XLOG_HASH_INSERT, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _h_indexbuild(), hashbuildCallback(), and hashinsert().

{
    Buffer      buf = InvalidBuffer;
    Buffer      bucket_buf;
    Buffer      metabuf;
    HashMetaPage metap;
    HashMetaPage usedmetap = NULL;
    Page        metapage;
    Page        page;
    HashPageOpaque pageopaque;
    Size        itemsz;
    bool        do_expand;
    uint32      hashkey;
    Bucket      bucket;
    OffsetNumber itup_off;

    /*
     * Get the hash key for the item (it's stored in the index tuple itself).
     */
    hashkey = _hash_get_indextuple_hashkey(itup);

    /* compute item size too */
    itemsz = IndexTupleDSize(*itup);
    itemsz = MAXALIGN(itemsz);  /* be safe, PageAddItem will do this but we
                                 * need to be consistent */

restart_insert:

    /*
     * Read the metapage.  We don't lock it yet; HashMaxItemSize() will
     * examine pd_pagesize_version, but that can't change so we can examine it
     * without a lock.
     */
    metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK, LH_META_PAGE);
    metapage = BufferGetPage(metabuf);

    /*
     * Check whether the item can fit on a hash page at all. (Eventually, we
     * ought to try to apply TOAST methods if not.)  Note that at this point,
     * itemsz doesn't include the ItemId.
     *
     * XXX this is useless code if we are only storing hash keys.
     */
    if (itemsz > HashMaxItemSize(metapage))
        ereport(ERROR,
                (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                 errmsg("index row size %zu exceeds hash maximum %zu",
                        itemsz, HashMaxItemSize(metapage)),
                 errhint("Values larger than a buffer page cannot be indexed.")));

    /* Lock the primary bucket page for the target bucket. */
    buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_WRITE,
                                          &usedmetap);
    Assert(usedmetap != NULL);

    /* remember the primary bucket buffer to release the pin on it at end. */
    bucket_buf = buf;

    page = BufferGetPage(buf);
    pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
    bucket = pageopaque->hasho_bucket;

    /*
     * If this bucket is in the process of being split, try to finish the
     * split before inserting, because that might create room for the
     * insertion to proceed without allocating an additional overflow page.
     * It's only interesting to finish the split if we're trying to insert
     * into the bucket from which we're removing tuples (the "old" bucket),
     * not if we're trying to insert into the bucket into which tuples are
     * being moved (the "new" bucket).
     */
    if (H_BUCKET_BEING_SPLIT(pageopaque) && IsBufferCleanupOK(buf))
    {
        /* release the lock on bucket buffer, before completing the split. */
        LockBuffer(buf, BUFFER_LOCK_UNLOCK);

        _hash_finish_split(rel, metabuf, buf, bucket,
                           usedmetap->hashm_maxbucket,
                           usedmetap->hashm_highmask,
                           usedmetap->hashm_lowmask);

        /* release the pin on old and meta buffer.  retry for insert. */
        _hash_dropbuf(rel, buf);
        _hash_dropbuf(rel, metabuf);
        goto restart_insert;
    }

    /* Do the insertion */
    while (PageGetFreeSpace(page) < itemsz)
    {
        BlockNumber nextblkno;

        /*
         * Check if current page has any DEAD tuples. If yes, delete these
         * tuples and see if we can get a space for the new item to be
         * inserted before moving to the next page in the bucket chain.
         */
        if (H_HAS_DEAD_TUPLES(pageopaque))
        {

            if (IsBufferCleanupOK(buf))
            {
                _hash_vacuum_one_page(rel, metabuf, buf, heapRel->rd_node);

                if (PageGetFreeSpace(page) >= itemsz)
                    break;      /* OK, now we have enough space */
            }
        }

        /*
         * no space on this page; check for an overflow page
         */
        nextblkno = pageopaque->hasho_nextblkno;

        if (BlockNumberIsValid(nextblkno))
        {
            /*
             * ovfl page exists; go get it.  if it doesn't have room, we'll
             * find out next pass through the loop test above.  we always
             * release both the lock and pin if this is an overflow page, but
             * only the lock if this is the primary bucket page, since the pin
             * on the primary bucket must be retained throughout the scan.
             */
            if (buf != bucket_buf)
                _hash_relbuf(rel, buf);
            else
                LockBuffer(buf, BUFFER_LOCK_UNLOCK);
            buf = _hash_getbuf(rel, nextblkno, HASH_WRITE, LH_OVERFLOW_PAGE);
            page = BufferGetPage(buf);
        }
        else
        {
            /*
             * we're at the end of the bucket chain and we haven't found a
             * page with enough room.  allocate a new overflow page.
             */

            /* release our write lock without modifying buffer */
            LockBuffer(buf, BUFFER_LOCK_UNLOCK);

            /* chain to a new overflow page */
            buf = _hash_addovflpage(rel, metabuf, buf, (buf == bucket_buf) ? true : false);
            page = BufferGetPage(buf);

            /* should fit now, given test above */
            Assert(PageGetFreeSpace(page) >= itemsz);
        }
        pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
        Assert((pageopaque->hasho_flag & LH_PAGE_TYPE) == LH_OVERFLOW_PAGE);
        Assert(pageopaque->hasho_bucket == bucket);
    }

    /*
     * Write-lock the metapage so we can increment the tuple count. After
     * incrementing it, check to see if it's time for a split.
     */
    LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);

    /* Do the update.  No ereport(ERROR) until changes are logged */
    START_CRIT_SECTION();

    /* found page with enough space, so add the item here */
    itup_off = _hash_pgaddtup(rel, buf, itemsz, itup);
    MarkBufferDirty(buf);

    /* metapage operations */
    metap = HashPageGetMeta(metapage);
    metap->hashm_ntuples += 1;

    /* Make sure this stays in sync with _hash_expandtable() */
    do_expand = metap->hashm_ntuples >
        (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);

    MarkBufferDirty(metabuf);

    /* XLOG stuff */
    if (RelationNeedsWAL(rel))
    {
        xl_hash_insert xlrec;
        XLogRecPtr  recptr;

        xlrec.offnum = itup_off;

        XLogBeginInsert();
        XLogRegisterData((char *) &xlrec, SizeOfHashInsert);

        XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);

        XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
        XLogRegisterBufData(0, (char *) itup, IndexTupleDSize(*itup));

        recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_INSERT);

        PageSetLSN(BufferGetPage(buf), recptr);
        PageSetLSN(BufferGetPage(metabuf), recptr);
    }

    END_CRIT_SECTION();

    /* drop lock on metapage, but keep pin */
    LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

    /*
     * Release the modified page and ensure to release the pin on primary
     * page.
     */
    _hash_relbuf(rel, buf);
    if (buf != bucket_buf)
        _hash_dropbuf(rel, bucket_buf);

    /* Attempt to split if a split is needed */
    if (do_expand)
        _hash_expandtable(rel, metabuf);

    /* Finally drop our pin on the metapage */
    _hash_dropbuf(rel, metabuf);
}

void _hash_dropbuf	(	Relation	rel,
		Buffer	buf
	)

Definition at line 285 of file hashpage.c.

References ReleaseBuffer().

Referenced by _hash_doinsert(), _hash_dropscanbuf(), _hash_expandtable(), _hash_finish_split(), _hash_first(), _hash_getbucketbuf_from_hashkey(), _hash_next(), _hash_readprev(), and hashbulkdelete().

{
    ReleaseBuffer(buf);
}

void _hash_dropscanbuf	(	Relation	rel,
		HashScanOpaque	so
	)

Definition at line 297 of file hashpage.c.

References _hash_dropbuf(), HashScanPosData::buf, BufferIsValid, HashScanOpaqueData::currPos, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_split_bucket_buf, and InvalidBuffer.

Referenced by _hash_next(), hashendscan(), and hashrescan().

{
    /* release pin we hold on primary bucket page */
    if (BufferIsValid(so->hashso_bucket_buf) &&
        so->hashso_bucket_buf != so->currPos.buf)
        _hash_dropbuf(rel, so->hashso_bucket_buf);
    so->hashso_bucket_buf = InvalidBuffer;

    /* release pin we hold on primary bucket page  of bucket being split */
    if (BufferIsValid(so->hashso_split_bucket_buf) &&
        so->hashso_split_bucket_buf != so->currPos.buf)
        _hash_dropbuf(rel, so->hashso_split_bucket_buf);
    so->hashso_split_bucket_buf = InvalidBuffer;

    /* release any pin we still hold */
    if (BufferIsValid(so->currPos.buf))
        _hash_dropbuf(rel, so->currPos.buf);
    so->currPos.buf = InvalidBuffer;

    /* reset split scan */
    so->hashso_buc_populated = false;
    so->hashso_buc_split = false;
}

void _hash_expandtable	(	Relation	rel,
		Buffer	metabuf
	)

Definition at line 624 of file hashpage.c.

References _hash_alloc_buckets(), _hash_checkpage(), _hash_dropbuf(), _hash_finish_split(), _hash_get_totalbuckets(), _hash_getbuf_with_condlock_cleanup(), _hash_getnewbuf(), _hash_relbuf(), _hash_spareindex(), _hash_splitbucket(), Assert, BUCKET_TO_BLKNO, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, END_CRIT_SECTION, xl_hash_split_allocate_page::flags, H_BUCKET_BEING_SPLIT, H_NEEDS_SPLIT_CLEANUP, hashbucketcleanup(), HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_ntuples, HashMetaPageData::hashm_ovflpoint, HashMetaPageData::hashm_spares, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, HashPageGetMeta, InvalidBlockNumber, IsBufferCleanupOK(), LH_BUCKET_BEING_POPULATED, LH_BUCKET_BEING_SPLIT, LH_BUCKET_PAGE, LH_META_PAGE, LockBuffer(), MAIN_FORKNUM, MarkBufferDirty(), xl_hash_split_allocate_page::new_bucket, xl_hash_split_allocate_page::new_bucket_flag, xl_hash_split_allocate_page::old_bucket_flag, PageGetSpecialPointer, PageSetLSN, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationNeedsWAL, SizeOfHashSplitAllocPage, START_CRIT_SECTION, XLH_SPLIT_META_UPDATE_MASKS, XLH_SPLIT_META_UPDATE_SPLITPOINT, XLOG_HASH_SPLIT_ALLOCATE_PAGE, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _hash_doinsert().

{
    HashMetaPage metap;
    Bucket      old_bucket;
    Bucket      new_bucket;
    uint32      spare_ndx;
    BlockNumber start_oblkno;
    BlockNumber start_nblkno;
    Buffer      buf_nblkno;
    Buffer      buf_oblkno;
    Page        opage;
    Page        npage;
    HashPageOpaque oopaque;
    HashPageOpaque nopaque;
    uint32      maxbucket;
    uint32      highmask;
    uint32      lowmask;
    bool        metap_update_masks = false;
    bool        metap_update_splitpoint = false;

restart_expand:

    /*
     * Write-lock the meta page.  It used to be necessary to acquire a
     * heavyweight lock to begin a split, but that is no longer required.
     */
    LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);

    _hash_checkpage(rel, metabuf, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));

    /*
     * Check to see if split is still needed; someone else might have already
     * done one while we waited for the lock.
     *
     * Make sure this stays in sync with _hash_doinsert()
     */
    if (metap->hashm_ntuples <=
        (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1))
        goto fail;

    /*
     * Can't split anymore if maxbucket has reached its maximum possible
     * value.
     *
     * Ideally we'd allow bucket numbers up to UINT_MAX-1 (no higher because
     * the calculation maxbucket+1 mustn't overflow).  Currently we restrict
     * to half that because of overflow looping in _hash_log2() and
     * insufficient space in hashm_spares[].  It's moot anyway because an
     * index with 2^32 buckets would certainly overflow BlockNumber and hence
     * _hash_alloc_buckets() would fail, but if we supported buckets smaller
     * than a disk block then this would be an independent constraint.
     *
     * If you change this, see also the maximum initial number of buckets in
     * _hash_init().
     */
    if (metap->hashm_maxbucket >= (uint32) 0x7FFFFFFE)
        goto fail;

    /*
     * Determine which bucket is to be split, and attempt to take cleanup lock
     * on the old bucket.  If we can't get the lock, give up.
     *
     * The cleanup lock protects us not only against other backends, but
     * against our own backend as well.
     *
     * The cleanup lock is mainly to protect the split from concurrent
     * inserts. See src/backend/access/hash/README, Lock Definitions for
     * further details.  Due to this locking restriction, if there is any
     * pending scan, the split will give up which is not good, but harmless.
     */
    new_bucket = metap->hashm_maxbucket + 1;

    old_bucket = (new_bucket & metap->hashm_lowmask);

    start_oblkno = BUCKET_TO_BLKNO(metap, old_bucket);

    buf_oblkno = _hash_getbuf_with_condlock_cleanup(rel, start_oblkno, LH_BUCKET_PAGE);
    if (!buf_oblkno)
        goto fail;

    opage = BufferGetPage(buf_oblkno);
    oopaque = (HashPageOpaque) PageGetSpecialPointer(opage);

    /*
     * We want to finish the split from a bucket as there is no apparent
     * benefit by not doing so and it will make the code complicated to finish
     * the split that involves multiple buckets considering the case where new
     * split also fails.  We don't need to consider the new bucket for
     * completing the split here as it is not possible that a re-split of new
     * bucket starts when there is still a pending split from old bucket.
     */
    if (H_BUCKET_BEING_SPLIT(oopaque))
    {
        /*
         * Copy bucket mapping info now; refer the comment in code below where
         * we copy this information before calling _hash_splitbucket to see
         * why this is okay.
         */
        maxbucket = metap->hashm_maxbucket;
        highmask = metap->hashm_highmask;
        lowmask = metap->hashm_lowmask;

        /*
         * Release the lock on metapage and old_bucket, before completing the
         * split.
         */
        LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
        LockBuffer(buf_oblkno, BUFFER_LOCK_UNLOCK);

        _hash_finish_split(rel, metabuf, buf_oblkno, old_bucket, maxbucket,
                           highmask, lowmask);

        /* release the pin on old buffer and retry for expand. */
        _hash_dropbuf(rel, buf_oblkno);

        goto restart_expand;
    }

    /*
     * Clean the tuples remained from the previous split.  This operation
     * requires cleanup lock and we already have one on the old bucket, so
     * let's do it. We also don't want to allow further splits from the bucket
     * till the garbage of previous split is cleaned.  This has two
     * advantages; first, it helps in avoiding the bloat due to garbage and
     * second is, during cleanup of bucket, we are always sure that the
     * garbage tuples belong to most recently split bucket.  On the contrary,
     * if we allow cleanup of bucket after meta page is updated to indicate
     * the new split and before the actual split, the cleanup operation won't
     * be able to decide whether the tuple has been moved to the newly created
     * bucket and ended up deleting such tuples.
     */
    if (H_NEEDS_SPLIT_CLEANUP(oopaque))
    {
        /*
         * Copy bucket mapping info now; refer to the comment in code below
         * where we copy this information before calling _hash_splitbucket to
         * see why this is okay.
         */
        maxbucket = metap->hashm_maxbucket;
        highmask = metap->hashm_highmask;
        lowmask = metap->hashm_lowmask;

        /* Release the metapage lock. */
        LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

        hashbucketcleanup(rel, old_bucket, buf_oblkno, start_oblkno, NULL,
                          maxbucket, highmask, lowmask, NULL, NULL, true,
                          NULL, NULL);

        _hash_dropbuf(rel, buf_oblkno);

        goto restart_expand;
    }

    /*
     * There shouldn't be any active scan on new bucket.
     *
     * Note: it is safe to compute the new bucket's blkno here, even though we
     * may still need to update the BUCKET_TO_BLKNO mapping.  This is because
     * the current value of hashm_spares[hashm_ovflpoint] correctly shows
     * where we are going to put a new splitpoint's worth of buckets.
     */
    start_nblkno = BUCKET_TO_BLKNO(metap, new_bucket);

    /*
     * If the split point is increasing we need to allocate a new batch of
     * bucket pages.
     */
    spare_ndx = _hash_spareindex(new_bucket + 1);
    if (spare_ndx > metap->hashm_ovflpoint)
    {
        uint32      buckets_to_add;

        Assert(spare_ndx == metap->hashm_ovflpoint + 1);

        /*
         * We treat allocation of buckets as a separate WAL-logged action.
         * Even if we fail after this operation, won't leak bucket pages;
         * rather, the next split will consume this space. In any case, even
         * without failure we don't use all the space in one split operation.
         */
        buckets_to_add = _hash_get_totalbuckets(spare_ndx) - new_bucket;
        if (!_hash_alloc_buckets(rel, start_nblkno, buckets_to_add))
        {
            /* can't split due to BlockNumber overflow */
            _hash_relbuf(rel, buf_oblkno);
            goto fail;
        }
    }

    /*
     * Physically allocate the new bucket's primary page.  We want to do this
     * before changing the metapage's mapping info, in case we can't get the
     * disk space.  Ideally, we don't need to check for cleanup lock on new
     * bucket as no other backend could find this bucket unless meta page is
     * updated.  However, it is good to be consistent with old bucket locking.
     */
    buf_nblkno = _hash_getnewbuf(rel, start_nblkno, MAIN_FORKNUM);
    if (!IsBufferCleanupOK(buf_nblkno))
    {
        _hash_relbuf(rel, buf_oblkno);
        _hash_relbuf(rel, buf_nblkno);
        goto fail;
    }

    /*
     * Since we are scribbling on the pages in the shared buffers, establish a
     * critical section.  Any failure in this next code leaves us with a big
     * problem: the metapage is effectively corrupt but could get written back
     * to disk.
     */
    START_CRIT_SECTION();

    /*
     * Okay to proceed with split.  Update the metapage bucket mapping info.
     */
    metap->hashm_maxbucket = new_bucket;

    if (new_bucket > metap->hashm_highmask)
    {
        /* Starting a new doubling */
        metap->hashm_lowmask = metap->hashm_highmask;
        metap->hashm_highmask = new_bucket | metap->hashm_lowmask;
        metap_update_masks = true;
    }

    /*
     * If the split point is increasing we need to adjust the hashm_spares[]
     * array and hashm_ovflpoint so that future overflow pages will be created
     * beyond this new batch of bucket pages.
     */
    if (spare_ndx > metap->hashm_ovflpoint)
    {
        metap->hashm_spares[spare_ndx] = metap->hashm_spares[metap->hashm_ovflpoint];
        metap->hashm_ovflpoint = spare_ndx;
        metap_update_splitpoint = true;
    }

    MarkBufferDirty(metabuf);

    /*
     * Copy bucket mapping info now; this saves re-accessing the meta page
     * inside _hash_splitbucket's inner loop.  Note that once we drop the
     * split lock, other splits could begin, so these values might be out of
     * date before _hash_splitbucket finishes.  That's okay, since all it
     * needs is to tell which of these two buckets to map hashkeys into.
     */
    maxbucket = metap->hashm_maxbucket;
    highmask = metap->hashm_highmask;
    lowmask = metap->hashm_lowmask;

    opage = BufferGetPage(buf_oblkno);
    oopaque = (HashPageOpaque) PageGetSpecialPointer(opage);

    /*
     * Mark the old bucket to indicate that split is in progress.  (At
     * operation end, we will clear the split-in-progress flag.)  Also, for a
     * primary bucket page, hasho_prevblkno stores the number of buckets that
     * existed as of the last split, so we must update that value here.
     */
    oopaque->hasho_flag |= LH_BUCKET_BEING_SPLIT;
    oopaque->hasho_prevblkno = maxbucket;

    MarkBufferDirty(buf_oblkno);

    npage = BufferGetPage(buf_nblkno);

    /*
     * initialize the new bucket's primary page and mark it to indicate that
     * split is in progress.
     */
    nopaque = (HashPageOpaque) PageGetSpecialPointer(npage);
    nopaque->hasho_prevblkno = maxbucket;
    nopaque->hasho_nextblkno = InvalidBlockNumber;
    nopaque->hasho_bucket = new_bucket;
    nopaque->hasho_flag = LH_BUCKET_PAGE | LH_BUCKET_BEING_POPULATED;
    nopaque->hasho_page_id = HASHO_PAGE_ID;

    MarkBufferDirty(buf_nblkno);

    /* XLOG stuff */
    if (RelationNeedsWAL(rel))
    {
        xl_hash_split_allocate_page xlrec;
        XLogRecPtr  recptr;

        xlrec.new_bucket = maxbucket;
        xlrec.old_bucket_flag = oopaque->hasho_flag;
        xlrec.new_bucket_flag = nopaque->hasho_flag;
        xlrec.flags = 0;

        XLogBeginInsert();

        XLogRegisterBuffer(0, buf_oblkno, REGBUF_STANDARD);
        XLogRegisterBuffer(1, buf_nblkno, REGBUF_WILL_INIT);
        XLogRegisterBuffer(2, metabuf, REGBUF_STANDARD);

        if (metap_update_masks)
        {
            xlrec.flags |= XLH_SPLIT_META_UPDATE_MASKS;
            XLogRegisterBufData(2, (char *) &metap->hashm_lowmask, sizeof(uint32));
            XLogRegisterBufData(2, (char *) &metap->hashm_highmask, sizeof(uint32));
        }

        if (metap_update_splitpoint)
        {
            xlrec.flags |= XLH_SPLIT_META_UPDATE_SPLITPOINT;
            XLogRegisterBufData(2, (char *) &metap->hashm_ovflpoint,
                                sizeof(uint32));
            XLogRegisterBufData(2,
                                (char *) &metap->hashm_spares[metap->hashm_ovflpoint],
                                sizeof(uint32));
        }

        XLogRegisterData((char *) &xlrec, SizeOfHashSplitAllocPage);

        recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SPLIT_ALLOCATE_PAGE);

        PageSetLSN(BufferGetPage(buf_oblkno), recptr);
        PageSetLSN(BufferGetPage(buf_nblkno), recptr);
        PageSetLSN(BufferGetPage(metabuf), recptr);
    }

    END_CRIT_SECTION();

    /* drop lock, but keep pin */
    LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

    /* Relocate records to the new bucket */
    _hash_splitbucket(rel, metabuf,
                      old_bucket, new_bucket,
                      buf_oblkno, buf_nblkno, NULL,
                      maxbucket, highmask, lowmask);

    /* all done, now release the pins on primary buckets. */
    _hash_dropbuf(rel, buf_oblkno);
    _hash_dropbuf(rel, buf_nblkno);

    return;

    /* Here if decide not to split or fail to acquire old bucket lock */
fail:

    /* We didn't write the metapage, so just drop lock */
    LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
}

void _hash_finish_split	(	Relation	rel,
		Buffer	metabuf,
		Buffer	obuf,
		Bucket	obucket,
		uint32	maxbucket,
		uint32	highmask,
		uint32	lowmask
	)

Definition at line 1356 of file hashpage.c.

References _hash_dropbuf(), _hash_get_newblock_from_oldbucket(), _hash_getbuf(), _hash_relbuf(), _hash_splitbucket(), Assert, BlockNumberIsValid, BUFFER_LOCK_UNLOCK, BufferGetPage, ConditionalLockBufferForCleanup(), CurrentMemoryContext, HASHCTL::entrysize, FirstOffsetNumber, HASH_BLOBS, HASH_CONTEXT, hash_create(), hash_destroy(), HASH_ELEM, HASH_ENTER, HASH_READ, hash_search(), HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_nextblkno, HASHCTL::hcxt, InvalidBuffer, HASHCTL::keysize, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, LockBuffer(), OffsetNumberNext, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, and IndexTupleData::t_tid.

Referenced by _hash_doinsert(), and _hash_expandtable().

{
    HASHCTL     hash_ctl;
    HTAB       *tidhtab;
    Buffer      bucket_nbuf = InvalidBuffer;
    Buffer      nbuf;
    Page        npage;
    BlockNumber nblkno;
    BlockNumber bucket_nblkno;
    HashPageOpaque npageopaque;
    Bucket      nbucket;
    bool        found;

    /* Initialize hash tables used to track TIDs */
    memset(&hash_ctl, 0, sizeof(hash_ctl));
    hash_ctl.keysize = sizeof(ItemPointerData);
    hash_ctl.entrysize = sizeof(ItemPointerData);
    hash_ctl.hcxt = CurrentMemoryContext;

    tidhtab =
        hash_create("bucket ctids",
                    256,        /* arbitrary initial size */
                    &hash_ctl,
                    HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);

    bucket_nblkno = nblkno = _hash_get_newblock_from_oldbucket(rel, obucket);

    /*
     * Scan the new bucket and build hash table of TIDs
     */
    for (;;)
    {
        OffsetNumber noffnum;
        OffsetNumber nmaxoffnum;

        nbuf = _hash_getbuf(rel, nblkno, HASH_READ,
                            LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);

        /* remember the primary bucket buffer to acquire cleanup lock on it. */
        if (nblkno == bucket_nblkno)
            bucket_nbuf = nbuf;

        npage = BufferGetPage(nbuf);
        npageopaque = (HashPageOpaque) PageGetSpecialPointer(npage);

        /* Scan each tuple in new page */
        nmaxoffnum = PageGetMaxOffsetNumber(npage);
        for (noffnum = FirstOffsetNumber;
             noffnum <= nmaxoffnum;
             noffnum = OffsetNumberNext(noffnum))
        {
            IndexTuple  itup;

            /* Fetch the item's TID and insert it in hash table. */
            itup = (IndexTuple) PageGetItem(npage,
                                            PageGetItemId(npage, noffnum));

            (void) hash_search(tidhtab, &itup->t_tid, HASH_ENTER, &found);

            Assert(!found);
        }

        nblkno = npageopaque->hasho_nextblkno;

        /*
         * release our write lock without modifying buffer and ensure to
         * retain the pin on primary bucket.
         */
        if (nbuf == bucket_nbuf)
            LockBuffer(nbuf, BUFFER_LOCK_UNLOCK);
        else
            _hash_relbuf(rel, nbuf);

        /* Exit loop if no more overflow pages in new bucket */
        if (!BlockNumberIsValid(nblkno))
            break;
    }

    /*
     * Conditionally get the cleanup lock on old and new buckets to perform
     * the split operation.  If we don't get the cleanup locks, silently give
     * up and next insertion on old bucket will try again to complete the
     * split.
     */
    if (!ConditionalLockBufferForCleanup(obuf))
    {
        hash_destroy(tidhtab);
        return;
    }
    if (!ConditionalLockBufferForCleanup(bucket_nbuf))
    {
        LockBuffer(obuf, BUFFER_LOCK_UNLOCK);
        hash_destroy(tidhtab);
        return;
    }

    npage = BufferGetPage(bucket_nbuf);
    npageopaque = (HashPageOpaque) PageGetSpecialPointer(npage);
    nbucket = npageopaque->hasho_bucket;

    _hash_splitbucket(rel, metabuf, obucket,
                      nbucket, obuf, bucket_nbuf, tidhtab,
                      maxbucket, highmask, lowmask);

    _hash_dropbuf(rel, bucket_nbuf);
    hash_destroy(tidhtab);
}

bool _hash_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 290 of file hashsearch.c.

References _hash_datum2hashkey(), _hash_datum2hashkey_type(), _hash_dropbuf(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_getbuf(), _hash_readnext(), _hash_readpage(), Assert, BlockNumberIsValid, buf, HashScanPosData::buf, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage, BufferIsInvalid, cur, HashScanOpaqueData::currPos, ereport, errcode(), errmsg(), ERROR, H_BUCKET_BEING_POPULATED, HASH_READ, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_sk_hash, HashScanOpaqueData::hashso_split_bucket_buf, HTEqualStrategyNumber, IndexScanDescData::indexRelation, InvalidBuffer, InvalidOid, HashScanPosData::itemIndex, HashScanPosData::items, IndexScanDescData::keyData, LH_BUCKET_PAGE, LockBuffer(), IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, PageGetSpecialPointer, pgstat_count_index_scan, RelationData::rd_opcintype, ScanDirectionIsBackward, SK_ISNULL, HeapTupleData::t_self, TestForOldSnapshot(), IndexScanDescData::xs_ctup, and IndexScanDescData::xs_snapshot.

Referenced by hashgetbitmap(), and hashgettuple().

{
    Relation    rel = scan->indexRelation;
    HashScanOpaque so = (HashScanOpaque) scan->opaque;
    ScanKey     cur;
    uint32      hashkey;
    Bucket      bucket;
    Buffer      buf;
    Page        page;
    HashPageOpaque opaque;
    HashScanPosItem *currItem;

    pgstat_count_index_scan(rel);

    /*
     * We do not support hash scans with no index qualification, because we
     * would have to read the whole index rather than just one bucket. That
     * creates a whole raft of problems, since we haven't got a practical way
     * to lock all the buckets against splits or compactions.
     */
    if (scan->numberOfKeys < 1)
        ereport(ERROR,
                (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
                 errmsg("hash indexes do not support whole-index scans")));

    /* There may be more than one index qual, but we hash only the first */
    cur = &scan->keyData[0];

    /* We support only single-column hash indexes */
    Assert(cur->sk_attno == 1);
    /* And there's only one operator strategy, too */
    Assert(cur->sk_strategy == HTEqualStrategyNumber);

    /*
     * If the constant in the index qual is NULL, assume it cannot match any
     * items in the index.
     */
    if (cur->sk_flags & SK_ISNULL)
        return false;

    /*
     * Okay to compute the hash key.  We want to do this before acquiring any
     * locks, in case a user-defined hash function happens to be slow.
     *
     * If scankey operator is not a cross-type comparison, we can use the
     * cached hash function; otherwise gotta look it up in the catalogs.
     *
     * We support the convention that sk_subtype == InvalidOid means the
     * opclass input type; this is a hack to simplify life for ScanKeyInit().
     */
    if (cur->sk_subtype == rel->rd_opcintype[0] ||
        cur->sk_subtype == InvalidOid)
        hashkey = _hash_datum2hashkey(rel, cur->sk_argument);
    else
        hashkey = _hash_datum2hashkey_type(rel, cur->sk_argument,
                                           cur->sk_subtype);

    so->hashso_sk_hash = hashkey;

    buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_READ, NULL);
    page = BufferGetPage(buf);
    TestForOldSnapshot(scan->xs_snapshot, rel, page);
    opaque = (HashPageOpaque) PageGetSpecialPointer(page);
    bucket = opaque->hasho_bucket;

    so->hashso_bucket_buf = buf;

    /*
     * If a bucket split is in progress, then while scanning the bucket being
     * populated, we need to skip tuples that were copied from bucket being
     * split.  We also need to maintain a pin on the bucket being split to
     * ensure that split-cleanup work done by vacuum doesn't remove tuples
     * from it till this scan is done.  We need to maintain a pin on the
     * bucket being populated to ensure that vacuum doesn't squeeze that
     * bucket till this scan is complete; otherwise, the ordering of tuples
     * can't be maintained during forward and backward scans.  Here, we have
     * to be cautious about locking order: first, acquire the lock on bucket
     * being split; then, release the lock on it but not the pin; then,
     * acquire a lock on bucket being populated and again re-verify whether
     * the bucket split is still in progress.  Acquiring the lock on bucket
     * being split first ensures that the vacuum waits for this scan to
     * finish.
     */
    if (H_BUCKET_BEING_POPULATED(opaque))
    {
        BlockNumber old_blkno;
        Buffer      old_buf;

        old_blkno = _hash_get_oldblock_from_newbucket(rel, bucket);

        /*
         * release the lock on new bucket and re-acquire it after acquiring
         * the lock on old bucket.
         */
        LockBuffer(buf, BUFFER_LOCK_UNLOCK);

        old_buf = _hash_getbuf(rel, old_blkno, HASH_READ, LH_BUCKET_PAGE);
        TestForOldSnapshot(scan->xs_snapshot, rel, BufferGetPage(old_buf));

        /*
         * remember the split bucket buffer so as to use it later for
         * scanning.
         */
        so->hashso_split_bucket_buf = old_buf;
        LockBuffer(old_buf, BUFFER_LOCK_UNLOCK);

        LockBuffer(buf, BUFFER_LOCK_SHARE);
        page = BufferGetPage(buf);
        opaque = (HashPageOpaque) PageGetSpecialPointer(page);
        Assert(opaque->hasho_bucket == bucket);

        if (H_BUCKET_BEING_POPULATED(opaque))
            so->hashso_buc_populated = true;
        else
        {
            _hash_dropbuf(rel, so->hashso_split_bucket_buf);
            so->hashso_split_bucket_buf = InvalidBuffer;
        }
    }

    /* If a backwards scan is requested, move to the end of the chain */
    if (ScanDirectionIsBackward(dir))
    {
        /*
         * Backward scans that start during split needs to start from end of
         * bucket being split.
         */
        while (BlockNumberIsValid(opaque->hasho_nextblkno) ||
               (so->hashso_buc_populated && !so->hashso_buc_split))
            _hash_readnext(scan, &buf, &page, &opaque);
    }

    /* remember which buffer we have pinned, if any */
    Assert(BufferIsInvalid(so->currPos.buf));
    so->currPos.buf = buf;

    /* Now find all the tuples satisfying the qualification from a page */
    if (!_hash_readpage(scan, &buf, dir))
        return false;

    /* OK, itemIndex says what to return */
    currItem = &so->currPos.items[so->currPos.itemIndex];
    scan->xs_ctup.t_self = currItem->heapTid;

    /* if we're here, _hash_readpage found a valid tuples */
    return true;
}

BlockNumber _hash_freeovflpage	(	Relation	rel,
		Buffer	bucketbuf,
		Buffer	ovflbuf,
		Buffer	wbuf,
		IndexTuple *	itups,
		OffsetNumber *	itup_offsets,
		Size *	tups_size,
		uint16	nitups,
		BufferAccessStrategy	bstrategy
	)

Definition at line 488 of file hashovfl.c.

References _hash_checkpage(), _hash_getbuf(), _hash_getbuf_with_strategy(), _hash_ovflblkno_to_bitno(), _hash_pageinit(), _hash_pgaddmultitup(), _hash_relbuf(), Assert, BlockNumberIsValid, BMPG_MASK, BMPG_SHIFT, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, BufferGetPageSize, BufferIsValid, CLRBIT, elog, END_CRIT_SECTION, ERROR, HASH_METAPAGE, HASH_READ, HASH_WRITE, HASH_XLOG_FREE_OVFL_BUFS, HashMetaPageData::hashm_firstfree, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_nmaps, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, HashPageGetBitmap, HashPageGetMeta, i, InvalidBlockNumber, InvalidBuffer, xl_hash_squeeze_page::is_prev_bucket_same_wrt, xl_hash_squeeze_page::is_prim_bucket_same_wrt, ISSET, LH_BITMAP_PAGE, LH_BUCKET_PAGE, LH_META_PAGE, LH_OVERFLOW_PAGE, LH_UNUSED_PAGE, LockBuffer(), MarkBufferDirty(), xl_hash_squeeze_page::nextblkno, xl_hash_squeeze_page::ntups, PageGetSpecialPointer, PageSetLSN, PG_USED_FOR_ASSERTS_ONLY, xl_hash_squeeze_page::prevblkno, REGBUF_NO_IMAGE, REGBUF_STANDARD, RelationNeedsWAL, SizeOfHashSqueezePage, START_CRIT_SECTION, XLOG_HASH_SQUEEZE_PAGE, XLogBeginInsert(), XLogEnsureRecordSpace(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _hash_squeezebucket().

{
    HashMetaPage metap;
    Buffer      metabuf;
    Buffer      mapbuf;
    BlockNumber ovflblkno;
    BlockNumber prevblkno;
    BlockNumber blkno;
    BlockNumber nextblkno;
    BlockNumber writeblkno;
    HashPageOpaque ovflopaque;
    Page        ovflpage;
    Page        mappage;
    uint32     *freep;
    uint32      ovflbitno;
    int32       bitmappage,
                bitmapbit;
    Bucket      bucket PG_USED_FOR_ASSERTS_ONLY;
    Buffer      prevbuf = InvalidBuffer;
    Buffer      nextbuf = InvalidBuffer;
    bool        update_metap = false;

    /* Get information from the doomed page */
    _hash_checkpage(rel, ovflbuf, LH_OVERFLOW_PAGE);
    ovflblkno = BufferGetBlockNumber(ovflbuf);
    ovflpage = BufferGetPage(ovflbuf);
    ovflopaque = (HashPageOpaque) PageGetSpecialPointer(ovflpage);
    nextblkno = ovflopaque->hasho_nextblkno;
    prevblkno = ovflopaque->hasho_prevblkno;
    writeblkno = BufferGetBlockNumber(wbuf);
    bucket = ovflopaque->hasho_bucket;

    /*
     * Fix up the bucket chain.  this is a doubly-linked list, so we must fix
     * up the bucket chain members behind and ahead of the overflow page being
     * deleted.  Concurrency issues are avoided by using lock chaining as
     * described atop hashbucketcleanup.
     */
    if (BlockNumberIsValid(prevblkno))
    {
        if (prevblkno == writeblkno)
            prevbuf = wbuf;
        else
            prevbuf = _hash_getbuf_with_strategy(rel,
                                                 prevblkno,
                                                 HASH_WRITE,
                                                 LH_BUCKET_PAGE | LH_OVERFLOW_PAGE,
                                                 bstrategy);
    }
    if (BlockNumberIsValid(nextblkno))
        nextbuf = _hash_getbuf_with_strategy(rel,
                                             nextblkno,
                                             HASH_WRITE,
                                             LH_OVERFLOW_PAGE,
                                             bstrategy);

    /* Note: bstrategy is intentionally not used for metapage and bitmap */

    /* Read the metapage so we can determine which bitmap page to use */
    metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));

    /* Identify which bit to set */
    ovflbitno = _hash_ovflblkno_to_bitno(metap, ovflblkno);

    bitmappage = ovflbitno >> BMPG_SHIFT(metap);
    bitmapbit = ovflbitno & BMPG_MASK(metap);

    if (bitmappage >= metap->hashm_nmaps)
        elog(ERROR, "invalid overflow bit number %u", ovflbitno);
    blkno = metap->hashm_mapp[bitmappage];

    /* Release metapage lock while we access the bitmap page */
    LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

    /* read the bitmap page to clear the bitmap bit */
    mapbuf = _hash_getbuf(rel, blkno, HASH_WRITE, LH_BITMAP_PAGE);
    mappage = BufferGetPage(mapbuf);
    freep = HashPageGetBitmap(mappage);
    Assert(ISSET(freep, bitmapbit));

    /* Get write-lock on metapage to update firstfree */
    LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);

    /* This operation needs to log multiple tuples, prepare WAL for that */
    if (RelationNeedsWAL(rel))
        XLogEnsureRecordSpace(HASH_XLOG_FREE_OVFL_BUFS, 4 + nitups);

    START_CRIT_SECTION();

    /*
     * we have to insert tuples on the "write" page, being careful to preserve
     * hashkey ordering.  (If we insert many tuples into the same "write" page
     * it would be worth qsort'ing them).
     */
    if (nitups > 0)
    {
        _hash_pgaddmultitup(rel, wbuf, itups, itup_offsets, nitups);
        MarkBufferDirty(wbuf);
    }

    /*
     * Reinitialize the freed overflow page.  Just zeroing the page won't
     * work, because WAL replay routines expect pages to be initialized. See
     * explanation of RBM_NORMAL mode atop XLogReadBufferExtended.  We are
     * careful to make the special space valid here so that tools like
     * pageinspect won't get confused.
     */
    _hash_pageinit(ovflpage, BufferGetPageSize(ovflbuf));

    ovflopaque = (HashPageOpaque) PageGetSpecialPointer(ovflpage);

    ovflopaque->hasho_prevblkno = InvalidBlockNumber;
    ovflopaque->hasho_nextblkno = InvalidBlockNumber;
    ovflopaque->hasho_bucket = -1;
    ovflopaque->hasho_flag = LH_UNUSED_PAGE;
    ovflopaque->hasho_page_id = HASHO_PAGE_ID;

    MarkBufferDirty(ovflbuf);

    if (BufferIsValid(prevbuf))
    {
        Page        prevpage = BufferGetPage(prevbuf);
        HashPageOpaque prevopaque = (HashPageOpaque) PageGetSpecialPointer(prevpage);

        Assert(prevopaque->hasho_bucket == bucket);
        prevopaque->hasho_nextblkno = nextblkno;
        MarkBufferDirty(prevbuf);
    }
    if (BufferIsValid(nextbuf))
    {
        Page        nextpage = BufferGetPage(nextbuf);
        HashPageOpaque nextopaque = (HashPageOpaque) PageGetSpecialPointer(nextpage);

        Assert(nextopaque->hasho_bucket == bucket);
        nextopaque->hasho_prevblkno = prevblkno;
        MarkBufferDirty(nextbuf);
    }

    /* Clear the bitmap bit to indicate that this overflow page is free */
    CLRBIT(freep, bitmapbit);
    MarkBufferDirty(mapbuf);

    /* if this is now the first free page, update hashm_firstfree */
    if (ovflbitno < metap->hashm_firstfree)
    {
        metap->hashm_firstfree = ovflbitno;
        update_metap = true;
        MarkBufferDirty(metabuf);
    }

    /* XLOG stuff */
    if (RelationNeedsWAL(rel))
    {
        xl_hash_squeeze_page xlrec;
        XLogRecPtr  recptr;
        int         i;

        xlrec.prevblkno = prevblkno;
        xlrec.nextblkno = nextblkno;
        xlrec.ntups = nitups;
        xlrec.is_prim_bucket_same_wrt = (wbuf == bucketbuf);
        xlrec.is_prev_bucket_same_wrt = (wbuf == prevbuf);

        XLogBeginInsert();
        XLogRegisterData((char *) &xlrec, SizeOfHashSqueezePage);

        /*
         * bucket buffer needs to be registered to ensure that we can acquire
         * a cleanup lock on it during replay.
         */
        if (!xlrec.is_prim_bucket_same_wrt)
            XLogRegisterBuffer(0, bucketbuf, REGBUF_STANDARD | REGBUF_NO_IMAGE);

        XLogRegisterBuffer(1, wbuf, REGBUF_STANDARD);
        if (xlrec.ntups > 0)
        {
            XLogRegisterBufData(1, (char *) itup_offsets,
                                nitups * sizeof(OffsetNumber));
            for (i = 0; i < nitups; i++)
                XLogRegisterBufData(1, (char *) itups[i], tups_size[i]);
        }

        XLogRegisterBuffer(2, ovflbuf, REGBUF_STANDARD);

        /*
         * If prevpage and the writepage (block in which we are moving tuples
         * from overflow) are same, then no need to separately register
         * prevpage.  During replay, we can directly update the nextblock in
         * writepage.
         */
        if (BufferIsValid(prevbuf) && !xlrec.is_prev_bucket_same_wrt)
            XLogRegisterBuffer(3, prevbuf, REGBUF_STANDARD);

        if (BufferIsValid(nextbuf))
            XLogRegisterBuffer(4, nextbuf, REGBUF_STANDARD);

        XLogRegisterBuffer(5, mapbuf, REGBUF_STANDARD);
        XLogRegisterBufData(5, (char *) &bitmapbit, sizeof(uint32));

        if (update_metap)
        {
            XLogRegisterBuffer(6, metabuf, REGBUF_STANDARD);
            XLogRegisterBufData(6, (char *) &metap->hashm_firstfree, sizeof(uint32));
        }

        recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SQUEEZE_PAGE);

        PageSetLSN(BufferGetPage(wbuf), recptr);
        PageSetLSN(BufferGetPage(ovflbuf), recptr);

        if (BufferIsValid(prevbuf) && !xlrec.is_prev_bucket_same_wrt)
            PageSetLSN(BufferGetPage(prevbuf), recptr);
        if (BufferIsValid(nextbuf))
            PageSetLSN(BufferGetPage(nextbuf), recptr);

        PageSetLSN(BufferGetPage(mapbuf), recptr);

        if (update_metap)
            PageSetLSN(BufferGetPage(metabuf), recptr);
    }

    END_CRIT_SECTION();

    /* release previous bucket if it is not same as write bucket */
    if (BufferIsValid(prevbuf) && prevblkno != writeblkno)
        _hash_relbuf(rel, prevbuf);

    if (BufferIsValid(ovflbuf))
        _hash_relbuf(rel, ovflbuf);

    if (BufferIsValid(nextbuf))
        _hash_relbuf(rel, nextbuf);

    _hash_relbuf(rel, mapbuf);
    _hash_relbuf(rel, metabuf);

    return nextblkno;
}

uint32 _hash_get_indextuple_hashkey

(

IndexTuple

itup

)

Definition at line 299 of file hashutil.c.

References IndexInfoFindDataOffset, and IndexTupleData::t_info.

Referenced by _h_indexbuild(), _hash_binsearch(), _hash_binsearch_last(), _hash_doinsert(), _hash_load_qualified_items(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_splitbucket(), hash_page_items(), and hashbucketcleanup().

{
    char       *attp;

    /*
     * We assume the hash key is the first attribute and can't be null, so
     * this can be done crudely but very very cheaply ...
     */
    attp = (char *) itup + IndexInfoFindDataOffset(itup->t_info);
    return *((uint32 *) attp);
}

BlockNumber _hash_get_newblock_from_oldbucket	(	Relation	rel,
		Bucket	old_bucket
	)

Definition at line 469 of file hashutil.c.

References _hash_get_newbucket_from_oldbucket(), _hash_getbuf(), _hash_relbuf(), BUCKET_TO_BLKNO, BufferGetPage, HASH_METAPAGE, HASH_READ, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_maxbucket, HashPageGetMeta, and LH_META_PAGE.

Referenced by _hash_finish_split().

{
    Bucket      new_bucket;
    Buffer      metabuf;
    HashMetaPage metap;
    BlockNumber blkno;

    metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));

    new_bucket = _hash_get_newbucket_from_oldbucket(rel, old_bucket,
                                                    metap->hashm_lowmask,
                                                    metap->hashm_maxbucket);
    blkno = BUCKET_TO_BLKNO(metap, new_bucket);

    _hash_relbuf(rel, metabuf);

    return blkno;
}

Bucket _hash_get_newbucket_from_oldbucket	(	Relation	rel,
		Bucket	old_bucket,
		uint32	lowmask,
		uint32	maxbucket
	)

Definition at line 502 of file hashutil.c.

References CALC_NEW_BUCKET.

Referenced by _hash_get_newblock_from_oldbucket(), and hashbucketcleanup().

{
    Bucket      new_bucket;

    new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
    if (new_bucket > maxbucket)
    {
        lowmask = lowmask >> 1;
        new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
    }

    return new_bucket;
}

BlockNumber _hash_get_oldblock_from_newbucket	(	Relation	rel,
		Bucket	new_bucket
	)

Definition at line 430 of file hashutil.c.

References _hash_getbuf(), _hash_relbuf(), BUCKET_TO_BLKNO, BufferGetPage, fls(), HASH_METAPAGE, HASH_READ, HashPageGetMeta, and LH_META_PAGE.

Referenced by _hash_first().

{
    Bucket      old_bucket;
    uint32      mask;
    Buffer      metabuf;
    HashMetaPage metap;
    BlockNumber blkno;

    /*
     * To get the old bucket from the current bucket, we need a mask to modulo
     * into lower half of table.  This mask is stored in meta page as
     * hashm_lowmask, but here we can't rely on the same, because we need a
     * value of lowmask that was prevalent at the time when bucket split was
     * started.  Masking the most significant bit of new bucket would give us
     * old bucket.
     */
    mask = (((uint32) 1) << (fls(new_bucket) - 1)) - 1;
    old_bucket = new_bucket & mask;

    metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));

    blkno = BUCKET_TO_BLKNO(metap, old_bucket);

    _hash_relbuf(rel, metabuf);

    return blkno;
}

uint32 _hash_get_totalbuckets

(

uint32

splitpoint_phase

)

Definition at line 189 of file hashutil.c.

References HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE, HASH_SPLITPOINT_PHASE_BITS, and HASH_SPLITPOINT_PHASE_MASK.

Referenced by _hash_expandtable(), _hash_init_metabuffer(), _hash_ovflblkno_to_bitno(), and bitno_to_blkno().

{
    uint32      splitpoint_group;
    uint32      total_buckets;
    uint32      phases_within_splitpoint_group;

    if (splitpoint_phase < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
        return (1 << splitpoint_phase);

    /* get splitpoint's group */
    splitpoint_group = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
    splitpoint_group +=
        ((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) >>
         HASH_SPLITPOINT_PHASE_BITS);

    /* account for buckets before splitpoint_group */
    total_buckets = (1 << (splitpoint_group - 1));

    /* account for buckets within splitpoint_group */
    phases_within_splitpoint_group =
        (((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) &
          HASH_SPLITPOINT_PHASE_MASK) + 1); /* from 0-based to 1-based */
    total_buckets +=
        (((1 << (splitpoint_group - 1)) >> HASH_SPLITPOINT_PHASE_BITS) *
         phases_within_splitpoint_group);

    return total_buckets;
}

Buffer _hash_getbucketbuf_from_hashkey	(	Relation	rel,
		uint32	hashkey,
		int	access,
		HashMetaPage *	cachedmetap
	)

Definition at line 1560 of file hashpage.c.

References _hash_dropbuf(), _hash_getbuf(), _hash_getcachedmetap(), _hash_hashkey2bucket(), _hash_relbuf(), Assert, BUCKET_TO_BLKNO, buf, BufferGetPage, BufferIsValid, HASH_READ, HASH_WRITE, HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_maxbucket, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_prevblkno, InvalidBlockNumber, InvalidBuffer, LH_BUCKET_PAGE, and PageGetSpecialPointer.

Referenced by _hash_doinsert(), and _hash_first().

{
    HashMetaPage metap;
    Buffer      buf;
    Buffer      metabuf = InvalidBuffer;
    Page        page;
    Bucket      bucket;
    BlockNumber blkno;
    HashPageOpaque opaque;

    /* We read from target bucket buffer, hence locking is must. */
    Assert(access == HASH_READ || access == HASH_WRITE);

    metap = _hash_getcachedmetap(rel, &metabuf, false);
    Assert(metap != NULL);

    /*
     * Loop until we get a lock on the correct target bucket.
     */
    for (;;)
    {
        /*
         * Compute the target bucket number, and convert to block number.
         */
        bucket = _hash_hashkey2bucket(hashkey,
                                      metap->hashm_maxbucket,
                                      metap->hashm_highmask,
                                      metap->hashm_lowmask);

        blkno = BUCKET_TO_BLKNO(metap, bucket);

        /* Fetch the primary bucket page for the bucket */
        buf = _hash_getbuf(rel, blkno, access, LH_BUCKET_PAGE);
        page = BufferGetPage(buf);
        opaque = (HashPageOpaque) PageGetSpecialPointer(page);
        Assert(opaque->hasho_bucket == bucket);
        Assert(opaque->hasho_prevblkno != InvalidBlockNumber);

        /*
         * If this bucket hasn't been split, we're done.
         */
        if (opaque->hasho_prevblkno <= metap->hashm_maxbucket)
            break;

        /* Drop lock on this buffer, update cached metapage, and retry. */
        _hash_relbuf(rel, buf);
        metap = _hash_getcachedmetap(rel, &metabuf, true);
        Assert(metap != NULL);
    }

    if (BufferIsValid(metabuf))
        _hash_dropbuf(rel, metabuf);

    if (cachedmetap)
        *cachedmetap = metap;

    return buf;
}

Buffer _hash_getbuf	(	Relation	rel,
		BlockNumber	blkno,
		int	access,
		int	flags
	)

Definition at line 78 of file hashpage.c.

References _hash_checkpage(), buf, elog, ERROR, HASH_NOLOCK, LockBuffer(), P_NEW, and ReadBuffer().

Referenced by _hash_addovflpage(), _hash_doinsert(), _hash_finish_split(), _hash_first(), _hash_freeovflpage(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_getcachedmetap(), _hash_kill_items(), _hash_next(), _hash_readnext(), _hash_readprev(), _hash_splitbucket(), hash_bitmap_info(), hashbulkdelete(), and pgstathashindex().

{
    Buffer      buf;

    if (blkno == P_NEW)
        elog(ERROR, "hash AM does not use P_NEW");

    buf = ReadBuffer(rel, blkno);

    if (access != HASH_NOLOCK)
        LockBuffer(buf, access);

    /* ref count and lock type are correct */

    _hash_checkpage(rel, buf, flags);

    return buf;
}

Buffer _hash_getbuf_with_condlock_cleanup	(	Relation	rel,
		BlockNumber	blkno,
		int	flags
	)

Definition at line 104 of file hashpage.c.

References _hash_checkpage(), buf, ConditionalLockBufferForCleanup(), elog, ERROR, InvalidBuffer, P_NEW, ReadBuffer(), and ReleaseBuffer().

Referenced by _hash_expandtable().

{
    Buffer      buf;

    if (blkno == P_NEW)
        elog(ERROR, "hash AM does not use P_NEW");

    buf = ReadBuffer(rel, blkno);

    if (!ConditionalLockBufferForCleanup(buf))
    {
        ReleaseBuffer(buf);
        return InvalidBuffer;
    }

    /* ref count and lock type are correct */

    _hash_checkpage(rel, buf, flags);

    return buf;
}

Buffer _hash_getbuf_with_strategy	(	Relation	rel,
		BlockNumber	blkno,
		int	access,
		int	flags,
		BufferAccessStrategy	bstrategy
	)

Definition at line 247 of file hashpage.c.

References _hash_checkpage(), buf, elog, ERROR, HASH_NOLOCK, LockBuffer(), MAIN_FORKNUM, P_NEW, RBM_NORMAL, and ReadBufferExtended().

Referenced by _hash_freeovflpage(), _hash_squeezebucket(), hashbucketcleanup(), and pgstat_hash_page().

{
    Buffer      buf;

    if (blkno == P_NEW)
        elog(ERROR, "hash AM does not use P_NEW");

    buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL, bstrategy);

    if (access != HASH_NOLOCK)
        LockBuffer(buf, access);

    /* ref count and lock type are correct */

    _hash_checkpage(rel, buf, flags);

    return buf;
}

HashMetaPage _hash_getcachedmetap	(	Relation	rel,
		Buffer *	metabuf,
		bool	force_refresh
	)

Definition at line 1502 of file hashpage.c.

References _hash_getbuf(), Assert, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage, BufferIsValid, HASH_METAPAGE, HASH_READ, HashPageGetMeta, LH_META_PAGE, LockBuffer(), MemoryContextAlloc(), RelationData::rd_amcache, and RelationData::rd_indexcxt.

Referenced by _hash_getbucketbuf_from_hashkey(), and hashbulkdelete().

{
    Page        page;

    Assert(metabuf);
    if (force_refresh || rel->rd_amcache == NULL)
    {
        char       *cache = NULL;

        /*
         * It's important that we don't set rd_amcache to an invalid value.
         * Either MemoryContextAlloc or _hash_getbuf could fail, so don't
         * install a pointer to the newly-allocated storage in the actual
         * relcache entry until both have succeeeded.
         */
        if (rel->rd_amcache == NULL)
            cache = MemoryContextAlloc(rel->rd_indexcxt,
                                       sizeof(HashMetaPageData));

        /* Read the metapage. */
        if (BufferIsValid(*metabuf))
            LockBuffer(*metabuf, BUFFER_LOCK_SHARE);
        else
            *metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ,
                                    LH_META_PAGE);
        page = BufferGetPage(*metabuf);

        /* Populate the cache. */
        if (rel->rd_amcache == NULL)
            rel->rd_amcache = cache;
        memcpy(rel->rd_amcache, HashPageGetMeta(page),
               sizeof(HashMetaPageData));

        /* Release metapage lock, but keep the pin. */
        LockBuffer(*metabuf, BUFFER_LOCK_UNLOCK);
    }

    return (HashMetaPage) rel->rd_amcache;
}

Buffer _hash_getinitbuf	(	Relation	rel,
		BlockNumber	blkno
	)

Definition at line 143 of file hashpage.c.

References _hash_pageinit(), buf, BufferGetPage, BufferGetPageSize, elog, ERROR, MAIN_FORKNUM, P_NEW, RBM_ZERO_AND_LOCK, and ReadBufferExtended().

Referenced by _hash_addovflpage().

{
    Buffer      buf;

    if (blkno == P_NEW)
        elog(ERROR, "hash AM does not use P_NEW");

    buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_ZERO_AND_LOCK,
                             NULL);

    /* ref count and lock type are correct */

    /* initialize the page */
    _hash_pageinit(BufferGetPage(buf), BufferGetPageSize(buf));

    return buf;
}

Buffer _hash_getnewbuf	(	Relation	rel,
		BlockNumber	blkno,
		ForkNumber	forkNum
	)

Definition at line 206 of file hashpage.c.

References _hash_pageinit(), buf, BufferGetBlockNumber(), BufferGetPage, BufferGetPageSize, elog, ERROR, HASH_WRITE, LockBuffer(), P_NEW, RBM_NORMAL, RBM_ZERO_AND_LOCK, ReadBufferExtended(), RelationGetNumberOfBlocksInFork(), and RelationGetRelationName.

Referenced by _hash_addovflpage(), _hash_expandtable(), and _hash_init().

{
    BlockNumber nblocks = RelationGetNumberOfBlocksInFork(rel, forkNum);
    Buffer      buf;

    if (blkno == P_NEW)
        elog(ERROR, "hash AM does not use P_NEW");
    if (blkno > nblocks)
        elog(ERROR, "access to noncontiguous page in hash index \"%s\"",
             RelationGetRelationName(rel));

    /* smgr insists we use P_NEW to extend the relation */
    if (blkno == nblocks)
    {
        buf = ReadBufferExtended(rel, forkNum, P_NEW, RBM_NORMAL, NULL);
        if (BufferGetBlockNumber(buf) != blkno)
            elog(ERROR, "unexpected hash relation size: %u, should be %u",
                 BufferGetBlockNumber(buf), blkno);
        LockBuffer(buf, HASH_WRITE);
    }
    else
    {
        buf = ReadBufferExtended(rel, forkNum, blkno, RBM_ZERO_AND_LOCK,
                                 NULL);
    }

    /* ref count and lock type are correct */

    /* initialize the page */
    _hash_pageinit(BufferGetPage(buf), BufferGetPageSize(buf));

    return buf;
}

Bucket _hash_hashkey2bucket	(	uint32	hashkey,
		uint32	maxbucket,
		uint32	highmask,
		uint32	lowmask
	)

Definition at line 125 of file hashutil.c.

Referenced by _h_indexbuild(), _hash_getbucketbuf_from_hashkey(), _hash_splitbucket(), comparetup_index_hash(), and hashbucketcleanup().

{
    Bucket      bucket;

    bucket = hashkey & highmask;
    if (bucket > maxbucket)
        bucket = bucket & lowmask;

    return bucket;
}

uint32 _hash_init	(	Relation	rel,
		double	num_tuples,
		ForkNumber	forkNum
	)

Definition at line 335 of file hashpage.c.

References _hash_getnewbuf(), _hash_init_metabuffer(), _hash_initbitmapbuffer(), _hash_initbuf(), _hash_relbuf(), xl_hash_init_bitmap_page::bmsize, BUCKET_TO_BLKNO, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, CHECK_FOR_INTERRUPTS, elog, ereport, errcode(), errmsg(), ERROR, xl_hash_init_meta_page::ffactor, HASH_DEFAULT_FILLFACTOR, HASH_MAX_BITMAPS, HASH_METAPAGE, HashMetaPageData::hashm_bmsize, HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_nmaps, HashMetaPageData::hashm_procid, HashPageGetMeta, HASHSTANDARD_PROC, i, index_getprocid(), INIT_FORKNUM, LH_BUCKET_PAGE, LockBuffer(), log_newpage(), MarkBufferDirty(), MAXALIGN, xl_hash_init_meta_page::num_tuples, PageSetLSN, xl_hash_init_meta_page::procid, RelationData::rd_node, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationGetNumberOfBlocksInFork(), RelationGetRelationName, RelationGetTargetPageUsage, RelationNeedsWAL, SizeOfHashInitBitmapPage, SizeOfHashInitMetaPage, XLOG_HASH_INIT_BITMAP_PAGE, XLOG_HASH_INIT_META_PAGE, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by hashbuild(), and hashbuildempty().

{
    Buffer      metabuf;
    Buffer      buf;
    Buffer      bitmapbuf;
    Page        pg;
    HashMetaPage metap;
    RegProcedure procid;
    int32       data_width;
    int32       item_width;
    int32       ffactor;
    uint32      num_buckets;
    uint32      i;
    bool        use_wal;

    /* safety check */
    if (RelationGetNumberOfBlocksInFork(rel, forkNum) != 0)
        elog(ERROR, "cannot initialize non-empty hash index \"%s\"",
             RelationGetRelationName(rel));

    /*
     * WAL log creation of pages if the relation is persistent, or this is the
     * init fork.  Init forks for unlogged relations always need to be WAL
     * logged.
     */
    use_wal = RelationNeedsWAL(rel) || forkNum == INIT_FORKNUM;

    /*
     * Determine the target fill factor (in tuples per bucket) for this index.
     * The idea is to make the fill factor correspond to pages about as full
     * as the user-settable fillfactor parameter says.  We can compute it
     * exactly since the index datatype (i.e. uint32 hash key) is fixed-width.
     */
    data_width = sizeof(uint32);
    item_width = MAXALIGN(sizeof(IndexTupleData)) + MAXALIGN(data_width) +
        sizeof(ItemIdData);     /* include the line pointer */
    ffactor = RelationGetTargetPageUsage(rel, HASH_DEFAULT_FILLFACTOR) / item_width;
    /* keep to a sane range */
    if (ffactor < 10)
        ffactor = 10;

    procid = index_getprocid(rel, 1, HASHSTANDARD_PROC);

    /*
     * We initialize the metapage, the first N bucket pages, and the first
     * bitmap page in sequence, using _hash_getnewbuf to cause smgrextend()
     * calls to occur.  This ensures that the smgr level has the right idea of
     * the physical index length.
     *
     * Critical section not required, because on error the creation of the
     * whole relation will be rolled back.
     */
    metabuf = _hash_getnewbuf(rel, HASH_METAPAGE, forkNum);
    _hash_init_metabuffer(metabuf, num_tuples, procid, ffactor, false);
    MarkBufferDirty(metabuf);

    pg = BufferGetPage(metabuf);
    metap = HashPageGetMeta(pg);

    /* XLOG stuff */
    if (use_wal)
    {
        xl_hash_init_meta_page xlrec;
        XLogRecPtr  recptr;

        xlrec.num_tuples = num_tuples;
        xlrec.procid = metap->hashm_procid;
        xlrec.ffactor = metap->hashm_ffactor;

        XLogBeginInsert();
        XLogRegisterData((char *) &xlrec, SizeOfHashInitMetaPage);
        XLogRegisterBuffer(0, metabuf, REGBUF_WILL_INIT);

        recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_INIT_META_PAGE);

        PageSetLSN(BufferGetPage(metabuf), recptr);
    }

    num_buckets = metap->hashm_maxbucket + 1;

    /*
     * Release buffer lock on the metapage while we initialize buckets.
     * Otherwise, we'll be in interrupt holdoff and the CHECK_FOR_INTERRUPTS
     * won't accomplish anything.  It's a bad idea to hold buffer locks for
     * long intervals in any case, since that can block the bgwriter.
     */
    LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);

    /*
     * Initialize and WAL Log the first N buckets
     */
    for (i = 0; i < num_buckets; i++)
    {
        BlockNumber blkno;

        /* Allow interrupts, in case N is huge */
        CHECK_FOR_INTERRUPTS();

        blkno = BUCKET_TO_BLKNO(metap, i);
        buf = _hash_getnewbuf(rel, blkno, forkNum);
        _hash_initbuf(buf, metap->hashm_maxbucket, i, LH_BUCKET_PAGE, false);
        MarkBufferDirty(buf);

        if (use_wal)
            log_newpage(&rel->rd_node,
                        forkNum,
                        blkno,
                        BufferGetPage(buf),
                        true);
        _hash_relbuf(rel, buf);
    }

    /* Now reacquire buffer lock on metapage */
    LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);

    /*
     * Initialize bitmap page
     */
    bitmapbuf = _hash_getnewbuf(rel, num_buckets + 1, forkNum);
    _hash_initbitmapbuffer(bitmapbuf, metap->hashm_bmsize, false);
    MarkBufferDirty(bitmapbuf);

    /* add the new bitmap page to the metapage's list of bitmaps */
    /* metapage already has a write lock */
    if (metap->hashm_nmaps >= HASH_MAX_BITMAPS)
        ereport(ERROR,
                (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                 errmsg("out of overflow pages in hash index \"%s\"",
                        RelationGetRelationName(rel))));

    metap->hashm_mapp[metap->hashm_nmaps] = num_buckets + 1;

    metap->hashm_nmaps++;
    MarkBufferDirty(metabuf);

    /* XLOG stuff */
    if (use_wal)
    {
        xl_hash_init_bitmap_page xlrec;
        XLogRecPtr  recptr;

        xlrec.bmsize = metap->hashm_bmsize;

        XLogBeginInsert();
        XLogRegisterData((char *) &xlrec, SizeOfHashInitBitmapPage);
        XLogRegisterBuffer(0, bitmapbuf, REGBUF_WILL_INIT);

        /*
         * This is safe only because nobody else can be modifying the index at
         * this stage; it's only visible to the transaction that is creating
         * it.
         */
        XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);

        recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_INIT_BITMAP_PAGE);

        PageSetLSN(BufferGetPage(bitmapbuf), recptr);
        PageSetLSN(BufferGetPage(metabuf), recptr);
    }

    /* all done */
    _hash_relbuf(rel, bitmapbuf);
    _hash_relbuf(rel, metabuf);

    return num_buckets;
}

void _hash_init_metabuffer	(	Buffer	buf,
		double	num_tuples,
		RegProcedure	procid,
		uint16	ffactor,
		bool	initpage
	)

Definition at line 506 of file hashpage.c.

References _hash_get_totalbuckets(), _hash_log2(), _hash_pageinit(), _hash_spareindex(), Assert, BMPG_MASK, BMPG_SHIFT, BufferGetPage, BufferGetPageSize, BYTE_TO_BIT, HASH_MAGIC, HASH_MAX_SPLITPOINTS, HASH_VERSION, HashGetMaxBitmapSize, HashMetaPageData::hashm_bmshift, HashMetaPageData::hashm_bmsize, HashMetaPageData::hashm_bsize, HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_firstfree, HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_magic, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_nmaps, HashMetaPageData::hashm_ntuples, HashMetaPageData::hashm_ovflpoint, HashMetaPageData::hashm_procid, HashMetaPageData::hashm_spares, HashMetaPageData::hashm_version, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, HashPageGetMeta, i, InvalidBlockNumber, LH_META_PAGE, MemSet, and PageGetSpecialPointer.

Referenced by _hash_init(), and hash_xlog_init_meta_page().

{
    HashMetaPage metap;
    HashPageOpaque pageopaque;
    Page        page;
    double      dnumbuckets;
    uint32      num_buckets;
    uint32      spare_index;
    uint32      i;

    /*
     * Choose the number of initial bucket pages to match the fill factor
     * given the estimated number of tuples.  We round up the result to the
     * total number of buckets which has to be allocated before using its
     * _hashm_spare element. However always force at least 2 bucket pages. The
     * upper limit is determined by considerations explained in
     * _hash_expandtable().
     */
    dnumbuckets = num_tuples / ffactor;
    if (dnumbuckets <= 2.0)
        num_buckets = 2;
    else if (dnumbuckets >= (double) 0x40000000)
        num_buckets = 0x40000000;
    else
        num_buckets = _hash_get_totalbuckets(_hash_spareindex(dnumbuckets));

    spare_index = _hash_spareindex(num_buckets);
    Assert(spare_index < HASH_MAX_SPLITPOINTS);

    page = BufferGetPage(buf);
    if (initpage)
        _hash_pageinit(page, BufferGetPageSize(buf));

    pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
    pageopaque->hasho_prevblkno = InvalidBlockNumber;
    pageopaque->hasho_nextblkno = InvalidBlockNumber;
    pageopaque->hasho_bucket = -1;
    pageopaque->hasho_flag = LH_META_PAGE;
    pageopaque->hasho_page_id = HASHO_PAGE_ID;

    metap = HashPageGetMeta(page);

    metap->hashm_magic = HASH_MAGIC;
    metap->hashm_version = HASH_VERSION;
    metap->hashm_ntuples = 0;
    metap->hashm_nmaps = 0;
    metap->hashm_ffactor = ffactor;
    metap->hashm_bsize = HashGetMaxBitmapSize(page);
    /* find largest bitmap array size that will fit in page size */
    for (i = _hash_log2(metap->hashm_bsize); i > 0; --i)
    {
        if ((1 << i) <= metap->hashm_bsize)
            break;
    }
    Assert(i > 0);
    metap->hashm_bmsize = 1 << i;
    metap->hashm_bmshift = i + BYTE_TO_BIT;
    Assert((1 << BMPG_SHIFT(metap)) == (BMPG_MASK(metap) + 1));

    /*
     * Label the index with its primary hash support function's OID.  This is
     * pretty useless for normal operation (in fact, hashm_procid is not used
     * anywhere), but it might be handy for forensic purposes so we keep it.
     */
    metap->hashm_procid = procid;

    /*
     * We initialize the index with N buckets, 0 .. N-1, occupying physical
     * blocks 1 to N.  The first freespace bitmap page is in block N+1.
     */
    metap->hashm_maxbucket = num_buckets - 1;

    /*
     * Set highmask as next immediate ((2 ^ x) - 1), which should be
     * sufficient to cover num_buckets.
     */
    metap->hashm_highmask = (1 << (_hash_log2(num_buckets + 1))) - 1;
    metap->hashm_lowmask = (metap->hashm_highmask >> 1);

    MemSet(metap->hashm_spares, 0, sizeof(metap->hashm_spares));
    MemSet(metap->hashm_mapp, 0, sizeof(metap->hashm_mapp));

    /* Set up mapping for one spare page after the initial splitpoints */
    metap->hashm_spares[spare_index] = 1;
    metap->hashm_ovflpoint = spare_index;
    metap->hashm_firstfree = 0;

    /*
     * Set pd_lower just past the end of the metadata.  This is to log full
     * page image of metapage in xloginsert.c.
     */
    ((PageHeader) page)->pd_lower =
        ((char *) metap + sizeof(HashMetaPageData)) - (char *) page;
}

void _hash_initbitmapbuffer	(	Buffer	buf,
		uint16	bmsize,
		bool	initpage
	)

Definition at line 739 of file hashovfl.c.

References _hash_pageinit(), BufferGetPage, BufferGetPageSize, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, HashPageGetBitmap, InvalidBlockNumber, LH_BITMAP_PAGE, MemSet, and PageGetSpecialPointer.

Referenced by _hash_addovflpage(), _hash_init(), hash_xlog_add_ovfl_page(), and hash_xlog_init_bitmap_page().

{
    Page        pg;
    HashPageOpaque op;
    uint32     *freep;

    pg = BufferGetPage(buf);

    /* initialize the page */
    if (initpage)
        _hash_pageinit(pg, BufferGetPageSize(buf));

    /* initialize the page's special space */
    op = (HashPageOpaque) PageGetSpecialPointer(pg);
    op->hasho_prevblkno = InvalidBlockNumber;
    op->hasho_nextblkno = InvalidBlockNumber;
    op->hasho_bucket = -1;
    op->hasho_flag = LH_BITMAP_PAGE;
    op->hasho_page_id = HASHO_PAGE_ID;

    /* set all of the bits to 1 */
    freep = HashPageGetBitmap(pg);
    MemSet(freep, 0xFF, bmsize);

    /*
     * Set pd_lower just past the end of the bitmap page data.  We could even
     * set pd_lower equal to pd_upper, but this is more precise and makes the
     * page look compressible to xlog.c.
     */
    ((PageHeader) pg)->pd_lower = ((char *) freep + bmsize) - (char *) pg;
}

void _hash_initbuf	(	Buffer	buf,
		uint32	max_bucket,
		uint32	num_bucket,
		uint32	flag,
		bool	initpage
	)

Definition at line 165 of file hashpage.c.

References _hash_pageinit(), BufferGetPage, BufferGetPageSize, flag(), HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, InvalidBlockNumber, and PageGetSpecialPointer.

Referenced by _hash_init(), hash_xlog_add_ovfl_page(), and hash_xlog_split_allocate_page().

{
    HashPageOpaque pageopaque;
    Page        page;

    page = BufferGetPage(buf);

    /* initialize the page */
    if (initpage)
        _hash_pageinit(page, BufferGetPageSize(buf));

    pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);

    /*
     * Set hasho_prevblkno with current hashm_maxbucket. This value will be
     * used to validate cached HashMetaPageData. See
     * _hash_getbucketbuf_from_hashkey().
     */
    pageopaque->hasho_prevblkno = max_bucket;
    pageopaque->hasho_nextblkno = InvalidBlockNumber;
    pageopaque->hasho_bucket = num_bucket;
    pageopaque->hasho_flag = flag;
    pageopaque->hasho_page_id = HASHO_PAGE_ID;
}

void _hash_kill_items

(

IndexScanDesc

scan

)

Definition at line 544 of file hashutil.c.

References _hash_getbuf(), _hash_relbuf(), Assert, buf, HashScanPosData::buf, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage, HashScanPosData::currPage, HashScanOpaqueData::currPos, HashScanPosData::firstItem, HASH_READ, HashScanPosIsPinned, HashScanPosIsValid, HashScanOpaqueData::hashso_bucket_buf, HashScanPosItem::heapTid, i, HashScanPosItem::indexOffset, IndexScanDescData::indexRelation, ItemIdMarkDead, ItemPointerEquals(), HashScanPosData::items, HashScanOpaqueData::killedItems, LH_OVERFLOW_PAGE, LH_PAGE_HAS_DEAD_TUPLES, LockBuffer(), MarkBufferDirtyHint(), HashScanOpaqueData::numKilled, OffsetNumberNext, IndexScanDescData::opaque, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, and IndexTupleData::t_tid.

Referenced by _hash_next(), _hash_readpage(), hashendscan(), and hashrescan().

{
    HashScanOpaque so = (HashScanOpaque) scan->opaque;
    Relation    rel = scan->indexRelation;
    BlockNumber blkno;
    Buffer      buf;
    Page        page;
    HashPageOpaque opaque;
    OffsetNumber offnum,
                maxoff;
    int         numKilled = so->numKilled;
    int         i;
    bool        killedsomething = false;
    bool        havePin = false;

    Assert(so->numKilled > 0);
    Assert(so->killedItems != NULL);
    Assert(HashScanPosIsValid(so->currPos));

    /*
     * Always reset the scan state, so we don't look for same items on other
     * pages.
     */
    so->numKilled = 0;

    blkno = so->currPos.currPage;
    if (HashScanPosIsPinned(so->currPos))
    {
        /*
         * We already have pin on this buffer, so, all we need to do is
         * acquire lock on it.
         */
        havePin = true;
        buf = so->currPos.buf;
        LockBuffer(buf, BUFFER_LOCK_SHARE);
    }
    else
        buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);

    page = BufferGetPage(buf);
    opaque = (HashPageOpaque) PageGetSpecialPointer(page);
    maxoff = PageGetMaxOffsetNumber(page);

    for (i = 0; i < numKilled; i++)
    {
        int         itemIndex = so->killedItems[i];
        HashScanPosItem *currItem = &so->currPos.items[itemIndex];

        offnum = currItem->indexOffset;

        Assert(itemIndex >= so->currPos.firstItem &&
               itemIndex <= so->currPos.lastItem);

        while (offnum <= maxoff)
        {
            ItemId      iid = PageGetItemId(page, offnum);
            IndexTuple  ituple = (IndexTuple) PageGetItem(page, iid);

            if (ItemPointerEquals(&ituple->t_tid, &currItem->heapTid))
            {
                /* found the item */
                ItemIdMarkDead(iid);
                killedsomething = true;
                break;          /* out of inner search loop */
            }
            offnum = OffsetNumberNext(offnum);
        }
    }

    /*
     * Since this can be redone later if needed, mark as dirty hint. Whenever
     * we mark anything LP_DEAD, we also set the page's
     * LH_PAGE_HAS_DEAD_TUPLES flag, which is likewise just a hint.
     */
    if (killedsomething)
    {
        opaque->hasho_flag |= LH_PAGE_HAS_DEAD_TUPLES;
        MarkBufferDirtyHint(buf, true);
    }

    if (so->hashso_bucket_buf == so->currPos.buf ||
        havePin)
        LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
    else
        _hash_relbuf(rel, buf);
}

uint32 _hash_log2

(

uint32

num

)

Definition at line 141 of file hashutil.c.

References i.

Referenced by _h_spoolinit(), _hash_init_metabuffer(), and _hash_spareindex().

{
    uint32      i,
                limit;

    limit = 1;
    for (i = 0; limit < num; limit <<= 1, i++)
        ;
    return i;
}

bool _hash_next	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 47 of file hashsearch.c.

References _hash_dropbuf(), _hash_dropscanbuf(), _hash_getbuf(), _hash_kill_items(), _hash_readpage(), BlockNumberIsValid, buf, BufferGetPage, HashScanOpaqueData::currPos, HashScanPosData::firstItem, HASH_READ, HashScanPosInvalidate, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_split_bucket_buf, IndexScanDescData::indexRelation, HashScanPosData::itemIndex, HashScanPosData::items, HashScanPosData::lastItem, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, HashScanPosData::nextPage, HashScanOpaqueData::numKilled, IndexScanDescData::opaque, HashScanPosData::prevPage, ScanDirectionIsForward, HeapTupleData::t_self, TestForOldSnapshot(), IndexScanDescData::xs_ctup, and IndexScanDescData::xs_snapshot.

Referenced by hashgetbitmap(), and hashgettuple().

{
    Relation    rel = scan->indexRelation;
    HashScanOpaque so = (HashScanOpaque) scan->opaque;
    HashScanPosItem *currItem;
    BlockNumber blkno;
    Buffer      buf;
    bool        end_of_scan = false;

    /*
     * Advance to the next tuple on the current page; or if done, try to read
     * data from the next or previous page based on the scan direction. Before
     * moving to the next or previous page make sure that we deal with all the
     * killed items.
     */
    if (ScanDirectionIsForward(dir))
    {
        if (++so->currPos.itemIndex > so->currPos.lastItem)
        {
            if (so->numKilled > 0)
                _hash_kill_items(scan);

            blkno = so->currPos.nextPage;
            if (BlockNumberIsValid(blkno))
            {
                buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
                TestForOldSnapshot(scan->xs_snapshot, rel, BufferGetPage(buf));
                if (!_hash_readpage(scan, &buf, dir))
                    end_of_scan = true;
            }
            else
                end_of_scan = true;
        }
    }
    else
    {
        if (--so->currPos.itemIndex < so->currPos.firstItem)
        {
            if (so->numKilled > 0)
                _hash_kill_items(scan);

            blkno = so->currPos.prevPage;
            if (BlockNumberIsValid(blkno))
            {
                buf = _hash_getbuf(rel, blkno, HASH_READ,
                                   LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
                TestForOldSnapshot(scan->xs_snapshot, rel, BufferGetPage(buf));

                /*
                 * We always maintain the pin on bucket page for whole scan
                 * operation, so releasing the additional pin we have acquired
                 * here.
                 */
                if (buf == so->hashso_bucket_buf ||
                    buf == so->hashso_split_bucket_buf)
                    _hash_dropbuf(rel, buf);

                if (!_hash_readpage(scan, &buf, dir))
                    end_of_scan = true;
            }
            else
                end_of_scan = true;
        }
    }

    if (end_of_scan)
    {
        _hash_dropscanbuf(rel, so);
        HashScanPosInvalidate(so->currPos);
        return false;
    }

    /* OK, itemIndex says what to return */
    currItem = &so->currPos.items[so->currPos.itemIndex];
    scan->xs_ctup.t_self = currItem->heapTid;

    return true;
}

uint32 _hash_ovflblkno_to_bitno	(	HashMetaPage	metap,
		BlockNumber	ovflblkno
	)

Definition at line 61 of file hashovfl.c.

References _hash_get_totalbuckets(), ereport, errcode(), errmsg(), ERROR, HashMetaPageData::hashm_ovflpoint, HashMetaPageData::hashm_spares, and i.

Referenced by _hash_freeovflpage(), and hash_bitmap_info().

{
    uint32      splitnum = metap->hashm_ovflpoint;
    uint32      i;
    uint32      bitnum;

    /* Determine the split number containing this page */
    for (i = 1; i <= splitnum; i++)
    {
        if (ovflblkno <= (BlockNumber) _hash_get_totalbuckets(i))
            break;              /* oops */
        bitnum = ovflblkno - _hash_get_totalbuckets(i);

        /*
         * bitnum has to be greater than number of overflow page added in
         * previous split point. The overflow page at this splitnum (i) if any
         * should start from (_hash_get_totalbuckets(i) +
         * metap->hashm_spares[i - 1] + 1).
         */
        if (bitnum > metap->hashm_spares[i - 1] &&
            bitnum <= metap->hashm_spares[i])
            return bitnum - 1;  /* -1 to convert 1-based to 0-based */
    }

    ereport(ERROR,
            (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
             errmsg("invalid overflow block number %u", ovflblkno)));
    return 0;                   /* keep compiler quiet */
}

void _hash_pageinit	(	Page	page,
		Size	size
	)

Definition at line 606 of file hashpage.c.

References PageInit().

Referenced by _hash_alloc_buckets(), _hash_freeovflpage(), _hash_getinitbuf(), _hash_getnewbuf(), _hash_init_metabuffer(), _hash_initbitmapbuffer(), _hash_initbuf(), and hash_xlog_squeeze_page().

{
    PageInit(page, size, sizeof(HashPageOpaqueData));
}

void _hash_pgaddmultitup	(	Relation	rel,
		Buffer	buf,
		IndexTuple *	itups, </