#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "catalog/pg_am_d.h"
#include "common/hashfn.h"
#include "lib/stringinfo.h"
#include "storage/bufmgr.h"
#include "storage/lockdefs.h"
#include "utils/hsearch.h"
#include "utils/relcache.h"

Include dependency graph for hash.h:

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

Go to the source code of this file.

Data Structures
struct	HashPageOpaqueData

struct	HashScanPosItem

struct	HashScanPosData

struct	HashScanOpaqueData

struct	HashMetaPageData

struct	HashOptions

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	HashPageGetOpaque(page) ((HashPageOpaque) PageGetSpecialPointer(page))

#define	H_NEEDS_SPLIT_CLEANUP(opaque) (((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)

#define	H_BUCKET_BEING_SPLIT(opaque) (((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)

#define	H_BUCKET_BEING_POPULATED(opaque) (((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)

#define	H_HAS_DEAD_TUPLES(opaque) (((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)

#define	HASHO_PAGE_ID 0xFF80

#define	HashScanPosIsPinned(scanpos)

#define	HashScanPosIsValid(scanpos)

#define	HashScanPosInvalidate(scanpos)

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

#define	HASH_MAGIC 0x6440640

#define	HASH_VERSION 4

#define	HASH_MAX_BITMAPS Min(BLCKSZ / 8, 1024)

#define	HASH_SPLITPOINT_PHASE_BITS 2

#define	HASH_SPLITPOINT_PHASES_PER_GRP (1 << HASH_SPLITPOINT_PHASE_BITS)

#define	HASH_SPLITPOINT_PHASE_MASK (HASH_SPLITPOINT_PHASES_PER_GRP - 1)

#define	HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE 10

#define	HASH_MAX_SPLITPOINT_GROUP 32

#define	HASH_MAX_SPLITPOINTS

#define	HashGetFillFactor(relation)

#define	HashGetTargetPageUsage(relation) (BLCKSZ * HashGetFillFactor(relation) / 100)

#define	HashMaxItemSize(page)

#define	INDEX_MOVED_BY_SPLIT_MASK INDEX_AM_RESERVED_BIT

#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	HASHSTANDARD_PROC 1

#define	HASHEXTENDED_PROC 2

#define	HASHOPTIONS_PROC 3

#define	HASHNProcs 3

Typedefs
typedef uint32	Bucket

typedef struct HashPageOpaqueData	HashPageOpaqueData

typedef HashPageOpaqueData *	HashPageOpaque

typedef struct HashScanPosItem	HashScanPosItem

typedef struct HashScanPosData	HashScanPosData

typedef struct HashScanOpaqueData	HashScanOpaqueData

typedef HashScanOpaqueData *	HashScanOpaque

typedef struct HashMetaPageData	HashMetaPageData

typedef HashMetaPageData *	HashMetaPage

typedef struct HashOptions	HashOptions

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, bool indexUnchanged, 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)

void	hashadjustmembers (Oid opfamilyoid, Oid opclassoid, List operators, List functions)

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

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

void	_hash_pgaddmultitup (Relation rel, Buffer buf, IndexTuple itups, OffsetNumber itup_offsets, uint16 nitups)

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

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

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

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

uint32	_hash_ovflblkno_to_bitno (HashMetaPage metap, BlockNumber ovflblkno)

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

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

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

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

Buffer	_hash_getinitbuf (Relation rel, BlockNumber blkno)

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

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

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

void	_hash_relbuf (Relation rel, Buffer buf)

void	_hash_dropbuf (Relation rel, Buffer buf)

void	_hash_dropscanbuf (Relation rel, HashScanOpaque so)

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

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

void	_hash_pageinit (Page page, Size size)

void	_hash_expandtable (Relation rel, Buffer metabuf)

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

bool	_hash_next (IndexScanDesc scan, ScanDirection dir)

bool	_hash_first (IndexScanDesc scan, ScanDirection dir)

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

void	_h_spooldestroy (HSpool *hspool)

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

void	_h_indexbuild (HSpool *hspool, Relation heapRel)

bool	_hash_checkqual (IndexScanDesc scan, IndexTuple itup)

uint32	_hash_datum2hashkey (Relation rel, Datum key)

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

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

uint32	_hash_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 split_cleanup, IndexBulkDeleteCallback callback, void *callback_state)

Macro Definition Documentation

◆ ALL_SET

#define ALL_SET ((uint32) ~0)

Definition at line 302 of file hash.h.

◆ BITS_PER_MAP

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

Definition at line 329 of file hash.h.

◆ BMPG_MASK

#define BMPG_MASK ( metap ) (BMPGSZ_BIT(metap) - 1)

Definition at line 314 of file hash.h.

◆ BMPG_SHIFT

#define BMPG_SHIFT ( metap ) ((metap)->hashm_bmshift)

Definition at line 313 of file hash.h.

◆ BMPGSZ_BIT

#define BMPGSZ_BIT ( metap ) ((metap)->hashm_bmsize << BYTE_TO_BIT)

Definition at line 312 of file hash.h.

◆ BMPGSZ_BYTE

#define BMPGSZ_BYTE ( metap ) ((metap)->hashm_bmsize)

Definition at line 311 of file hash.h.

◆ BUCKET_TO_BLKNO

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

Definition at line 39 of file hash.h.

◆ BYTE_TO_BIT

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

Definition at line 301 of file hash.h.

◆ CLRBIT

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

Definition at line 332 of file hash.h.

◆ H_BUCKET_BEING_POPULATED

#define H_BUCKET_BEING_POPULATED ( opaque ) (((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)

Definition at line 92 of file hash.h.

◆ H_BUCKET_BEING_SPLIT

#define H_BUCKET_BEING_SPLIT ( opaque ) (((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)

Definition at line 91 of file hash.h.

◆ H_HAS_DEAD_TUPLES

#define H_HAS_DEAD_TUPLES ( opaque ) (((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)

Definition at line 93 of file hash.h.

◆ H_NEEDS_SPLIT_CLEANUP

#define H_NEEDS_SPLIT_CLEANUP ( opaque ) (((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)

Definition at line 90 of file hash.h.

◆ HASH_DEFAULT_FILLFACTOR

#define HASH_DEFAULT_FILLFACTOR 75

Definition at line 296 of file hash.h.

◆ HASH_MAGIC

#define HASH_MAGIC 0x6440640

Definition at line 200 of file hash.h.

◆ HASH_MAX_BITMAPS

#define HASH_MAX_BITMAPS Min(BLCKSZ / 8, 1024)

Definition at line 230 of file hash.h.

◆ HASH_MAX_SPLITPOINT_GROUP

#define HASH_MAX_SPLITPOINT_GROUP 32

Definition at line 238 of file hash.h.

◆ HASH_MAX_SPLITPOINTS

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

◆ HASH_METAPAGE

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

Definition at line 198 of file hash.h.

◆ HASH_MIN_FILLFACTOR

#define HASH_MIN_FILLFACTOR 10

Definition at line 295 of file hash.h.

◆ HASH_NOLOCK

#define HASH_NOLOCK (-1)

Definition at line 341 of file hash.h.

◆ HASH_READ

#define HASH_READ BUFFER_LOCK_SHARE

Definition at line 339 of file hash.h.

◆ HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE

#define HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE 10

Definition at line 235 of file hash.h.

◆ HASH_SPLITPOINT_PHASE_BITS

#define HASH_SPLITPOINT_PHASE_BITS 2

Definition at line 232 of file hash.h.

◆ HASH_SPLITPOINT_PHASE_MASK

#define HASH_SPLITPOINT_PHASE_MASK (HASH_SPLITPOINT_PHASES_PER_GRP - 1)

Definition at line 234 of file hash.h.

◆ HASH_SPLITPOINT_PHASES_PER_GRP

#define HASH_SPLITPOINT_PHASES_PER_GRP (1 << HASH_SPLITPOINT_PHASE_BITS)

Definition at line 233 of file hash.h.

◆ HASH_VERSION

#define HASH_VERSION 4

Definition at line 201 of file hash.h.

◆ HASH_WRITE

#define HASH_WRITE BUFFER_LOCK_EXCLUSIVE

Definition at line 340 of file hash.h.

◆ HASHEXTENDED_PROC

#define HASHEXTENDED_PROC 2

Definition at line 356 of file hash.h.

◆ HashGetFillFactor

#define HashGetFillFactor ( relation )

Value:

    (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
                 relation->rd_rel->relam == HASH_AM_OID), \
     (relation)->rd_options ? \
     ((HashOptions *) (relation)->rd_options)->fillfactor : \
     HASH_DEFAULT_FILLFACTOR)

Definition at line 275 of file hash.h.

◆ HashGetMaxBitmapSize

#define HashGetMaxBitmapSize ( page )

Value:

(PageGetPageSize((Page) page) - \

(MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(HashPageOpaqueData))))

Page

Pointer Page

Definition: bufpage.h:78

PageGetPageSize

static Size PageGetPageSize(Page page)

Definition: bufpage.h:273

SizeOfPageHeaderData

#define SizeOfPageHeaderData

Definition: bufpage.h:213

MAXALIGN

#define MAXALIGN(LEN)

Definition: c.h:747

HashPageOpaqueData

Definition: hash.h:78

Definition at line 319 of file hash.h.

◆ HashGetTargetPageUsage

#define HashGetTargetPageUsage ( relation ) (BLCKSZ * HashGetFillFactor(relation) / 100)

Definition at line 281 of file hash.h.

◆ HashMaxItemSize

#define HashMaxItemSize ( page )

Value:

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

Definition at line 287 of file hash.h.

◆ HASHNProcs

#define HASHNProcs 3

Definition at line 358 of file hash.h.

◆ HASHO_PAGE_ID

#define HASHO_PAGE_ID 0xFF80

Definition at line 101 of file hash.h.

◆ HASHOPTIONS_PROC

#define HASHOPTIONS_PROC 3

Definition at line 357 of file hash.h.

◆ HashPageGetBitmap

#define HashPageGetBitmap ( page ) ((uint32 *) PageGetContents(page))

Definition at line 316 of file hash.h.

◆ HashPageGetMeta

#define HashPageGetMeta ( page ) ((HashMetaPage) PageGetContents(page))

