codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * hash.h4 *	  header file for postgres hash access method implementation5 *6 *7 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group8 * Portions Copyright (c) 1994, Regents of the University of California9 *10 * src/include/access/hash.h11 *12 * NOTES13 *		modeled after Margo Seltzer's hash implementation for unix.14 *15 *-------------------------------------------------------------------------16 */17#ifndef HASH_H18#define HASH_H19 20#include "access/amapi.h"21#include "access/itup.h"22#include "access/sdir.h"23#include "catalog/pg_am_d.h"24#include "common/hashfn.h"25#include "lib/stringinfo.h"26#include "storage/bufmgr.h"27#include "storage/lockdefs.h"28#include "utils/hsearch.h"29#include "utils/relcache.h"30 31/*32 * Mapping from hash bucket number to physical block number of bucket's33 * starting page.  Beware of multiple evaluations of argument!34 */35typedef uint32 Bucket;36 37#define InvalidBucket	((Bucket) 0xFFFFFFFF)38 39#define BUCKET_TO_BLKNO(metap,B) \40		((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_spareindex((B)+1)-1] : 0)) + 1)41 42/*43 * Special space for hash index pages.44 *45 * hasho_flag's LH_PAGE_TYPE bits tell us which type of page we're looking at.46 * Additional bits in the flag word are used for more transient purposes.47 *48 * To test a page's type, do (hasho_flag & LH_PAGE_TYPE) == LH_xxx_PAGE.49 * However, we ensure that each used page type has a distinct bit so that50 * we can OR together page types for uses such as the allowable-page-types51 * argument of _hash_checkpage().52 */53#define LH_UNUSED_PAGE			(0)54#define LH_OVERFLOW_PAGE		(1 << 0)55#define LH_BUCKET_PAGE			(1 << 1)56#define LH_BITMAP_PAGE			(1 << 2)57#define LH_META_PAGE			(1 << 3)58#define LH_BUCKET_BEING_POPULATED	(1 << 4)59#define LH_BUCKET_BEING_SPLIT	(1 << 5)60#define LH_BUCKET_NEEDS_SPLIT_CLEANUP	(1 << 6)61#define LH_PAGE_HAS_DEAD_TUPLES (1 << 7)62 63#define LH_PAGE_TYPE \64	(LH_OVERFLOW_PAGE | LH_BUCKET_PAGE | LH_BITMAP_PAGE | LH_META_PAGE)65 66/*67 * In an overflow page, hasho_prevblkno stores the block number of the previous68 * page in the bucket chain; in a bucket page, hasho_prevblkno stores the69 * hashm_maxbucket value as of the last time the bucket was last split, or70 * else as of the time the bucket was created.  The latter convention is used71 * to determine whether a cached copy of the metapage is too stale to be used72 * without needing to lock or pin the metapage.73 *74 * hasho_nextblkno is always the block number of the next page in the75 * bucket chain, or InvalidBlockNumber if there are no more such pages.76 */77typedef struct HashPageOpaqueData78{79	BlockNumber hasho_prevblkno;	/* see above */80	BlockNumber hasho_nextblkno;	/* see above */81	Bucket		hasho_bucket;	/* bucket number this pg belongs to */82	uint16		hasho_flag;		/* page type code + flag bits, see above */83	uint16		hasho_page_id;	/* for identification of hash indexes */84} HashPageOpaqueData;85 86typedef HashPageOpaqueData *HashPageOpaque;87 88#define HashPageGetOpaque(page) ((HashPageOpaque) PageGetSpecialPointer(page))89 90#define H_NEEDS_SPLIT_CLEANUP(opaque)	(((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP) != 0)91#define H_BUCKET_BEING_SPLIT(opaque)	(((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT) != 0)92#define H_BUCKET_BEING_POPULATED(opaque)	(((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED) != 0)93#define H_HAS_DEAD_TUPLES(opaque)		(((opaque)->hasho_flag & LH_PAGE_HAS_DEAD_TUPLES) != 0)94 95/*96 * The page ID is for the convenience of pg_filedump and similar utilities,97 * which otherwise would have a hard time telling pages of different index98 * types apart.  It should be the last 2 bytes on the page.  This is more or99 * less "free" due to alignment considerations.100 */101#define HASHO_PAGE_ID		0xFF80102 103typedef struct HashScanPosItem	/* what we remember about each match */104{105	ItemPointerData heapTid;	/* TID of referenced heap item */106	OffsetNumber indexOffset;	/* index item's location within page */107} HashScanPosItem;108 109typedef struct HashScanPosData110{111	Buffer		buf;			/* if valid, the buffer is pinned */112	BlockNumber currPage;		/* current hash index page */113	BlockNumber nextPage;		/* next overflow page */114	BlockNumber prevPage;		/* prev overflow or bucket page */115 116	/*117	 * The items array is always ordered in index order (ie, increasing118	 * indexoffset).  When scanning backwards it is convenient to fill the119	 * array back-to-front, so we start at the last slot and fill downwards.120	 * Hence we need both a first-valid-entry and a last-valid-entry counter.121	 * itemIndex is a cursor showing which entry was last returned to caller.122	 */123	int			firstItem;		/* first valid index in items[] */124	int			lastItem;		/* last valid index in items[] */125	int			itemIndex;		/* current index in items[] */126 127	HashScanPosItem items[MaxIndexTuplesPerPage];	/* MUST BE LAST */128} HashScanPosData;129 130#define HashScanPosIsPinned(scanpos) \131( \132	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \133				!BufferIsValid((scanpos).buf)), \134	BufferIsValid((scanpos).buf) \135)136 137#define HashScanPosIsValid(scanpos) \138( \139	AssertMacro(BlockNumberIsValid((scanpos).currPage) || \140				!BufferIsValid((scanpos).buf)), \141	BlockNumberIsValid((scanpos).currPage) \142)143 144#define HashScanPosInvalidate(scanpos) \145	do { \146		(scanpos).buf = InvalidBuffer; \147		(scanpos).currPage = InvalidBlockNumber; \148		(scanpos).nextPage = InvalidBlockNumber; \149		(scanpos).prevPage = InvalidBlockNumber; \150		(scanpos).firstItem = 0; \151		(scanpos).lastItem = 0; \152		(scanpos).itemIndex = 0; \153	} while (0)154 155/*156 *	HashScanOpaqueData is private state for a hash index scan.157 */158typedef struct HashScanOpaqueData159{160	/* Hash value of the scan key, ie, the hash key we seek */161	uint32		hashso_sk_hash;162 163	/* remember the buffer associated with primary bucket */164	Buffer		hashso_bucket_buf;165 166	/*167	 * remember the buffer associated with primary bucket page of bucket being168	 * split.  it is required during the scan of the bucket which is being169	 * populated during split operation.170	 */171	Buffer		hashso_split_bucket_buf;172 173	/* Whether scan starts on bucket being populated due to split */174	bool		hashso_buc_populated;175 176	/*177	 * Whether scanning bucket being split?  The value of this parameter is178	 * referred only when hashso_buc_populated is true.179	 */180	bool		hashso_buc_split;181	/* info about killed items if any (killedItems is NULL if never used) */182	int		   *killedItems;	/* currPos.items indexes of killed items */183	int			numKilled;		/* number of currently stored items */184 185	/*186	 * Identify all the matching items on a page and save them in187	 * HashScanPosData188	 */189	HashScanPosData currPos;	/* current position data */190} HashScanOpaqueData;191 192typedef HashScanOpaqueData *HashScanOpaque;193 194/*195 * Definitions for metapage.196 */197 198#define HASH_METAPAGE	0		/* metapage is always block 0 */199 200#define HASH_MAGIC		0x6440640201#define HASH_VERSION	4202 203/*204 * spares[] holds the number of overflow pages currently allocated at or205 * before a certain splitpoint. For example, if spares[3] = 7 then there are206 * 7 ovflpages before splitpoint 3 (compare BUCKET_TO_BLKNO macro).  The207 * value in spares[ovflpoint] increases as overflow pages are added at the208 * end of the index.  Once ovflpoint increases (ie, we have actually allocated209 * the bucket pages belonging to that splitpoint) the number of spares at the210 * prior splitpoint cannot change anymore.211 *212 * ovflpages that have been recycled for reuse can be found by looking at213 * bitmaps that are stored within ovflpages dedicated for the purpose.214 * The blknos of these bitmap pages are kept in mapp[]; nmaps is the215 * number of currently existing bitmaps.216 *217 * The limitation on the size of spares[] comes from the fact that there's218 * no point in having more than 2^32 buckets with only uint32 hashcodes.219 * (Note: The value of HASH_MAX_SPLITPOINTS which is the size of spares[] is220 * adjusted in such a way to accommodate multi phased allocation of buckets221 * after HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE).222 *223 * There is no particular upper limit on the size of mapp[], other than224 * needing to fit into the metapage.  (With 8K block size, 1024 bitmaps225 * limit us to 256 GB of overflow space...).  For smaller block size we226 * can not use 1024 bitmaps as it will lead to the meta page data crossing227 * the block size boundary.  So we use BLCKSZ to determine the maximum number228 * of bitmaps.229 */230#define HASH_MAX_BITMAPS			Min(BLCKSZ / 8, 1024)231 232#define HASH_SPLITPOINT_PHASE_BITS	2233#define HASH_SPLITPOINT_PHASES_PER_GRP	(1 << HASH_SPLITPOINT_PHASE_BITS)234#define HASH_SPLITPOINT_PHASE_MASK		(HASH_SPLITPOINT_PHASES_PER_GRP - 1)235#define HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE	10236 237/* defines max number of splitpoint phases a hash index can have */238#define HASH_MAX_SPLITPOINT_GROUP	32239#define HASH_MAX_SPLITPOINTS \240	(((HASH_MAX_SPLITPOINT_GROUP - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) * \241	  HASH_SPLITPOINT_PHASES_PER_GRP) + \242	 HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)243 244typedef struct HashMetaPageData245{246	uint32		hashm_magic;	/* magic no. for hash tables */247	uint32		hashm_version;	/* version ID */248	double		hashm_ntuples;	/* number of tuples stored in the table */249	uint16		hashm_ffactor;	/* target fill factor (tuples/bucket) */250	uint16		hashm_bsize;	/* index page size (bytes) */251	uint16		hashm_bmsize;	/* bitmap array size (bytes) - must be a power252								 * of 2 */253	uint16		hashm_bmshift;	/* log2(bitmap array size in BITS) */254	uint32		hashm_maxbucket;	/* ID of maximum bucket in use */255	uint32		hashm_highmask; /* mask to modulo into entire table */256	uint32		hashm_lowmask;	/* mask to modulo into lower half of table */257	uint32		hashm_ovflpoint;	/* splitpoint from which ovflpage being258									 * allocated */259	uint32		hashm_firstfree;	/* lowest-number free ovflpage (bit#) */260	uint32		hashm_nmaps;	/* number of bitmap pages */261	RegProcedure hashm_procid;	/* hash function id from pg_proc */262	uint32		hashm_spares[HASH_MAX_SPLITPOINTS]; /* spare pages before each263													 * splitpoint */264	BlockNumber hashm_mapp[HASH_MAX_BITMAPS];	/* blknos of ovfl bitmaps */265} HashMetaPageData;266 267typedef HashMetaPageData *HashMetaPage;268 269typedef struct HashOptions270{271	int32		varlena_header_;	/* varlena header (do not touch directly!) */272	int			fillfactor;		/* page fill factor in percent (0..100) */273} HashOptions;274 275#define HashGetFillFactor(relation) \276	(AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \277				 relation->rd_rel->relam == HASH_AM_OID), \278	 (relation)->rd_options ? \279	 ((HashOptions *) (relation)->rd_options)->fillfactor :	\280	 HASH_DEFAULT_FILLFACTOR)281#define HashGetTargetPageUsage(relation) \282	(BLCKSZ * HashGetFillFactor(relation) / 100)283 284/*285 * Maximum size of a hash index item (it's okay to have only one per page)286 */287#define HashMaxItemSize(page) \288	MAXALIGN_DOWN(PageGetPageSize(page) - \289				  SizeOfPageHeaderData - \290				  sizeof(ItemIdData) - \291				  MAXALIGN(sizeof(HashPageOpaqueData)))292 293#define INDEX_MOVED_BY_SPLIT_MASK	INDEX_AM_RESERVED_BIT294 295#define HASH_MIN_FILLFACTOR			10296#define HASH_DEFAULT_FILLFACTOR		75297 298/*299 * Constants300 */301#define BYTE_TO_BIT				3	/* 2^3 bits/byte */302#define ALL_SET					((uint32) ~0)303 304/*305 * Bitmap pages do not contain tuples.  They do contain the standard306 * page headers and trailers; however, everything in between is a307 * giant bit array.  The number of bits that fit on a page obviously308 * depends on the page size and the header/trailer overhead.  We require309 * the number of bits per page to be a power of 2.310 */311#define BMPGSZ_BYTE(metap)		((metap)->hashm_bmsize)312#define BMPGSZ_BIT(metap)		((metap)->hashm_bmsize << BYTE_TO_BIT)313#define BMPG_SHIFT(metap)		((metap)->hashm_bmshift)314#define BMPG_MASK(metap)		(BMPGSZ_BIT(metap) - 1)315 316#define HashPageGetBitmap(page) \317	((uint32 *) PageGetContents(page))318 319#define HashGetMaxBitmapSize(page) \320	(PageGetPageSize((Page) page) - \321	 (MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(HashPageOpaqueData))))322 323#define HashPageGetMeta(page) \324	((HashMetaPage) PageGetContents(page))325 326/*327 * The number of bits in an ovflpage bitmap word.328 */329#define BITS_PER_MAP	32		/* Number of bits in uint32 */330 331/* Given the address of the beginning of a bit map, clear/set the nth bit */332#define CLRBIT(A, N)	((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))333#define SETBIT(A, N)	((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))334#define ISSET(A, N)		((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))335 336/*337 * page-level and high-level locking modes (see README)338 */339#define HASH_READ		BUFFER_LOCK_SHARE340#define HASH_WRITE		BUFFER_LOCK_EXCLUSIVE341#define HASH_NOLOCK		(-1)342 343/*344 * When a new operator class is declared, we require that the user supply345 * us with an amproc function for hashing a key of the new type, returning346 * a 32-bit hash value.  We call this the "standard" hash function.  We347 * also allow an optional "extended" hash function which accepts a salt and348 * returns a 64-bit hash value.  This is highly recommended but, for reasons349 * of backward compatibility, optional.350 *351 * When the salt is 0, the low 32 bits of the value returned by the extended352 * hash function should match the value that would have been returned by the353 * standard hash function.354 */355#define HASHSTANDARD_PROC		1356#define HASHEXTENDED_PROC		2357#define HASHOPTIONS_PROC		3358#define HASHNProcs				3359 360 361/* public routines */362 363extern IndexBuildResult *hashbuild(Relation heap, Relation index,364								   struct IndexInfo *indexInfo);365extern void hashbuildempty(Relation index);366extern bool hashinsert(Relation rel, Datum *values, bool *isnull,367					   ItemPointer ht_ctid, Relation heapRel,368					   IndexUniqueCheck checkUnique,369					   bool indexUnchanged,370					   struct IndexInfo *indexInfo);371extern bool hashgettuple(IndexScanDesc scan, ScanDirection dir);372extern int64 hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);373extern IndexScanDesc hashbeginscan(Relation rel, int nkeys, int norderbys);374extern void hashrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,375					   ScanKey orderbys, int norderbys);376extern void hashendscan(IndexScanDesc scan);377extern IndexBulkDeleteResult *hashbulkdelete(IndexVacuumInfo *info,378											 IndexBulkDeleteResult *stats,379											 IndexBulkDeleteCallback callback,380											 void *callback_state);381extern IndexBulkDeleteResult *hashvacuumcleanup(IndexVacuumInfo *info,382												IndexBulkDeleteResult *stats);383extern bytea *hashoptions(Datum reloptions, bool validate);384extern bool hashvalidate(Oid opclassoid);385extern void hashadjustmembers(Oid opfamilyoid,386							  Oid opclassoid,387							  List *operators,388							  List *functions);389 390/* private routines */391 392/* hashinsert.c */393extern void _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel,394						   bool sorted);395extern OffsetNumber _hash_pgaddtup(Relation rel, Buffer buf,396								   Size itemsize, IndexTuple itup,397								   bool appendtup);398extern void _hash_pgaddmultitup(Relation rel, Buffer buf, IndexTuple *itups,399								OffsetNumber *itup_offsets, uint16 nitups);400 401/* hashovfl.c */402extern Buffer _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf, bool retain_pin);403extern BlockNumber _hash_freeovflpage(Relation rel, Buffer bucketbuf, Buffer ovflbuf,404									  Buffer wbuf, IndexTuple *itups, OffsetNumber *itup_offsets,405									  Size *tups_size, uint16 nitups, BufferAccessStrategy bstrategy);406extern void _hash_initbitmapbuffer(Buffer buf, uint16 bmsize, bool initpage);407extern void _hash_squeezebucket(Relation rel,408								Bucket bucket, BlockNumber bucket_blkno,409								Buffer bucket_buf,410								BufferAccessStrategy bstrategy);411extern uint32 _hash_ovflblkno_to_bitno(HashMetaPage metap, BlockNumber ovflblkno);412 413/* hashpage.c */414extern Buffer _hash_getbuf(Relation rel, BlockNumber blkno,415						   int access, int flags);416extern Buffer _hash_getbuf_with_condlock_cleanup(Relation rel,417												 BlockNumber blkno, int flags);418extern HashMetaPage _hash_getcachedmetap(Relation rel, Buffer *metabuf,419										 bool force_refresh);420extern Buffer _hash_getbucketbuf_from_hashkey(Relation rel, uint32 hashkey,421											  int access,422											  HashMetaPage *cachedmetap);423extern Buffer _hash_getinitbuf(Relation rel, BlockNumber blkno);424extern void _hash_initbuf(Buffer buf, uint32 max_bucket, uint32 num_bucket,425						  uint32 flag, bool initpage);426extern Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno,427							  ForkNumber forkNum);428extern Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno,429										 int access, int flags,430										 BufferAccessStrategy bstrategy);431extern void _hash_relbuf(Relation rel, Buffer buf);432extern void _hash_dropbuf(Relation rel, Buffer buf);433extern void _hash_dropscanbuf(Relation rel, HashScanOpaque so);434extern uint32 _hash_init(Relation rel, double num_tuples,435						 ForkNumber forkNum);436extern void _hash_init_metabuffer(Buffer buf, double num_tuples,437								  RegProcedure procid, uint16 ffactor, bool initpage);438extern void _hash_pageinit(Page page, Size size);439extern void _hash_expandtable(Relation rel, Buffer metabuf);440extern void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf,441							   Bucket obucket, uint32 maxbucket, uint32 highmask,442							   uint32 lowmask);443 444/* hashsearch.c */445extern bool _hash_next(IndexScanDesc scan, ScanDirection dir);446extern bool _hash_first(IndexScanDesc scan, ScanDirection dir);447 448/* hashsort.c */449typedef struct HSpool HSpool;	/* opaque struct in hashsort.c */450 451extern HSpool *_h_spoolinit(Relation heap, Relation index, uint32 num_buckets);452extern void _h_spooldestroy(HSpool *hspool);453extern void _h_spool(HSpool *hspool, ItemPointer self,454					 Datum *values, bool *isnull);455extern void _h_indexbuild(HSpool *hspool, Relation heapRel);456 457/* hashutil.c */458extern bool _hash_checkqual(IndexScanDesc scan, IndexTuple itup);459extern uint32 _hash_datum2hashkey(Relation rel, Datum key);460extern uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype);461extern Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,462								   uint32 highmask, uint32 lowmask);463extern uint32 _hash_spareindex(uint32 num_bucket);464extern uint32 _hash_get_totalbuckets(uint32 splitpoint_phase);465extern void _hash_checkpage(Relation rel, Buffer buf, int flags);466extern uint32 _hash_get_indextuple_hashkey(IndexTuple itup);467extern bool _hash_convert_tuple(Relation index,468								Datum *user_values, bool *user_isnull,469								Datum *index_values, bool *index_isnull);470extern OffsetNumber _hash_binsearch(Page page, uint32 hash_value);471extern OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value);472extern BlockNumber _hash_get_oldblock_from_newbucket(Relation rel, Bucket new_bucket);473extern BlockNumber _hash_get_newblock_from_oldbucket(Relation rel, Bucket old_bucket);474extern Bucket _hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket,475												 uint32 lowmask, uint32 maxbucket);476extern void _hash_kill_items(IndexScanDesc scan);477 478/* hash.c */479extern void hashbucketcleanup(Relation rel, Bucket cur_bucket,480							  Buffer bucket_buf, BlockNumber bucket_blkno,481							  BufferAccessStrategy bstrategy,482							  uint32 maxbucket, uint32 highmask, uint32 lowmask,483							  double *tuples_removed, double *num_index_tuples,484							  bool split_cleanup,485							  IndexBulkDeleteCallback callback, void *callback_state);486 487#endif							/* HASH_H */488