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	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	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	HASH_METAPAGE   0 /* metapage is always block 0 */
#define	HASH_MAGIC   0x6440640
#define	HASH_VERSION
#define	HASH_MAX_BITMAPS   128
#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	HASHPROC   1
#define	HASHNProcs   1

Typedefs
typedef uint32	Bucket
typedef struct HashPageOpaqueData	HashPageOpaqueData
typedef HashPageOpaqueData *	HashPageOpaque
typedef struct HashScanPosItem	HashScanPosItem
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_uint32 (uint32 k)
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)
bool	_hash_step (IndexScanDesc scan, Buffer *bufP, 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 245 of file hash.h.

Referenced by _hash_addovflpage().

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

Definition at line 272 of file hash.h.

Referenced by _hash_addovflpage(), and _hash_firstfreebit().

#define BMPG_MASK

(

metap

)

(BMPGSZ_BIT(metap) - 1)

Definition at line 257 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 256 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 255 of file hash.h.

Referenced by _hash_addovflpage().

#define BMPGSZ_BYTE

(

metap

)

((metap)->hashm_bmsize)

Definition at line 254 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 244 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 275 of file hash.h.

#define H_BUCKET_BEING_POPULATED

(

opaque

)

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

Definition at line 89 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 88 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 90 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 87 of file hash.h.

Referenced by _hash_expandtable(), and hashbulkdelete().

#define HASH_DEFAULT_FILLFACTOR   75

Definition at line 239 of file hash.h.

Referenced by _hash_init().

#define HASH_MAGIC   0x6440640

Definition at line 160 of file hash.h.

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

#define HASH_MAX_BITMAPS   128

Definition at line 188 of file hash.h.

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

#define HASH_MAX_SPLITPOINT_GROUP   32

Definition at line 196 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 197 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 158 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 238 of file hash.h.

#define HASH_NOLOCK   (-1)

Definition at line 284 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 282 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_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 193 of file hash.h.

Referenced by _hash_get_totalbuckets(), and _hash_spareindex().

#define HASH_SPLITPOINT_PHASE_BITS   2

Definition at line 190 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 192 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 191 of file hash.h.

#define HASH_VERSION

Value:

3       /* 3 signifies multi-phased bucket allocation
                                 * to reduce doubling */

Definition at line 161 of file hash.h.

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

#define HASH_WRITE   BUFFER_LOCK_EXCLUSIVE

Definition at line 283 of file hash.h.

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

#define HashGetMaxBitmapSize

(

page

)

Value:

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

Definition at line 262 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 230 of file hash.h.

Referenced by _hash_doinsert().

#define HASHNProcs   1

Definition at line 298 of file hash.h.

Referenced by hashhandler().

#define HASHO_PAGE_ID   0xFF80

Definition at line 98 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 259 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 266 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 HASHPROC   1

Definition at line 297 of file hash.h.

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

#define HTEqualStrategyNumber   1

Definition at line 289 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 290 of file hash.h.

Referenced by hashhandler(), and hashvalidate().

#define INDEX_MOVED_BY_SPLIT_MASK   0x2000

Definition at line 236 of file hash.h.

Referenced by _hash_splitbucket(), and _hash_step().

#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 277 of file hash.h.

Referenced by _hash_freeovflpage(), and hash_bitmap_info().

#define LH_BITMAP_PAGE   (1 << 2)

Definition at line 55 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 57 of file hash.h.

Referenced by _hash_expandtable(), and _hash_splitbucket().

#define LH_BUCKET_BEING_SPLIT   (1 << 5)

Definition at line 58 of file hash.h.

Referenced by _hash_expandtable(), and _hash_splitbucket().

#define LH_BUCKET_NEEDS_SPLIT_CLEANUP   (1 << 6)

Definition at line 59 of file hash.h.

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

#define LH_BUCKET_PAGE   (1 << 1)

Definition at line 54 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_readprev(), _hash_step(), 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 56 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 53 of file hash.h.

Referenced by _hash_addovflpage(), _hash_doinsert(), _hash_finish_split(), _hash_first(), _hash_freeovflpage(), _hash_next(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_readnext(), _hash_readprev(), _hash_splitbucket(), _hash_squeezebucket(), _hash_step(), 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 60 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 62 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 52 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 SETBIT	(		A,
			N
	)		((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))

Definition at line 276 of file hash.h.

Typedef Documentation

typedef uint32 Bucket

Definition at line 34 of file hash.h.

typedef HashMetaPageData* HashMetaPage

Definition at line 225 of file hash.h.

typedef struct HashMetaPageData HashMetaPageData

typedef HashPageOpaqueData* HashPageOpaque

Definition at line 85 of file hash.h.

typedef struct HashPageOpaqueData HashPageOpaqueData

typedef HashScanOpaqueData* HashScanOpaque

Definition at line 152 of file hash.h.

typedef struct HashScanOpaqueData HashScanOpaqueData

typedef struct HashScanPosItem HashScanPosItem

typedef struct HSpool HSpool

Definition at line 386 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, NULL, 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(), NULL, 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_step().

{
    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_step().

{
    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_first(), _hash_freeovflpage(), _hash_getbuf(), _hash_getbuf_with_condlock_cleanup(), _hash_getbuf_with_strategy(), _hash_next(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_step(), 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_step().

{
    /*
     * 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(), HASHPROC, 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, HASHPROC);
    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(), HASHPROC, 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,
                                  HASHPROC);
    if (!RegProcedureIsValid(hash_proc))
        elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
             HASHPROC, 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, NULL, 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_first(), _hash_getbucketbuf_from_hashkey(), _hash_readprev(), and hashbulkdelete().

{
    ReleaseBuffer(buf);
}

void _hash_dropscanbuf	(	Relation	rel,
		HashScanOpaque	so
	)

Definition at line 297 of file hashpage.c.

References _hash_dropbuf(), BufferIsValid, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_curbuf, HashScanOpaqueData::hashso_split_bucket_buf, and InvalidBuffer.

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

{
    /* release pin we hold on primary bucket page */
    if (BufferIsValid(so->hashso_bucket_buf) &&
        so->hashso_bucket_buf != so->hashso_curbuf)
        _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->hashso_curbuf)
        _hash_dropbuf(rel, so->hashso_split_bucket_buf);
    so->hashso_split_bucket_buf = InvalidBuffer;

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

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

void _hash_expandtable	(	Relation	rel,
		Buffer	metabuf
	)

Definition at line 615 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, NULL, 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 locks and pins on primary buckets. */
    _hash_relbuf(rel, buf_oblkno);
    _hash_relbuf(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 1323 of file hashpage.c.

References _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_relbuf(rel, bucket_nbuf);
    LockBuffer(obuf, BUFFER_LOCK_UNLOCK);
    hash_destroy(tidhtab);
}

bool _hash_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 222 of file hashsearch.c.

References _hash_checkpage(), _hash_datum2hashkey(), _hash_datum2hashkey_type(), _hash_dropbuf(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_getbuf(), _hash_readnext(), _hash_step(), Assert, BlockNumberIsValid, buf, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage, cur, ereport, errcode(), errmsg(), ERROR, H_BUCKET_BEING_POPULATED, HASH_READ, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_curpos, HashScanOpaqueData::hashso_heappos, HashScanOpaqueData::hashso_sk_hash, HashScanOpaqueData::hashso_split_bucket_buf, HTEqualStrategyNumber, IndexScanDescData::indexRelation, InvalidBuffer, InvalidOid, ItemPointerGetOffsetNumber, ItemPointerSetInvalid, IndexScanDescData::keyData, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, LockBuffer(), NULL, IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, PageGetItem, PageGetItemId, PageGetSpecialPointer, pgstat_count_index_scan, RelationData::rd_opcintype, ScanDirectionIsBackward, SK_ISNULL, TestForOldSnapshot(), 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;
    IndexTuple  itup;
    ItemPointer current;
    OffsetNumber offnum;

    pgstat_count_index_scan(rel);

    current = &(so->hashso_curpos);
    ItemPointerSetInvalid(current);

    /*
     * 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);
    }

    /* Now find the first tuple satisfying the qualification */
    if (!_hash_step(scan, &buf, dir))
        return false;

    /* if we're here, _hash_step found a valid tuple */
    offnum = ItemPointerGetOffsetNumber(current);
    _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
    page = BufferGetPage(buf);
    itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
    so->hashso_heappos = itup->t_tid;

    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_pgaddmultitup(), _hash_pgaddtup(), _hash_splitbucket(), _hash_step(), 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 1528 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, NULL, 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_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 1470 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(), NULL, 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, NULL, 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(), NULL, 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, HASHPROC, i, index_getprocid(), 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;

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

    /*
     * 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, HASHPROC);

    /*
     * 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 (RelationNeedsWAL(rel))
    {
        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);

        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 (RelationNeedsWAL(rel))
    {
        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 497 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 529 of file hashutil.c.

References Assert, BufferGetPage, HashScanOpaqueData::hashso_curbuf, HashScanPosItem::heapTid, i, HashScanPosItem::indexOffset, ItemIdMarkDead, ItemPointerEquals(), HashScanOpaqueData::killedItems, LH_PAGE_HAS_DEAD_TUPLES, MarkBufferDirtyHint(), NULL, HashScanOpaqueData::numKilled, OffsetNumberNext, IndexScanDescData::opaque, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, and IndexTupleData::t_tid.

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

{
    HashScanOpaque so = (HashScanOpaque) scan->opaque;
    Page        page;
    HashPageOpaque opaque;
    OffsetNumber offnum,
                maxoff;
    int         numKilled = so->numKilled;
    int         i;
    bool        killedsomething = false;

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

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

    page = BufferGetPage(so->hashso_curbuf);
    opaque = (HashPageOpaque) PageGetSpecialPointer(page);
    maxoff = PageGetMaxOffsetNumber(page);

    for (i = 0; i < numKilled; i++)
    {
        offnum = so->killedItems[i].indexOffset;

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

            if (ItemPointerEquals(&ituple->t_tid, &so->killedItems[i].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(so->hashso_curbuf, true);
    }
}

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 34 of file hashsearch.c.

References _hash_checkpage(), _hash_step(), Assert, buf, BufferGetPage, BufferIsValid, HashScanOpaqueData::hashso_curbuf, HashScanOpaqueData::hashso_curpos, HashScanOpaqueData::hashso_heappos, IndexScanDescData::indexRelation, ItemPointerGetOffsetNumber, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, IndexScanDescData::opaque, PageGetItem, and PageGetItemId.

Referenced by hashgetbitmap(), and hashgettuple().

{
    Relation    rel = scan->indexRelation;
    HashScanOpaque so = (HashScanOpaque) scan->opaque;
    Buffer      buf;
    Page        page;
    OffsetNumber offnum;
    ItemPointer current;
    IndexTuple  itup;

    /* we still have the buffer pinned and read-locked */
    buf = so->hashso_curbuf;
    Assert(BufferIsValid(buf));

    /*
     * step to next valid tuple.
     */
    if (!_hash_step(scan, &buf, dir))
        return false;

    /* if we're here, _hash_step found a valid tuple */
    current = &(so->hashso_curpos);
    offnum = ItemPointerGetOffsetNumber(current);
    _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
    page = BufferGetPage(buf);
    itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
    so->hashso_heappos = itup->t_tid;

    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 597 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,
		OffsetNumber *	itup_offsets,
		uint16	nitups
	)

Definition at line 297 of file hashinsert.c.

References _hash_binsearch(), _hash_checkpage(), _hash_get_indextuple_hashkey(), BufferGetPage, elog, ERROR, i, IndexTupleDSize, InvalidOffsetNumber, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, MAXALIGN, PageAddItem, and RelationGetRelationName.

Referenced by _hash_freeovflpage(), _hash_splitbucket(), and _hash_squeezebucket().

{
    OffsetNumber itup_off;
    Page        page;
    uint32      hashkey;
    int         i;

    _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
    page = BufferGetPage(buf);

    for (i = 0; i < nitups; i++)
    {
        Size        itemsize;

        itemsize = IndexTupleDSize(*itups[i]);
        itemsize = MAXALIGN(itemsize);

        /* Find where to insert the tuple (preserving page's hashkey ordering) */
        hashkey = _hash_get_indextuple_hashkey(itups[i]);
        itup_off = _hash_binsearch(page, hashkey);

        itup_offsets[i] = itup_off;

        if (PageAddItem(page, (Item) itups[i], itemsize, itup_off, false, false)
            == InvalidOffsetNumber)
            elog(ERROR, "failed to add index item to \"%s\"",
                 RelationGetRelationName(rel));
    }
}

OffsetNumber _hash_pgaddtup	(	Relation	rel,
		Buffer	buf,
		Size	itemsize,
		IndexTuple	itup
	)

Definition at line 266 of file hashinsert.c.

References _hash_binsearch(), _hash_checkpage(), _hash_get_indextuple_hashkey(), BufferGetPage, elog, ERROR, InvalidOffsetNumber, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, PageAddItem, and RelationGetRelationName.

Referenced by _hash_doinsert().

{
    OffsetNumber itup_off;
    Page        page;
    uint32      hashkey;

    _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
    page = BufferGetPage(buf);

    /* Find where to insert the tuple (preserving page's hashkey ordering) */
    hashkey = _hash_get_indextuple_hashkey(itup);
    itup_off = _hash_binsearch(page, hashkey);

    if (PageAddItem(page, (Item) itup, itemsize, itup_off, false, false)
        == InvalidOffsetNumber)
        elog(ERROR, "failed to add index item to \"%s\"",
             RelationGetRelationName(rel));

    return itup_off;
}

void _hash_relbuf	(	Relation	rel,
		Buffer	buf
	)

Definition at line 274 of file hashpage.c.

References UnlockReleaseBuffer().

Referenced by _hash_addovflpage(), _hash_doinsert(), _hash_expandtable(), _hash_finish_split(), _hash_freeovflpage(), _hash_get_newblock_from_oldbucket(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_init(), _hash_readnext(), _hash_readprev(), _hash_splitbucket(), _hash_squeezebucket(), hash_bitmap_info(), hashbucketcleanup(), hashbulkdelete(), pgstat_hash_page(), and pgstathashindex().

{
    UnlockReleaseBuffer(buf);
}

uint32 _hash_spareindex

(

uint32

num_bucket

)

Definition at line 157 of file hashutil.c.

References _hash_log2(), HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE, HASH_SPLITPOINT_PHASE_BITS, and HASH_SPLITPOINT_PHASE_MASK.

Referenced by _hash_expandtable(), and _hash_init_metabuffer().

{
    uint32      splitpoint_group;
    uint32      splitpoint_phases;

    splitpoint_group = _hash_log2(num_bucket);

    if (splitpoint_group < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
        return splitpoint_group;

    /* account for single-phase groups */
    splitpoint_phases = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;

    /* account for multi-phase groups before splitpoint_group */
    splitpoint_phases +=
        ((splitpoint_group - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) <<
         HASH_SPLITPOINT_PHASE_BITS);

    /* account for phases within current group */
    splitpoint_phases +=
        (((num_bucket - 1) >>
          (splitpoint_group - (HASH_SPLITPOINT_PHASE_BITS + 1))) &
         HASH_SPLITPOINT_PHASE_MASK);   /* to 0-based value. */

    return splitpoint_phases;
}

void _hash_squeezebucket	(	Relation	rel,
		Bucket	bucket,
		BlockNumber	bucket_blkno,
		Buffer	bucket_buf,
		BufferAccessStrategy	bstrategy
	)

Definition at line 804 of file hashovfl.c.

References _hash_freeovflpage(), _hash_getbuf_with_strategy(), _hash_pgaddmultitup(), _hash_relbuf(), Assert, BlockNumberIsValid, BUFFER_LOCK_UNLOCK, BufferGetPage, CopyIndexTuple(), END_CRIT_SECTION, FirstOffsetNumber, HASH_WRITE, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_prevblkno, i, IndexTupleDSize, InvalidBuffer, xl_hash_move_page_contents::is_prim_bucket_same_wrt, ItemIdIsDead, LH_OVERFLOW_PAGE, LockBuffer(), MarkBufferDirty(), MAXALIGN, MaxIndexTuplesPerPage, MaxOffsetNumber, xl_hash_move_page_contents::ntups, OffsetNumberNext, PageGetFreeSpaceForMultipleTuples(), PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, PageIndexMultiDelete(), PageIsEmpty, PageSetLSN,