Definition at line 323 of file hash.h.

◆ HashPageGetOpaque

#define HashPageGetOpaque ( page ) ((HashPageOpaque) PageGetSpecialPointer(page))

Definition at line 88 of file hash.h.

◆ HashScanPosInvalidate

#define HashScanPosInvalidate ( scanpos )

Value:

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

Definition at line 144 of file hash.h.

◆ HashScanPosIsPinned

#define HashScanPosIsPinned ( scanpos )

Value:

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

Definition at line 130 of file hash.h.

◆ HashScanPosIsValid

#define HashScanPosIsValid ( scanpos )

Value:

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

Definition at line 137 of file hash.h.

◆ HASHSTANDARD_PROC

#define HASHSTANDARD_PROC 1

Definition at line 355 of file hash.h.

◆ INDEX_MOVED_BY_SPLIT_MASK

#define INDEX_MOVED_BY_SPLIT_MASK INDEX_AM_RESERVED_BIT

Definition at line 293 of file hash.h.

◆ InvalidBucket

#define InvalidBucket ((Bucket) 0xFFFFFFFF)

Definition at line 37 of file hash.h.

◆ ISSET

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

Definition at line 334 of file hash.h.

◆ LH_BITMAP_PAGE

#define LH_BITMAP_PAGE (1 << 2)

Definition at line 56 of file hash.h.

◆ LH_BUCKET_BEING_POPULATED

#define LH_BUCKET_BEING_POPULATED (1 << 4)

Definition at line 58 of file hash.h.

◆ LH_BUCKET_BEING_SPLIT

#define LH_BUCKET_BEING_SPLIT (1 << 5)

Definition at line 59 of file hash.h.

◆ LH_BUCKET_NEEDS_SPLIT_CLEANUP

#define LH_BUCKET_NEEDS_SPLIT_CLEANUP (1 << 6)

Definition at line 60 of file hash.h.

◆ LH_BUCKET_PAGE

#define LH_BUCKET_PAGE (1 << 1)

Definition at line 55 of file hash.h.

◆ LH_META_PAGE

#define LH_META_PAGE (1 << 3)

Definition at line 57 of file hash.h.

◆ LH_OVERFLOW_PAGE

#define LH_OVERFLOW_PAGE (1 << 0)

Definition at line 54 of file hash.h.

◆ LH_PAGE_HAS_DEAD_TUPLES

#define LH_PAGE_HAS_DEAD_TUPLES (1 << 7)

Definition at line 61 of file hash.h.

◆ LH_PAGE_TYPE

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

Definition at line 63 of file hash.h.

◆ LH_UNUSED_PAGE

#define LH_UNUSED_PAGE (0)

Definition at line 53 of file hash.h.

◆ SETBIT

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

Definition at line 333 of file hash.h.

Typedef Documentation

◆ Bucket

typedef uint32 Bucket

Definition at line 35 of file hash.h.

◆ HashMetaPage

typedef HashMetaPageData* HashMetaPage

Definition at line 267 of file hash.h.

◆ HashMetaPageData

typedef struct HashMetaPageData HashMetaPageData

◆ HashOptions

typedef struct HashOptions HashOptions

◆ HashPageOpaque

typedef HashPageOpaqueData* HashPageOpaque

Definition at line 86 of file hash.h.

◆ HashPageOpaqueData

typedef struct HashPageOpaqueData HashPageOpaqueData

◆ HashScanOpaque

typedef HashScanOpaqueData* HashScanOpaque

Definition at line 192 of file hash.h.

◆ HashScanOpaqueData

typedef struct HashScanOpaqueData HashScanOpaqueData

◆ HashScanPosData

typedef struct HashScanPosData HashScanPosData

◆ HashScanPosItem

typedef struct HashScanPosItem HashScanPosItem

◆ HSpool

typedef struct HSpool HSpool

Definition at line 446 of file hash.h.

Function Documentation

◆ _h_indexbuild()

void _h_indexbuild	(	HSpool *	hspool,
		Relation	heapRel
	)

Definition at line 120 of file hashsort.c.

 {
     IndexTuple  itup;
     int64       tups_done = 0;
 #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
  
         /* the tuples are sorted by hashkey, so pass 'sorted' as true */
         _hash_doinsert(hspool->index, itup, heapRel, true);
  
         pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
                                      ++tups_done);
     }
 }

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

Referenced by hashbuild().

◆ _h_spool()

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

Definition at line 109 of file hashsort.c.

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

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

Referenced by hashbuildCallback().

◆ _h_spooldestroy()

void _h_spooldestroy ( HSpool * hspool )

Definition at line 99 of file hashsort.c.

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

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

Referenced by hashbuild().

◆ _h_spoolinit()

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

Definition at line 60 of file hashsort.c.

 {
     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 = pg_nextpower2_32(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,
                                                    NULL,
                                                    TUPLESORT_NONE);
  
     return hspool;
 }

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

Referenced by hashbuild().

◆ _hash_addovflpage()

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

Definition at line 112 of file hashovfl.c.

 {
     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 = HashPageGetOpaque(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 = HashPageGetOpaque(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;
 }

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, buf, 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, HashPageGetOpaque, i, InvalidBlockNumber, InvalidBuffer, j, LH_BITMAP_PAGE, LH_BUCKET_PAGE, LH_META_PAGE, LH_OVERFLOW_PAGE, LH_PAGE_TYPE, LockBuffer(), MAIN_FORKNUM, MarkBufferDirty(), 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().

◆ _hash_binsearch()

OffsetNumber _hash_binsearch	(	Page	page,
		uint32	hash_value
	)

Definition at line 351 of file hashutil.c.

 {
     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;
 }

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

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

◆ _hash_binsearch_last()

OffsetNumber _hash_binsearch_last	(	Page	page,
		uint32	hash_value
	)

Definition at line 389 of file hashutil.c.

 {
     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;
 }

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

Referenced by _hash_readpage().

◆ _hash_checkpage()

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

Definition at line 211 of file hashutil.c.

 {
     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 = HashPageGetOpaque(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.")));
     }
 }

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

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

◆ _hash_checkqual()

bool _hash_checkqual	(	IndexScanDesc	scan,
		IndexTuple	itup
	)

Definition at line 32 of file hashutil.c.

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

References DatumGetBool(), FunctionCall2Coll(), index_getattr(), IndexScanDescData::indexRelation, sort-test::key, IndexScanDescData::keyData, IndexScanDescData::numberOfKeys, RelationGetDescr, SK_ISNULL, and test().

Referenced by _hash_load_qualified_items().

◆ _hash_convert_tuple()

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

Definition at line 319 of file hashutil.c.

 {
     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;
 }

References _hash_datum2hashkey(), and UInt32GetDatum().

Referenced by hashbuildCallback(), and hashinsert().

◆ _hash_datum2hashkey()

uint32 _hash_datum2hashkey	(	Relation	rel,
		Datum	key
	)

Definition at line 83 of file hashutil.c.

 {
     FmgrInfo   *procinfo;
     Oid         collation;
  
     /* XXX assumes index has only one attribute */
     procinfo = index_getprocinfo(rel, 1, HASHSTANDARD_PROC);
     collation = rel->rd_indcollation[0];
  
     return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
 }

References DatumGetUInt32(), FunctionCall1Coll(), HASHSTANDARD_PROC, index_getprocinfo(), sort-test::key, and RelationData::rd_indcollation.

Referenced by _hash_convert_tuple(), and _hash_first().

◆ _hash_datum2hashkey_type()

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

Definition at line 103 of file hashutil.c.

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

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

Referenced by _hash_first().

◆ _hash_doinsert()

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

Definition at line 40 of file hashinsert.c.

 {
     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 = IndexTupleSize(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);
  
     CheckForSerializableConflictIn(rel, NULL, BufferGetBlockNumber(buf));
  
     /* remember the primary bucket buffer to release the pin on it at end. */
     bucket_buf = buf;
  
     page = BufferGetPage(buf);
     pageopaque = HashPageGetOpaque(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, heapRel, metabuf, buf);
  
                 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));
             page = BufferGetPage(buf);
  
             /* should fit now, given test above */
             Assert(PageGetFreeSpace(page) >= itemsz);
         }
         pageopaque = HashPageGetOpaque(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, sorted);
     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, IndexTupleSize(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);
 }

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, BufferGetBlockNumber(), BufferGetPage(), CheckForSerializableConflictIn(), 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, HashPageGetOpaque, IndexTupleSize, InvalidBuffer, IsBufferCleanupOK(), LH_META_PAGE, LH_OVERFLOW_PAGE, LH_PAGE_TYPE, LockBuffer(), MarkBufferDirty(), MAXALIGN, xl_hash_insert::offnum, PageGetFreeSpace(), PageSetLSN(), REGBUF_STANDARD, RelationNeedsWAL, SizeOfHashInsert, START_CRIT_SECTION, XLOG_HASH_INSERT, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

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

◆ _hash_dropbuf()

void _hash_dropbuf	(	Relation	rel,
		Buffer	buf
	)

Definition at line 277 of file hashpage.c.

 {
     ReleaseBuffer(buf);
 }

References buf, and ReleaseBuffer().

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

◆ _hash_dropscanbuf()

void _hash_dropscanbuf	(	Relation	rel,
		HashScanOpaque	so
	)

Definition at line 289 of file hashpage.c.

 {
     /* release pin we hold on primary bucket page */
     if (BufferIsValid(so->hashso_bucket_buf) &&
         so->hashso_bucket_buf != so->currPos.buf)
         _hash_dropbuf(rel, so->hashso_bucket_buf);
     so->hashso_bucket_buf = InvalidBuffer;
  
     /* release pin we hold on primary bucket page  of bucket being split */
     if (BufferIsValid(so->hashso_split_bucket_buf) &&
         so->hashso_split_bucket_buf != so->currPos.buf)
         _hash_dropbuf(rel, so->hashso_split_bucket_buf);
     so->hashso_split_bucket_buf = InvalidBuffer;
  
     /* release any pin we still hold */
     if (BufferIsValid(so->currPos.buf))
         _hash_dropbuf(rel, so->currPos.buf);
     so->currPos.buf = InvalidBuffer;
  
     /* reset split scan */
     so->hashso_buc_populated = false;
     so->hashso_buc_split = false;
 }

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

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

