codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * gist_private.h4 *	  private declarations for GiST -- declarations related to the5 *	  internal implementation of GiST, not the public API6 *7 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group8 * Portions Copyright (c) 1994, Regents of the University of California9 *10 * src/include/access/gist_private.h11 *12 *-------------------------------------------------------------------------13 */14#ifndef GIST_PRIVATE_H15#define GIST_PRIVATE_H16 17#include "access/amapi.h"18#include "access/gist.h"19#include "access/itup.h"20#include "lib/pairingheap.h"21#include "storage/bufmgr.h"22#include "storage/buffile.h"23#include "utils/hsearch.h"24#include "access/genam.h"25 26/*27 * Maximum number of "halves" a page can be split into in one operation.28 * Typically a split produces 2 halves, but can be more if keys have very29 * different lengths, or when inserting multiple keys in one operation (as30 * when inserting downlinks to an internal node).  There is no theoretical31 * limit on this, but in practice if you get more than a handful page halves32 * in one split, there's something wrong with the opclass implementation.33 * GIST_MAX_SPLIT_PAGES is an arbitrary limit on that, used to size some34 * local arrays used during split.  Note that there is also a limit on the35 * number of buffers that can be held locked at a time, MAX_SIMUL_LWLOCKS,36 * so if you raise this higher than that limit, you'll just get a different37 * error.38 */39#define GIST_MAX_SPLIT_PAGES		7540 41/* Buffer lock modes */42#define GIST_SHARE	BUFFER_LOCK_SHARE43#define GIST_EXCLUSIVE	BUFFER_LOCK_EXCLUSIVE44#define GIST_UNLOCK BUFFER_LOCK_UNLOCK45 46typedef struct47{48	BlockNumber prev;49	uint32		freespace;50	char		tupledata[FLEXIBLE_ARRAY_MEMBER];51} GISTNodeBufferPage;52 53#define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))54/* Returns free space in node buffer page */55#define PAGE_FREE_SPACE(nbp) (nbp->freespace)56/* Checks if node buffer page is empty */57#define PAGE_IS_EMPTY(nbp) (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)58/* Checks if node buffers page don't contain sufficient space for index tuple */59#define PAGE_NO_SPACE(nbp, itup) (PAGE_FREE_SPACE(nbp) < \60										MAXALIGN(IndexTupleSize(itup)))61 62/*63 * GISTSTATE: information needed for any GiST index operation64 *65 * This struct retains call info for the index's opclass-specific support66 * functions (per index column), plus the index's tuple descriptor.67 *68 * scanCxt holds the GISTSTATE itself as well as any data that lives for the69 * lifetime of the index operation.  We pass this to the support functions70 * via fn_mcxt, so that they can store scan-lifespan data in it.  The71 * functions are invoked in tempCxt, which is typically short-lifespan72 * (that is, it's reset after each tuple).  However, tempCxt can be the same73 * as scanCxt if we're not bothering with per-tuple context resets.74 */75typedef struct GISTSTATE76{77	MemoryContext scanCxt;		/* context for scan-lifespan data */78	MemoryContext tempCxt;		/* short-term context for calling functions */79 80	TupleDesc	leafTupdesc;	/* index's tuple descriptor */81	TupleDesc	nonLeafTupdesc; /* truncated tuple descriptor for non-leaf82								 * pages */83	TupleDesc	fetchTupdesc;	/* tuple descriptor for tuples returned in an84								 * index-only scan */85 86	FmgrInfo	consistentFn[INDEX_MAX_KEYS];87	FmgrInfo	unionFn[INDEX_MAX_KEYS];88	FmgrInfo	compressFn[INDEX_MAX_KEYS];89	FmgrInfo	decompressFn[INDEX_MAX_KEYS];90	FmgrInfo	penaltyFn[INDEX_MAX_KEYS];91	FmgrInfo	picksplitFn[INDEX_MAX_KEYS];92	FmgrInfo	equalFn[INDEX_MAX_KEYS];93	FmgrInfo	distanceFn[INDEX_MAX_KEYS];94	FmgrInfo	fetchFn[INDEX_MAX_KEYS];95 96	/* Collations to pass to the support functions */97	Oid			supportCollation[INDEX_MAX_KEYS];98} GISTSTATE;99 100 101/*102 * During a GiST index search, we must maintain a queue of unvisited items,103 * which can be either individual heap tuples or whole index pages.  If it104 * is an ordered search, the unvisited items should be visited in distance105 * order.  Unvisited items at the same distance should be visited in106 * depth-first order, that is heap items first, then lower index pages, then107 * upper index pages; this rule avoids doing extra work during a search that108 * ends early due to LIMIT.109 *110 * To perform an ordered search, we use a pairing heap to manage the111 * distance-order queue.  In a non-ordered search (no order-by operators),112 * we use it to return heap tuples before unvisited index pages, to113 * ensure depth-first order, but all entries are otherwise considered114 * equal.115 */116 117/* Individual heap tuple to be visited */118typedef struct GISTSearchHeapItem119{120	ItemPointerData heapPtr;121	bool		recheck;		/* T if quals must be rechecked */122	bool		recheckDistances;	/* T if distances must be rechecked */123	HeapTuple	recontup;		/* data reconstructed from the index, used in124								 * index-only scans */125	OffsetNumber offnum;		/* track offset in page to mark tuple as126								 * LP_DEAD */127} GISTSearchHeapItem;128 129/* Unvisited item, either index page or heap tuple */130typedef struct GISTSearchItem131{132	pairingheap_node phNode;133	BlockNumber blkno;			/* index page number, or InvalidBlockNumber */134	union135	{136		GistNSN		parentlsn;	/* parent page's LSN, if index page */137		/* we must store parentlsn to detect whether a split occurred */138		GISTSearchHeapItem heap;	/* heap info, if heap tuple */139	}			data;140 141	/* numberOfOrderBys entries */142	IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER];143} GISTSearchItem;144 145#define GISTSearchItemIsHeap(item)	((item).blkno == InvalidBlockNumber)146 147#define SizeOfGISTSearchItem(n_distances) \148	(offsetof(GISTSearchItem, distances) + \149	 sizeof(IndexOrderByDistance) * (n_distances))150 151/*152 * GISTScanOpaqueData: private state for a scan of a GiST index153 */154typedef struct GISTScanOpaqueData155{156	GISTSTATE  *giststate;		/* index information, see above */157	Oid		   *orderByTypes;	/* datatypes of ORDER BY expressions */158 159	pairingheap *queue;			/* queue of unvisited items */160	MemoryContext queueCxt;		/* context holding the queue */161	bool		qual_ok;		/* false if qual can never be satisfied */162	bool		firstCall;		/* true until first gistgettuple call */163 164	/* pre-allocated workspace arrays */165	IndexOrderByDistance *distances;	/* output area for gistindex_keytest */166 167	/* info about killed items if any (killedItems is NULL if never used) */168	OffsetNumber *killedItems;	/* offset numbers of killed items */169	int			numKilled;		/* number of currently stored items */170	BlockNumber curBlkno;		/* current number of block */171	GistNSN		curPageLSN;		/* pos in the WAL stream when page was read */172 173	/* In a non-ordered search, returnable heap items are stored here: */174	GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];175	OffsetNumber nPageData;		/* number of valid items in array */176	OffsetNumber curPageData;	/* next item to return */177	MemoryContext pageDataCxt;	/* context holding the fetched tuples, for178								 * index-only scans */179} GISTScanOpaqueData;180 181typedef GISTScanOpaqueData *GISTScanOpaque;182 183/* despite the name, gistxlogPage is not part of any xlog record */184typedef struct gistxlogPage185{186	BlockNumber blkno;187	int			num;			/* number of index tuples following */188} gistxlogPage;189 190/* SplitedPageLayout - gistSplit function result */191typedef struct SplitedPageLayout192{193	gistxlogPage block;194	IndexTupleData *list;195	int			lenlist;196	IndexTuple	itup;			/* union key for page */197	Page		page;			/* to operate */198	Buffer		buffer;			/* to write after all proceed */199 200	struct SplitedPageLayout *next;201} SplitedPageLayout;202 203/*204 * GISTInsertStack used for locking buffers and transfer arguments during205 * insertion206 */207typedef struct GISTInsertStack208{209	/* current page */210	BlockNumber blkno;211	Buffer		buffer;212	Page		page;213 214	/*215	 * log sequence number from page->lsn to recognize page update and compare216	 * it with page's nsn to recognize page split217	 */218	GistNSN		lsn;219 220	/*221	 * If set, we split the page while descending the tree to find an222	 * insertion target. It means that we need to retry from the parent,223	 * because the downlink of this page might no longer cover the new key.224	 */225	bool		retry_from_parent;226 227	/* offset of the downlink in the parent page, that points to this page */228	OffsetNumber downlinkoffnum;229 230	/* pointer to parent */231	struct GISTInsertStack *parent;232} GISTInsertStack;233 234/* Working state and results for multi-column split logic in gistsplit.c */235typedef struct GistSplitVector236{237	GIST_SPLITVEC splitVector;	/* passed to/from user PickSplit method */238 239	Datum		spl_lattr[INDEX_MAX_KEYS];	/* Union of subkeys in240											 * splitVector.spl_left */241	bool		spl_lisnull[INDEX_MAX_KEYS];242 243	Datum		spl_rattr[INDEX_MAX_KEYS];	/* Union of subkeys in244											 * splitVector.spl_right */245	bool		spl_risnull[INDEX_MAX_KEYS];246 247	bool	   *spl_dontcare;	/* flags tuples which could go to either side248								 * of the split for zero penalty */249} GistSplitVector;250 251typedef struct252{253	Relation	r;254	Relation	heapRel;255	Size		freespace;		/* free space to be left */256	bool		is_build;257 258	GISTInsertStack *stack;259} GISTInsertState;260 261/* root page of a gist index */262#define GIST_ROOT_BLKNO				0263 264/*265 * Before PostgreSQL 9.1, we used to rely on so-called "invalid tuples" on266 * inner pages to finish crash recovery of incomplete page splits. If a crash267 * happened in the middle of a page split, so that the downlink pointers were268 * not yet inserted, crash recovery inserted a special downlink pointer. The269 * semantics of an invalid tuple was that it if you encounter one in a scan,270 * it must always be followed, because we don't know if the tuples on the271 * child page match or not.272 *273 * We no longer create such invalid tuples, we now mark the left-half of such274 * an incomplete split with the F_FOLLOW_RIGHT flag instead, and finish the275 * split properly the next time we need to insert on that page. To retain276 * on-disk compatibility for the sake of pg_upgrade, we still store 0xffff as277 * the offset number of all inner tuples. If we encounter any invalid tuples278 * with 0xfffe during insertion, we throw an error, though scans still handle279 * them. You should only encounter invalid tuples if you pg_upgrade a pre-9.1280 * gist index which already has invalid tuples in it because of a crash. That281 * should be rare, and you are recommended to REINDEX anyway if you have any282 * invalid tuples in an index, so throwing an error is as far as we go with283 * supporting that.284 */285#define TUPLE_IS_VALID		0xffff286#define TUPLE_IS_INVALID	0xfffe287 288#define  GistTupleIsInvalid(itup)	( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )289#define  GistTupleSetValid(itup)	ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )290 291 292 293 294/*295 * A buffer attached to an internal node, used when building an index in296 * buffering mode.297 */298typedef struct299{300	BlockNumber nodeBlocknum;	/* index block # this buffer is for */301	int32		blocksCount;	/* current # of blocks occupied by buffer */302 303	BlockNumber pageBlocknum;	/* temporary file block # */304	GISTNodeBufferPage *pageBuffer; /* in-memory buffer page */305 306	/* is this buffer queued for emptying? */307	bool		queuedForEmptying;308 309	/* is this a temporary copy, not in the hash table? */310	bool		isTemp;311 312	int			level;			/* 0 == leaf */313} GISTNodeBuffer;314 315/*316 * Does specified level have buffers? (Beware of multiple evaluation of317 * arguments.)318 */319#define LEVEL_HAS_BUFFERS(nlevel, gfbb) \320	((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \321	 (nlevel) != (gfbb)->rootlevel)322 323/* Is specified buffer at least half-filled (should be queued for emptying)? */324#define BUFFER_HALF_FILLED(nodeBuffer, gfbb) \325	((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)326 327/*328 * Is specified buffer full? Our buffers can actually grow indefinitely,329 * beyond the "maximum" size, so this just means whether the buffer has grown330 * beyond the nominal maximum size.331 */332#define BUFFER_OVERFLOWED(nodeBuffer, gfbb) \333	((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)334 335/*336 * Data structure with general information about build buffers.337 */338typedef struct GISTBuildBuffers339{340	/* Persistent memory context for the buffers and metadata. */341	MemoryContext context;342 343	BufFile    *pfile;			/* Temporary file to store buffers in */344	long		nFileBlocks;	/* Current size of the temporary file */345 346	/*347	 * resizable array of free blocks.348	 */349	long	   *freeBlocks;350	int			nFreeBlocks;	/* # of currently free blocks in the array */351	int			freeBlocksLen;	/* current allocated length of the array */352 353	/* Hash for buffers by block number */354	HTAB	   *nodeBuffersTab;355 356	/* List of buffers scheduled for emptying */357	List	   *bufferEmptyingQueue;358 359	/*360	 * Parameters to the buffering build algorithm. levelStep determines which361	 * levels in the tree have buffers, and pagesPerBuffer determines how362	 * large each buffer is.363	 */364	int			levelStep;365	int			pagesPerBuffer;366 367	/* Array of lists of buffers on each level, for final emptying */368	List	  **buffersOnLevels;369	int			buffersOnLevelsLen;370 371	/*372	 * Dynamically-sized array of buffers that currently have their last page373	 * loaded in main memory.374	 */375	GISTNodeBuffer **loadedBuffers;376	int			loadedBuffersCount; /* # of entries in loadedBuffers */377	int			loadedBuffersLen;	/* allocated size of loadedBuffers */378 379	/* Level of the current root node (= height of the index tree - 1) */380	int			rootlevel;381} GISTBuildBuffers;382 383/* GiSTOptions->buffering_mode values */384typedef enum GistOptBufferingMode385{386	GIST_OPTION_BUFFERING_AUTO,387	GIST_OPTION_BUFFERING_ON,388	GIST_OPTION_BUFFERING_OFF389} GistOptBufferingMode;390 391/*392 * Storage type for GiST's reloptions393 */394typedef struct GiSTOptions395{396	int32		vl_len_;		/* varlena header (do not touch directly!) */397	int			fillfactor;		/* page fill factor in percent (0..100) */398	GistOptBufferingMode buffering_mode;	/* buffering build mode */399} GiSTOptions;400 401/* gist.c */402extern void gistbuildempty(Relation index);403extern bool gistinsert(Relation r, Datum *values, bool *isnull,404					   ItemPointer ht_ctid, Relation heapRel,405					   IndexUniqueCheck checkUnique,406					   bool indexUnchanged,407					   struct IndexInfo *indexInfo);408extern MemoryContext createTempGistContext(void);409extern GISTSTATE *initGISTstate(Relation index);410extern void freeGISTstate(GISTSTATE *giststate);411extern void gistdoinsert(Relation r,412						 IndexTuple itup,413						 Size freespace,414						 GISTSTATE *giststate,415						 Relation heapRel,416						 bool is_build);417 418/* A List of these is returned from gistplacetopage() in *splitinfo */419typedef struct420{421	Buffer		buf;			/* the split page "half" */422	IndexTuple	downlink;		/* downlink for this half. */423} GISTPageSplitInfo;424 425extern bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,426							Buffer buffer,427							IndexTuple *itup, int ntup,428							OffsetNumber oldoffnum, BlockNumber *newblkno,429							Buffer leftchildbuf,430							List **splitinfo,431							bool markfollowright,432							Relation heapRel,433							bool is_build);434 435extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,436									int len, GISTSTATE *giststate);437 438/* gistxlog.c */439extern XLogRecPtr gistXLogPageDelete(Buffer buffer,440									 FullTransactionId xid, Buffer parentBuffer,441									 OffsetNumber downlinkOffset);442 443extern void gistXLogPageReuse(Relation rel, Relation heaprel, BlockNumber blkno,444							  FullTransactionId deleteXid);445 446extern XLogRecPtr gistXLogUpdate(Buffer buffer,447								 OffsetNumber *todelete, int ntodelete,448								 IndexTuple *itup, int ituplen,449								 Buffer leftchildbuf);450 451extern XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete,452								 int ntodelete, TransactionId snapshotConflictHorizon,453								 Relation heaprel);454 455extern XLogRecPtr gistXLogSplit(bool page_is_leaf,456								SplitedPageLayout *dist,457								BlockNumber origrlink, GistNSN orignsn,458								Buffer leftchildbuf, bool markfollowright);459 460extern XLogRecPtr gistXLogAssignLSN(void);461 462/* gistget.c */463extern bool gistgettuple(IndexScanDesc scan, ScanDirection dir);464extern int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);465extern bool gistcanreturn(Relation index, int attno);466 467/* gistvalidate.c */468extern bool gistvalidate(Oid opclassoid);469extern void gistadjustmembers(Oid opfamilyoid,470							  Oid opclassoid,471							  List *operators,472							  List *functions);473 474/* gistutil.c */475 476#define GiSTPageSize   \477	( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )478 479#define GIST_MIN_FILLFACTOR			10480#define GIST_DEFAULT_FILLFACTOR		90481 482extern bytea *gistoptions(Datum reloptions, bool validate);483extern bool gistproperty(Oid index_oid, int attno,484						 IndexAMProperty prop, const char *propname,485						 bool *res, bool *isnull);486extern bool gistfitpage(IndexTuple *itvec, int len);487extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);488extern void gistcheckpage(Relation rel, Buffer buf);489extern Buffer gistNewBuffer(Relation r, Relation heaprel);490extern bool gistPageRecyclable(Page page);491extern void gistfillbuffer(Page page, IndexTuple *itup, int len,492						   OffsetNumber off);493extern IndexTuple *gistextractpage(Page page, int *len /* out */ );494extern IndexTuple *gistjoinvector(IndexTuple *itvec, int *len,495								  IndexTuple *additvec, int addlen);496extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);497 498extern IndexTuple gistunion(Relation r, IndexTuple *itvec,499							int len, GISTSTATE *giststate);500extern IndexTuple gistgetadjusted(Relation r,501								  IndexTuple oldtup,502								  IndexTuple addtup,503								  GISTSTATE *giststate);504extern IndexTuple gistFormTuple(GISTSTATE *giststate,505								Relation r, Datum *attdata, bool *isnull, bool isleaf);506extern void gistCompressValues(GISTSTATE *giststate, Relation r,507							   Datum *attdata, bool *isnull, bool isleaf, Datum *compatt);508 509extern OffsetNumber gistchoose(Relation r, Page p,510							   IndexTuple it,511							   GISTSTATE *giststate);512 513extern void GISTInitBuffer(Buffer b, uint32 f);514extern void gistinitpage(Page page, uint32 f);515extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,516						   Datum k, Relation r, Page pg, OffsetNumber o,517						   bool l, bool isNull);518 519extern float gistpenalty(GISTSTATE *giststate, int attno,520						 GISTENTRY *orig, bool isNullOrig,521						 GISTENTRY *add, bool isNullAdd);522extern void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,523							   Datum *attr, bool *isnull);524extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);525extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,526							  OffsetNumber o, GISTENTRY *attdata, bool *isnull);527extern HeapTuple gistFetchTuple(GISTSTATE *giststate, Relation r,528								IndexTuple tuple);529extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,530							 GISTENTRY *entry1, bool isnull1,531							 GISTENTRY *entry2, bool isnull2,532							 Datum *dst, bool *dstisnull);533 534extern XLogRecPtr gistGetFakeLSN(Relation rel);535 536/* gistvacuum.c */537extern IndexBulkDeleteResult *gistbulkdelete(IndexVacuumInfo *info,538											 IndexBulkDeleteResult *stats,539											 IndexBulkDeleteCallback callback,540											 void *callback_state);541extern IndexBulkDeleteResult *gistvacuumcleanup(IndexVacuumInfo *info,542												IndexBulkDeleteResult *stats);543 544/* gistsplit.c */545extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,546						   int len, GISTSTATE *giststate,547						   GistSplitVector *v,548						   int attno);549 550/* gistbuild.c */551extern IndexBuildResult *gistbuild(Relation heap, Relation index,552								   struct IndexInfo *indexInfo);553 554/* gistbuildbuffers.c */555extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep,556											  int maxLevel);557extern GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb,558										 GISTSTATE *giststate,559										 BlockNumber nodeBlocknum, int level);560extern void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb,561									 GISTNodeBuffer *nodeBuffer, IndexTuple itup);562extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb,563									  GISTNodeBuffer *nodeBuffer, IndexTuple *itup);564extern void gistFreeBuildBuffers(GISTBuildBuffers *gfbb);565extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb,566											GISTSTATE *giststate, Relation r,567											int level, Buffer buffer,568											List *splitinfo);569extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);570 571#endif							/* GIST_PRIVATE_H */572