◆ _hash_expandtable()

void _hash_expandtable	(	Relation	rel,
		Buffer	metabuf
	)

Definition at line 614 of file hashpage.c.

 {
     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 to prevent failure of pg_ceil_log2_32() 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 = HashPageGetOpaque(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.
      *
      * XXX It doesn't make sense to call _hash_getnewbuf first, zeroing the
      * buffer, and then only afterwards check whether we have a cleanup lock.
      * However, since no scan can be accessing the buffer yet, any concurrent
      * accesses will just be from processes like the bgwriter or checkpointer
      * which don't care about its contents, so it doesn't really matter.
      */
     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 = HashPageGetOpaque(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 = HashPageGetOpaque(npage);
     nopaque->hasho_prevblkno = maxbucket;
     nopaque->hasho_nextblkno = InvalidBlockNumber;
     nopaque->hasho_bucket = new_bucket;
     nopaque->hasho_flag = LH_BUCKET_PAGE | LH_BUCKET_BEING_POPULATED;
     nopaque->hasho_page_id = HASHO_PAGE_ID;
  
     MarkBufferDirty(buf_nblkno);
  
     /* XLOG stuff */
     if (RelationNeedsWAL(rel))
     {
         xl_hash_split_allocate_page xlrec;
         XLogRecPtr  recptr;
  
         xlrec.new_bucket = maxbucket;
         xlrec.old_bucket_flag = oopaque->hasho_flag;
         xlrec.new_bucket_flag = nopaque->hasho_flag;
         xlrec.flags = 0;
  
         XLogBeginInsert();
  
         XLogRegisterBuffer(0, buf_oblkno, REGBUF_STANDARD);
         XLogRegisterBuffer(1, buf_nblkno, REGBUF_WILL_INIT);
         XLogRegisterBuffer(2, metabuf, REGBUF_STANDARD);
  
         if (metap_update_masks)
         {
             xlrec.flags |= XLH_SPLIT_META_UPDATE_MASKS;
             XLogRegisterBufData(2, (char *) &metap->hashm_lowmask, sizeof(uint32));
             XLogRegisterBufData(2, (char *) &metap->hashm_highmask, sizeof(uint32));
         }
  
         if (metap_update_splitpoint)
         {
             xlrec.flags |= XLH_SPLIT_META_UPDATE_SPLITPOINT;
             XLogRegisterBufData(2, (char *) &metap->hashm_ovflpoint,
                                 sizeof(uint32));
             XLogRegisterBufData(2,
                                 (char *) &metap->hashm_spares[metap->hashm_ovflpoint],
                                 sizeof(uint32));
         }
  
         XLogRegisterData((char *) &xlrec, SizeOfHashSplitAllocPage);
  
         recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SPLIT_ALLOCATE_PAGE);
  
         PageSetLSN(BufferGetPage(buf_oblkno), recptr);
         PageSetLSN(BufferGetPage(buf_nblkno), recptr);
         PageSetLSN(BufferGetPage(metabuf), recptr);
     }
  
     END_CRIT_SECTION();
  
     /* drop lock, but keep pin */
     LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
  
     /* Relocate records to the new bucket */
     _hash_splitbucket(rel, metabuf,
                       old_bucket, new_bucket,
                       buf_oblkno, buf_nblkno, NULL,
                       maxbucket, highmask, lowmask);
  
     /* all done, now release the pins on primary buckets. */
     _hash_dropbuf(rel, buf_oblkno);
     _hash_dropbuf(rel, buf_nblkno);
  
     return;
  
     /* Here if decide not to split or fail to acquire old bucket lock */
 fail:
  
     /* We didn't write the metapage, so just drop lock */
     LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
 }

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, HashPageGetOpaque, InvalidBlockNumber, IsBufferCleanupOK(), LH_BUCKET_BEING_POPULATED, LH_BUCKET_BEING_SPLIT, LH_BUCKET_PAGE, LH_META_PAGE, LockBuffer(), MAIN_FORKNUM, MarkBufferDirty(), xl_hash_split_allocate_page::new_bucket, xl_hash_split_allocate_page::new_bucket_flag, xl_hash_split_allocate_page::old_bucket_flag, 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().

◆ _hash_finish_split()

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

Definition at line 1356 of file hashpage.c.

 {
     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 */
     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 = HashPageGetOpaque(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 = HashPageGetOpaque(npage);
     nbucket = npageopaque->hasho_bucket;
  
     _hash_splitbucket(rel, metabuf, obucket,
                       nbucket, obuf, bucket_nbuf, tidhtab,
                       maxbucket, highmask, lowmask);
  
     _hash_dropbuf(rel, bucket_nbuf);
     hash_destroy(tidhtab);
 }

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

Referenced by _hash_doinsert(), and _hash_expandtable().

◆ _hash_first()

bool _hash_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 292 of file hashsearch.c.

 {
     Relation    rel = scan->indexRelation;
     HashScanOpaque so = (HashScanOpaque) scan->opaque;
     ScanKey     cur;
     uint32      hashkey;
     Bucket      bucket;
     Buffer      buf;
     Page        page;
     HashPageOpaque opaque;
     HashScanPosItem *currItem;
  
     pgstat_count_index_scan(rel);
  
     /*
      * We do not support hash scans with no index qualification, because we
      * would have to read the whole index rather than just one bucket. That
      * creates a whole raft of problems, since we haven't got a practical way
      * to lock all the buckets against splits or compactions.
      */
     if (scan->numberOfKeys < 1)
         ereport(ERROR,
                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
                  errmsg("hash indexes do not support whole-index scans")));
  
     /* There may be more than one index qual, but we hash only the first */
     cur = &scan->keyData[0];
  
     /* We support only single-column hash indexes */
     Assert(cur->sk_attno == 1);
     /* And there's only one operator strategy, too */
     Assert(cur->sk_strategy == HTEqualStrategyNumber);
  
     /*
      * If the constant in the index qual is NULL, assume it cannot match any
      * items in the index.
      */
     if (cur->sk_flags & SK_ISNULL)
         return false;
  
     /*
      * Okay to compute the hash key.  We want to do this before acquiring any
      * locks, in case a user-defined hash function happens to be slow.
      *
      * If scankey operator is not a cross-type comparison, we can use the
      * cached hash function; otherwise gotta look it up in the catalogs.
      *
      * We support the convention that sk_subtype == InvalidOid means the
      * opclass input type; this is a hack to simplify life for ScanKeyInit().
      */
     if (cur->sk_subtype == rel->rd_opcintype[0] ||
         cur->sk_subtype == InvalidOid)
         hashkey = _hash_datum2hashkey(rel, cur->sk_argument);
     else
         hashkey = _hash_datum2hashkey_type(rel, cur->sk_argument,
                                            cur->sk_subtype);
  
     so->hashso_sk_hash = hashkey;
  
     buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_READ, NULL);
     PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
     page = BufferGetPage(buf);
     TestForOldSnapshot(scan->xs_snapshot, rel, page);
     opaque = HashPageGetOpaque(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 = HashPageGetOpaque(page);
         Assert(opaque->hasho_bucket == bucket);
  
         if (H_BUCKET_BEING_POPULATED(opaque))
             so->hashso_buc_populated = true;
         else
         {
             _hash_dropbuf(rel, so->hashso_split_bucket_buf);
             so->hashso_split_bucket_buf = InvalidBuffer;
         }
     }
  
     /* If a backwards scan is requested, move to the end of the chain */
     if (ScanDirectionIsBackward(dir))
     {
         /*
          * Backward scans that start during split needs to start from end of
          * bucket being split.
          */
         while (BlockNumberIsValid(opaque->hasho_nextblkno) ||
                (so->hashso_buc_populated && !so->hashso_buc_split))
             _hash_readnext(scan, &buf, &page, &opaque);
     }
  
     /* remember which buffer we have pinned, if any */
     Assert(BufferIsInvalid(so->currPos.buf));
     so->currPos.buf = buf;
  
     /* Now find all the tuples satisfying the qualification from a page */
     if (!_hash_readpage(scan, &buf, dir))
         return false;
  
     /* OK, itemIndex says what to return */
     currItem = &so->currPos.items[so->currPos.itemIndex];
     scan->xs_heaptid = currItem->heapTid;
  
     /* if we're here, _hash_readpage found a valid tuples */
     return true;
 }

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

Referenced by hashgetbitmap(), and hashgettuple().

◆ _hash_freeovflpage()

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 490 of file hashovfl.c.

 {
     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 = HashPageGetOpaque(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 = HashPageGetOpaque(ovflpage);
  
     ovflopaque->hasho_prevblkno = InvalidBlockNumber;
     ovflopaque->hasho_nextblkno = InvalidBlockNumber;
     ovflopaque->hasho_bucket = InvalidBucket;
     ovflopaque->hasho_flag = LH_UNUSED_PAGE;
     ovflopaque->hasho_page_id = HASHO_PAGE_ID;
  
     MarkBufferDirty(ovflbuf);
  
     if (BufferIsValid(prevbuf))
     {
         Page        prevpage = BufferGetPage(prevbuf);
         HashPageOpaque prevopaque = HashPageGetOpaque(prevpage);
  
         Assert(prevopaque->hasho_bucket == bucket);
         prevopaque->hasho_nextblkno = nextblkno;
         MarkBufferDirty(prevbuf);
     }
     if (BufferIsValid(nextbuf))
     {
         Page        nextpage = BufferGetPage(nextbuf);
         HashPageOpaque nextopaque = HashPageGetOpaque(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;
 }

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, HashPageGetOpaque, i, InvalidBlockNumber, InvalidBucket, 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, 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().

◆ _hash_get_indextuple_hashkey()

uint32 _hash_get_indextuple_hashkey ( IndexTuple itup )

Definition at line 292 of file hashutil.c.

 {
     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);
 }

References IndexInfoFindDataOffset(), and IndexTupleData::t_info.

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

◆ _hash_get_newblock_from_oldbucket()

BlockNumber _hash_get_newblock_from_oldbucket	(	Relation	rel,
		Bucket	old_bucket
	)

Definition at line 462 of file hashutil.c.

 {
     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;
 }

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

◆ _hash_get_newbucket_from_oldbucket()

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

Definition at line 495 of file hashutil.c.

 {
     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;
 }

References CALC_NEW_BUCKET.

Referenced by _hash_get_newblock_from_oldbucket(), and hashbucketcleanup().

◆ _hash_get_oldblock_from_newbucket()

BlockNumber _hash_get_oldblock_from_newbucket	(	Relation	rel,
		Bucket	new_bucket
	)

Definition at line 423 of file hashutil.c.

 {
     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) << pg_leftmost_one_pos32(new_bucket)) - 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;
 }

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

Referenced by _hash_first().

◆ _hash_get_totalbuckets()

uint32 _hash_get_totalbuckets ( uint32 splitpoint_phase )

Definition at line 175 of file hashutil.c.

 {
     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;
 }

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

◆ _hash_getbucketbuf_from_hashkey()

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

Definition at line 1559 of file hashpage.c.

 {
     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 = HashPageGetOpaque(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;
 }

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, HashPageGetOpaque, InvalidBlockNumber, InvalidBuffer, and LH_BUCKET_PAGE.

Referenced by _hash_doinsert(), and _hash_first().

◆ _hash_getbuf()

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

Definition at line 70 of file hashpage.c.

 {
     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;
 }

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

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

◆ _hash_getbuf_with_condlock_cleanup()

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

Definition at line 96 of file hashpage.c.

 {
     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;
 }

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

Referenced by _hash_expandtable().

◆ _hash_getbuf_with_strategy()

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

Definition at line 239 of file hashpage.c.

 {
     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;
 }

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

◆ _hash_getcachedmetap()

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

Definition at line 1501 of file hashpage.c.

 {
     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 succeeded.
          */
         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;
 }

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

Referenced by _hash_getbucketbuf_from_hashkey(), and hashbulkdelete().

◆ _hash_getinitbuf()

Buffer _hash_getinitbuf	(	Relation	rel,
		BlockNumber	blkno
	)

Definition at line 135 of file hashpage.c.

 {
     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;
 }

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

Referenced by _hash_addovflpage().

◆ _hash_getnewbuf()

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

Definition at line 198 of file hashpage.c.

 {
     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;
 }

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

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

◆ _hash_hashkey2bucket()

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

Definition at line 126 of file hashutil.c.

 {
     Bucket      bucket;
  
     bucket = hashkey & highmask;
     if (bucket > maxbucket)
         bucket = bucket & lowmask;
  
     return bucket;
 }

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

◆ _hash_init()

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

Definition at line 327 of file hashpage.c.

 {
     Buffer      metabuf;
     Buffer      buf;
     Buffer      bitmapbuf;
     Page        pg;
     HashMetaPage metap;
     RegProcedure procid;
     int32       data_width;
     int32       item_width;
     int32       ffactor;
     uint32      num_buckets;
     uint32      i;
     bool        use_wal;
  
     /* safety check */
     if (RelationGetNumberOfBlocksInFork(rel, forkNum) != 0)
         elog(ERROR, "cannot initialize non-empty hash index \"%s\"",
              RelationGetRelationName(rel));
  
     /*
      * WAL log creation of pages if the relation is persistent, or this is the
      * init fork.  Init forks for unlogged relations always need to be WAL
      * logged.
      */
     use_wal = RelationNeedsWAL(rel) || forkNum == INIT_FORKNUM;
  
     /*
      * Determine the target fill factor (in tuples per bucket) for this index.
      * The idea is to make the fill factor correspond to pages about as full
      * as the user-settable fillfactor parameter says.  We can compute it
      * exactly since the index datatype (i.e. uint32 hash key) is fixed-width.
      */
     data_width = sizeof(uint32);
     item_width = MAXALIGN(sizeof(IndexTupleData)) + MAXALIGN(data_width) +
         sizeof(ItemIdData);     /* include the line pointer */
     ffactor = HashGetTargetPageUsage(rel) / item_width;
     /* keep to a sane range */
     if (ffactor < 10)
         ffactor = 10;
  
     procid = index_getprocid(rel, 1, HASHSTANDARD_PROC);
  
     /*
      * We initialize the metapage, the first N bucket pages, and the first
      * bitmap page in sequence, using _hash_getnewbuf to cause smgrextend()
      * calls to occur.  This ensures that the smgr level has the right idea of
      * the physical index length.
      *
      * Critical section not required, because on error the creation of the
      * whole relation will be rolled back.
      */
     metabuf = _hash_getnewbuf(rel, HASH_METAPAGE, forkNum);
     _hash_init_metabuffer(metabuf, num_tuples, procid, ffactor, false);
     MarkBufferDirty(metabuf);
  
     pg = BufferGetPage(metabuf);
     metap = HashPageGetMeta(pg);
  
     /* XLOG stuff */
     if (use_wal)
     {
         xl_hash_init_meta_page xlrec;
         XLogRecPtr  recptr;
  
         xlrec.num_tuples = num_tuples;
         xlrec.procid = metap->hashm_procid;
         xlrec.ffactor = metap->hashm_ffactor;
  
         XLogBeginInsert();
         XLogRegisterData((char *) &xlrec, SizeOfHashInitMetaPage);
         XLogRegisterBuffer(0, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
  
         recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_INIT_META_PAGE);
  
         PageSetLSN(BufferGetPage(metabuf), recptr);
     }
  
     num_buckets = metap->hashm_maxbucket + 1;
  
     /*
      * Release buffer lock on the metapage while we initialize buckets.
      * Otherwise, we'll be in interrupt holdoff and the CHECK_FOR_INTERRUPTS
      * won't accomplish anything.  It's a bad idea to hold buffer locks for
      * long intervals in any case, since that can block the bgwriter.
      */
     LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
  
     /*
      * Initialize and WAL Log the first N buckets
      */
     for (i = 0; i < num_buckets; i++)
     {
         BlockNumber blkno;
  
         /* Allow interrupts, in case N is huge */
         CHECK_FOR_INTERRUPTS();
  
         blkno = BUCKET_TO_BLKNO(metap, i);
         buf = _hash_getnewbuf(rel, blkno, forkNum);
         _hash_initbuf(buf, metap->hashm_maxbucket, i, LH_BUCKET_PAGE, false);
         MarkBufferDirty(buf);
  
         if (use_wal)
             log_newpage(&rel->rd_locator,
                         forkNum,
                         blkno,
                         BufferGetPage(buf),
                         true);
         _hash_relbuf(rel, buf);
     }
  
     /* Now reacquire buffer lock on metapage */
     LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
  
     /*
      * Initialize bitmap page
      */
     bitmapbuf = _hash_getnewbuf(rel, num_buckets + 1, forkNum);
     _hash_initbitmapbuffer(bitmapbuf, metap->hashm_bmsize, false);
     MarkBufferDirty(bitmapbuf);
  
     /* add the new bitmap page to the metapage's list of bitmaps */
     /* metapage already has a write lock */
     if (metap->hashm_nmaps >= HASH_MAX_BITMAPS)
         ereport(ERROR,
                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                  errmsg("out of overflow pages in hash index \"%s\"",
                         RelationGetRelationName(rel))));
  
     metap->hashm_mapp[metap->hashm_nmaps] = num_buckets + 1;
  
     metap->hashm_nmaps++;
     MarkBufferDirty(metabuf);
  
     /* XLOG stuff */
     if (use_wal)
     {
         xl_hash_init_bitmap_page xlrec;
         XLogRecPtr  recptr;
  
         xlrec.bmsize = metap->hashm_bmsize;
  
         XLogBeginInsert();
         XLogRegisterData((char *) &xlrec, SizeOfHashInitBitmapPage);
         XLogRegisterBuffer(0, bitmapbuf, REGBUF_WILL_INIT);
  
         /*
          * This is safe only because nobody else can be modifying the index at
          * this stage; it's only visible to the transaction that is creating
          * it.
          */
         XLogRegisterBuffer(1, metabuf, REGBUF_STANDARD);
  
         recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_INIT_BITMAP_PAGE);
  
         PageSetLSN(BufferGetPage(bitmapbuf), recptr);
         PageSetLSN(BufferGetPage(metabuf), recptr);
     }
  
     /* all done */
     _hash_relbuf(rel, bitmapbuf);
     _hash_relbuf(rel, metabuf);
  
     return num_buckets;
 }

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_MAX_BITMAPS, HASH_METAPAGE, HashGetTargetPageUsage, HashMetaPageData::hashm_bmsize, HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_nmaps, HashMetaPageData::hashm_procid, HashPageGetMeta, HASHSTANDARD_PROC, i, index_getprocid(), INIT_FORKNUM, LH_BUCKET_PAGE, LockBuffer(), log_newpage(), MarkBufferDirty(), MAXALIGN, xl_hash_init_meta_page::num_tuples, PageSetLSN(), xl_hash_init_meta_page::procid, RelationData::rd_locator, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationGetNumberOfBlocksInFork(), RelationGetRelationName, RelationNeedsWAL, SizeOfHashInitBitmapPage, SizeOfHashInitMetaPage, XLOG_HASH_INIT_BITMAP_PAGE, XLOG_HASH_INIT_META_PAGE, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by hashbuild(), and hashbuildempty().

◆ _hash_init_metabuffer()

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

Definition at line 498 of file hashpage.c.

 {
     HashMetaPage metap;
     HashPageOpaque pageopaque;
     Page        page;
     double      dnumbuckets;
     uint32      num_buckets;
     uint32      spare_index;
     uint32      lshift;
  
     /*
      * 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_spares 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 = HashPageGetOpaque(page);
     pageopaque->hasho_prevblkno = InvalidBlockNumber;
     pageopaque->hasho_nextblkno = InvalidBlockNumber;
     pageopaque->hasho_bucket = InvalidBucket;
     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 */
     lshift = pg_leftmost_one_pos32(metap->hashm_bsize);
     Assert(lshift > 0);
     metap->hashm_bmsize = 1 << lshift;
     metap->hashm_bmshift = lshift + 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 = pg_nextpower2_32(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 essential,
      * because without doing so, metadata will be lost if xlog.c compresses
      * the page.
      */
     ((PageHeader) page)->pd_lower =
         ((char *) metap + sizeof(HashMetaPageData)) - (char *) page;
 }

Referenced by _hash_init(), and hash_xlog_init_meta_page().

◆ _hash_initbitmapbuffer()

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

Definition at line 741 of file hashovfl.c.

 {
     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 = HashPageGetOpaque(pg);
     op->hasho_prevblkno = InvalidBlockNumber;
     op->hasho_nextblkno = InvalidBlockNumber;
     op->hasho_bucket = InvalidBucket;
     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;
 }

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

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

◆ _hash_initbuf()

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

Definition at line 157 of file hashpage.c.

 {
     HashPageOpaque pageopaque;
     Page        page;
  
     page = BufferGetPage(buf);
  
     /* initialize the page */
     if (initpage)
         _hash_pageinit(page, BufferGetPageSize(buf));
  
     pageopaque = HashPageGetOpaque(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;
 }

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

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

◆ _hash_kill_items()

void _hash_kill_items ( IndexScanDesc scan )

Definition at line 537 of file hashutil.c.

 {
     HashScanOpaque so = (HashScanOpaque) scan->opaque;
     Relation    rel = scan->indexRelation;
     BlockNumber blkno;
     Buffer      buf;
     Page        page;
     HashPageOpaque opaque;
     OffsetNumber offnum,
                 maxoff;
     int         numKilled = so->numKilled;
     int         i;
     bool        killedsomething = false;
     bool        havePin = false;
  
     Assert(so->numKilled > 0);
     Assert(so->killedItems != NULL);
     Assert(HashScanPosIsValid(so->currPos));
  
     /*
      * Always reset the scan state, so we don't look for same items on other
      * pages.
      */
     so->numKilled = 0;
  
     blkno = so->currPos.currPage;
     if (HashScanPosIsPinned(so->currPos))
     {
         /*
          * We already have pin on this buffer, so, all we need to do is
          * acquire lock on it.
          */
         havePin = true;
         buf = so->currPos.buf;
         LockBuffer(buf, BUFFER_LOCK_SHARE);
     }
     else
         buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
  
     page = BufferGetPage(buf);
     opaque = HashPageGetOpaque(page);
     maxoff = PageGetMaxOffsetNumber(page);
  
     for (i = 0; i < numKilled; i++)
     {
         int         itemIndex = so->killedItems[i];
         HashScanPosItem *currItem = &so->currPos.items[itemIndex];
  
         offnum = currItem->indexOffset;
  
         Assert(itemIndex >= so->currPos.firstItem &&
                itemIndex <= so->currPos.lastItem);
  
         while (offnum <= maxoff)
         {
             ItemId      iid = PageGetItemId(page, offnum);
             IndexTuple  ituple = (IndexTuple) PageGetItem(page, iid);
  
             if (ItemPointerEquals(&ituple->t_tid, &currItem->heapTid))
             {
                 /* found the item */
                 ItemIdMarkDead(iid);
                 killedsomething = true;
                 break;          /* out of inner search loop */
             }
             offnum = OffsetNumberNext(offnum);
         }
     }
  
     /*
      * Since this can be redone later if needed, mark as dirty hint. Whenever
      * we mark anything LP_DEAD, we also set the page's
      * LH_PAGE_HAS_DEAD_TUPLES flag, which is likewise just a hint.
      */
     if (killedsomething)
     {
         opaque->hasho_flag |= LH_PAGE_HAS_DEAD_TUPLES;
         MarkBufferDirtyHint(buf, true);
     }
  
     if (so->hashso_bucket_buf == so->currPos.buf ||
         havePin)
         LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
     else
         _hash_relbuf(rel, buf);
 }

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

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

◆ _hash_next()

bool _hash_next	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 48 of file hashsearch.c.

 {
     Relation    rel = scan->indexRelation;
     HashScanOpaque so = (HashScanOpaque) scan->opaque;
     HashScanPosItem *currItem;
     BlockNumber blkno;
     Buffer      buf;
     bool        end_of_scan = false;
  
     /*
      * Advance to the next tuple on the current page; or if done, try to read
      * data from the next or previous page based on the scan direction. Before
      * moving to the next or previous page make sure that we deal with all the
      * killed items.
      */
     if (ScanDirectionIsForward(dir))
     {
         if (++so->currPos.itemIndex > so->currPos.lastItem)
         {
             if (so->numKilled > 0)
                 _hash_kill_items(scan);
  
             blkno = so->currPos.nextPage;
             if (BlockNumberIsValid(blkno))
             {
                 buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
                 TestForOldSnapshot(scan->xs_snapshot, rel, BufferGetPage(buf));
                 if (!_hash_readpage(scan, &buf, dir))
                     end_of_scan = true;
             }
             else
                 end_of_scan = true;
         }
     }
     else
     {
         if (--so->currPos.itemIndex < so->currPos.firstItem)
         {
             if (so->numKilled > 0)
                 _hash_kill_items(scan);
  
             blkno = so->currPos.prevPage;
             if (BlockNumberIsValid(blkno))
             {
                 buf = _hash_getbuf(rel, blkno, HASH_READ,
                                    LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
                 TestForOldSnapshot(scan->xs_snapshot, rel, BufferGetPage(buf));
  
                 /*
                  * We always maintain the pin on bucket page for whole scan
                  * operation, so releasing the additional pin we have acquired
                  * here.
                  */
                 if (buf == so->hashso_bucket_buf ||
                     buf == so->hashso_split_bucket_buf)
                     _hash_dropbuf(rel, buf);
  
                 if (!_hash_readpage(scan, &buf, dir))
                     end_of_scan = true;
             }
             else
                 end_of_scan = true;
         }
     }
  
     if (end_of_scan)
     {
         _hash_dropscanbuf(rel, so);
         HashScanPosInvalidate(so->currPos);
         return false;
     }
  
     /* OK, itemIndex says what to return */
     currItem = &so->currPos.items[so->currPos.itemIndex];
     scan->xs_heaptid = currItem->heapTid;
  
     return true;
 }

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

Referenced by hashgetbitmap(), and hashgettuple().

◆ _hash_ovflblkno_to_bitno()

uint32 _hash_ovflblkno_to_bitno	(	HashMetaPage	metap,
		BlockNumber	ovflblkno
	)

Definition at line 62 of file hashovfl.c.

 {
     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 */
 }

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

Referenced by _hash_freeovflpage(), and hash_bitmap_info().

◆ _hash_pageinit()

void _hash_pageinit	(	Page	page,
		Size	size
	)

Definition at line 596 of file hashpage.c.

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

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

◆ _hash_pgaddmultitup()

void _hash_pgaddmultitup	(	Relation	rel,
		Buffer	buf,
		IndexTuple *	itups,
		OffsetNumber *	itup_offsets,
		uint16	nitups
	)

Definition at line 333 of file hashinsert.c.

 {
     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 = IndexTupleSize(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));
     }
 }

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

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

◆ _hash_pgaddtup()

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

Definition at line 276 of file hashinsert.c.

 {
     OffsetNumber itup_off;
     Page        page;
  
     _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
     page = BufferGetPage(buf);
  
     /*
      * Find where to insert the tuple (preserving page's hashkey ordering). If
      * 'appendtup' is true then we just insert it at the end.
      */
     if (appendtup)
     {
         itup_off = PageGetMaxOffsetNumber(page) + 1;
  
 #ifdef USE_ASSERT_CHECKING
         /* ensure this tuple's hashkey is >= the final existing tuple */
         if (PageGetMaxOffsetNumber(page) > 0)
         {
             IndexTuple  lasttup;
             ItemId      itemid;
  
             itemid = PageGetItemId(page, PageGetMaxOffsetNumber(page));
             lasttup = (IndexTuple) PageGetItem(page, itemid);
  
             Assert(_hash_get_indextuple_hashkey(lasttup) <=
                    _hash_get_indextuple_hashkey(itup));
         }
 #endif
     }
     else
     {
         uint32      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;
 }

References _hash_binsearch(), _hash_checkpage(), _hash_get_indextuple_hashkey(), Assert(), buf, BufferGetPage(), elog(), ERROR, InvalidOffsetNumber, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, PageAddItem, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and RelationGetRelationName.

Referenced by _hash_doinsert().

◆ _hash_relbuf()

void _hash_relbuf	(	Relation	rel,
		Buffer	buf
	)

Definition at line 266 of file hashpage.c.

 {
     UnlockReleaseBuffer(buf);
 }

References buf, and 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_kill_items(), _hash_readnext(), _hash_readpage(), _hash_readprev(), _hash_splitbucket(), _hash_squeezebucket(), hash_bitmap_info(), hashbucketcleanup(), hashbulkdelete(), pgstat_hash_page(), and pgstathashindex().

◆ _hash_spareindex()

uint32 _hash_spareindex ( uint32 num_bucket )

Definition at line 143 of file hashutil.c.

 {
     uint32      splitpoint_group;
     uint32      splitpoint_phases;
  
     splitpoint_group = pg_ceil_log2_32(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;
 }

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

Referenced by _hash_expandtable(), and _hash_init_metabuffer().

◆ _hash_squeezebucket()

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

Definition at line 806 of file hashovfl.c.

 {
     BlockNumber wblkno;
     BlockNumber rblkno;
     Buffer      wbuf;
     Buffer      rbuf;
     Page        wpage;
     Page        rpage;
     HashPageOpaque wopaque;
     HashPageOpaque ropaque;
  
     /*
      * start squeezing into the primary bucket page.
      */
     wblkno = bucket_blkno;
     wbuf = bucket_buf;
     wpage = BufferGetPage(wbuf);
     wopaque = HashPageGetOpaque(wpage);
  
     /*
      * if there aren't any overflow pages, there's nothing to squeeze. caller
      * is responsible for releasing the pin on primary bucket page.
      */
     if (!BlockNumberIsValid(wopaque->hasho_nextblkno))
     {
         LockBuffer(wbuf, BUFFER_LOCK_UNLOCK);
         return;
     }
  
     /*
      * Find the last page in the bucket chain by starting at the base bucket
      * page and working forward.  Note: we assume that a hash bucket chain is
      * usually smaller than the buffer ring being used by VACUUM, else using
      * the access strategy here would be counterproductive.
      */
     rbuf = InvalidBuffer;
     ropaque = wopaque;
     do
     {
         rblkno = ropaque->hasho_nextblkno;
         if (rbuf != InvalidBuffer)
             _hash_relbuf(rel, rbuf);
         rbuf = _hash_getbuf_with_strategy(rel,
                                           rblkno,
                                           HASH_WRITE,
                                           LH_OVERFLOW_PAGE,
                                           bstrategy);
         rpage = BufferGetPage(rbuf);
         ropaque = HashPageGetOpaque(rpage);
         Assert(ropaque->hasho_bucket == bucket);
     } while (BlockNumberIsValid(ropaque->hasho_nextblkno));
  
     /*
      * squeeze the tuples.
      */
     for (;;)
     {
         OffsetNumber roffnum;
         OffsetNumber maxroffnum;
         OffsetNumber deletable[MaxOffsetNumber];
         IndexTuple  itups[MaxIndexTuplesPerPage];
         Size        tups_size[MaxIndexTuplesPerPage];
         OffsetNumber itup_offsets[MaxIndexTuplesPerPage];
         uint16      ndeletable = 0;
         uint16      nitups = 0;
         Size        all_tups_size = 0;
         int         i;
         bool        retain_pin = false;
  
 readpage:
         /* Scan each tuple in "read" page */
         maxroffnum = PageGetMaxOffsetNumber(rpage);
         for (roffnum = FirstOffsetNumber;
              roffnum <= maxroffnum;
              roffnum = OffsetNumberNext(roffnum))
         {
             IndexTuple  itup;
             Size        itemsz;
  
             /* skip dead tuples */
             if (ItemIdIsDead(PageGetItemId(rpage, roffnum)))
                 continue;
  
             itup = (IndexTuple) PageGetItem(rpage,
                                             PageGetItemId(rpage, roffnum));
             itemsz = IndexTupleSize(itup);
             itemsz = MAXALIGN(itemsz);
  
             /*
              * Walk up the bucket chain, looking for a page big enough for
              * this item and all other accumulated items.  Exit if we reach
              * the read page.
              */
             while (PageGetFreeSpaceForMultipleTuples(wpage, nitups + 1) < (all_tups_size + itemsz))
             {
                 Buffer      next_wbuf = InvalidBuffer;
                 bool        tups_moved = false;
  
                 Assert(!PageIsEmpty(wpage));
  
                 if (wblkno == bucket_blkno)
                     retain_pin = true;
  
                 wblkno = wopaque->hasho_nextblkno;
                 Assert(BlockNumberIsValid(wblkno));
  
                 /* don't need to move to next page if we reached the read page */
                 if (wblkno != rblkno)
                     next_wbuf = _hash_getbuf_with_strategy(rel,
                                                            wblkno,
                                                            HASH_WRITE,
                                                            LH_OVERFLOW_PAGE,
                                                            bstrategy);
  
                 if (nitups > 0)
                 {
                     Assert(nitups == ndeletable);
  
                     /*
                      * This operation needs to log multiple tuples, prepare
                      * WAL for that.
                      */
                     if (RelationNeedsWAL(rel))
                         XLogEnsureRecordSpace(0, 3 + 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).
                      */
                     _hash_pgaddmultitup(rel, wbuf, itups, itup_offsets, nitups);
                     MarkBufferDirty(wbuf);
  
                     /* Delete tuples we already moved off read page */
                     PageIndexMultiDelete(rpage, deletable, ndeletable);
                     MarkBufferDirty(rbuf);
  
                     /* XLOG stuff */
                     if (RelationNeedsWAL(rel))
                     {
                         XLogRecPtr  recptr;
                         xl_hash_move_page_contents xlrec;
  
                         xlrec.ntups = nitups;
                         xlrec.is_prim_bucket_same_wrt = (wbuf == bucket_buf);
  
                         XLogBeginInsert();
                         XLogRegisterData((char *) &xlrec, SizeOfHashMovePageContents);
  
                         /*
                          * 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, bucket_buf, REGBUF_STANDARD | REGBUF_NO_IMAGE);
  
                         XLogRegisterBuffer(1, wbuf, REGBUF_STANDARD);
                         XLogRegisterBufData(1, (char *) itup_offsets,
                                             nitups * sizeof(OffsetNumber));
                         for (i = 0; i < nitups; i++)
                             XLogRegisterBufData(1, (char *) itups[i], tups_size[i]);
  
                         XLogRegisterBuffer(2, rbuf, REGBUF_STANDARD);
                         XLogRegisterBufData(2, (char *) deletable,
                                             ndeletable * sizeof(OffsetNumber));
  
                         recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_MOVE_PAGE_CONTENTS);
  
                         PageSetLSN(BufferGetPage(wbuf), recptr);
                         PageSetLSN(BufferGetPage(rbuf), recptr);
                     }
  
                     END_CRIT_SECTION();
  
                     tups_moved = true;
                 }
  
                 /*
                  * release the lock on previous page after acquiring the lock
                  * on next page
                  */
                 if (retain_pin)
                     LockBuffer(wbuf, BUFFER_LOCK_UNLOCK);
                 else
                     _hash_relbuf(rel, wbuf);
  
                 /* nothing more to do if we reached the read page */
                 if (rblkno == wblkno)
                 {
                     _hash_relbuf(rel, rbuf);
                     return;
                 }
  
                 wbuf = next_wbuf;
                 wpage = BufferGetPage(wbuf);
                 wopaque = HashPageGetOpaque(wpage);
                 Assert(wopaque->hasho_bucket == bucket);
                 retain_pin = false;
  
                 /* be tidy */
                 for (i = 0; i < nitups; i++)
                     pfree(itups[i]);
                 nitups = 0;
                 all_tups_size = 0;
                 ndeletable = 0;
  
                 /*
                  * after moving the tuples, rpage would have been compacted,
                  * so we need to rescan it.
                  */
                 if (tups_moved)
                     goto readpage;
             }
  
             /* remember tuple for deletion from "read" page */
             deletable[ndeletable++] = roffnum;
  
             /*
              * we need a copy of index tuples as they can be freed as part of
              * overflow page, however we need them to write a WAL record in
              * _hash_freeovflpage.
              */
             itups[nitups] = CopyIndexTuple(itup);
             tups_size[nitups++] = itemsz;
             all_tups_size += itemsz;
         }
  
         /*
          * If we reach here, there are no live tuples on the "read" page ---
          * it was empty when we got to it, or we moved them all.  So we can
          * just free the page without bothering with deleting tuples
          * individually.  Then advance to the previous "read" page.
          *
          * Tricky point here: if our read and write pages are adjacent in the
          * bucket chain, our write lock on wbuf will conflict with
          * _hash_freeovflpage's attempt to update the sibling links of the
          * removed page.  In that case, we don't need to lock it again.
          */
         rblkno = ropaque->hasho_prevblkno;
         Assert(BlockNumberIsValid(rblkno));
  
         /* free this overflow page (releases rbuf) */
         _hash_freeovflpage(rel, bucket_buf, rbuf, wbuf, itups, itup_offsets,
                            tups_size, nitups, bstrategy);
  
         /* be tidy */
         for (i = 0; i < nitups; i++)
             pfree(itups[i]);
  
         /* are we freeing the page adjacent to wbuf? */
         if (rblkno == wblkno)
         {
             /* retain the pin on primary bucket page till end of bucket scan */
             if (wblkno == bucket_blkno)
                 LockBuffer(wbuf, BUFFER_LOCK_UNLOCK);
             else
                 _hash_relbuf(rel, wbuf);
             return;
         }
  
         rbuf = _hash_getbuf_with_strategy(rel,
                                           rblkno,
                                           HASH_WRITE,
                                           LH_OVERFLOW_PAGE,
                                           bstrategy);
         rpage = BufferGetPage(rbuf);
         ropaque = HashPageGetOpaque(rpage);
         Assert(ropaque->hasho_bucket == bucket);
     }
  
     /* NOTREACHED */
 }

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, HashPageGetOpaque, i, IndexTupleSize, 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(), PageIndexMultiDelete(), PageIsEmpty(), PageSetLSN(), pfree(), REGBUF_NO_IMAGE, REGBUF_STANDARD, RelationNeedsWAL, SizeOfHashMovePageContents, START_CRIT_SECTION, XLOG_HASH_MOVE_PAGE_CONTENTS, XLogBeginInsert(), XLogEnsureRecordSpace(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by hashbucketcleanup().

◆ hashadjustmembers()

void hashadjustmembers	(	Oid	opfamilyoid,
		Oid	opclassoid,
		List *	operators,
		List *	functions
	)

Definition at line 352 of file hashvalidate.c.

 {
     Oid         opcintype;
     ListCell   *lc;
  
     /*
      * Hash operators and required support functions are always "loose"
      * members of the opfamily if they are cross-type.  If they are not
      * cross-type, we prefer to tie them to the appropriate opclass ... but if
      * the user hasn't created one, we can't do that, and must fall back to
      * using the opfamily dependency.  (We mustn't force creation of an
      * opclass in such a case, as leaving an incomplete opclass laying about
      * would be bad.  Throwing an error is another undesirable alternative.)
      *
      * This behavior results in a bit of a dump/reload hazard, in that the
      * order of restoring objects could affect what dependencies we end up
      * with.  pg_dump's existing behavior will preserve the dependency choices
      * in most cases, but not if a cross-type operator has been bound tightly
      * into an opclass.  That's a mistake anyway, so silently "fixing" it
      * isn't awful.
      *
      * Optional support functions are always "loose" family members.
      *
      * To avoid repeated lookups, we remember the most recently used opclass's
      * input type.
      */
     if (OidIsValid(opclassoid))
     {
         /* During CREATE OPERATOR CLASS, need CCI to see the pg_opclass row */
         CommandCounterIncrement();
         opcintype = get_opclass_input_type(opclassoid);
     }
     else
         opcintype = InvalidOid;
  
     /*
      * We handle operators and support functions almost identically, so rather
      * than duplicate this code block, just join the lists.
      */
     foreach(lc, list_concat_copy(operators, functions))
     {
         OpFamilyMember *op = (OpFamilyMember *) lfirst(lc);
  
         if (op->is_func && op->number != HASHSTANDARD_PROC)
         {
             /* Optional support proc, so always a soft family dependency */
             op->ref_is_hard = false;
             op->ref_is_family = true;
             op->refobjid = opfamilyoid;
         }
         else if (op->lefttype != op->righttype)
         {
             /* Cross-type, so always a soft family dependency */
             op->ref_is_hard = false;
             op->ref_is_family = true;
             op->refobjid = opfamilyoid;
         }
         else
         {
             /* Not cross-type; is there a suitable opclass? */
             if (op->lefttype != opcintype)
             {
                 /* Avoid repeating this expensive lookup, even if it fails */
                 opcintype = op->lefttype;
                 opclassoid = opclass_for_family_datatype(HASH_AM_OID,
                                                          opfamilyoid,
                                                          opcintype);
             }
             if (OidIsValid(opclassoid))
             {
                 /* Hard dependency on opclass */
                 op->ref_is_hard = true;
                 op->ref_is_family = false;
                 op->refobjid = opclassoid;
             }
             else
             {
                 /* We're stuck, so make a soft dependency on the opfamily */
                 op->ref_is_hard = false;
                 op->ref_is_family = true;
                 op->refobjid = opfamilyoid;
             }
         }
     }
 }

References CommandCounterIncrement(), functions, get_opclass_input_type(), HASHSTANDARD_PROC, InvalidOid, OpFamilyMember::is_func, OpFamilyMember::lefttype, lfirst, list_concat_copy(), OpFamilyMember::number, OidIsValid, opclass_for_family_datatype(), OpFamilyMember::ref_is_family, OpFamilyMember::ref_is_hard, OpFamilyMember::refobjid, and OpFamilyMember::righttype.

Referenced by hashhandler().

◆ hashbeginscan()

IndexScanDesc hashbeginscan	(	Relation	rel,
		int	nkeys,
		int	norderbys
	)

Definition at line 364 of file hash.c.

 {
     IndexScanDesc scan;
     HashScanOpaque so;
  
     /* no order by operators allowed */
     Assert(norderbys == 0);
  
     scan = RelationGetIndexScan(rel, nkeys, norderbys);
  
     so = (HashScanOpaque) palloc(sizeof(HashScanOpaqueData));
     HashScanPosInvalidate(so->currPos);
     so->hashso_bucket_buf = InvalidBuffer;
     so->hashso_split_bucket_buf = InvalidBuffer;
  
     so->hashso_buc_populated = false;
     so->hashso_buc_split = false;
  
     so->killedItems = NULL;
     so->numKilled = 0;
  
     scan->opaque = so;
  
     return scan;
 }

References Assert(), HashScanOpaqueData::currPos, HashScanPosInvalidate, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_split_bucket_buf, InvalidBuffer, HashScanOpaqueData::killedItems, HashScanOpaqueData::numKilled, IndexScanDescData::opaque, palloc(), and RelationGetIndexScan().

Referenced by hashhandler().

◆ hashbucketcleanup()

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	split_cleanup,
		IndexBulkDeleteCallback	callback,
		void *	callback_state
	)

Definition at line 684 of file hash.c.

 {
     BlockNumber blkno;
     Buffer      buf;
     Bucket      new_bucket PG_USED_FOR_ASSERTS_ONLY = InvalidBucket;
     bool        bucket_dirty = false;
  
     blkno = bucket_blkno;
     buf = bucket_buf;
  
     if (split_cleanup)
         new_bucket = _hash_get_newbucket_from_oldbucket(rel, cur_bucket,
                                                         lowmask, maxbucket);
  
     /* Scan each page in bucket */
     for (;;)
     {
         HashPageOpaque opaque;
         OffsetNumber offno;
         OffsetNumber maxoffno;
         Buffer      next_buf;
         Page        page;
         OffsetNumber deletable[MaxOffsetNumber];
         int         ndeletable = 0;
         bool        retain_pin = false;
         bool        clear_dead_marking = false;
  
         vacuum_delay_point();
  
         page = BufferGetPage(buf);
         opaque = HashPageGetOpaque(page);
  
         /* Scan each tuple in page */
         maxoffno = PageGetMaxOffsetNumber(page);
         for (offno = FirstOffsetNumber;
              offno <= maxoffno;
              offno = OffsetNumberNext(offno))
         {
             ItemPointer htup;
             IndexTuple  itup;
             Bucket      bucket;
             bool        kill_tuple = false;
  
             itup = (IndexTuple) PageGetItem(page,
                                             PageGetItemId(page, offno));
             htup = &(itup->t_tid);
  
             /*
              * To remove the dead tuples, we strictly want to rely on results
              * of callback function.  refer btvacuumpage for detailed reason.
              */
             if (callback && callback(htup, callback_state))
             {
                 kill_tuple = true;
                 if (tuples_removed)
                     *tuples_removed += 1;
             }
             else if (split_cleanup)
             {
                 /* delete the tuples that are moved by split. */
                 bucket = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
                                               maxbucket,
                                               highmask,
                                               lowmask);
                 /* mark the item for deletion */
                 if (bucket != cur_bucket)
                 {
                     /*
                      * We expect tuples to either belong to current bucket or
                      * new_bucket.  This is ensured because we don't allow
                      * further splits from bucket that contains garbage. See
                      * comments in _hash_expandtable.
                      */
                     Assert(bucket == new_bucket);
                     kill_tuple = true;
                 }
             }
  
             if (kill_tuple)
             {
                 /* mark the item for deletion */
                 deletable[ndeletable++] = offno;
             }
             else
             {
                 /* we're keeping it, so count it */
                 if (num_index_tuples)
                     *num_index_tuples += 1;
             }
         }
  
         /* retain the pin on primary bucket page till end of bucket scan */
         if (blkno == bucket_blkno)
             retain_pin = true;
         else
             retain_pin = false;
  
         blkno = opaque->hasho_nextblkno;
  
         /*
          * Apply deletions, advance to next page and write page if needed.
          */
         if (ndeletable > 0)
         {
             /* No ereport(ERROR) until changes are logged */
             START_CRIT_SECTION();
  
             PageIndexMultiDelete(page, deletable, ndeletable);
             bucket_dirty = true;
  
             /*
              * Let us mark the page as clean if vacuum removes the DEAD tuples
              * from an index page. We do this by clearing
              * LH_PAGE_HAS_DEAD_TUPLES flag.
              */
             if (tuples_removed && *tuples_removed > 0 &&
                 H_HAS_DEAD_TUPLES(opaque))
             {
                 opaque->hasho_flag &= ~LH_PAGE_HAS_DEAD_TUPLES;
                 clear_dead_marking = true;
             }
  
             MarkBufferDirty(buf);
  
             /* XLOG stuff */
             if (RelationNeedsWAL(rel))
             {
                 xl_hash_delete xlrec;
                 XLogRecPtr  recptr;
  
                 xlrec.clear_dead_marking = clear_dead_marking;
                 xlrec.is_primary_bucket_page = (buf == bucket_buf);
  
                 XLogBeginInsert();
                 XLogRegisterData((char *) &xlrec, SizeOfHashDelete);
  
                 /*
                  * bucket buffer needs to be registered to ensure that we can
                  * acquire a cleanup lock on it during replay.
                  */
                 if (!xlrec.is_primary_bucket_page)
                     XLogRegisterBuffer(0, bucket_buf, REGBUF_STANDARD | REGBUF_NO_IMAGE);
  
                 XLogRegisterBuffer(1, buf, REGBUF_STANDARD);
                 XLogRegisterBufData(1, (char *) deletable,
                                     ndeletable * sizeof(OffsetNumber));
  
                 recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_DELETE);
                 PageSetLSN(BufferGetPage(buf), recptr);
             }
  
             END_CRIT_SECTION();
         }
  
         /* bail out if there are no more pages to scan. */
         if (!BlockNumberIsValid(blkno))
             break;
  
         next_buf = _hash_getbuf_with_strategy(rel, blkno, HASH_WRITE,
                                               LH_OVERFLOW_PAGE,
                                               bstrategy);
  
         /*
          * release the lock on previous page after acquiring the lock on next
          * page
          */
         if (retain_pin)
             LockBuffer(buf, BUFFER_LOCK_UNLOCK);
         else
             _hash_relbuf(rel, buf);
  
         buf = next_buf;
     }
  
     /*
      * lock the bucket page to clear the garbage flag and squeeze the bucket.
      * if the current buffer is same as bucket buffer, then we already have
      * lock on bucket page.
      */
     if (buf != bucket_buf)
     {
         _hash_relbuf(rel, buf);
         LockBuffer(bucket_buf, BUFFER_LOCK_EXCLUSIVE);
     }
  
     /*
      * Clear the garbage flag from bucket after deleting the tuples that are
      * moved by split.  We purposefully clear the flag before squeeze bucket,
      * so that after restart, vacuum shouldn't again try to delete the moved
      * by split tuples.
      */
     if (split_cleanup)
     {
         HashPageOpaque bucket_opaque;
         Page        page;
  
         page = BufferGetPage(bucket_buf);
         bucket_opaque = HashPageGetOpaque(page);
  
         /* No ereport(ERROR) until changes are logged */
         START_CRIT_SECTION();
  
         bucket_opaque->hasho_flag &= ~LH_BUCKET_NEEDS_SPLIT_CLEANUP;
         MarkBufferDirty(bucket_buf);
  
         /* XLOG stuff */
         if (RelationNeedsWAL(rel))
         {
             XLogRecPtr  recptr;
  
             XLogBeginInsert();
             XLogRegisterBuffer(0, bucket_buf, REGBUF_STANDARD);
  
             recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SPLIT_CLEANUP);
             PageSetLSN(page, recptr);
         }
  
         END_CRIT_SECTION();
     }
  
     /*
      * If we have deleted anything, try to compact free space.  For squeezing
      * the bucket, we must have a cleanup lock, else it can impact the
      * ordering of tuples for a scan that has started before it.
      */
     if (bucket_dirty && IsBufferCleanupOK(bucket_buf))
         _hash_squeezebucket(rel, cur_bucket, bucket_blkno, bucket_buf,
                             bstrategy);
     else
         LockBuffer(bucket_buf, BUFFER_LOCK_UNLOCK);
 }

References _hash_get_indextuple_hashkey(), _hash_get_newbucket_from_oldbucket(), _hash_getbuf_with_strategy(), _hash_hashkey2bucket(), _hash_relbuf(), _hash_squeezebucket(), Assert(), BlockNumberIsValid(), buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage(), callback(), xl_hash_delete::clear_dead_marking, END_CRIT_SECTION, FirstOffsetNumber, H_HAS_DEAD_TUPLES, HASH_WRITE, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageGetOpaque, InvalidBucket, xl_hash_delete::is_primary_bucket_page, IsBufferCleanupOK(), LH_BUCKET_NEEDS_SPLIT_CLEANUP, LH_OVERFLOW_PAGE, LH_PAGE_HAS_DEAD_TUPLES, LockBuffer(), MarkBufferDirty(), MaxOffsetNumber, OffsetNumberNext, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), PageIndexMultiDelete(), PageSetLSN(), PG_USED_FOR_ASSERTS_ONLY, REGBUF_NO_IMAGE, REGBUF_STANDARD, RelationNeedsWAL, SizeOfHashDelete, START_CRIT_SECTION, IndexTupleData::t_tid, vacuum_delay_point(), XLOG_HASH_DELETE, XLOG_HASH_SPLIT_CLEANUP, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

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

◆ hashbuild()

IndexBuildResult* hashbuild	(	Relation	heap,
		Relation	index,
		struct IndexInfo *	indexInfo
	)

Definition at line 112 of file hash.c.

 {
     IndexBuildResult *result;
     BlockNumber relpages;
     double      reltuples;
     double      allvisfrac;
     uint32      num_buckets;
     long        sort_threshold;
     HashBuildState buildstate;
  
     /*
      * We expect to be called exactly once for any index relation. If that's
      * not the case, big trouble's what we have.
      */
     if (RelationGetNumberOfBlocks(index) != 0)
         elog(ERROR, "index \"%s\" already contains data",
              RelationGetRelationName(index));
  
     /* Estimate the number of rows currently present in the table */
     estimate_rel_size(heap, NULL, &relpages, &reltuples, &allvisfrac);
  
     /* Initialize the hash index metadata page and initial buckets */
     num_buckets = _hash_init(index, reltuples, MAIN_FORKNUM);
  
     /*
      * If we just insert the tuples into the index in scan order, then
      * (assuming their hash codes are pretty random) there will be no locality
      * of access to the index, and if the index is bigger than available RAM
      * then we'll thrash horribly.  To prevent that scenario, we can sort the
      * tuples by (expected) bucket number.  However, such a sort is useless
      * overhead when the index does fit in RAM.  We choose to sort if the
      * initial index size exceeds maintenance_work_mem, or the number of
      * buffers usable for the index, whichever is less.  (Limiting by the
      * number of buffers should reduce thrashing between PG buffers and kernel
      * buffers, which seems useful even if no physical I/O results.  Limiting
      * by maintenance_work_mem is useful to allow easy testing of the sort
      * code path, and may be useful to DBAs as an additional control knob.)
      *
      * NOTE: this test will need adjustment if a bucket is ever different from
      * one page.  Also, "initial index size" accounting does not include the
      * metapage, nor the first bitmap page.
      */
     sort_threshold = (maintenance_work_mem * 1024L) / BLCKSZ;
     if (index->rd_rel->relpersistence != RELPERSISTENCE_TEMP)
         sort_threshold = Min(sort_threshold, NBuffers);
     else
         sort_threshold = Min(sort_threshold, NLocBuffer);
  
     if (num_buckets >= (uint32) sort_threshold)
         buildstate.spool = _h_spoolinit(heap, index, num_buckets);
     else
         buildstate.spool = NULL;
  
     /* prepare to build the index */
     buildstate.indtuples = 0;
     buildstate.heapRel = heap;
  
     /* do the heap scan */
     reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
                                        hashbuildCallback,
                                        (void *) &buildstate, NULL);
     pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_TOTAL,
                                  buildstate.indtuples);
  
     if (buildstate.spool)
     {
         /* sort the tuples and insert them into the index */
         _h_indexbuild(buildstate.spool, buildstate.heapRel);
         _h_spooldestroy(buildstate.spool);
     }
  
     /*
      * Return statistics
      */
     result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
  
     result->heap_tuples = reltuples;
     result->index_tuples = buildstate.indtuples;
  
     return result;
 }

References _h_indexbuild(), _h_spooldestroy(), _h_spoolinit(), _hash_init(), elog(), ERROR, estimate_rel_size(), hashbuildCallback(), IndexBuildResult::heap_tuples, HashBuildState::heapRel, IndexBuildResult::index_tuples, HashBuildState::indtuples, MAIN_FORKNUM, maintenance_work_mem, Min, NBuffers, NLocBuffer, palloc(), pgstat_progress_update_param(), PROGRESS_CREATEIDX_TUPLES_TOTAL, RelationGetNumberOfBlocks, RelationGetRelationName, HashBuildState::spool, and table_index_build_scan().

Referenced by hashhandler().

◆ hashbuildempty()

void hashbuildempty ( Relation index )

Definition at line 198 of file hash.c.

 {
     _hash_init(index, 0, INIT_FORKNUM);
 }

References _hash_init(), and INIT_FORKNUM.

Referenced by hashhandler().

◆ hashbulkdelete()

IndexBulkDeleteResult* hashbulkdelete	(	IndexVacuumInfo *	info,
		IndexBulkDeleteResult *	stats,
		IndexBulkDeleteCallback	callback,
		void *	callback_state
	)

Definition at line 459 of file hash.c.

 {
     Relation    rel = info->index;
     double      tuples_removed;
     double      num_index_tuples;
     double      orig_ntuples;
     Bucket      orig_maxbucket;
     Bucket      cur_maxbucket;
     Bucket      cur_bucket;
     Buffer      metabuf = InvalidBuffer;
     HashMetaPage metap;
     HashMetaPage cachedmetap;
  
     tuples_removed = 0;
     num_index_tuples = 0;
  
     /*
      * We need a copy of the metapage so that we can use its hashm_spares[]
      * values to compute bucket page addresses, but a cached copy should be
      * good enough.  (If not, we'll detect that further down and refresh the
      * cache as necessary.)
      */
     cachedmetap = _hash_getcachedmetap(rel, &metabuf, false);
     Assert(cachedmetap != NULL);
  
     orig_maxbucket = cachedmetap->hashm_maxbucket;
     orig_ntuples = cachedmetap->hashm_ntuples;
  
     /* Scan the buckets that we know exist */
     cur_bucket = 0;
     cur_maxbucket = orig_maxbucket;
  
 loop_top:
     while (cur_bucket <= cur_maxbucket)
     {
         BlockNumber bucket_blkno;
         BlockNumber blkno;
         Buffer      bucket_buf;
         Buffer      buf;
         HashPageOpaque bucket_opaque;
         Page        page;
         bool        split_cleanup = false;
  
         /* Get address of bucket's start page */
         bucket_blkno = BUCKET_TO_BLKNO(cachedmetap, cur_bucket);
  
         blkno = bucket_blkno;
  
         /*
          * We need to acquire a cleanup lock on the primary bucket page to out
          * wait concurrent scans befo

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ ALL_SET

◆ BITS_PER_MAP

◆ BMPG_MASK

◆ BMPG_SHIFT

◆ BMPGSZ_BIT

◆ BMPGSZ_BYTE

◆ BUCKET_TO_BLKNO

◆ BYTE_TO_BIT

◆ CLRBIT

◆ H_BUCKET_BEING_POPULATED

◆ H_BUCKET_BEING_SPLIT

◆ H_HAS_DEAD_TUPLES

◆ H_NEEDS_SPLIT_CLEANUP

◆ HASH_DEFAULT_FILLFACTOR

◆ HASH_MAGIC

◆ HASH_MAX_BITMAPS

◆ HASH_MAX_SPLITPOINT_GROUP

◆ HASH_MAX_SPLITPOINTS

◆ HASH_METAPAGE

◆ HASH_MIN_FILLFACTOR

◆ HASH_NOLOCK

◆ HASH_READ

◆ HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE

◆ HASH_SPLITPOINT_PHASE_BITS

◆ HASH_SPLITPOINT_PHASE_MASK

◆ HASH_SPLITPOINT_PHASES_PER_GRP

◆ HASH_VERSION

◆ HASH_WRITE

◆ HASHEXTENDED_PROC

◆ HashGetFillFactor

◆ HashGetMaxBitmapSize

◆ HashGetTargetPageUsage

◆ HashMaxItemSize

◆ HASHNProcs

◆ HASHO_PAGE_ID

◆ HASHOPTIONS_PROC

◆ HashPageGetBitmap

◆ HashPageGetMeta

◆ HashPageGetOpaque

◆ HashScanPosInvalidate

◆ HashScanPosIsPinned

◆ HashScanPosIsValid

◆ HASHSTANDARD_PROC

◆ INDEX_MOVED_BY_SPLIT_MASK

◆ InvalidBucket

◆ ISSET

◆ LH_BITMAP_PAGE

◆ LH_BUCKET_BEING_POPULATED

◆ LH_BUCKET_BEING_SPLIT

◆ LH_BUCKET_NEEDS_SPLIT_CLEANUP

◆ LH_BUCKET_PAGE

◆ LH_META_PAGE

◆ LH_OVERFLOW_PAGE

◆ LH_PAGE_HAS_DEAD_TUPLES

◆ LH_PAGE_TYPE

◆ LH_UNUSED_PAGE

◆ SETBIT

Typedef Documentation

◆ Bucket

◆ HashMetaPage

◆ HashMetaPageData

◆ HashOptions

◆ HashPageOpaque

◆ HashPageOpaqueData

◆ HashScanOpaque

◆ HashScanOpaqueData

◆ HashScanPosData

◆ HashScanPosItem

◆ HSpool

Function Documentation

◆ _h_indexbuild()

◆ _h_spool()

◆ _h_spooldestroy()

◆ _h_spoolinit()

◆ _hash_addovflpage()