PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hash.h File Reference
#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "fmgr.h"
#include "lib/stringinfo.h"
#include "storage/bufmgr.h"
#include "storage/lockdefs.h"
#include "utils/hsearch.h"
#include "utils/relcache.h"
Include dependency graph for hash.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  HashPageOpaqueData
 
struct  HashScanOpaqueData
 
struct  HashMetaPageData
 

Macros

#define InvalidBucket   ((Bucket) 0xFFFFFFFF)
 
#define BUCKET_TO_BLKNO(metap, B)   ((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_log2((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_TYPE   (LH_OVERFLOW_PAGE|LH_BUCKET_PAGE|LH_BITMAP_PAGE|LH_META_PAGE)
 
#define H_NEEDS_SPLIT_CLEANUP(opaque)   ((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP)
 
#define H_BUCKET_BEING_SPLIT(opaque)   ((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT)
 
#define H_BUCKET_BEING_POPULATED(opaque)   ((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED)
 
#define HASHO_PAGE_ID   0xFF80
 
#define HASH_METAPAGE   0 /* metapage is always block 0 */
 
#define HASH_MAGIC   0x6440640
 
#define HASH_VERSION   2 /* 2 signifies only hash key value is stored */
 
#define HASH_MAX_SPLITPOINTS   32
 
#define HASH_MAX_BITMAPS   128
 
#define HashMaxItemSize(page)
 
#define INDEX_MOVED_BY_SPLIT_MASK   0x2000
 
#define HASH_MIN_FILLFACTOR   10
 
#define HASH_DEFAULT_FILLFACTOR   75
 
#define BYTE_TO_BIT   3 /* 2^3 bits/byte */
 
#define ALL_SET   ((uint32) ~0)
 
#define BMPGSZ_BYTE(metap)   ((metap)->hashm_bmsize)
 
#define BMPGSZ_BIT(metap)   ((metap)->hashm_bmsize << BYTE_TO_BIT)
 
#define BMPG_SHIFT(metap)   ((metap)->hashm_bmshift)
 
#define BMPG_MASK(metap)   (BMPGSZ_BIT(metap) - 1)
 
#define HashPageGetBitmap(page)   ((uint32 *) PageGetContents(page))
 
#define HashGetMaxBitmapSize(page)
 
#define HashPageGetMeta(page)   ((HashMetaPage) PageGetContents(page))
 
#define BITS_PER_MAP   32 /* Number of bits in uint32 */
 
#define CLRBIT(A, N)   ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
 
#define SETBIT(A, N)   ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
 
#define ISSET(A, N)   ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
 
#define HASH_READ   BUFFER_LOCK_SHARE
 
#define HASH_WRITE   BUFFER_LOCK_EXCLUSIVE
 
#define HASH_NOLOCK   (-1)
 
#define HTEqualStrategyNumber   1
 
#define HTMaxStrategyNumber   1
 
#define HASHPROC   1
 
#define HASHNProcs   1
 

Typedefs

typedef uint32 Bucket
 
typedef struct HashPageOpaqueData HashPageOpaqueData
 
typedef HashPageOpaqueDataHashPageOpaque
 
typedef struct HashScanOpaqueData HashScanOpaqueData
 
typedef HashScanOpaqueDataHashScanOpaque
 
typedef struct HashMetaPageData HashMetaPageData
 
typedef HashMetaPageDataHashMetaPage
 
typedef struct HSpool HSpool
 

Functions

IndexBuildResulthashbuild (Relation heap, Relation index, struct IndexInfo *indexInfo)
 
void hashbuildempty (Relation index)
 
bool hashinsert (Relation rel, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, struct IndexInfo *indexInfo)
 
bool hashgettuple (IndexScanDesc scan, ScanDirection dir)
 
int64 hashgetbitmap (IndexScanDesc scan, TIDBitmap *tbm)
 
IndexScanDesc hashbeginscan (Relation rel, int nkeys, int norderbys)
 
void hashrescan (IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
 
void hashendscan (IndexScanDesc scan)
 
IndexBulkDeleteResulthashbulkdelete (IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
 
IndexBulkDeleteResulthashvacuumcleanup (IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
 
byteahashoptions (Datum reloptions, bool validate)
 
bool hashvalidate (Oid opclassoid)
 
Datum hash_any (register const unsigned char *k, register int keylen)
 
Datum hash_uint32 (uint32 k)
 
void _hash_doinsert (Relation rel, IndexTuple itup)
 
OffsetNumber _hash_pgaddtup (Relation rel, Buffer buf, Size itemsize, IndexTuple itup)
 
Buffer _hash_addovflpage (Relation rel, Buffer metabuf, Buffer buf, bool retain_pin)
 
BlockNumber _hash_freeovflpage (Relation rel, Buffer ovflbuf, Buffer wbuf, BufferAccessStrategy bstrategy)
 
void _hash_initbitmap (Relation rel, HashMetaPage metap, BlockNumber blkno, ForkNumber forkNum)
 
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)
 
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_metapinit (Relation rel, double num_tuples, ForkNumber forkNum)
 
void _hash_pageinit (Page page, Size size)
 
void _hash_expandtable (Relation rel, Buffer metabuf)
 
void _hash_finish_split (Relation rel, Buffer metabuf, Buffer obuf, Bucket obucket, uint32 maxbucket, uint32 highmask, uint32 lowmask)
 
bool _hash_next (IndexScanDesc scan, ScanDirection dir)
 
bool _hash_first (IndexScanDesc scan, ScanDirection dir)
 
bool _hash_step (IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
 
HSpool_h_spoolinit (Relation heap, Relation index, uint32 num_buckets)
 
void _h_spooldestroy (HSpool *hspool)
 
void _h_spool (HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
 
void _h_indexbuild (HSpool *hspool)
 
bool _hash_checkqual (IndexScanDesc scan, IndexTuple itup)
 
uint32 _hash_datum2hashkey (Relation rel, Datum key)
 
uint32 _hash_datum2hashkey_type (Relation rel, Datum key, Oid keytype)
 
Bucket _hash_hashkey2bucket (uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
 
uint32 _hash_log2 (uint32 num)
 
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 hashbucketcleanup (Relation rel, Bucket cur_bucket, Buffer bucket_buf, BlockNumber bucket_blkno, BufferAccessStrategy bstrategy, uint32 maxbucket, uint32 highmask, uint32 lowmask, double *tuples_removed, double *num_index_tuples, bool bucket_has_garbage, IndexBulkDeleteCallback callback, void *callback_state)
 

Macro Definition Documentation

#define ALL_SET   ((uint32) ~0)

Definition at line 217 of file hash.h.

Referenced by _hash_getovflpage().

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

Definition at line 244 of file hash.h.

Referenced by _hash_firstfreebit(), and _hash_getovflpage().

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

Definition at line 229 of file hash.h.

Referenced by _hash_freeovflpage(), _hash_getovflpage(), _hash_metapinit(), and hash_bitmap_info().

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

Definition at line 228 of file hash.h.

Referenced by _hash_freeovflpage(), _hash_getovflpage(), _hash_metapinit(), and hash_bitmap_info().

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

Definition at line 227 of file hash.h.

Referenced by _hash_getovflpage().

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

Definition at line 226 of file hash.h.

Referenced by _hash_initbitmap().

#define BUCKET_TO_BLKNO (   metap,
 
)    ((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_log2((B)+1)-1] : 0)) + 1)
#define BYTE_TO_BIT   3 /* 2^3 bits/byte */

Definition at line 216 of file hash.h.

Referenced by _hash_metapinit().

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

Definition at line 247 of file hash.h.

#define H_BUCKET_BEING_POPULATED (   opaque)    ((opaque)->hasho_flag & LH_BUCKET_BEING_POPULATED)

Definition at line 88 of file hash.h.

Referenced by _hash_first().

#define H_BUCKET_BEING_SPLIT (   opaque)    ((opaque)->hasho_flag & LH_BUCKET_BEING_SPLIT)

Definition at line 87 of file hash.h.

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

#define H_NEEDS_SPLIT_CLEANUP (   opaque)    ((opaque)->hasho_flag & LH_BUCKET_NEEDS_SPLIT_CLEANUP)

Definition at line 86 of file hash.h.

Referenced by _hash_expandtable(), and hashbulkdelete().

#define HASH_DEFAULT_FILLFACTOR   75

Definition at line 211 of file hash.h.

Referenced by _hash_metapinit().

#define HASH_MAGIC   0x6440640

Definition at line 148 of file hash.h.

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

#define HASH_MAX_BITMAPS   128

Definition at line 172 of file hash.h.

Referenced by _hash_initbitmap(), and hash_metapage_info().

#define HASH_MAX_SPLITPOINTS   32

Definition at line 171 of file hash.h.

Referenced by _hash_metapinit(), and hash_metapage_info().

#define HASH_MIN_FILLFACTOR   10

Definition at line 210 of file hash.h.

#define HASH_NOLOCK   (-1)

Definition at line 256 of file hash.h.

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

#define HASH_VERSION   2 /* 2 signifies only hash key value is stored */

Definition at line 149 of file hash.h.

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

#define HashGetMaxBitmapSize (   page)
Value:
(PageGetPageSize((Page) page) - \
#define SizeOfPageHeaderData
Definition: bufpage.h:213
#define PageGetPageSize(page)
Definition: bufpage.h:265
#define MAXALIGN(LEN)
Definition: c.h:584
Pointer Page
Definition: bufpage.h:74

Definition at line 234 of file hash.h.

Referenced by _hash_metapinit().

#define HashMaxItemSize (   page)
Value:
sizeof(ItemIdData) - \
#define SizeOfPageHeaderData
Definition: bufpage.h:213
#define PageGetPageSize(page)
Definition: bufpage.h:265
#define MAXALIGN(LEN)
Definition: c.h:584
#define MAXALIGN_DOWN(LEN)
Definition: c.h:596

Definition at line 202 of file hash.h.

Referenced by _hash_doinsert().

#define HASHNProcs   1

Definition at line 270 of file hash.h.

Referenced by hashhandler().

#define HASHO_PAGE_ID   0xFF80
#define HashPageGetBitmap (   page)    ((uint32 *) PageGetContents(page))

Definition at line 231 of file hash.h.

Referenced by _hash_freeovflpage(), _hash_getovflpage(), _hash_initbitmap(), and hash_bitmap_info().

#define HTEqualStrategyNumber   1
#define HTMaxStrategyNumber   1

Definition at line 262 of file hash.h.

Referenced by hashhandler(), and hashvalidate().

#define INDEX_MOVED_BY_SPLIT_MASK   0x2000

Definition at line 208 of file hash.h.

Referenced by _hash_splitbucket_guts(), and _hash_step().

#define InvalidBucket   ((Bucket) 0xFFFFFFFF)

Definition at line 36 of file hash.h.

Referenced by hashbucketcleanup().

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

Definition at line 249 of file hash.h.

Referenced by _hash_freeovflpage(), and hash_bitmap_info().

#define LH_BITMAP_PAGE   (1 << 2)
#define LH_BUCKET_BEING_POPULATED   (1 << 4)

Definition at line 57 of file hash.h.

Referenced by _hash_splitbucket(), and _hash_splitbucket_guts().

#define LH_BUCKET_BEING_SPLIT   (1 << 5)

Definition at line 58 of file hash.h.

Referenced by _hash_splitbucket(), and _hash_splitbucket_guts().

#define LH_BUCKET_NEEDS_SPLIT_CLEANUP   (1 << 6)

Definition at line 59 of file hash.h.

Referenced by _hash_splitbucket_guts(), and hashbucketcleanup().

Definition at line 61 of file hash.h.

Referenced by verify_hash_page().

#define LH_UNUSED_PAGE   (0)

Definition at line 52 of file hash.h.

Referenced by pgstat_hash_page().

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

Definition at line 248 of file hash.h.

Typedef Documentation

Definition at line 34 of file hash.h.

Definition at line 197 of file hash.h.

Definition at line 84 of file hash.h.

Definition at line 140 of file hash.h.

Definition at line 352 of file hash.h.

Function Documentation

void _h_indexbuild ( HSpool hspool)

Definition at line 104 of file hashsort.c.

References _hash_doinsert(), _hash_get_indextuple_hashkey(), Assert, HSpool::hash_mask, HSpool::index, NULL, HSpool::sortstate, tuplesort_getindextuple(), and tuplesort_performsort().

Referenced by hashbuild().

105 {
106  IndexTuple itup;
107 #ifdef USE_ASSERT_CHECKING
108  uint32 hashkey = 0;
109 #endif
110 
112 
113  while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
114  {
115  /*
116  * Technically, it isn't critical that hash keys be found in sorted
117  * order, since this sorting is only used to increase locality of
118  * access as a performance optimization. It still seems like a good
119  * idea to test tuplesort.c's handling of hash index tuple sorts
120  * through an assertion, though.
121  */
122 #ifdef USE_ASSERT_CHECKING
123  uint32 lasthashkey = hashkey;
124 
125  hashkey = _hash_get_indextuple_hashkey(itup) & hspool->hash_mask;
126  Assert(hashkey >= lasthashkey);
127 #endif
128 
129  _hash_doinsert(hspool->index, itup);
130  }
131 }
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2154
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1763
Tuplesortstate * sortstate
Definition: hashsort.c:38
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
unsigned int uint32
Definition: c.h:265
void _hash_doinsert(Relation rel, IndexTuple itup)
Definition: hashinsert.c:29
Relation index
Definition: hashsort.c:39
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
uint32 hash_mask
Definition: hashsort.c:40
void _h_spool ( HSpool hspool,
ItemPointer  self,
Datum values,
bool isnull 
)

Definition at line 93 of file hashsort.c.

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

Referenced by hashbuildCallback().

94 {
96  self, values, isnull);
97 }
Tuplesortstate * sortstate
Definition: hashsort.c:38
Relation index
Definition: hashsort.c:39
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1397
static Datum values[MAXATTR]
Definition: bootstrap.c:162
void _h_spooldestroy ( HSpool hspool)

Definition at line 83 of file hashsort.c.

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

Referenced by hashbuild().

84 {
85  tuplesort_end(hspool->sortstate);
86  pfree(hspool);
87 }
Tuplesortstate * sortstate
Definition: hashsort.c:38
void pfree(void *pointer)
Definition: mcxt.c:992
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1157
HSpool* _h_spoolinit ( Relation  heap,
Relation  index,
uint32  num_buckets 
)

Definition at line 48 of file hashsort.c.

References _hash_log2(), HSpool::hash_mask, HSpool::index, maintenance_work_mem, palloc0(), HSpool::sortstate, and tuplesort_begin_index_hash().

Referenced by hashbuild().

49 {
50  HSpool *hspool = (HSpool *) palloc0(sizeof(HSpool));
51 
52  hspool->index = index;
53 
54  /*
55  * Determine the bitmask for hash code values. Since there are currently
56  * num_buckets buckets in the index, the appropriate mask can be computed
57  * as follows.
58  *
59  * Note: at present, the passed-in num_buckets is always a power of 2, so
60  * we could just compute num_buckets - 1. We prefer not to assume that
61  * here, though.
62  */
63  hspool->hash_mask = (((uint32) 1) << _hash_log2(num_buckets)) - 1;
64 
65  /*
66  * We size the sort area as maintenance_work_mem rather than work_mem to
67  * speed index creation. This should be OK since a single backend can't
68  * run multiple index creations in parallel.
69  */
71  index,
72  hspool->hash_mask,
74  false);
75 
76  return hspool;
77 }
Tuplesortstate * sortstate
Definition: hashsort.c:38
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 hash_mask, int workMem, bool randomAccess)
Definition: tuplesort.c:992
unsigned int uint32
Definition: c.h:265
void * palloc0(Size size)
Definition: mcxt.c:920
Relation index
Definition: hashsort.c:39
int maintenance_work_mem
Definition: globals.c:113
uint32 _hash_log2(uint32 num)
Definition: hashutil.c:140
uint32 hash_mask
Definition: hashsort.c:40
Buffer _hash_addovflpage ( Relation  rel,
Buffer  metabuf,
Buffer  buf,
bool  retain_pin 
)

Definition at line 109 of file hashovfl.c.

References _hash_checkpage(), _hash_getbuf(), _hash_getovflpage(), _hash_relbuf(), Assert, BlockNumberIsValid, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, HASH_WRITE, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, InvalidBlockNumber, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, LockBuffer(), MarkBufferDirty(), and PageGetSpecialPointer.

Referenced by _hash_doinsert(), and _hash_splitbucket_guts().

110 {
111  Buffer ovflbuf;
112  Page page;
113  Page ovflpage;
114  HashPageOpaque pageopaque;
115  HashPageOpaque ovflopaque;
116 
117  /* allocate and lock an empty overflow page */
118  ovflbuf = _hash_getovflpage(rel, metabuf);
119 
120  /*
121  * Write-lock the tail page. It is okay to hold two buffer locks here
122  * since there cannot be anyone else contending for access to ovflbuf.
123  */
125 
126  /* probably redundant... */
128 
129  /* loop to find current tail page, in case someone else inserted too */
130  for (;;)
131  {
132  BlockNumber nextblkno;
133 
134  page = BufferGetPage(buf);
135  pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
136  nextblkno = pageopaque->hasho_nextblkno;
137 
138  if (!BlockNumberIsValid(nextblkno))
139  break;
140 
141  /* we assume we do not need to write the unmodified page */
142  if (retain_pin)
143  {
144  /* pin will be retained only for the primary bucket page */
145  Assert(pageopaque->hasho_flag & LH_BUCKET_PAGE);
147  }
148  else
149  _hash_relbuf(rel, buf);
150 
151  retain_pin = false;
152 
153  buf = _hash_getbuf(rel, nextblkno, HASH_WRITE, LH_OVERFLOW_PAGE);
154  }
155 
156  /* now that we have correct backlink, initialize new overflow page */
157  ovflpage = BufferGetPage(ovflbuf);
158  ovflopaque = (HashPageOpaque) PageGetSpecialPointer(ovflpage);
160  ovflopaque->hasho_nextblkno = InvalidBlockNumber;
161  ovflopaque->hasho_bucket = pageopaque->hasho_bucket;
162  ovflopaque->hasho_flag = LH_OVERFLOW_PAGE;
163  ovflopaque->hasho_page_id = HASHO_PAGE_ID;
164 
165  MarkBufferDirty(ovflbuf);
166 
167  /* logically chain overflow page to previous page */
168  pageopaque->hasho_nextblkno = BufferGetBlockNumber(ovflbuf);
170  if (retain_pin)
171  {
172  /* pin will be retained only for the primary bucket page */
173  Assert(pageopaque->hasho_flag & LH_BUCKET_PAGE);
175  }
176  else
177  _hash_relbuf(rel, buf);
178 
179  return ovflbuf;
180 }
uint16 hasho_page_id
Definition: hash.h:81
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
static Buffer _hash_getovflpage(Relation rel, Buffer metabuf)
Definition: hashovfl.c:193
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
uint32 BlockNumber
Definition: block.h:31
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
BlockNumber hasho_prevblkno
Definition: hash.h:77
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_WRITE
Definition: hash.h:255
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
#define InvalidBlockNumber
Definition: block.h:33
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define HASHO_PAGE_ID
Definition: hash.h:96
uint16 hasho_flag
Definition: hash.h:80
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2588
BlockNumber hasho_nextblkno
Definition: hash.h:78
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
OffsetNumber _hash_binsearch ( Page  page,
uint32  hash_value 
)

Definition at line 291 of file hashutil.c.

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

Referenced by _hash_pgaddtup(), and _hash_step().

292 {
295 
296  /* Loop invariant: lower <= desired place <= upper */
297  upper = PageGetMaxOffsetNumber(page) + 1;
298  lower = FirstOffsetNumber;
299 
300  while (upper > lower)
301  {
302  OffsetNumber off;
303  IndexTuple itup;
304  uint32 hashkey;
305 
306  off = (upper + lower) / 2;
308 
309  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
310  hashkey = _hash_get_indextuple_hashkey(itup);
311  if (hashkey < hash_value)
312  lower = off + 1;
313  else
314  upper = off;
315  }
316 
317  return lower;
318 }
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:354
uint16 OffsetNumber
Definition: off.h:24
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
unsigned int uint32
Definition: c.h:265
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
#define Assert(condition)
Definition: c.h:671
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:40
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
OffsetNumber _hash_binsearch_last ( Page  page,
uint32  hash_value 
)

Definition at line 329 of file hashutil.c.

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

Referenced by _hash_step().

330 {
333 
334  /* Loop invariant: lower <= desired place <= upper */
335  upper = PageGetMaxOffsetNumber(page);
336  lower = FirstOffsetNumber - 1;
337 
338  while (upper > lower)
339  {
340  IndexTuple itup;
341  OffsetNumber off;
342  uint32 hashkey;
343 
344  off = (upper + lower + 1) / 2;
346 
347  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
348  hashkey = _hash_get_indextuple_hashkey(itup);
349  if (hashkey > hash_value)
350  upper = off - 1;
351  else
352  lower = off;
353  }
354 
355  return lower;
356 }
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:43
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:74
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:354
uint16 OffsetNumber
Definition: off.h:24
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
unsigned int uint32
Definition: c.h:265
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
#define Assert(condition)
Definition: c.h:671
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:40
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
void _hash_checkpage ( Relation  rel,
Buffer  buf,
int  flags 
)

Definition at line 158 of file hashutil.c.

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

Referenced by _hash_addovflpage(), _hash_expandtable(), _hash_first(), _hash_freeovflpage(), _hash_getbuf(), _hash_getbuf_with_condlock_cleanup(), _hash_getbuf_with_strategy(), _hash_getovflpage(), _hash_next(), _hash_pgaddtup(), _hash_step(), and hashbulkdelete().

159 {
160  Page page = BufferGetPage(buf);
161 
162  /*
163  * ReadBuffer verifies that every newly-read page passes
164  * PageHeaderIsValid, which means it either contains a reasonably sane
165  * page header or is all-zero. We have to defend against the all-zero
166  * case, however.
167  */
168  if (PageIsNew(page))
169  ereport(ERROR,
170  (errcode(ERRCODE_INDEX_CORRUPTED),
171  errmsg("index \"%s\" contains unexpected zero page at block %u",
174  errhint("Please REINDEX it.")));
175 
176  /*
177  * Additionally check that the special area looks sane.
178  */
179  if (PageGetSpecialSize(page) != MAXALIGN(sizeof(HashPageOpaqueData)))
180  ereport(ERROR,
181  (errcode(ERRCODE_INDEX_CORRUPTED),
182  errmsg("index \"%s\" contains corrupted page at block %u",
185  errhint("Please REINDEX it.")));
186 
187  if (flags)
188  {
190 
191  if ((opaque->hasho_flag & flags) == 0)
192  ereport(ERROR,
193  (errcode(ERRCODE_INDEX_CORRUPTED),
194  errmsg("index \"%s\" contains corrupted page at block %u",
197  errhint("Please REINDEX it.")));
198  }
199 
200  /*
201  * When checking the metapage, also verify magic number and version.
202  */
203  if (flags == LH_META_PAGE)
204  {
205  HashMetaPage metap = HashPageGetMeta(page);
206 
207  if (metap->hashm_magic != HASH_MAGIC)
208  ereport(ERROR,
209  (errcode(ERRCODE_INDEX_CORRUPTED),
210  errmsg("index \"%s\" is not a hash index",
211  RelationGetRelationName(rel))));
212 
213  if (metap->hashm_version != HASH_VERSION)
214  ereport(ERROR,
215  (errcode(ERRCODE_INDEX_CORRUPTED),
216  errmsg("index \"%s\" has wrong hash version",
218  errhint("Please REINDEX it.")));
219  }
220 }
int errhint(const char *fmt,...)
Definition: elog.c:987
#define LH_META_PAGE
Definition: hash.h:56
uint32 hashm_magic
Definition: hash.h:176
int errcode(int sqlerrcode)
Definition: elog.c:575
#define HASH_VERSION
Definition: hash.h:149
#define HASH_MAGIC
Definition: hash.h:148
#define ERROR
Definition: elog.h:43
uint32 hashm_version
Definition: hash.h:177
static char * buf
Definition: pg_test_fsync.c:65
#define RelationGetRelationName(relation)
Definition: rel.h:433
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define ereport(elevel, rest)
Definition: elog.h:122
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define MAXALIGN(LEN)
Definition: c.h:584
#define PageGetSpecialSize(page)
Definition: bufpage.h:297
uint16 hasho_flag
Definition: hash.h:80
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2588
#define PageIsNew(page)
Definition: bufpage.h:226
#define HashPageGetMeta(page)
Definition: hash.h:238
int errmsg(const char *fmt,...)
Definition: elog.c:797
Pointer Page
Definition: bufpage.h:74
bool _hash_checkqual ( IndexScanDesc  scan,
IndexTuple  itup 
)

Definition at line 30 of file hashutil.c.

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

Referenced by _hash_step().

31 {
32  /*
33  * Currently, we can't check any of the scan conditions since we do not
34  * have the original index entry value to supply to the sk_func. Always
35  * return true; we expect that hashgettuple already set the recheck flag
36  * to make the main indexscan code do it.
37  */
38 #ifdef NOT_USED
39  TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
40  ScanKey key = scan->keyData;
41  int scanKeySize = scan->numberOfKeys;
42 
43  while (scanKeySize > 0)
44  {
45  Datum datum;
46  bool isNull;
47  Datum test;
48 
49  datum = index_getattr(itup,
50  key->sk_attno,
51  tupdesc,
52  &isNull);
53 
54  /* assume sk_func is strict */
55  if (isNull)
56  return false;
57  if (key->sk_flags & SK_ISNULL)
58  return false;
59 
60  test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
61  datum, key->sk_argument);
62 
63  if (!DatumGetBool(test))
64  return false;
65 
66  key++;
67  scanKeySize--;
68  }
69 #endif
70 
71  return true;
72 }
static void test(void)
#define RelationGetDescr(relation)
Definition: rel.h:425
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1306
Relation indexRelation
Definition: relscan.h:89
FmgrInfo sk_func
Definition: skey.h:71
#define DatumGetBool(X)
Definition: postgres.h:401
#define SK_ISNULL
Definition: skey.h:115
uintptr_t Datum
Definition: postgres.h:374
int sk_flags
Definition: skey.h:66
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:100
ScanKey keyData
Definition: relscan.h:93
Oid sk_collation
Definition: skey.h:70
Datum sk_argument
Definition: skey.h:72
AttrNumber sk_attno
Definition: skey.h:67
bool _hash_convert_tuple ( Relation  index,
Datum user_values,
bool user_isnull,
Datum index_values,
bool index_isnull 
)

Definition at line 259 of file hashutil.c.

References _hash_datum2hashkey(), and UInt32GetDatum.

Referenced by hashbuildCallback(), and hashinsert().

262 {
263  uint32 hashkey;
264 
265  /*
266  * We do not insert null values into hash indexes. This is okay because
267  * the only supported search operator is '=', and we assume it is strict.
268  */
269  if (user_isnull[0])
270  return false;
271 
272  hashkey = _hash_datum2hashkey(index, user_values[0]);
273  index_values[0] = UInt32GetDatum(hashkey);
274  index_isnull[0] = false;
275  return true;
276 }
uint32 _hash_datum2hashkey(Relation rel, Datum key)
Definition: hashutil.c:81
unsigned int uint32
Definition: c.h:265
#define UInt32GetDatum(X)
Definition: postgres.h:501
uint32 _hash_datum2hashkey ( Relation  rel,
Datum  key 
)

Definition at line 81 of file hashutil.c.

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

Referenced by _hash_convert_tuple(), and _hash_first().

82 {
83  FmgrInfo *procinfo;
84  Oid collation;
85 
86  /* XXX assumes index has only one attribute */
87  procinfo = index_getprocinfo(rel, 1, HASHPROC);
88  collation = rel->rd_indcollation[0];
89 
90  return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
91 }
#define DatumGetUInt32(X)
Definition: postgres.h:494
Definition: fmgr.h:53
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:855
unsigned int Oid
Definition: postgres_ext.h:31
Oid * rd_indcollation
Definition: rel.h:189
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1286
#define HASHPROC
Definition: hash.h:269
uint32 _hash_datum2hashkey_type ( Relation  rel,
Datum  key,
Oid  keytype 
)

Definition at line 101 of file hashutil.c.

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

Referenced by _hash_first().

102 {
103  RegProcedure hash_proc;
104  Oid collation;
105 
106  /* XXX assumes index has only one attribute */
107  hash_proc = get_opfamily_proc(rel->rd_opfamily[0],
108  keytype,
109  keytype,
110  HASHPROC);
111  if (!RegProcedureIsValid(hash_proc))
112  elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
113  HASHPROC, keytype, keytype,
115  collation = rel->rd_indcollation[0];
116 
117  return DatumGetUInt32(OidFunctionCall1Coll(hash_proc, collation, key));
118 }
#define DatumGetUInt32(X)
Definition: postgres.h:494
regproc RegProcedure
Definition: c.h:392
unsigned int Oid
Definition: postgres_ext.h:31
Oid * rd_indcollation
Definition: rel.h:189
#define ERROR
Definition: elog.h:43
#define RegProcedureIsValid(p)
Definition: c.h:536
#define RelationGetRelationName(relation)
Definition: rel.h:433
Oid * rd_opfamily
Definition: rel.h:178
Datum OidFunctionCall1Coll(Oid functionId, Oid collation, Datum arg1)
Definition: fmgr.c:1578
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
Definition: lsyscache.c:744
#define HASHPROC
Definition: hash.h:269
#define elog
Definition: elog.h:219
void _hash_doinsert ( Relation  rel,
IndexTuple  itup 
)

Definition at line 29 of file hashinsert.c.

References _hash_addovflpage(), _hash_dropbuf(), _hash_expandtable(), _hash_finish_split(), _hash_get_indextuple_hashkey(), _hash_getbucketbuf_from_hashkey(), _hash_getbuf(), _hash_pgaddtup(), _hash_relbuf(), Assert, BlockNumberIsValid, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, ereport, errcode(), errhint(), errmsg(), ERROR, H_BUCKET_BEING_SPLIT, HASH_METAPAGE, HASH_NOLOCK, HASH_WRITE, HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_ntuples, HashMaxItemSize, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageGetMeta, IndexTupleDSize, InvalidBuffer, IsBufferCleanupOK(), LH_META_PAGE, LH_OVERFLOW_PAGE, LockBuffer(), MarkBufferDirty(), MAXALIGN, NULL, PageGetFreeSpace(), and PageGetSpecialPointer.

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

30 {
32  Buffer bucket_buf;
33  Buffer metabuf;
34  HashMetaPage metap;
35  HashMetaPage usedmetap = NULL;
36  Page metapage;
37  Page page;
38  HashPageOpaque pageopaque;
39  Size itemsz;
40  bool do_expand;
41  uint32 hashkey;
42  Bucket bucket;
43 
44  /*
45  * Get the hash key for the item (it's stored in the index tuple itself).
46  */
47  hashkey = _hash_get_indextuple_hashkey(itup);
48 
49  /* compute item size too */
50  itemsz = IndexTupleDSize(*itup);
51  itemsz = MAXALIGN(itemsz); /* be safe, PageAddItem will do this but we
52  * need to be consistent */
53 
54 restart_insert:
55 
56  /*
57  * Read the metapage. We don't lock it yet; HashMaxItemSize() will
58  * examine pd_pagesize_version, but that can't change so we can examine
59  * it without a lock.
60  */
62  metapage = BufferGetPage(metabuf);
63 
64  /*
65  * Check whether the item can fit on a hash page at all. (Eventually, we
66  * ought to try to apply TOAST methods if not.) Note that at this point,
67  * itemsz doesn't include the ItemId.
68  *
69  * XXX this is useless code if we are only storing hash keys.
70  */
71  if (itemsz > HashMaxItemSize(metapage))
72  ereport(ERROR,
73  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
74  errmsg("index row size %zu exceeds hash maximum %zu",
75  itemsz, HashMaxItemSize(metapage)),
76  errhint("Values larger than a buffer page cannot be indexed.")));
77 
78  /* Lock the primary bucket page for the target bucket. */
79  buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_WRITE,
80  &usedmetap);
81  Assert(usedmetap != NULL);
82 
83  /* remember the primary bucket buffer to release the pin on it at end. */
84  bucket_buf = buf;
85 
86  page = BufferGetPage(buf);
87  pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
88  bucket = pageopaque->hasho_bucket;
89 
90  /*
91  * If this bucket is in the process of being split, try to finish the
92  * split before inserting, because that might create room for the
93  * insertion to proceed without allocating an additional overflow page.
94  * It's only interesting to finish the split if we're trying to insert
95  * into the bucket from which we're removing tuples (the "old" bucket),
96  * not if we're trying to insert into the bucket into which tuples are
97  * being moved (the "new" bucket).
98  */
99  if (H_BUCKET_BEING_SPLIT(pageopaque) && IsBufferCleanupOK(buf))
100  {
101  /* release the lock on bucket buffer, before completing the split. */
103 
104  _hash_finish_split(rel, metabuf, buf, bucket,
105  usedmetap->hashm_maxbucket,
106  usedmetap->hashm_highmask,
107  usedmetap->hashm_lowmask);
108 
109  /* release the pin on old and meta buffer. retry for insert. */
110  _hash_dropbuf(rel, buf);
111  _hash_dropbuf(rel, metabuf);
112  goto restart_insert;
113  }
114 
115  /* Do the insertion */
116  while (PageGetFreeSpace(page) < itemsz)
117  {
118  /*
119  * no space on this page; check for an overflow page
120  */
121  BlockNumber nextblkno = pageopaque->hasho_nextblkno;
122 
123  if (BlockNumberIsValid(nextblkno))
124  {
125  /*
126  * ovfl page exists; go get it. if it doesn't have room, we'll
127  * find out next pass through the loop test above. we always
128  * release both the lock and pin if this is an overflow page, but
129  * only the lock if this is the primary bucket page, since the pin
130  * on the primary bucket must be retained throughout the scan.
131  */
132  if (buf != bucket_buf)
133  _hash_relbuf(rel, buf);
134  else
136  buf = _hash_getbuf(rel, nextblkno, HASH_WRITE, LH_OVERFLOW_PAGE);
137  page = BufferGetPage(buf);
138  }
139  else
140  {
141  /*
142  * we're at the end of the bucket chain and we haven't found a
143  * page with enough room. allocate a new overflow page.
144  */
145 
146  /* release our write lock without modifying buffer */
148 
149  /* chain to a new overflow page */
150  buf = _hash_addovflpage(rel, metabuf, buf, (buf == bucket_buf) ? true : false);
151  page = BufferGetPage(buf);
152 
153  /* should fit now, given test above */
154  Assert(PageGetFreeSpace(page) >= itemsz);
155  }
156  pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
157  Assert(pageopaque->hasho_flag == LH_OVERFLOW_PAGE);
158  Assert(pageopaque->hasho_bucket == bucket);
159  }
160 
161  /* found page with enough space, so add the item here */
162  (void) _hash_pgaddtup(rel, buf, itemsz, itup);
163 
164  /*
165  * dirty and release the modified page. if the page we modified was an
166  * overflow page, we also need to separately drop the pin we retained on
167  * the primary bucket page.
168  */
169  MarkBufferDirty(buf);
170  _hash_relbuf(rel, buf);
171  if (buf != bucket_buf)
172  _hash_dropbuf(rel, bucket_buf);
173 
174  /*
175  * Write-lock the metapage so we can increment the tuple count. After
176  * incrementing it, check to see if it's time for a split.
177  */
179 
180  metap = HashPageGetMeta(metapage);
181  metap->hashm_ntuples += 1;
182 
183  /* Make sure this stays in sync with _hash_expandtable() */
184  do_expand = metap->hashm_ntuples >
185  (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);
186 
187  /* Write out the metapage and drop lock, but keep pin */
188  MarkBufferDirty(metabuf);
189  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
190 
191  /* Attempt to split if a split is needed */
192  if (do_expand)
193  _hash_expandtable(rel, metabuf);
194 
195  /* Finally drop our pin on the metapage */
196  _hash_dropbuf(rel, metabuf);
197 }
#define HashMaxItemSize(page)
Definition: hash.h:202
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
int errhint(const char *fmt,...)
Definition: elog.c:987
#define LH_META_PAGE
Definition: hash.h:56
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
uint16 hashm_ffactor
Definition: hash.h:179
uint32 hashm_highmask
Definition: hash.h:185
#define InvalidBuffer
Definition: buf.h:25
int errcode(int sqlerrcode)
Definition: elog.c:575
Buffer _hash_getbucketbuf_from_hashkey(Relation rel, uint32 hashkey, int access, HashMetaPage *cachedmetap)
Definition: hashpage.c:1274
uint32 BlockNumber
Definition: block.h:31
void _hash_dropbuf(Relation rel, Buffer buf)
Definition: hashpage.c:256
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
uint32 hashm_lowmask
Definition: hash.h:186
Size PageGetFreeSpace(Page page)
Definition: bufpage.c:582
uint32 Bucket
Definition: hash.h:34
#define ERROR
Definition: elog.h:43
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf, Bucket obucket, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashpage.c:1095
#define IndexTupleDSize(itup)
Definition: itup.h:71
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_WRITE
Definition: hash.h:255
#define HASH_NOLOCK
Definition: hash.h:256
unsigned int uint32
Definition: c.h:265
void _hash_expandtable(Relation rel, Buffer metabuf)
Definition: hashpage.c:490
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define ereport(elevel, rest)
Definition: elog.h:122
bool IsBufferCleanupOK(Buffer buffer)
Definition: bufmgr.c:3757
#define HASH_METAPAGE
Definition: hash.h:146
double hashm_ntuples
Definition: hash.h:178
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define H_BUCKET_BEING_SPLIT(opaque)
Definition: hash.h:87
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
size_t Size
Definition: c.h:353
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
Buffer _hash_addovflpage(Relation rel, Buffer metabuf, Buffer buf, bool retain_pin)
Definition: hashovfl.c:109
#define MAXALIGN(LEN)
Definition: c.h:584
uint32 hashm_maxbucket
Definition: hash.h:184
OffsetNumber _hash_pgaddtup(Relation rel, Buffer buf, Size itemsize, IndexTuple itup)
Definition: hashinsert.c:211
uint16 hasho_flag
Definition: hash.h:80
#define HashPageGetMeta(page)
Definition: hash.h:238
int errmsg(const char *fmt,...)
Definition: elog.c:797
BlockNumber hasho_nextblkno
Definition: hash.h:78
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
void _hash_dropbuf ( Relation  rel,
Buffer  buf 
)

Definition at line 256 of file hashpage.c.

References ReleaseBuffer().

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

257 {
259 }
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3292
static char * buf
Definition: pg_test_fsync.c:65
void _hash_dropscanbuf ( Relation  rel,
HashScanOpaque  so 
)

Definition at line 268 of file hashpage.c.

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

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

269 {
270  /* release pin we hold on primary bucket page */
271  if (BufferIsValid(so->hashso_bucket_buf) &&
272  so->hashso_bucket_buf != so->hashso_curbuf)
275 
276  /* release pin we hold on primary bucket page of bucket being split */
281 
282  /* release any pin we still hold */
283  if (BufferIsValid(so->hashso_curbuf))
284  _hash_dropbuf(rel, so->hashso_curbuf);
286 
287  /* reset split scan */
288  so->hashso_buc_populated = false;
289  so->hashso_buc_split = false;
290 }
#define InvalidBuffer
Definition: buf.h:25
void _hash_dropbuf(Relation rel, Buffer buf)
Definition: hashpage.c:256
Buffer hashso_bucket_buf
Definition: hash.h:115
bool hashso_buc_populated
Definition: hash.h:131
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
bool hashso_buc_split
Definition: hash.h:137
Buffer hashso_split_bucket_buf
Definition: hash.h:122
Buffer hashso_curbuf
Definition: hash.h:112
void _hash_expandtable ( Relation  rel,
Buffer  metabuf 
)

Definition at line 490 of file hashpage.c.

References _hash_alloc_buckets(), _hash_checkpage(), _hash_dropbuf(), _hash_finish_split(), _hash_getbuf_with_condlock_cleanup(), _hash_getnewbuf(), _hash_log2(), _hash_relbuf(), _hash_splitbucket(), Assert, BUCKET_TO_BLKNO, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, END_CRIT_SECTION, 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, HashPageGetMeta, IsBufferCleanupOK(), LH_BUCKET_PAGE, LH_META_PAGE, LockBuffer(), MAIN_FORKNUM, MarkBufferDirty(), NULL, PageGetSpecialPointer, and START_CRIT_SECTION.

Referenced by _hash_doinsert().

491 {
492  HashMetaPage metap;
493  Bucket old_bucket;
494  Bucket new_bucket;
495  uint32 spare_ndx;
496  BlockNumber start_oblkno;
497  BlockNumber start_nblkno;
498  Buffer buf_nblkno;
499  Buffer buf_oblkno;
500  Page opage;
501  HashPageOpaque oopaque;
502  uint32 maxbucket;
503  uint32 highmask;
504  uint32 lowmask;
505 
506 restart_expand:
507 
508  /*
509  * Write-lock the meta page. It used to be necessary to acquire a
510  * heavyweight lock to begin a split, but that is no longer required.
511  */
513 
514  _hash_checkpage(rel, metabuf, LH_META_PAGE);
515  metap = HashPageGetMeta(BufferGetPage(metabuf));
516 
517  /*
518  * Check to see if split is still needed; someone else might have already
519  * done one while we waited for the lock.
520  *
521  * Make sure this stays in sync with _hash_doinsert()
522  */
523  if (metap->hashm_ntuples <=
524  (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1))
525  goto fail;
526 
527  /*
528  * Can't split anymore if maxbucket has reached its maximum possible
529  * value.
530  *
531  * Ideally we'd allow bucket numbers up to UINT_MAX-1 (no higher because
532  * the calculation maxbucket+1 mustn't overflow). Currently we restrict
533  * to half that because of overflow looping in _hash_log2() and
534  * insufficient space in hashm_spares[]. It's moot anyway because an
535  * index with 2^32 buckets would certainly overflow BlockNumber and hence
536  * _hash_alloc_buckets() would fail, but if we supported buckets smaller
537  * than a disk block then this would be an independent constraint.
538  *
539  * If you change this, see also the maximum initial number of buckets in
540  * _hash_metapinit().
541  */
542  if (metap->hashm_maxbucket >= (uint32) 0x7FFFFFFE)
543  goto fail;
544 
545  /*
546  * Determine which bucket is to be split, and attempt to take cleanup lock
547  * on the old bucket. If we can't get the lock, give up.
548  *
549  * The cleanup lock protects us not only against other backends, but
550  * against our own backend as well.
551  *
552  * The cleanup lock is mainly to protect the split from concurrent
553  * inserts. See src/backend/access/hash/README, Lock Definitions for
554  * further details. Due to this locking restriction, if there is any
555  * pending scan, the split will give up which is not good, but harmless.
556  */
557  new_bucket = metap->hashm_maxbucket + 1;
558 
559  old_bucket = (new_bucket & metap->hashm_lowmask);
560 
561  start_oblkno = BUCKET_TO_BLKNO(metap, old_bucket);
562 
563  buf_oblkno = _hash_getbuf_with_condlock_cleanup(rel, start_oblkno, LH_BUCKET_PAGE);
564  if (!buf_oblkno)
565  goto fail;
566 
567  opage = BufferGetPage(buf_oblkno);
568  oopaque = (HashPageOpaque) PageGetSpecialPointer(opage);
569 
570  /*
571  * We want to finish the split from a bucket as there is no apparent
572  * benefit by not doing so and it will make the code complicated to finish
573  * the split that involves multiple buckets considering the case where new
574  * split also fails. We don't need to consider the new bucket for
575  * completing the split here as it is not possible that a re-split of new
576  * bucket starts when there is still a pending split from old bucket.
577  */
578  if (H_BUCKET_BEING_SPLIT(oopaque))
579  {
580  /*
581  * Copy bucket mapping info now; refer the comment in code below where
582  * we copy this information before calling _hash_splitbucket to see
583  * why this is okay.
584  */
585  maxbucket = metap->hashm_maxbucket;
586  highmask = metap->hashm_highmask;
587  lowmask = metap->hashm_lowmask;
588 
589  /*
590  * Release the lock on metapage and old_bucket, before completing the
591  * split.
592  */
593  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
594  LockBuffer(buf_oblkno, BUFFER_LOCK_UNLOCK);
595 
596  _hash_finish_split(rel, metabuf, buf_oblkno, old_bucket, maxbucket,
597  highmask, lowmask);
598 
599  /* release the pin on old buffer and retry for expand. */
600  _hash_dropbuf(rel, buf_oblkno);
601 
602  goto restart_expand;
603  }
604 
605  /*
606  * Clean the tuples remained from the previous split. This operation
607  * requires cleanup lock and we already have one on the old bucket, so
608  * let's do it. We also don't want to allow further splits from the bucket
609  * till the garbage of previous split is cleaned. This has two
610  * advantages; first, it helps in avoiding the bloat due to garbage and
611  * second is, during cleanup of bucket, we are always sure that the
612  * garbage tuples belong to most recently split bucket. On the contrary,
613  * if we allow cleanup of bucket after meta page is updated to indicate
614  * the new split and before the actual split, the cleanup operation won't
615  * be able to decide whether the tuple has been moved to the newly created
616  * bucket and ended up deleting such tuples.
617  */
618  if (H_NEEDS_SPLIT_CLEANUP(oopaque))
619  {
620  /*
621  * Copy bucket mapping info now; refer to the comment in code below
622  * where we copy this information before calling _hash_splitbucket
623  * to see why this is okay.
624  */
625  maxbucket = metap->hashm_maxbucket;
626  highmask = metap->hashm_highmask;
627  lowmask = metap->hashm_lowmask;
628 
629  /* Release the metapage lock. */
630  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
631 
632  hashbucketcleanup(rel, old_bucket, buf_oblkno, start_oblkno, NULL,
633  maxbucket, highmask, lowmask, NULL, NULL, true,
634  NULL, NULL);
635 
636  _hash_dropbuf(rel, buf_oblkno);
637 
638  goto restart_expand;
639  }
640 
641  /*
642  * There shouldn't be any active scan on new bucket.
643  *
644  * Note: it is safe to compute the new bucket's blkno here, even though we
645  * may still need to update the BUCKET_TO_BLKNO mapping. This is because
646  * the current value of hashm_spares[hashm_ovflpoint] correctly shows
647  * where we are going to put a new splitpoint's worth of buckets.
648  */
649  start_nblkno = BUCKET_TO_BLKNO(metap, new_bucket);
650 
651  /*
652  * If the split point is increasing (hashm_maxbucket's log base 2
653  * increases), we need to allocate a new batch of bucket pages.
654  */
655  spare_ndx = _hash_log2(new_bucket + 1);
656  if (spare_ndx > metap->hashm_ovflpoint)
657  {
658  Assert(spare_ndx == metap->hashm_ovflpoint + 1);
659 
660  /*
661  * The number of buckets in the new splitpoint is equal to the total
662  * number already in existence, i.e. new_bucket. Currently this maps
663  * one-to-one to blocks required, but someday we may need a more
664  * complicated calculation here.
665  */
666  if (!_hash_alloc_buckets(rel, start_nblkno, new_bucket))
667  {
668  /* can't split due to BlockNumber overflow */
669  _hash_relbuf(rel, buf_oblkno);
670  goto fail;
671  }
672  }
673 
674  /*
675  * Physically allocate the new bucket's primary page. We want to do this
676  * before changing the metapage's mapping info, in case we can't get the
677  * disk space. Ideally, we don't need to check for cleanup lock on new
678  * bucket as no other backend could find this bucket unless meta page is
679  * updated. However, it is good to be consistent with old bucket locking.
680  */
681  buf_nblkno = _hash_getnewbuf(rel, start_nblkno, MAIN_FORKNUM);
682  if (!IsBufferCleanupOK(buf_nblkno))
683  {
684  _hash_relbuf(rel, buf_oblkno);
685  _hash_relbuf(rel, buf_nblkno);
686  goto fail;
687  }
688 
689 
690  /*
691  * Okay to proceed with split. Update the metapage bucket mapping info.
692  *
693  * Since we are scribbling on the metapage data right in the shared
694  * buffer, any failure in this next little bit leaves us with a big
695  * problem: the metapage is effectively corrupt but could get written back
696  * to disk. We don't really expect any failure, but just to be sure,
697  * establish a critical section.
698  */
700 
701  metap->hashm_maxbucket = new_bucket;
702 
703  if (new_bucket > metap->hashm_highmask)
704  {
705  /* Starting a new doubling */
706  metap->hashm_lowmask = metap->hashm_highmask;
707  metap->hashm_highmask = new_bucket | metap->hashm_lowmask;
708  }
709 
710  /*
711  * If the split point is increasing (hashm_maxbucket's log base 2
712  * increases), we need to adjust the hashm_spares[] array and
713  * hashm_ovflpoint so that future overflow pages will be created beyond
714  * this new batch of bucket pages.
715  */
716  if (spare_ndx > metap->hashm_ovflpoint)
717  {
718  metap->hashm_spares[spare_ndx] = metap->hashm_spares[metap->hashm_ovflpoint];
719  metap->hashm_ovflpoint = spare_ndx;
720  }
721 
722  /* Done mucking with metapage */
724 
725  /*
726  * Copy bucket mapping info now; this saves re-accessing the meta page
727  * inside _hash_splitbucket's inner loop. Note that once we drop the
728  * split lock, other splits could begin, so these values might be out of
729  * date before _hash_splitbucket finishes. That's okay, since all it
730  * needs is to tell which of these two buckets to map hashkeys into.
731  */
732  maxbucket = metap->hashm_maxbucket;
733  highmask = metap->hashm_highmask;
734  lowmask = metap->hashm_lowmask;
735 
736  /* Write out the metapage and drop lock, but keep pin */
737  MarkBufferDirty(metabuf);
738  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
739 
740  /* Relocate records to the new bucket */
741  _hash_splitbucket(rel, metabuf,
742  old_bucket, new_bucket,
743  buf_oblkno, buf_nblkno,
744  maxbucket, highmask, lowmask);
745 
746  return;
747 
748  /* Here if decide not to split or fail to acquire old bucket lock */
749 fail:
750 
751  /* We didn't write the metapage, so just drop lock */
752  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
753 }
static void _hash_splitbucket(Relation rel, Buffer metabuf, Bucket obucket, Bucket nbucket, Buffer obuf, Buffer nbuf, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashpage.c:830
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
#define LH_META_PAGE
Definition: hash.h:56
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
#define END_CRIT_SECTION()
Definition: miscadmin.h:132
uint16 hashm_ffactor
Definition: hash.h:179
uint32 hashm_highmask
Definition: hash.h:185
#define START_CRIT_SECTION()
Definition: miscadmin.h:130
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: hash.c:711
uint32 BlockNumber
Definition: block.h:31
Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno, ForkNumber forkNum)
Definition: hashpage.c:177
void _hash_dropbuf(Relation rel, Buffer buf)
Definition: hashpage.c:256
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
uint32 hashm_lowmask
Definition: hash.h:186
#define BUCKET_TO_BLKNO(metap, B)
Definition: hash.h:38
static bool _hash_alloc_buckets(Relation rel, BlockNumber firstblock, uint32 nblocks)
Definition: hashpage.c:781
uint32 Bucket
Definition: hash.h:34
#define H_NEEDS_SPLIT_CLEANUP(opaque)
Definition: hash.h:86
void _hash_finish_split(Relation rel, Buffer metabuf, Buffer obuf, Bucket obucket, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashpage.c:1095
unsigned int uint32
Definition: c.h:265
Buffer _hash_getbuf_with_condlock_cleanup(Relation rel, BlockNumber blkno, int flags)
Definition: hashpage.c:105
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
bool IsBufferCleanupOK(Buffer buffer)
Definition: bufmgr.c:3757
uint32 hashm_ovflpoint
Definition: hash.h:187
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
double hashm_ntuples
Definition: hash.h:178
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
uint32 hashm_spares[HASH_MAX_SPLITPOINTS]
Definition: hash.h:192
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define H_BUCKET_BEING_SPLIT(opaque)
Definition: hash.h:87
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
uint32 hashm_maxbucket
Definition: hash.h:184
#define HashPageGetMeta(page)
Definition: hash.h:238
uint32 _hash_log2(uint32 num)
Definition: hashutil.c:140
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
void _hash_finish_split ( Relation  rel,
Buffer  metabuf,
Buffer  obuf,
Bucket  obucket,
uint32  maxbucket,
uint32  highmask,
uint32  lowmask 
)

Definition at line 1095 of file hashpage.c.

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

Referenced by _hash_doinsert(), and _hash_expandtable().

1097 {
1098  HASHCTL hash_ctl;
1099  HTAB *tidhtab;
1100  Buffer bucket_nbuf = InvalidBuffer;
1101  Buffer nbuf;
1102  Page npage;
1103  BlockNumber nblkno;
1104  BlockNumber bucket_nblkno;
1105  HashPageOpaque npageopaque;
1106  Bucket nbucket;
1107  bool found;
1108 
1109  /* Initialize hash tables used to track TIDs */
1110  memset(&hash_ctl, 0, sizeof(hash_ctl));
1111  hash_ctl.keysize = sizeof(ItemPointerData);
1112  hash_ctl.entrysize = sizeof(ItemPointerData);
1113  hash_ctl.hcxt = CurrentMemoryContext;
1114 
1115  tidhtab =
1116  hash_create("bucket ctids",
1117  256, /* arbitrary initial size */
1118  &hash_ctl,
1120 
1121  bucket_nblkno = nblkno = _hash_get_newblock_from_oldbucket(rel, obucket);
1122 
1123  /*
1124  * Scan the new bucket and build hash table of TIDs
1125  */
1126  for (;;)
1127  {
1128  OffsetNumber noffnum;
1129  OffsetNumber nmaxoffnum;
1130 
1131  nbuf = _hash_getbuf(rel, nblkno, HASH_READ,
1133 
1134  /* remember the primary bucket buffer to acquire cleanup lock on it. */
1135  if (nblkno == bucket_nblkno)
1136  bucket_nbuf = nbuf;
1137 
1138  npage = BufferGetPage(nbuf);
1139  npageopaque = (HashPageOpaque) PageGetSpecialPointer(npage);
1140 
1141  /* Scan each tuple in new page */
1142  nmaxoffnum = PageGetMaxOffsetNumber(npage);
1143  for (noffnum = FirstOffsetNumber;
1144  noffnum <= nmaxoffnum;
1145  noffnum = OffsetNumberNext(noffnum))
1146  {
1147  IndexTuple itup;
1148 
1149  /* Fetch the item's TID and insert it in hash table. */
1150  itup = (IndexTuple) PageGetItem(npage,
1151  PageGetItemId(npage, noffnum));
1152 
1153  (void) hash_search(tidhtab, &itup->t_tid, HASH_ENTER, &found);
1154 
1155  Assert(!found);
1156  }
1157 
1158  nblkno = npageopaque->hasho_nextblkno;
1159 
1160  /*
1161  * release our write lock without modifying buffer and ensure to
1162  * retain the pin on primary bucket.
1163  */
1164  if (nbuf == bucket_nbuf)
1166  else
1167  _hash_relbuf(rel, nbuf);
1168 
1169  /* Exit loop if no more overflow pages in new bucket */
1170  if (!BlockNumberIsValid(nblkno))
1171  break;
1172  }
1173 
1174  /*
1175  * Conditionally get the cleanup lock on old and new buckets to perform
1176  * the split operation. If we don't get the cleanup locks, silently give
1177  * up and next insertion on old bucket will try again to complete the
1178  * split.
1179  */
1181  {
1182  hash_destroy(tidhtab);
1183  return;
1184  }
1185  if (!ConditionalLockBufferForCleanup(bucket_nbuf))
1186  {
1188  hash_destroy(tidhtab);
1189  return;
1190  }
1191 
1192  npage = BufferGetPage(bucket_nbuf);
1193  npageopaque = (HashPageOpaque) PageGetSpecialPointer(npage);
1194  nbucket = npageopaque->hasho_bucket;
1195 
1196  _hash_splitbucket_guts(rel, metabuf, obucket,
1197  nbucket, obuf, bucket_nbuf, tidhtab,
1198  maxbucket, highmask, lowmask);
1199 
1200  _hash_relbuf(rel, bucket_nbuf);
1202  hash_destroy(tidhtab);
1203 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
void hash_destroy(HTAB *hashp)
Definition: dynahash.c:793
#define HASH_CONTEXT
Definition: hsearch.h:93
#define HASH_ELEM
Definition: hsearch.h:87
MemoryContext hcxt
Definition: hsearch.h:78
ItemPointerData t_tid
Definition: itup.h:37
#define InvalidBuffer
Definition: buf.h:25
Size entrysize
Definition: hsearch.h:73
uint32 BlockNumber
Definition: block.h:31
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:885
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:354
uint16 OffsetNumber
Definition: off.h:24
#define HASH_READ
Definition: hash.h:254
uint32 Bucket
Definition: hash.h:34
Definition: dynahash.c:193
bool ConditionalLockBufferForCleanup(Buffer buffer)
Definition: bufmgr.c:3701
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
#define HASH_BLOBS
Definition: hsearch.h:88
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:301
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
Size keysize
Definition: hsearch.h:72
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
BlockNumber _hash_get_newblock_from_oldbucket(Relation rel, Bucket old_bucket)
Definition: hashutil.c:402
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
static void _hash_splitbucket_guts(Relation rel, Buffer metabuf, Bucket obucket, Bucket nbucket, Buffer obuf, Buffer nbuf, HTAB *htab, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashpage.c:892
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
struct ItemPointerData ItemPointerData
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
BlockNumber hasho_nextblkno
Definition: hash.h:78
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
Pointer Page
Definition: bufpage.h:74
bool _hash_first ( IndexScanDesc  scan,
ScanDirection  dir 
)

Definition at line 220 of file hashsearch.c.

References _hash_checkpage(), _hash_datum2hashkey(), _hash_datum2hashkey_type(), _hash_dropbuf(), _hash_get_oldblock_from_newbucket(), _hash_getbucketbuf_from_hashkey(), _hash_getbuf(), _hash_readnext(), _hash_step(), Assert, BlockNumberIsValid, buf, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage, cur, ereport, errcode(), errmsg(), ERROR, H_BUCKET_BEING_POPULATED, HASH_READ, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_curpos, HashScanOpaqueData::hashso_heappos, HashScanOpaqueData::hashso_sk_hash, HashScanOpaqueData::hashso_split_bucket_buf, HTEqualStrategyNumber, IndexScanDescData::indexRelation, InvalidBuffer, InvalidOid, ItemPointerGetOffsetNumber, ItemPointerSetInvalid, IndexScanDescData::keyData, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, LockBuffer(), NULL, IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, PageGetItem, PageGetItemId, PageGetSpecialPointer, pgstat_count_index_scan, RelationData::rd_opcintype, ScanDirectionIsBackward, and SK_ISNULL.

Referenced by hashgetbitmap(), and hashgettuple().

221 {
222  Relation rel = scan->indexRelation;
223  HashScanOpaque so = (HashScanOpaque) scan->opaque;
224  ScanKey cur;
225  uint32 hashkey;
226  Bucket bucket;
227  Buffer buf;
228  Page page;
229  HashPageOpaque opaque;
230  IndexTuple itup;
231  ItemPointer current;
232  OffsetNumber offnum;
233 
235 
236  current = &(so->hashso_curpos);
237  ItemPointerSetInvalid(current);
238 
239  /*
240  * We do not support hash scans with no index qualification, because we
241  * would have to read the whole index rather than just one bucket. That
242  * creates a whole raft of problems, since we haven't got a practical way
243  * to lock all the buckets against splits or compactions.
244  */
245  if (scan->numberOfKeys < 1)
246  ereport(ERROR,
247  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
248  errmsg("hash indexes do not support whole-index scans")));
249 
250  /* There may be more than one index qual, but we hash only the first */
251  cur = &scan->keyData[0];
252 
253  /* We support only single-column hash indexes */
254  Assert(cur->sk_attno == 1);
255  /* And there's only one operator strategy, too */
256  Assert(cur->sk_strategy == HTEqualStrategyNumber);
257 
258  /*
259  * If the constant in the index qual is NULL, assume it cannot match any
260  * items in the index.
261  */
262  if (cur->sk_flags & SK_ISNULL)
263  return false;
264 
265  /*
266  * Okay to compute the hash key. We want to do this before acquiring any
267  * locks, in case a user-defined hash function happens to be slow.
268  *
269  * If scankey operator is not a cross-type comparison, we can use the
270  * cached hash function; otherwise gotta look it up in the catalogs.
271  *
272  * We support the convention that sk_subtype == InvalidOid means the
273  * opclass input type; this is a hack to simplify life for ScanKeyInit().
274  */
275  if (cur->sk_subtype == rel->rd_opcintype[0] ||
276  cur->sk_subtype == InvalidOid)
277  hashkey = _hash_datum2hashkey(rel, cur->sk_argument);
278  else
279  hashkey = _hash_datum2hashkey_type(rel, cur->sk_argument,
280  cur->sk_subtype);
281 
282  so->hashso_sk_hash = hashkey;
283 
285  page = BufferGetPage(buf);
286  opaque = (HashPageOpaque) PageGetSpecialPointer(page);
287  bucket = opaque->hasho_bucket;
288 
289  so->hashso_bucket_buf = buf;
290 
291  /*
292  * If a bucket split is in progress, then while scanning the bucket being
293  * populated, we need to skip tuples that were copied from bucket being
294  * split. We also need to maintain a pin on the bucket being split to
295  * ensure that split-cleanup work done by vacuum doesn't remove tuples
296  * from it till this scan is done. We need to maintain a pin on the
297  * bucket being populated to ensure that vacuum doesn't squeeze that
298  * bucket till this scan is complete; otherwise, the ordering of tuples
299  * can't be maintained during forward and backward scans. Here, we have
300  * to be cautious about locking order: first, acquire the lock on bucket
301  * being split; then, release the lock on it but not the pin; then,
302  * acquire a lock on bucket being populated and again re-verify whether
303  * the bucket split is still in progress. Acquiring the lock on bucket
304  * being split first ensures that the vacuum waits for this scan to
305  * finish.
306  */
307  if (H_BUCKET_BEING_POPULATED(opaque))
308  {
309  BlockNumber old_blkno;
310  Buffer old_buf;
311 
312  old_blkno = _hash_get_oldblock_from_newbucket(rel, bucket);
313 
314  /*
315  * release the lock on new bucket and re-acquire it after acquiring
316  * the lock on old bucket.
317  */
319 
320  old_buf = _hash_getbuf(rel, old_blkno, HASH_READ, LH_BUCKET_PAGE);
321 
322  /*
323  * remember the split bucket buffer so as to use it later for
324  * scanning.
325  */
326  so->hashso_split_bucket_buf = old_buf;
327  LockBuffer(old_buf, BUFFER_LOCK_UNLOCK);
328 
330  page = BufferGetPage(buf);
331  opaque = (HashPageOpaque) PageGetSpecialPointer(page);
332  Assert(opaque->hasho_bucket == bucket);
333 
334  if (H_BUCKET_BEING_POPULATED(opaque))
335  so->hashso_buc_populated = true;
336  else
337  {
340  }
341  }
342 
343  /* If a backwards scan is requested, move to the end of the chain */
344  if (ScanDirectionIsBackward(dir))
345  {
346  /*
347  * Backward scans that start during split needs to start from end of
348  * bucket being split.
349  */
350  while (BlockNumberIsValid(opaque->hasho_nextblkno) ||
352  _hash_readnext(scan, &buf, &page, &opaque);
353  }
354 
355  /* Now find the first tuple satisfying the qualification */
356  if (!_hash_step(scan, &buf, dir))
357  return false;
358 
359  /* if we're here, _hash_step found a valid tuple */
360  offnum = ItemPointerGetOffsetNumber(current);
362  page = BufferGetPage(buf);
363  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
364  so->hashso_heappos = itup->t_tid;
365 
366  return true;
367 }
HashScanOpaqueData * HashScanOpaque
Definition: hash.h:140
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
static void _hash_readnext(IndexScanDesc scan, Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
Definition: hashsearch.c:71
bool _hash_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
Definition: hashsearch.c:387
#define HTEqualStrategyNumber
Definition: hash.h:261
#define InvalidBuffer
Definition: buf.h:25
struct cursor * cur
Definition: ecpg.c:28
int errcode(int sqlerrcode)
Definition: elog.c:575
Buffer _hash_getbucketbuf_from_hashkey(Relation rel, uint32 hashkey, int access, HashMetaPage *cachedmetap)
Definition: hashpage.c:1274
uint32 BlockNumber
Definition: block.h:31
uint32 _hash_datum2hashkey(Relation rel, Datum key)
Definition: hashutil.c:81
void _hash_dropbuf(Relation rel, Buffer buf)
Definition: hashpage.c:256
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
Relation indexRelation
Definition: relscan.h:89
uint16 OffsetNumber
Definition: off.h:24
#define HASH_READ
Definition: hash.h:254
uint32 Bucket
Definition: hash.h:34
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
#define ERROR
Definition: elog.h:43
static char * buf
Definition: pg_test_fsync.c:65
IndexTupleData * IndexTuple
Definition: itup.h:53
#define pgstat_count_index_scan(rel)
Definition: pgstat.h:1155
unsigned int uint32
Definition: c.h:265
#define SK_ISNULL
Definition: skey.h:115
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define ereport(elevel, rest)
Definition: elog.h:122
Buffer hashso_bucket_buf
Definition: hash.h:115
#define H_BUCKET_BEING_POPULATED(opaque)
Definition: hash.h:88
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
bool hashso_buc_populated
Definition: hash.h:131
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
uint32 hashso_sk_hash
Definition: hash.h:104
#define InvalidOid
Definition: postgres_ext.h:36
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
ItemPointerData hashso_curpos
Definition: hash.h:125
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
ScanKey keyData
Definition: relscan.h:93
BlockNumber _hash_get_oldblock_from_newbucket(Relation rel, Bucket new_bucket)
Definition: hashutil.c:363
bool hashso_buc_split
Definition: hash.h:137
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:131
int errmsg(const char *fmt,...)
Definition: elog.c:797
Buffer hashso_split_bucket_buf
Definition: hash.h:122
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:88
uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype)
Definition: hashutil.c:101
Oid * rd_opcintype
Definition: rel.h:179
int Buffer
Definition: buf.h:23
ItemPointerData hashso_heappos
Definition: hash.h:128
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
Pointer Page
Definition: bufpage.h:74
BlockNumber _hash_freeovflpage ( Relation  rel,
Buffer  ovflbuf,
Buffer  wbuf,
BufferAccessStrategy  bstrategy 
)

Definition at line 406 of file hashovfl.c.

References _hash_checkpage(), _hash_getbuf(), _hash_getbuf_with_strategy(), _hash_ovflblkno_to_bitno(), _hash_relbuf(), Assert, BlockNumberIsValid, BMPG_MASK, BMPG_SHIFT, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, BufferGetPageSize, CLRBIT, elog, ERROR, HASH_METAPAGE, HASH_READ, HASH_WRITE, HashMetaPageData::hashm_firstfree, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_nmaps, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_prevblkno, HashPageGetBitmap, HashPageGetMeta, InvalidBuffer, ISSET, LH_BITMAP_PAGE, LH_BUCKET_PAGE, LH_META_PAGE, LH_OVERFLOW_PAGE, LockBuffer(), MarkBufferDirty(), MemSet, PageGetSpecialPointer, and PG_USED_FOR_ASSERTS_ONLY.

Referenced by _hash_squeezebucket().

408 {
409  HashMetaPage metap;
410  Buffer metabuf;
411  Buffer mapbuf;
412  Buffer prevbuf = InvalidBuffer;
413  BlockNumber ovflblkno;
414  BlockNumber prevblkno;
415  BlockNumber blkno;
416  BlockNumber nextblkno;
417  BlockNumber writeblkno;
418  HashPageOpaque ovflopaque;
419  Page ovflpage;
420  Page mappage;
421  uint32 *freep;
422  uint32 ovflbitno;
423  int32 bitmappage,
424  bitmapbit;
426 
427  /* Get information from the doomed page */
428  _hash_checkpage(rel, ovflbuf, LH_OVERFLOW_PAGE);
429  ovflblkno = BufferGetBlockNumber(ovflbuf);
430  ovflpage = BufferGetPage(ovflbuf);
431  ovflopaque = (HashPageOpaque) PageGetSpecialPointer(ovflpage);
432  nextblkno = ovflopaque->hasho_nextblkno;
433  prevblkno = ovflopaque->hasho_prevblkno;
434  writeblkno = BufferGetBlockNumber(wbuf);
435  bucket = ovflopaque->hasho_bucket;
436 
437  /*
438  * Zero the page for debugging's sake; then write and release it. (Note:
439  * if we failed to zero the page here, we'd have problems with the Assert
440  * in _hash_pageinit() when the page is reused.)
441  */
442  MemSet(ovflpage, 0, BufferGetPageSize(ovflbuf));
443  MarkBufferDirty(ovflbuf);
444  _hash_relbuf(rel, ovflbuf);
445 
446  /*
447  * Fix up the bucket chain. this is a doubly-linked list, so we must fix
448  * up the bucket chain members behind and ahead of the overflow page being
449  * deleted. Concurrency issues are avoided by using lock chaining as
450  * described atop hashbucketcleanup.
451  */
452  if (BlockNumberIsValid(prevblkno))
453  {
454  Page prevpage;
455  HashPageOpaque prevopaque;
456 
457  if (prevblkno == writeblkno)
458  prevbuf = wbuf;
459  else
460  prevbuf = _hash_getbuf_with_strategy(rel,
461  prevblkno,
462  HASH_WRITE,
464  bstrategy);
465 
466  prevpage = BufferGetPage(prevbuf);
467  prevopaque = (HashPageOpaque) PageGetSpecialPointer(prevpage);
468 
469  Assert(prevopaque->hasho_bucket == bucket);
470  prevopaque->hasho_nextblkno = nextblkno;
471 
472  MarkBufferDirty(prevbuf);
473  if (prevblkno != writeblkno)
474  _hash_relbuf(rel, prevbuf);
475  }
476  if (BlockNumberIsValid(nextblkno))
477  {
478  Buffer nextbuf = _hash_getbuf_with_strategy(rel,
479  nextblkno,
480  HASH_WRITE,
482  bstrategy);
483  Page nextpage = BufferGetPage(nextbuf);
484  HashPageOpaque nextopaque = (HashPageOpaque) PageGetSpecialPointer(nextpage);
485 
486  Assert(nextopaque->hasho_bucket == bucket);
487  nextopaque->hasho_prevblkno = prevblkno;
488  MarkBufferDirty(nextbuf);
489  _hash_relbuf(rel, nextbuf);
490  }
491 
492  /* Note: bstrategy is intentionally not used for metapage and bitmap */
493 
494  /* Read the metapage so we can determine which bitmap page to use */
496  metap = HashPageGetMeta(BufferGetPage(metabuf));
497 
498  /* Identify which bit to set */
499  ovflbitno = _hash_ovflblkno_to_bitno(metap, ovflblkno);
500 
501  bitmappage = ovflbitno >> BMPG_SHIFT(metap);
502  bitmapbit = ovflbitno & BMPG_MASK(metap);
503 
504  if (bitmappage >= metap->hashm_nmaps)
505  elog(ERROR, "invalid overflow bit number %u", ovflbitno);
506  blkno = metap->hashm_mapp[bitmappage];
507 
508  /* Release metapage lock while we access the bitmap page */
509  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
510 
511  /* Clear the bitmap bit to indicate that this overflow page is free */
512  mapbuf = _hash_getbuf(rel, blkno, HASH_WRITE, LH_BITMAP_PAGE);
513  mappage = BufferGetPage(mapbuf);
514  freep = HashPageGetBitmap(mappage);
515  Assert(ISSET(freep, bitmapbit));
516  CLRBIT(freep, bitmapbit);
517  MarkBufferDirty(mapbuf);
518  _hash_relbuf(rel, mapbuf);
519 
520  /* Get write-lock on metapage to update firstfree */
522 
523  /* if this is now the first free page, update hashm_firstfree */
524  if (ovflbitno < metap->hashm_firstfree)
525  {
526  metap->hashm_firstfree = ovflbitno;
527  MarkBufferDirty(metabuf);
528  }
529  _hash_relbuf(rel, metabuf);
530 
531  return nextblkno;
532 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
#define HashPageGetBitmap(page)
Definition: hash.h:231
#define LH_BITMAP_PAGE
Definition: hash.h:55
#define LH_META_PAGE
Definition: hash.h:56
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno, int access, int flags, BufferAccessStrategy bstrategy)
Definition: hashpage.c:218
#define InvalidBuffer
Definition: buf.h:25
#define MemSet(start, val, len)
Definition: c.h:853
uint32 BlockNumber
Definition: block.h:31
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
signed int int32
Definition: c.h:253
#define HASH_READ
Definition: hash.h:254
uint32 Bucket
Definition: hash.h:34
BlockNumber hasho_prevblkno
Definition: hash.h:77
#define ERROR
Definition: elog.h:43
uint32 hashm_nmaps
Definition: hash.h:190
#define HASH_WRITE
Definition: hash.h:255
#define BMPG_MASK(metap)
Definition: hash.h:229
unsigned int uint32
Definition: c.h:265
#define BMPG_SHIFT(metap)
Definition: hash.h:228
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define ISSET(A, N)
Definition: hash.h:249
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
#define CLRBIT(x, i)
Definition: blutils.c:32
#define HASH_METAPAGE
Definition: hash.h:146
#define BufferGetPageSize(buffer)
Definition: bufmgr.h:147
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
uint32 hashm_firstfree
Definition: hash.h:189
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
uint32 _hash_ovflblkno_to_bitno(HashMetaPage metap, BlockNumber ovflblkno)
Definition: hashovfl.c:60
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2588
#define HashPageGetMeta(page)
Definition: hash.h:238
BlockNumber hasho_nextblkno
Definition: hash.h:78
#define elog
Definition: elog.h:219
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:986
BlockNumber hashm_mapp[HASH_MAX_BITMAPS]
Definition: hash.h:194
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
uint32 _hash_get_indextuple_hashkey ( IndexTuple  itup)

Definition at line 232 of file hashutil.c.

References IndexInfoFindDataOffset, and IndexTupleData::t_info.

Referenced by _h_indexbuild(), _hash_binsearch(), _hash_binsearch_last(), _hash_doinsert(), _hash_pgaddtup(), _hash_splitbucket_guts(), _hash_step(), hash_page_items(), and hashbucketcleanup().

233 {
234  char *attp;
235 
236  /*
237  * We assume the hash key is the first attribute and can't be null, so
238  * this can be done crudely but very very cheaply ...
239  */
240  attp = (char *) itup + IndexInfoFindDataOffset(itup->t_info);
241  return *((uint32 *) attp);
242 }
#define IndexInfoFindDataOffset(t_info)
Definition: itup.h:80
unsigned int uint32
Definition: c.h:265
unsigned short t_info
Definition: itup.h:49
BlockNumber _hash_get_newblock_from_oldbucket ( Relation  rel,
Bucket  old_bucket 
)

Definition at line 402 of file hashutil.c.

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

Referenced by _hash_finish_split().

403 {
404  Bucket new_bucket;
405  Buffer metabuf;
406  HashMetaPage metap;
407  BlockNumber blkno;
408 
410  metap = HashPageGetMeta(BufferGetPage(metabuf));
411 
412  new_bucket = _hash_get_newbucket_from_oldbucket(rel, old_bucket,
413  metap->hashm_lowmask,
414  metap->hashm_maxbucket);
415  blkno = BUCKET_TO_BLKNO(metap, new_bucket);
416 
417  _hash_relbuf(rel, metabuf);
418 
419  return blkno;
420 }
#define LH_META_PAGE
Definition: hash.h:56
uint32 BlockNumber
Definition: block.h:31
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
uint32 hashm_lowmask
Definition: hash.h:186
#define BUCKET_TO_BLKNO(metap, B)
Definition: hash.h:38
#define HASH_READ
Definition: hash.h:254
uint32 Bucket
Definition: hash.h:34
Bucket _hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket, uint32 lowmask, uint32 maxbucket)
Definition: hashutil.c:435
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define HASH_METAPAGE
Definition: hash.h:146
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
uint32 hashm_maxbucket
Definition: hash.h:184
#define HashPageGetMeta(page)
Definition: hash.h:238
int Buffer
Definition: buf.h:23
Bucket _hash_get_newbucket_from_oldbucket ( Relation  rel,
Bucket  old_bucket,
uint32  lowmask,
uint32  maxbucket 
)

Definition at line 435 of file hashutil.c.

References CALC_NEW_BUCKET.

Referenced by _hash_get_newblock_from_oldbucket(), and hashbucketcleanup().

437 {
438  Bucket new_bucket;
439 
440  new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
441  if (new_bucket > maxbucket)
442  {
443  lowmask = lowmask >> 1;
444  new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
445  }
446 
447  return new_bucket;
448 }
#define CALC_NEW_BUCKET(old_bucket, lowmask)
Definition: hashutil.c:23
uint32 Bucket
Definition: hash.h:34
BlockNumber _hash_get_oldblock_from_newbucket ( Relation  rel,
Bucket  new_bucket 
)

Definition at line 363 of file hashutil.c.

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

Referenced by _hash_first().

364 {
365  Bucket old_bucket;
366  uint32 mask;
367  Buffer metabuf;
368  HashMetaPage metap;
369  BlockNumber blkno;
370 
371  /*
372  * To get the old bucket from the current bucket, we need a mask to modulo
373  * into lower half of table. This mask is stored in meta page as
374  * hashm_lowmask, but here we can't rely on the same, because we need a
375  * value of lowmask that was prevalent at the time when bucket split was
376  * started. Masking the most significant bit of new bucket would give us
377  * old bucket.
378  */
379  mask = (((uint32) 1) << (fls(new_bucket) - 1)) - 1;
380  old_bucket = new_bucket & mask;
381 
383  metap = HashPageGetMeta(BufferGetPage(metabuf));
384 
385  blkno = BUCKET_TO_BLKNO(metap, old_bucket);
386 
387  _hash_relbuf(rel, metabuf);
388 
389  return blkno;
390 }
#define LH_META_PAGE
Definition: hash.h:56
uint32 BlockNumber
Definition: block.h:31
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
#define BUCKET_TO_BLKNO(metap, B)
Definition: hash.h:38
int fls(int mask)
Definition: fls.c:55
#define HASH_READ
Definition: hash.h:254
uint32 Bucket
Definition: hash.h:34
unsigned int uint32
Definition: c.h:265
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define HASH_METAPAGE
Definition: hash.h:146
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define HashPageGetMeta(page)
Definition: hash.h:238
int Buffer
Definition: buf.h:23
Buffer _hash_getbucketbuf_from_hashkey ( Relation  rel,
uint32  hashkey,
int  access,
HashMetaPage cachedmetap 
)

Definition at line 1274 of file hashpage.c.

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

Referenced by _hash_doinsert(), and _hash_first().

1276 {
1277  HashMetaPage metap;
1278  Buffer buf;
1279  Buffer metabuf = InvalidBuffer;
1280  Page page;
1281  Bucket bucket;
1282  BlockNumber blkno;
1283  HashPageOpaque opaque;
1284 
1285  /* We read from target bucket buffer, hence locking is must. */
1286  Assert(access == HASH_READ || access == HASH_WRITE);
1287 
1288  metap = _hash_getcachedmetap(rel, &metabuf, false);
1289  Assert(metap != NULL);
1290 
1291  /*
1292  * Loop until we get a lock on the correct target bucket.
1293  */
1294  for (;;)
1295  {
1296  /*
1297  * Compute the target bucket number, and convert to block number.
1298  */
1299  bucket = _hash_hashkey2bucket(hashkey,
1300  metap->hashm_maxbucket,
1301  metap->hashm_highmask,
1302  metap->hashm_lowmask);
1303 
1304  blkno = BUCKET_TO_BLKNO(metap, bucket);
1305 
1306  /* Fetch the primary bucket page for the bucket */
1307  buf = _hash_getbuf(rel, blkno, access, LH_BUCKET_PAGE);
1308  page = BufferGetPage(buf);
1309  opaque = (HashPageOpaque) PageGetSpecialPointer(page);
1310  Assert(opaque->hasho_bucket == bucket);
1311 
1312  /*
1313  * If this bucket hasn't been split, we're done.
1314  *
1315  * NB: The check for InvalidBlockNumber is only needed for on-disk
1316  * compatibility with indexes created before we started storing
1317  * hashm_maxbucket in the primary page's hasho_prevblkno.
1318  */
1319  if (opaque->hasho_prevblkno == InvalidBlockNumber ||
1320  opaque->hasho_prevblkno <= metap->hashm_maxbucket)
1321  break;
1322 
1323  /* Drop lock on this buffer, update cached metapage, and retry. */
1324  _hash_relbuf(rel, buf);
1325  metap = _hash_getcachedmetap(rel, &metabuf, true);
1326  Assert(metap != NULL);
1327  }
1328 
1329  if (BufferIsValid(metabuf))
1330  _hash_dropbuf(rel, metabuf);
1331 
1332  if (cachedmetap)
1333  *cachedmetap = metap;
1334 
1335  return buf;
1336 }
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:124
uint32 hashm_highmask
Definition: hash.h:185
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
void _hash_dropbuf(Relation rel, Buffer buf)
Definition: hashpage.c:256
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
uint32 hashm_lowmask
Definition: hash.h:186
#define BUCKET_TO_BLKNO(metap, B)
Definition: hash.h:38
#define HASH_READ
Definition: hash.h:254
uint32 Bucket
Definition: hash.h:34
BlockNumber hasho_prevblkno
Definition: hash.h:77
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_WRITE
Definition: hash.h:255
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
HashMetaPage _hash_getcachedmetap(Relation rel, Buffer *metabuf, bool force_refresh)
Definition: hashpage.c:1216
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
#define InvalidBlockNumber
Definition: block.h:33
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
uint32 hashm_maxbucket
Definition: hash.h:184
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
Buffer _hash_getbuf ( Relation  rel,
BlockNumber  blkno,
int  access,
int  flags 
)

Definition at line 79 of file hashpage.c.

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

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

80 {
81  Buffer buf;
82 
83  if (blkno == P_NEW)
84  elog(ERROR, "hash AM does not use P_NEW");
85 
86  buf = ReadBuffer(rel, blkno);
87 
88  if (access != HASH_NOLOCK)
89  LockBuffer(buf, access);
90 
91  /* ref count and lock type are correct */
92 
93  _hash_checkpage(rel, buf, flags);
94 
95  return buf;
96 }
#define P_NEW
Definition: bufmgr.h:82
#define ERROR
Definition: elog.h:43
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_NOLOCK
Definition: hash.h:256
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define elog
Definition: elog.h:219
int Buffer
Definition: buf.h:23
Buffer _hash_getbuf_with_condlock_cleanup ( Relation  rel,
BlockNumber  blkno,
int  flags 
)

Definition at line 105 of file hashpage.c.

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

Referenced by _hash_expandtable().

106 {
107  Buffer buf;
108 
109  if (blkno == P_NEW)
110  elog(ERROR, "hash AM does not use P_NEW");
111 
112  buf = ReadBuffer(rel, blkno);
113 
115  {
116  ReleaseBuffer(buf);
117  return InvalidBuffer;
118  }
119 
120  /* ref count and lock type are correct */
121 
122  _hash_checkpage(rel, buf, flags);
123 
124  return buf;
125 }
#define InvalidBuffer
Definition: buf.h:25
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3292
#define P_NEW
Definition: bufmgr.h:82
bool ConditionalLockBufferForCleanup(Buffer buffer)
Definition: bufmgr.c:3701
#define ERROR
Definition: elog.h:43
static char * buf
Definition: pg_test_fsync.c:65
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define elog
Definition: elog.h:219
int Buffer
Definition: buf.h:23
Buffer _hash_getbuf_with_strategy ( Relation  rel,
BlockNumber  blkno,
int  access,
int  flags,
BufferAccessStrategy  bstrategy 
)

Definition at line 218 of file hashpage.c.

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

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

221 {
222  Buffer buf;
223 
224  if (blkno == P_NEW)
225  elog(ERROR, "hash AM does not use P_NEW");
226 
227  buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL, bstrategy);
228 
229  if (access != HASH_NOLOCK)
230  LockBuffer(buf, access);
231 
232  /* ref count and lock type are correct */
233 
234  _hash_checkpage(rel, buf, flags);
235 
236  return buf;
237 }
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:640
#define P_NEW
Definition: bufmgr.h:82
#define ERROR
Definition: elog.h:43
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_NOLOCK
Definition: hash.h:256
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
#define elog
Definition: elog.h:219
int Buffer
Definition: buf.h:23
HashMetaPage _hash_getcachedmetap ( Relation  rel,
Buffer metabuf,
bool  force_refresh 
)

Definition at line 1216 of file hashpage.c.

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

Referenced by _hash_getbucketbuf_from_hashkey(), and hashbulkdelete().

1217 {
1218  Page page;
1219 
1220  Assert(metabuf);
1221  if (force_refresh || rel->rd_amcache == NULL)
1222  {
1223  char *cache = NULL;
1224 
1225  /*
1226  * It's important that we don't set rd_amcache to an invalid
1227  * value. Either MemoryContextAlloc or _hash_getbuf could fail,
1228  * so don't install a pointer to the newly-allocated storage in the
1229  * actual relcache entry until both have succeeeded.
1230  */
1231  if (rel->rd_amcache == NULL)
1232  cache = MemoryContextAlloc(rel->rd_indexcxt,
1233  sizeof(HashMetaPageData));
1234 
1235  /* Read the metapage. */
1236  if (BufferIsValid(*metabuf))
1237  LockBuffer(*metabuf, BUFFER_LOCK_SHARE);
1238  else
1239  *metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ,
1240  LH_META_PAGE);
1241  page = BufferGetPage(*metabuf);
1242 
1243  /* Populate the cache. */
1244  if (rel->rd_amcache == NULL)
1245  rel->rd_amcache = cache;
1246  memcpy(rel->rd_amcache, HashPageGetMeta(page),
1247  sizeof(HashMetaPageData));
1248 
1249  /* Release metapage lock, but keep the pin. */
1250  LockBuffer(*metabuf, BUFFER_LOCK_UNLOCK);
1251  }
1252 
1253  return (HashMetaPage) rel->rd_amcache;
1254 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
#define LH_META_PAGE
Definition: hash.h:56
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition: hashpage.c:79
#define HASH_READ
Definition: hash.h:254
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define HASH_METAPAGE
Definition: hash.h:146
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
#define HashPageGetMeta(page)
Definition: hash.h:238
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:749
MemoryContext rd_indexcxt
Definition: rel.h:175
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:88
void * rd_amcache
Definition: rel.h:188
Pointer Page
Definition: bufpage.h:74
Buffer _hash_getinitbuf ( Relation  rel,
BlockNumber  blkno 
)

Definition at line 144 of file hashpage.c.

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

Referenced by _hash_getovflpage().

145 {
146  Buffer buf;
147 
148  if (blkno == P_NEW)
149  elog(ERROR, "hash AM does not use P_NEW");
150 
152  NULL);
153 
154  /* ref count and lock type are correct */
155 
156  /* initialize the page */
158 
159  return buf;
160 }
void _hash_pageinit(Page page, Size size)
Definition: hashpage.c:471
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:640
#define P_NEW
Definition: bufmgr.h:82
#define ERROR
Definition: elog.h:43
static char * buf
Definition: pg_test_fsync.c:65
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define BufferGetPageSize(buffer)
Definition: bufmgr.h:147
#define NULL
Definition: c.h:226
#define elog
Definition: elog.h:219
int Buffer
Definition: buf.h:23
Buffer _hash_getnewbuf ( Relation  rel,
BlockNumber  blkno,
ForkNumber  forkNum 
)

Definition at line 177 of file hashpage.c.

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

Referenced by _hash_expandtable(), _hash_getovflpage(), _hash_initbitmap(), and _hash_metapinit().

178 {
179  BlockNumber nblocks = RelationGetNumberOfBlocksInFork(rel, forkNum);
180  Buffer buf;
181 
182  if (blkno == P_NEW)
183  elog(ERROR, "hash AM does not use P_NEW");
184  if (blkno > nblocks)
185  elog(ERROR, "access to noncontiguous page in hash index \"%s\"",
187 
188  /* smgr insists we use P_NEW to extend the relation */
189  if (blkno == nblocks)
190  {
191  buf = ReadBufferExtended(rel, forkNum, P_NEW, RBM_NORMAL, NULL);
192  if (BufferGetBlockNumber(buf) != blkno)
193  elog(ERROR, "unexpected hash relation size: %u, should be %u",
194  BufferGetBlockNumber(buf), blkno);
195  LockBuffer(buf, HASH_WRITE);
196  }
197  else
198  {
199  buf = ReadBufferExtended(rel, forkNum, blkno, RBM_ZERO_AND_LOCK,
200  NULL);
201  }
202 
203  /* ref count and lock type are correct */
204 
205  /* initialize the page */
207 
208  return buf;
209 }
void _hash_pageinit(Page page, Size size)
Definition: hashpage.c:471
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:640
uint32 BlockNumber
Definition: block.h:31
#define P_NEW
Definition: bufmgr.h:82
#define ERROR
Definition: elog.h:43
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_WRITE
Definition: hash.h:255
#define RelationGetRelationName(relation)
Definition: rel.h:433
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define BufferGetPageSize(buffer)
Definition: bufmgr.h:147
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
BlockNumber RelationGetNumberOfBlocksInFork(Relation relation, ForkNumber forkNum)
Definition: bufmgr.c:2771
#define NULL
Definition: c.h:226
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2588
#define elog
Definition: elog.h:219
int Buffer
Definition: buf.h:23
Bucket _hash_hashkey2bucket ( uint32  hashkey,
uint32  maxbucket,
uint32  highmask,
uint32  lowmask 
)

Definition at line 124 of file hashutil.c.

Referenced by _hash_getbucketbuf_from_hashkey(), _hash_splitbucket_guts(), and hashbucketcleanup().

126 {
127  Bucket bucket;
128 
129  bucket = hashkey & highmask;
130  if (bucket > maxbucket)
131  bucket = bucket & lowmask;
132 
133  return bucket;
134 }
uint32 Bucket
Definition: hash.h:34
void _hash_initbitmap ( Relation  rel,
HashMetaPage  metap,
BlockNumber  blkno,
ForkNumber  forkNum 
)

Definition at line 546 of file hashovfl.c.

References _hash_getnewbuf(), _hash_relbuf(), BMPGSZ_BYTE, buf, BufferGetPage, ereport, errcode(), errmsg(), ERROR, HASH_MAX_BITMAPS, 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, InvalidBlockNumber, LH_BITMAP_PAGE, MarkBufferDirty(), MemSet, PageGetSpecialPointer, and RelationGetRelationName.

Referenced by _hash_getovflpage(), and _hash_metapinit().

548 {
549  Buffer buf;
550  Page pg;
551  HashPageOpaque op;
552  uint32 *freep;
553 
554  /*
555  * It is okay to write-lock the new bitmap page while holding metapage
556  * write lock, because no one else could be contending for the new page.
557  * Also, the metapage lock makes it safe to extend the index using
558  * _hash_getnewbuf.
559  *
560  * There is some loss of concurrency in possibly doing I/O for the new
561  * page while holding the metapage lock, but this path is taken so seldom
562  * that it's not worth worrying about.
563  */
564  buf = _hash_getnewbuf(rel, blkno, forkNum);
565  pg = BufferGetPage(buf);
566 
567  /* initialize the page's special space */
571  op->hasho_bucket = -1;
574 
575  /* set all of the bits to 1 */
576  freep = HashPageGetBitmap(pg);
577  MemSet(freep, 0xFF, BMPGSZ_BYTE(metap));
578 
579  /* dirty the new bitmap page, and release write lock and pin */
580  MarkBufferDirty(buf);
581  _hash_relbuf(rel, buf);
582 
583  /* add the new bitmap page to the metapage's list of bitmaps */
584  /* metapage already has a write lock */
585  if (metap->hashm_nmaps >= HASH_MAX_BITMAPS)
586  ereport(ERROR,
587  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
588  errmsg("out of overflow pages in hash index \"%s\"",
589  RelationGetRelationName(rel))));
590 
591  metap->hashm_mapp[metap->hashm_nmaps] = blkno;
592 
593  metap->hashm_nmaps++;
594 }
uint16 hasho_page_id
Definition: hash.h:81
#define HashPageGetBitmap(page)
Definition: hash.h:231
#define LH_BITMAP_PAGE
Definition: hash.h:55
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
int errcode(int sqlerrcode)
Definition: elog.c:575
#define MemSet(start, val, len)
Definition: c.h:853
Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno, ForkNumber forkNum)
Definition: hashpage.c:177
BlockNumber hasho_prevblkno
Definition: hash.h:77
#define ERROR
Definition: elog.h:43
uint32 hashm_nmaps
Definition: hash.h:190
static char * buf
Definition: pg_test_fsync.c:65
#define RelationGetRelationName(relation)
Definition: rel.h:433
unsigned int uint32
Definition: c.h:265
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define ereport(elevel, rest)
Definition: elog.h:122
#define HASH_MAX_BITMAPS
Definition: hash.h:172
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
Bucket hasho_bucket
Definition: hash.h:79
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
#define InvalidBlockNumber
Definition: block.h:33
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define HASHO_PAGE_ID
Definition: hash.h:96
uint16 hasho_flag
Definition: hash.h:80
int errmsg(const char *fmt,...)
Definition: elog.c:797
BlockNumber hasho_nextblkno
Definition: hash.h:78
#define BMPGSZ_BYTE(metap)
Definition: hash.h:226
BlockNumber hashm_mapp[HASH_MAX_BITMAPS]
Definition: hash.h:194
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
uint32 _hash_log2 ( uint32  num)

Definition at line 140 of file hashutil.c.

References i.

Referenced by _h_spoolinit(), _hash_expandtable(), and _hash_metapinit().

141 {
142  uint32 i,
143  limit;
144 
145  limit = 1;
146  for (i = 0; limit < num; limit <<= 1, i++)
147  ;
148  return i;
149 }
unsigned int uint32
Definition: c.h:265
int i
uint32 _hash_metapinit ( Relation  rel,
double  num_tuples,
ForkNumber  forkNum 
)

Definition at line 306 of file hashpage.c.

References _hash_getnewbuf(), _hash_initbitmap(), _hash_log2(), _hash_relbuf(), Assert, BMPG_MASK, BMPG_SHIFT, BUCKET_TO_BLKNO, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, BYTE_TO_BIT, CHECK_FOR_INTERRUPTS, elog, ERROR, HASH_DEFAULT_FILLFACTOR, HASH_MAGIC, HASH_MAX_SPLITPOINTS, HASH_METAPAGE, HASH_VERSION, HashGetMaxBitmapSize, HashMetaPageData::hashm_bmshift, HashMetaPageData::hashm_bmsize, HashMetaPageData::hashm_bsize, HashMetaPageData::hashm_ffactor, HashMetaPageData::hashm_firstfree, HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_magic, HashMetaPageData::hashm_mapp, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_nmaps, HashMetaPageData::hashm_ntuples, HashMetaPageData::hashm_ovflpoint, HashMetaPageData::hashm_procid, HashMetaPageData::hashm_spares, HashMetaPageData::hashm_version, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_page_id, HASHO_PAGE_ID, HashPageOpaqueData::hasho_prevblkno, HashPageGetMeta, HASHPROC, i, index_getprocid(), InvalidBlockNumber, LH_BUCKET_PAGE, LH_META_PAGE, LockBuffer(), MarkBufferDirty(), MAXALIGN, MemSet, PageGetSpecialPointer, RelationGetNumberOfBlocksInFork(), RelationGetRelationName, and RelationGetTargetPageUsage.

Referenced by hashbuild(), and hashbuildempty().

307 {
308  HashMetaPage metap;
309  HashPageOpaque pageopaque;
310  Buffer metabuf;
311  Buffer buf;
312  Page pg;
313  int32 data_width;
314  int32 item_width;
315  int32 ffactor;
316  double dnumbuckets;
317  uint32 num_buckets;
318  uint32 log2_num_buckets;
319  uint32 i;
320 
321  /* safety check */
322  if (RelationGetNumberOfBlocksInFork(rel, forkNum) != 0)
323  elog(ERROR, "cannot initialize non-empty hash index \"%s\"",
325 
326  /*
327  * Determine the target fill factor (in tuples per bucket) for this index.
328  * The idea is to make the fill factor correspond to pages about as full
329  * as the user-settable fillfactor parameter says. We can compute it
330  * exactly since the index datatype (i.e. uint32 hash key) is fixed-width.
331  */
332  data_width = sizeof(uint32);
333  item_width = MAXALIGN(sizeof(IndexTupleData)) + MAXALIGN(data_width) +
334  sizeof(ItemIdData); /* include the line pointer */
335  ffactor = RelationGetTargetPageUsage(rel, HASH_DEFAULT_FILLFACTOR) / item_width;
336  /* keep to a sane range */
337  if (ffactor < 10)
338  ffactor = 10;
339 
340  /*
341  * Choose the number of initial bucket pages to match the fill factor
342  * given the estimated number of tuples. We round up the result to the
343  * next power of 2, however, and always force at least 2 bucket pages. The
344  * upper limit is determined by considerations explained in
345  * _hash_expandtable().
346  */
347  dnumbuckets = num_tuples / ffactor;
348  if (dnumbuckets <= 2.0)
349  num_buckets = 2;
350  else if (dnumbuckets >= (double) 0x40000000)
351  num_buckets = 0x40000000;
352  else
353  num_buckets = ((uint32) 1) << _hash_log2((uint32) dnumbuckets);
354 
355  log2_num_buckets = _hash_log2(num_buckets);
356  Assert(num_buckets == (((uint32) 1) << log2_num_buckets));
357  Assert(log2_num_buckets < HASH_MAX_SPLITPOINTS);
358 
359  /*
360  * We initialize the metapage, the first N bucket pages, and the first
361  * bitmap page in sequence, using _hash_getnewbuf to cause smgrextend()
362  * calls to occur. This ensures that the smgr level has the right idea of
363  * the physical index length.
364  */
365  metabuf = _hash_getnewbuf(rel, HASH_METAPAGE, forkNum);
366  pg = BufferGetPage(metabuf);
367 
368  pageopaque = (HashPageOpaque) PageGetSpecialPointer(pg);
369  pageopaque->hasho_prevblkno = InvalidBlockNumber;
370  pageopaque->hasho_nextblkno = InvalidBlockNumber;
371  pageopaque->hasho_bucket = -1;
372  pageopaque->hasho_flag = LH_META_PAGE;
373  pageopaque->hasho_page_id = HASHO_PAGE_ID;
374 
375  metap = HashPageGetMeta(pg);
376 
377  metap->hashm_magic = HASH_MAGIC;
378  metap->hashm_version = HASH_VERSION;
379  metap->hashm_ntuples = 0;
380  metap->hashm_nmaps = 0;
381  metap->hashm_ffactor = ffactor;
382  metap->hashm_bsize = HashGetMaxBitmapSize(pg);
383  /* find largest bitmap array size that will fit in page size */
384  for (i = _hash_log2(metap->hashm_bsize); i > 0; --i)
385  {
386  if ((1 << i) <= metap->hashm_bsize)
387  break;
388  }
389  Assert(i > 0);
390  metap->hashm_bmsize = 1 << i;
391  metap->hashm_bmshift = i + BYTE_TO_BIT;
392  Assert((1 << BMPG_SHIFT(metap)) == (BMPG_MASK(metap) + 1));
393 
394  /*
395  * Label the index with its primary hash support function's OID. This is
396  * pretty useless for normal operation (in fact, hashm_procid is not used
397  * anywhere), but it might be handy for forensic purposes so we keep it.
398  */
399  metap->hashm_procid = index_getprocid(rel, 1, HASHPROC);
400 
401  /*
402  * We initialize the index with N buckets, 0 .. N-1, occupying physical
403  * blocks 1 to N. The first freespace bitmap page is in block N+1. Since
404  * N is a power of 2, we can set the masks this way:
405  */
406  metap->hashm_maxbucket = metap->hashm_lowmask = num_buckets - 1;
407  metap->hashm_highmask = (num_buckets << 1) - 1;
408 
409  MemSet(metap->hashm_spares, 0, sizeof(metap->hashm_spares));
410  MemSet(metap->hashm_mapp, 0, sizeof(metap->hashm_mapp));
411 
412  /* Set up mapping for one spare page after the initial splitpoints */
413  metap->hashm_spares[log2_num_buckets] = 1;
414  metap->hashm_ovflpoint = log2_num_buckets;
415  metap->hashm_firstfree = 0;
416 
417  /*
418  * Release buffer lock on the metapage while we initialize buckets.
419  * Otherwise, we'll be in interrupt holdoff and the CHECK_FOR_INTERRUPTS
420  * won't accomplish anything. It's a bad idea to hold buffer locks for
421  * long intervals in any case, since that can block the bgwriter.
422  */
423  MarkBufferDirty(metabuf);
424  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
425 
426  /*
427  * Initialize the first N buckets
428  */
429  for (i = 0; i < num_buckets; i++)
430  {
431  /* Allow interrupts, in case N is huge */
433 
434  buf = _hash_getnewbuf(rel, BUCKET_TO_BLKNO(metap, i), forkNum);
435  pg = BufferGetPage(buf);
436  pageopaque = (HashPageOpaque) PageGetSpecialPointer(pg);
437 
438  /*
439  * Set hasho_prevblkno with current hashm_maxbucket. This value will
440  * be used to validate cached HashMetaPageData. See
441  * _hash_getbucketbuf_from_hashkey().
442  */
443  pageopaque->hasho_prevblkno = metap->hashm_maxbucket;
444  pageopaque->hasho_nextblkno = InvalidBlockNumber;
445  pageopaque->hasho_bucket = i;
446  pageopaque->hasho_flag = LH_BUCKET_PAGE;
447  pageopaque->hasho_page_id = HASHO_PAGE_ID;
448  MarkBufferDirty(buf);
449  _hash_relbuf(rel, buf);
450  }
451 
452  /* Now reacquire buffer lock on metapage */
454 
455  /*
456  * Initialize first bitmap page
457  */
458  _hash_initbitmap(rel, metap, num_buckets + 1, forkNum);
459 
460  /* all done */
461  MarkBufferDirty(metabuf);
462  _hash_relbuf(rel, metabuf);
463 
464  return num_buckets;
465 }
#define HASH_DEFAULT_FILLFACTOR
Definition: hash.h:211
uint16 hashm_bmshift
Definition: hash.h:183
uint16 hasho_page_id
Definition: hash.h:81
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
RegProcedure hashm_procid
Definition: hash.h:191
#define LH_META_PAGE
Definition: hash.h:56
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
#define BYTE_TO_BIT
Definition: hash.h:216
uint32 hashm_magic
Definition: hash.h:176
uint16 hashm_ffactor
Definition: hash.h:179
uint32 hashm_highmask
Definition: hash.h:185
#define MemSet(start, val, len)
Definition: c.h:853
Buffer _hash_getnewbuf(Relation rel, BlockNumber blkno, ForkNumber forkNum)
Definition: hashpage.c:177
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
#define HASH_VERSION
Definition: hash.h:149
uint32 hashm_lowmask
Definition: hash.h:186
signed int int32
Definition: c.h:253
#define BUCKET_TO_BLKNO(metap, B)
Definition: hash.h:38
#define HASH_MAX_SPLITPOINTS
Definition: hash.h:171
#define HASH_MAGIC
Definition: hash.h:148
#define HashGetMaxBitmapSize(page)
Definition: hash.h:234
BlockNumber hasho_prevblkno
Definition: hash.h:77
#define ERROR
Definition: elog.h:43
uint32 hashm_version
Definition: hash.h:177
uint32 hashm_nmaps
Definition: hash.h:190
static char * buf
Definition: pg_test_fsync.c:65
#define BMPG_MASK(metap)
Definition: hash.h:229
#define RelationGetRelationName(relation)
Definition: rel.h:433
unsigned int uint32
Definition: c.h:265
struct ItemIdData ItemIdData
#define BMPG_SHIFT(metap)
Definition: hash.h:228
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
uint32 hashm_ovflpoint
Definition: hash.h:187
uint16 hashm_bsize
Definition: hash.h:180
#define HASH_METAPAGE
Definition: hash.h:146
double hashm_ntuples
Definition: hash.h:178
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
uint32 hashm_firstfree
Definition: hash.h:189
uint32 hashm_spares[HASH_MAX_SPLITPOINTS]
Definition: hash.h:192
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define LH_BUCKET_PAGE
Definition: hash.h:54
BlockNumber RelationGetNumberOfBlocksInFork(Relation relation, ForkNumber forkNum)
Definition: bufmgr.c:2771
#define RelationGetTargetPageUsage(relation, defaultff)
Definition: rel.h:297
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
#define InvalidBlockNumber
Definition: block.h:33
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define HASHO_PAGE_ID
Definition: hash.h:96
#define MAXALIGN(LEN)
Definition: c.h:584
uint32 hashm_maxbucket
Definition: hash.h:184
uint16 hasho_flag
Definition: hash.h:80
#define HashPageGetMeta(page)
Definition: hash.h:238
uint32 _hash_log2(uint32 num)
Definition: hashutil.c:140
#define HASHPROC
Definition: hash.h:269
int i
BlockNumber hasho_nextblkno
Definition: hash.h:78
uint16 hashm_bmsize
Definition: hash.h:181
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:97
#define elog
Definition: elog.h:219
void _hash_initbitmap(Relation rel, HashMetaPage metap, BlockNumber blkno, ForkNumber forkNum)
Definition: hashovfl.c:546
BlockNumber hashm_mapp[HASH_MAX_BITMAPS]
Definition: hash.h:194
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:821
bool _hash_next ( IndexScanDesc  scan,
ScanDirection  dir 
)

Definition at line 34 of file hashsearch.c.

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

Referenced by hashgetbitmap(), and hashgettuple().

35 {
36  Relation rel = scan->indexRelation;
38  Buffer buf;
39  Page page;
40  OffsetNumber offnum;
41  ItemPointer current;
42  IndexTuple itup;
43 
44  /* we still have the buffer pinned and read-locked */
45  buf = so->hashso_curbuf;
47 
48  /*
49  * step to next valid tuple.
50  */
51  if (!_hash_step(scan, &buf, dir))
52  return false;
53 
54  /* if we're here, _hash_step found a valid tuple */
55  current = &(so->hashso_curpos);
56  offnum = ItemPointerGetOffsetNumber(current);
58  page = BufferGetPage(buf);
59  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
60  so->hashso_heappos = itup->t_tid;
61 
62  return true;
63 }
HashScanOpaqueData * HashScanOpaque
Definition: hash.h:140
bool _hash_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
Definition: hashsearch.c:387
Relation indexRelation
Definition: relscan.h:89
uint16 OffsetNumber
Definition: off.h:24
static char * buf
Definition: pg_test_fsync.c:65
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define Assert(condition)
Definition: c.h:671
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
ItemPointerData hashso_curpos
Definition: hash.h:125
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
int Buffer
Definition: buf.h:23
ItemPointerData hashso_heappos
Definition: hash.h:128
Buffer hashso_curbuf
Definition: hash.h:112
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
Pointer Page
Definition: bufpage.h:74
uint32 _hash_ovflblkno_to_bitno ( HashMetaPage  metap,
BlockNumber  ovflblkno 
)

Definition at line 60 of file hashovfl.c.

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

Referenced by _hash_freeovflpage(), and hash_bitmap_info().

61 {
62  uint32 splitnum = metap->hashm_ovflpoint;
63  uint32 i;
64  uint32 bitnum;
65 
66  /* Determine the split number containing this page */
67  for (i = 1; i <= splitnum; i++)
68  {
69  if (ovflblkno <= (BlockNumber) (1 << i))
70  break; /* oops */
71  bitnum = ovflblkno - (1 << i);
72 
73  /*
74  * bitnum has to be greater than number of overflow page added in
75  * previous split point. The overflow page at this splitnum (i) if any
76  * should start from ((2 ^ i) + metap->hashm_spares[i - 1] + 1).
77  */
78  if (bitnum > metap->hashm_spares[i - 1] &&
79  bitnum <= metap->hashm_spares[i])
80  return bitnum - 1; /* -1 to convert 1-based to 0-based */
81  }
82 
83  ereport(ERROR,
84  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
85  errmsg("invalid overflow block number %u", ovflblkno)));
86  return 0; /* keep compiler quiet */
87 }
int errcode(int sqlerrcode)
Definition: elog.c:575
uint32 BlockNumber
Definition: block.h:31
#define ERROR
Definition: elog.h:43
unsigned int uint32
Definition: c.h:265
#define ereport(elevel, rest)
Definition: elog.h:122
uint32 hashm_ovflpoint
Definition: hash.h:187
uint32 hashm_spares[HASH_MAX_SPLITPOINTS]
Definition: hash.h:192
int errmsg(const char *fmt,...)
Definition: elog.c:797
int i
void _hash_pageinit ( Page  page,
Size  size 
)

Definition at line 471 of file hashpage.c.

References Assert, PageInit(), and PageIsNew.

Referenced by _hash_getinitbuf(), and _hash_getnewbuf().

472 {
473  Assert(PageIsNew(page));
474  PageInit(page, size, sizeof(HashPageOpaqueData));
475 }
#define Assert(condition)
Definition: c.h:671
#define PageIsNew(page)
Definition: bufpage.h:226
void PageInit(Page page, Size pageSize, Size specialSize)
Definition: bufpage.c:41
OffsetNumber _hash_pgaddtup ( Relation  rel,
Buffer  buf,
Size  itemsize,
IndexTuple  itup 
)

Definition at line 211 of file hashinsert.c.

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

Referenced by _hash_doinsert(), _hash_splitbucket_guts(), and _hash_squeezebucket().

212 {
213  OffsetNumber itup_off;
214  Page page;
215  uint32 hashkey;
216 
218  page = BufferGetPage(buf);
219 
220  /* Find where to insert the tuple (preserving page's hashkey ordering) */
221  hashkey = _hash_get_indextuple_hashkey(itup);
222  itup_off = _hash_binsearch(page, hashkey);
223 
224  if (PageAddItem(page, (Item) itup, itemsize, itup_off, false, false)
226  elog(ERROR, "failed to add index item to \"%s\"",
228 
229  return itup_off;
230 }
Pointer Item
Definition: item.h:17
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:413
uint16 OffsetNumber
Definition: off.h:24
#define ERROR
Definition: elog.h:43
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
static char * buf
Definition: pg_test_fsync.c:65
#define RelationGetRelationName(relation)
Definition: rel.h:433
unsigned int uint32
Definition: c.h:265
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
#define InvalidOffsetNumber
Definition: off.h:26
OffsetNumber _hash_binsearch(Page page, uint32 hash_value)
Definition: hashutil.c:291
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define elog
Definition: elog.h:219
Pointer Page
Definition: bufpage.h:74
void _hash_squeezebucket ( Relation  rel,
Bucket  bucket,
BlockNumber  bucket_blkno,
Buffer  bucket_buf,
BufferAccessStrategy  bstrategy 
)

Definition at line 629 of file hashovfl.c.

References _hash_freeovflpage(), _hash_getbuf_with_strategy(), _hash_pgaddtup(), _hash_relbuf(), Assert, BlockNumberIsValid, BUFFER_LOCK_UNLOCK, BufferGetPage, FirstOffsetNumber, HASH_WRITE, HashPageOpaqueData::hasho_bucket, HashPageOpaqueData::hasho_nextblkno, HashPageOpaqueData::hasho_prevblkno, IndexTupleDSize, InvalidBuffer, ItemIdIsDead, LH_OVERFLOW_PAGE, LockBuffer(), MarkBufferDirty(), MAXALIGN, MaxOffsetNumber, OffsetNumberNext, PageGetFreeSpace(), PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, PageIndexMultiDelete(), and PageIsEmpty.

Referenced by hashbucketcleanup().

634 {
635  BlockNumber wblkno;
636  BlockNumber rblkno;
637  Buffer wbuf;
638  Buffer rbuf;
639  Page wpage;
640  Page rpage;
641  HashPageOpaque wopaque;
642  HashPageOpaque ropaque;
643  bool wbuf_dirty;
644 
645  /*
646  * start squeezing into the primary bucket page.
647  */
648  wblkno = bucket_blkno;
649  wbuf = bucket_buf;
650  wpage = BufferGetPage(wbuf);
651  wopaque = (HashPageOpaque) PageGetSpecialPointer(wpage);
652 
653  /*
654  * if there aren't any overflow pages, there's nothing to squeeze. caller
655  * is responsible for releasing the pin on primary bucket page.
656  */
657  if (!BlockNumberIsValid(wopaque->hasho_nextblkno))
658  {
660  return;
661  }
662 
663  /*
664  * Find the last page in the bucket chain by starting at the base bucket
665  * page and working forward. Note: we assume that a hash bucket chain is
666  * usually smaller than the buffer ring being used by VACUUM, else using
667  * the access strategy here would be counterproductive.
668  */
669  rbuf = InvalidBuffer;
670  ropaque = wopaque;
671  do
672  {
673  rblkno = ropaque->hasho_nextblkno;
674  if (rbuf != InvalidBuffer)
675  _hash_relbuf(rel, rbuf);
676  rbuf = _hash_getbuf_with_strategy(rel,
677  rblkno,
678  HASH_WRITE,
680  bstrategy);
681  rpage = BufferGetPage(rbuf);
682  ropaque = (HashPageOpaque) PageGetSpecialPointer(rpage);
683  Assert(ropaque->hasho_bucket == bucket);
684  } while (BlockNumberIsValid(ropaque->hasho_nextblkno));
685 
686  /*
687  * squeeze the tuples.
688  */
689  wbuf_dirty = false;
690  for (;;)
691  {
692  OffsetNumber roffnum;
693  OffsetNumber maxroffnum;
694  OffsetNumber deletable[MaxOffsetNumber];
695  int ndeletable = 0;
696  bool retain_pin = false;
697 
698  /* Scan each tuple in "read" page */
699  maxroffnum = PageGetMaxOffsetNumber(rpage);
700  for (roffnum = FirstOffsetNumber;
701  roffnum <= maxroffnum;
702  roffnum = OffsetNumberNext(roffnum))
703  {
704  IndexTuple itup;
705  Size itemsz;
706 
707  /* skip dead tuples */
708  if (ItemIdIsDead(PageGetItemId(rpage, roffnum)))
709  continue;
710 
711  itup = (IndexTuple) PageGetItem(rpage,
712  PageGetItemId(rpage, roffnum));
713  itemsz = IndexTupleDSize(*itup);
714  itemsz = MAXALIGN(itemsz);
715 
716  /*
717  * Walk up the bucket chain, looking for a page big enough for
718  * this item. Exit if we reach the read page.
719  */
720  while (PageGetFreeSpace(wpage) < itemsz)
721  {
722  Buffer next_wbuf = InvalidBuffer;
723 
724  Assert(!PageIsEmpty(wpage));
725 
726  if (wblkno == bucket_blkno)
727  retain_pin = true;
728 
729  wblkno = wopaque->hasho_nextblkno;
730  Assert(BlockNumberIsValid(wblkno));
731 
732  /* don't need to move to next page if we reached the read page */
733  if (wblkno != rblkno)
734  next_wbuf = _hash_getbuf_with_strategy(rel,
735  wblkno,
736  HASH_WRITE,
738  bstrategy);
739 
740  /*
741  * release the lock on previous page after acquiring the lock
742  * on next page
743  */
744  if (wbuf_dirty)
745  MarkBufferDirty(wbuf);
746  if (retain_pin)
748  else
749  _hash_relbuf(rel, wbuf);
750 
751  /* nothing more to do if we reached the read page */
752  if (rblkno == wblkno)
753  {
754  if (ndeletable > 0)
755  {
756  /* Delete tuples we already moved off read page */
757  PageIndexMultiDelete(rpage, deletable, ndeletable);
758  MarkBufferDirty(rbuf);
759  }
760  _hash_relbuf(rel, rbuf);
761  return;
762  }
763 
764  wbuf = next_wbuf;
765  wpage = BufferGetPage(wbuf);
766  wopaque = (HashPageOpaque) PageGetSpecialPointer(wpage);
767  Assert(wopaque->hasho_bucket == bucket);
768  wbuf_dirty = false;
769  retain_pin = false;
770  }
771 
772  /*
773  * we have found room so insert on the "write" page, being careful
774  * to preserve hashkey ordering. (If we insert many tuples into
775  * the same "write" page it would be worth qsort'ing instead of
776  * doing repeated _hash_pgaddtup.)
777  */
778  (void) _hash_pgaddtup(rel, wbuf, itemsz, itup);
779  wbuf_dirty = true;
780 
781  /* remember tuple for deletion from "read" page */
782  deletable[ndeletable++] = roffnum;
783  }
784 
785  /*
786  * If we reach here, there are no live tuples on the "read" page ---
787  * it was empty when we got to it, or we moved them all. So we can
788  * just free the page without bothering with deleting tuples
789  * individually. Then advance to the previous "read" page.
790  *
791  * Tricky point here: if our read and write pages are adjacent in the
792  * bucket chain, our write lock on wbuf will conflict with
793  * _hash_freeovflpage's attempt to update the sibling links of the
794  * removed page. In that case, we don't need to lock it again.
795  */
796  rblkno = ropaque->hasho_prevblkno;
797  Assert(BlockNumberIsValid(rblkno));
798 
799  /* free this overflow page (releases rbuf) */
800  _hash_freeovflpage(rel, rbuf, wbuf, bstrategy);
801 
802  if (wbuf_dirty)
803  MarkBufferDirty(wbuf);
804 
805  /* are we freeing the page adjacent to wbuf? */
806  if (rblkno == wblkno)
807  {
808  /* retain the pin on primary bucket page till end of bucket scan */
809  if (wblkno == bucket_blkno)
811  else
812  _hash_relbuf(rel, wbuf);
813  return;
814  }
815 
816  rbuf = _hash_getbuf_with_strategy(rel,
817  rblkno,
818  HASH_WRITE,
820  bstrategy);
821  rpage = BufferGetPage(rbuf);
822  ropaque = (HashPageOpaque) PageGetSpecialPointer(rpage);
823  Assert(ropaque->hasho_bucket == bucket);
824  }
825 
826  /* NOTREACHED */
827 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
BlockNumber _hash_freeovflpage(Relation rel, Buffer ovflbuf, Buffer wbuf, BufferAccessStrategy bstrategy)
Definition: hashovfl.c:406
#define PageIsEmpty(page)
Definition: bufpage.h:219
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
#define MaxOffsetNumber
Definition: off.h:28
Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno, int access, int flags, BufferAccessStrategy bstrategy)
Definition: hashpage.c:218
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
#define ItemIdIsDead(itemId)
Definition: itemid.h:112
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:354
Size PageGetFreeSpace(Page page)
Definition: bufpage.c:582
uint16 OffsetNumber
Definition: off.h:24
BlockNumber hasho_prevblkno
Definition: hash.h:77
#define IndexTupleDSize(itup)
Definition: itup.h:71
#define HASH_WRITE
Definition: hash.h:255
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define Assert(condition)
Definition: c.h:671
Bucket hasho_bucket
Definition: hash.h:79
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
Definition: bufpage.c:809
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
size_t Size
Definition: c.h:353
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define MAXALIGN(LEN)
Definition: c.h:584
OffsetNumber _hash_pgaddtup(Relation rel, Buffer buf, Size itemsize, IndexTuple itup)
Definition: hashinsert.c:211
BlockNumber hasho_nextblkno
Definition: hash.h:78
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
Pointer Page
Definition: bufpage.h:74
bool _hash_step ( IndexScanDesc  scan,
Buffer bufP,
ScanDirection  dir 
)

Definition at line 387 of file hashsearch.c.

References _hash_binsearch(), _hash_binsearch_last(), _hash_checkpage(), _hash_checkqual(), _hash_dropscanbuf(), _hash_get_indextuple_hashkey(), _hash_readnext(), _hash_readprev(), Assert, BackwardScanDirection, buf, BufferGetBlockNumber(), BufferGetPage, BufferIsValid, FirstOffsetNumber, ForwardScanDirection, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_curbuf, HashScanOpaqueData::hashso_curpos, HashScanOpaqueData::hashso_sk_hash, INDEX_MOVED_BY_SPLIT_MASK, IndexScanDescData::indexRelation, InvalidBuffer, InvalidOffsetNumber, ItemPointerGetOffsetNumber, ItemPointerIsValid, ItemPointerSet, ItemPointerSetInvalid, LH_BUCKET_PAGE, LH_OVERFLOW_PAGE, NULL, OffsetNumberNext, OffsetNumberPrev, IndexScanDescData::opaque, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and PageGetSpecialPointer.

Referenced by _hash_first(), and _hash_next().

388 {
389  Relation rel = scan->indexRelation;
390  HashScanOpaque so = (HashScanOpaque) scan->opaque;
391  ItemPointer current;
392  Buffer buf;
393  Page page;
394  HashPageOpaque opaque;
395  OffsetNumber maxoff;
396  OffsetNumber offnum;
397  BlockNumber blkno;
398  IndexTuple itup;
399 
400  current = &(so->hashso_curpos);
401 
402  buf = *bufP;
404  page = BufferGetPage(buf);
405  opaque = (HashPageOpaque) PageGetSpecialPointer(page);
406 
407  /*
408  * If _hash_step is called from _hash_first, current will not be valid, so
409  * we can't dereference it. However, in that case, we presumably want to
410  * start at the beginning/end of the page...
411  */
412  maxoff = PageGetMaxOffsetNumber(page);
413  if (ItemPointerIsValid(current))
414  offnum = ItemPointerGetOffsetNumber(current);
415  else
416  offnum = InvalidOffsetNumber;
417 
418  /*
419  * 'offnum' now points to the last tuple we examined (if any).
420  *
421  * continue to step through tuples until: 1) we get to the end of the
422  * bucket chain or 2) we find a valid tuple.
423  */
424  do
425  {
426  switch (dir)
427  {
429  if (offnum != InvalidOffsetNumber)
430  offnum = OffsetNumberNext(offnum); /* move forward */
431  else
432  {
433  /* new page, locate starting position by binary search */
434  offnum = _hash_binsearch(page, so->hashso_sk_hash);
435  }
436 
437  for (;;)
438  {
439  /*
440  * check if we're still in the range of items with the
441  * target hash key
442  */
443  if (offnum <= maxoff)
444  {
445  Assert(offnum >= FirstOffsetNumber);
446  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
447 
448  /*
449  * skip the tuples that are moved by split operation
450  * for the scan that has started when split was in
451  * progress
452  */
453  if (so->hashso_buc_populated && !so->hashso_buc_split &&
454  (itup->t_info & INDEX_MOVED_BY_SPLIT_MASK))
455  {
456  offnum = OffsetNumberNext(offnum); /* move forward */
457  continue;
458  }
459 
461  break; /* yes, so exit for-loop */
462  }
463 
464  /*
465  * ran off the end of this page, try the next
466  */
467  _hash_readnext(scan, &buf, &page, &opaque);
468  if (BufferIsValid(buf))
469  {
470  maxoff = PageGetMaxOffsetNumber(page);
471  offnum = _hash_binsearch(page, so->hashso_sk_hash);
472  }
473  else
474  {
475  itup = NULL;
476  break; /* exit for-loop */
477  }
478  }
479  break;
480 
482  if (offnum != InvalidOffsetNumber)
483  offnum = OffsetNumberPrev(offnum); /* move back */
484  else
485  {
486  /* new page, locate starting position by binary search */
487  offnum = _hash_binsearch_last(page, so->hashso_sk_hash);
488  }
489 
490  for (;;)
491  {
492  /*
493  * check if we're still in the range of items with the
494  * target hash key
495  */
496  if (offnum >= FirstOffsetNumber)
497  {
498  Assert(offnum <= maxoff);
499  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
500 
501  /*
502  * skip the tuples that are moved by split operation
503  * for the scan that has started when split was in
504  * progress
505  */
506  if (so->hashso_buc_populated && !so->hashso_buc_split &&
507  (itup->t_info & INDEX_MOVED_BY_SPLIT_MASK))
508  {
509  offnum = OffsetNumberPrev(offnum); /* move back */
510  continue;
511  }
512 
514  break; /* yes, so exit for-loop */
515  }
516 
517  /*
518  * ran off the end of this page, try the next
519  */
520  _hash_readprev(scan, &buf, &page, &opaque);
521  if (BufferIsValid(buf))
522  {
523  maxoff = PageGetMaxOffsetNumber(page);
524  offnum = _hash_binsearch_last(page, so->hashso_sk_hash);
525  }
526  else
527  {
528  itup = NULL;
529  break; /* exit for-loop */
530  }
531  }
532  break;
533 
534  default:
535  /* NoMovementScanDirection */
536  /* this should not be reached */
537  itup = NULL;
538  break;
539  }
540 
541  if (itup == NULL)
542  {
543  /*
544  * We ran off the end of the bucket without finding a match.
545  * Release the pin on bucket buffers. Normally, such pins are
546  * released at end of scan, however scrolling cursors can
547  * reacquire the bucket lock and pin in the same scan multiple
548  * times.
549  */
550  *bufP = so->hashso_curbuf = InvalidBuffer;
551  ItemPointerSetInvalid(current);
552  _hash_dropscanbuf(rel, so);
553  return false;
554  }
555 
556  /* check the tuple quals, loop around if not met */
557  } while (!_hash_checkqual(scan, itup));
558 
559  /* if we made it to here, we've found a valid tuple */
560  blkno = BufferGetBlockNumber(buf);
561  *bufP = so->hashso_curbuf = buf;
562  ItemPointerSet(current, blkno, offnum);
563  return true;
564 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:59
HashScanOpaqueData * HashScanOpaque
Definition: hash.h:140
static void _hash_readnext(IndexScanDesc scan, Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
Definition: hashsearch.c:71
OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value)
Definition: hashutil.c:329
void _hash_dropscanbuf(Relation rel, HashScanOpaque so)
Definition: hashpage.c:268
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:354
Relation indexRelation
Definition: relscan.h:89
uint16 OffsetNumber
Definition: off.h:24
bool _hash_checkqual(IndexScanDesc scan, IndexTuple itup)
Definition: hashutil.c:30
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
static char * buf
Definition: pg_test_fsync.c:65
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
bool hashso_buc_populated
Definition: hash.h:131
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
uint32 hashso_sk_hash
Definition: hash.h:104
#define InvalidOffsetNumber
Definition: off.h:26
OffsetNumber _hash_binsearch(Page page, uint32 hash_value)
Definition: hashutil.c:291
#define LH_BUCKET_PAGE
Definition: hash.h:54
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:55
#define BufferIsValid(bufnum)
Definition: bufmgr.h:114
ItemPointerData hashso_curpos
Definition: hash.h:125
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
static void _hash_readprev(IndexScanDesc scan, Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
Definition: hashsearch.c:136
bool hashso_buc_split
Definition: hash.h:137
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2588
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:131
#define INDEX_MOVED_BY_SPLIT_MASK
Definition: hash.h:208
int Buffer
Definition: buf.h:23
Buffer hashso_curbuf
Definition: hash.h:112
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
Pointer Page
Definition: bufpage.h:74
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:86
Datum hash_any ( register const unsigned char *  k,
register int  keylen 
)

Definition at line 307 of file hashfunc.c.

References mix, UINT32_ALIGN_MASK, and UInt32GetDatum.

Referenced by AppendJumble(), bernoulli_nextsampletuple(), bms_hash_value(), citext_hash(), hash_numeric(), hashbpchar(), hashfloat4(), hashfloat8(), hashinet(), hashmacaddr(), hashname(), hashoidvector(), hashtext(), hashvarlena(), hstore_hash(), JsonbHashScalarValue(), lexeme_hash(), make_text_key(), pgss_hash_string(), pgss_post_parse_analyze(), ResourceArrayAdd(), ResourceArrayRemove(), sepgsql_avc_hash(), string_hash(), system_nextsampleblock(), tag_hash(), uuid_hash(), and varstr_abbrev_convert().

308 {
309  register uint32 a,
310  b,
311  c,
312  len;
313 
314  /* Set up the internal state */
315  len = keylen;
316  a = b = c = 0x9e3779b9 + len + 3923095;
317 
318  /* If the source pointer is word-aligned, we use word-wide fetches */
319  if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
320  {
321  /* Code path for aligned source data */
322  register const uint32 *ka = (const uint32 *) k;
323 
324  /* handle most of the key */
325  while (len >= 12)
326  {
327  a += ka[0];
328  b += ka[1];
329  c += ka[2];
330  mix(a, b, c);
331  ka += 3;
332  len -= 12;
333  }
334 
335  /* handle the last 11 bytes */
336  k = (const unsigned char *) ka;
337 #ifdef WORDS_BIGENDIAN
338  switch (len)
339  {
340  case 11:
341  c += ((uint32) k[10] << 8);
342  /* fall through */
343  case 10:
344  c += ((uint32) k[9] << 16);
345  /* fall through */
346  case 9:
347  c += ((uint32) k[8] << 24);
348  /* the lowest byte of c is reserved for the length */
349  /* fall through */
350  case 8:
351  b += ka[1];
352  a += ka[0];
353  break;
354  case 7:
355  b += ((uint32) k[6] << 8);
356  /* fall through */
357  case 6:
358  b += ((uint32) k[5] << 16);
359  /* fall through */
360  case 5:
361  b += ((uint32) k[4] << 24);
362  /* fall through */
363  case 4:
364  a += ka[0];
365  break;
366  case 3:
367  a += ((uint32) k[2] << 8);
368  /* fall through */
369  case 2:
370  a += ((uint32) k[1] << 16);
371  /* fall through */
372  case 1:
373  a += ((uint32) k[0] << 24);
374  /* case 0: nothing left to add */
375  }
376 #else /* !WORDS_BIGENDIAN */
377  switch (len)
378  {
379  case 11:
380  c += ((uint32) k[10] << 24);
381  /* fall through */
382  case 10:
383  c += ((uint32) k[9] << 16);
384  /* fall through */
385  case 9:
386  c += ((uint32) k[8] << 8);
387  /* the lowest byte of c is reserved for the length */
388  /* fall through */
389  case 8:
390  b += ka[1];
391  a += ka[0];
392  break;
393  case 7:
394  b += ((uint32) k[6] << 16);
395  /* fall through */
396  case 6:
397  b += ((uint32) k[5] << 8);
398  /* fall through */
399  case 5:
400  b += k[4];
401  /* fall through */
402  case 4:
403  a += ka[0];
404  break;
405  case 3:
406  a += ((uint32) k[2] << 16);
407  /* fall through */
408  case 2:
409  a += ((uint32) k[1] << 8);
410  /* fall through */
411  case 1:
412  a += k[0];
413  /* case 0: nothing left to add */
414  }
415 #endif /* WORDS_BIGENDIAN */
416  }
417  else
418  {
419  /* Code path for non-aligned source data */
420 
421  /* handle most of the key */
422  while (len >= 12)
423  {
424 #ifdef WORDS_BIGENDIAN
425  a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
426  b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
427  c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
428 #else /* !WORDS_BIGENDIAN */
429  a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
430  b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
431  c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
432 #endif /* WORDS_BIGENDIAN */
433  mix(a, b, c);
434  k += 12;
435  len -= 12;
436  }
437 
438  /* handle the last 11 bytes */
439 #ifdef WORDS_BIGENDIAN
440  switch (len) /* all the case statements fall through */
441  {
442  case 11:
443  c += ((uint32) k[10] << 8);
444  case 10:
445  c += ((uint32) k[9] << 16);
446  case 9:
447  c += ((uint32) k[8] << 24);
448  /* the lowest byte of c is reserved for the length */
449  case 8:
450  b += k[7];
451  case 7:
452  b += ((uint32) k[6] << 8);
453  case 6:
454  b += ((uint32) k[5] << 16);
455  case 5:
456  b += ((uint32) k[4] << 24);
457  case 4:
458  a += k[3];
459  case 3:
460  a += ((uint32) k[2] << 8);
461  case 2:
462  a += ((uint32) k[1] << 16);
463  case 1:
464  a += ((uint32) k[0] << 24);
465  /* case 0: nothing left to add */
466  }
467 #else /* !WORDS_BIGENDIAN */
468  switch (len) /* all the case statements fall through */
469  {
470  case 11:
471  c += ((uint32) k[10] << 24);
472  case 10:
473  c += ((uint32) k[9] << 16);
474  case 9:
475  c += ((uint32) k[8] << 8);
476  /* the lowest byte of c is reserved for the length */
477  case 8:
478  b += ((uint32) k[7] << 24);
479  case 7:
480  b += ((uint32) k[6] << 16);
481  case 6:
482  b += ((uint32) k[5] << 8);
483  case 5:
484  b += k[4];
485  case 4:
486  a += ((uint32) k[3] << 24);
487  case 3:
488  a += ((uint32) k[2] << 16);
489  case 2:
490  a += ((uint32) k[1] << 8);
491  case 1:
492  a += k[0];
493  /* case 0: nothing left to add */
494  }
495 #endif /* WORDS_BIGENDIAN */
496  }
497 
498  final(a, b, c);
499 
500  /* report the result */
501  return UInt32GetDatum(c);
502 }
char * c
unsigned int uint32
Definition: c.h:265
#define UInt32GetDatum(X)
Definition: postgres.h:501
#define UINT32_ALIGN_MASK
Definition: hashfunc.c:206
#define mix(a, b, c)
Definition: hashfunc.c:243
Datum hash_uint32 ( uint32  k)

Definition at line 512 of file hashfunc.c.

References UInt32GetDatum.

Referenced by BuildTupleHashTable(), hash_range(), hashchar(), hashenum(), hashint2(), hashint4(), hashint8(), hashoid(), pgss_hash_fn(), timetz_hash(), uint32_hash(), uuid_abbrev_convert(), and varstr_abbrev_convert().

513 {
514  register uint32 a,
515  b,
516  c;
517 
518  a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
519  a += k;
520 
521  final(a, b, c);
522 
523  /* report the result */
524  return UInt32GetDatum(c);
525 }
char * c
unsigned int uint32
Definition: c.h:265
#define UInt32GetDatum(X)
Definition: postgres.h:501
IndexScanDesc hashbeginscan ( Relation  rel,
int  nkeys,
int  norderbys 
)

Definition at line 422 of file hash.c.

References Assert, HashScanOpaqueData::hashso_buc_populated, HashScanOpaqueData::hashso_buc_split, HashScanOpaqueData::hashso_bucket_buf, HashScanOpaqueData::hashso_curbuf, HashScanOpaqueData::hashso_curpos, HashScanOpaqueData::hashso_heappos, HashScanOpaqueData::hashso_split_bucket_buf, InvalidBuffer, ItemPointerSetInvalid, IndexScanDescData::opaque, palloc(), and RelationGetIndexScan().

Referenced by hashhandler().

423 {
424  IndexScanDesc scan;
425  HashScanOpaque so;
426 
427  /* no order by operators allowed */
428  Assert(norderbys == 0);
429 
430  scan = RelationGetIndexScan(rel, nkeys, norderbys);
431 
432  so = (HashScanOpaque) palloc(sizeof(HashScanOpaqueData));
436  /* set position invalid (this will cause _hash_first call) */
439 
440  so->hashso_buc_populated = false;
441  so->hashso_buc_split = false;
442 
443  scan->opaque = so;
444 
445  return scan;
446 }
HashScanOpaqueData * HashScanOpaque
Definition: hash.h:140
#define InvalidBuffer
Definition: buf.h:25
Buffer hashso_bucket_buf
Definition: hash.h:115
bool hashso_buc_populated
Definition: hash.h:131
#define Assert(condition)
Definition: c.h:671
ItemPointerData hashso_curpos
Definition: hash.h:125
bool hashso_buc_split
Definition: hash.h:137
#define ItemPointerSetInvalid(pointer)
Definition: itemptr.h:131
void * palloc(Size size)
Definition: mcxt.c:891
Buffer hashso_split_bucket_buf
Definition: hash.h:122
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:78
ItemPointerData hashso_heappos
Definition: hash.h:128
Buffer hashso_curbuf
Definition: hash.h:112
void hashbucketcleanup ( Relation  rel,
Bucket  cur_bucket,
Buffer  bucket_buf,
BlockNumber  bucket_blkno,
BufferAccessStrategy  bstrategy,
uint32  maxbucket,
uint32  highmask,
uint32  lowmask,
double *  tuples_removed,
double *  num_index_tuples,
bool  bucket_has_garbage,
IndexBulkDeleteCallback  callback,
void *  callback_state 
)

Definition at line 711 of file hash.c.

References _hash_get_indextuple_hashkey(), _hash_get_newbucket_from_oldbucket(), _hash_getbuf_with_strategy(), _hash_hashkey2bucket(), _hash_relbuf(), _hash_squeezebucket(), Assert, GistBDItem::blkno, BlockNumberIsValid, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, callback(), FirstOffsetNumber, HASH_WRITE, HashPageOpaqueData::hasho_flag, HashPageOpaqueData::hasho_nextblkno, InvalidBucket, IsBufferCleanupOK(), LH_BUCKET_NEEDS_SPLIT_CLEANUP, LH_OVERFLOW_PAGE, LockBuffer(), MarkBufferDirty(), MaxOffsetNumber, OffsetNumberNext, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, PageIndexMultiDelete(), PG_USED_FOR_ASSERTS_ONLY, IndexTupleData::t_tid, and vacuum_delay_point().

Referenced by _hash_expandtable(), and hashbulkdelete().

717 {
718  BlockNumber blkno;
719  Buffer buf;
721  bool bucket_dirty = false;
722 
723  blkno = bucket_blkno;
724  buf = bucket_buf;
725 
726  if (split_cleanup)
727  new_bucket = _hash_get_newbucket_from_oldbucket(rel, cur_bucket,
728  lowmask, maxbucket);
729 
730  /* Scan each page in bucket */
731  for (;;)
732  {
733  HashPageOpaque opaque;
734  OffsetNumber offno;
735  OffsetNumber maxoffno;
736  Buffer next_buf;
737  Page page;
738  OffsetNumber deletable[MaxOffsetNumber];
739  int ndeletable = 0;
740  bool retain_pin = false;
741 
743 
744  page = BufferGetPage(buf);
745  opaque = (HashPageOpaque) PageGetSpecialPointer(page);
746 
747  /* Scan each tuple in page */
748  maxoffno = PageGetMaxOffsetNumber(page);
749  for (offno = FirstOffsetNumber;
750  offno <= maxoffno;
751  offno = OffsetNumberNext(offno))
752  {
753  ItemPointer htup;
754  IndexTuple itup;
755  Bucket bucket;
756  bool kill_tuple = false;
757 
758  itup = (IndexTuple) PageGetItem(page,
759  PageGetItemId(page, offno));
760  htup = &(itup->t_tid);
761 
762  /*
763  * To remove the dead tuples, we strictly want to rely on results
764  * of callback function. refer btvacuumpage for detailed reason.
765  */
766  if (callback && callback(htup, callback_state))
767  {
768  kill_tuple = true;
769  if (tuples_removed)
770  *tuples_removed += 1;
771  }
772  else if (split_cleanup)
773  {
774  /* delete the tuples that are moved by split. */
776  maxbucket,
777  highmask,
778  lowmask);
779  /* mark the item for deletion */
780  if (bucket != cur_bucket)
781  {
782  /*
783  * We expect tuples to either belong to curent bucket or
784  * new_bucket. This is ensured because we don't allow
785  * further splits from bucket that contains garbage. See
786  * comments in _hash_expandtable.
787  */
788  Assert(bucket == new_bucket);
789  kill_tuple = true;
790  }
791  }
792 
793  if (kill_tuple)
794  {
795  /* mark the item for deletion */
796  deletable[ndeletable++] = offno;
797  }
798  else
799  {
800  /* we're keeping it, so count it */
801  if (num_index_tuples)
802  *num_index_tuples += 1;
803  }
804  }
805 
806  /* retain the pin on primary bucket page till end of bucket scan */
807  if (blkno == bucket_blkno)
808  retain_pin = true;
809  else
810  retain_pin = false;
811 
812  blkno = opaque->hasho_nextblkno;
813 
814  /*
815  * Apply deletions, advance to next page and write page if needed.
816  */
817  if (ndeletable > 0)
818  {
819  PageIndexMultiDelete(page, deletable, ndeletable);
820  bucket_dirty = true;
821  MarkBufferDirty(buf);
822  }
823 
824  /* bail out if there are no more pages to scan. */
825  if (!BlockNumberIsValid(blkno))
826  break;
827 
828  next_buf = _hash_getbuf_with_strategy(rel, blkno, HASH_WRITE,
830  bstrategy);
831 
832  /*
833  * release the lock on previous page after acquiring the lock on next
834  * page
835  */
836  if (retain_pin)
838  else
839  _hash_relbuf(rel, buf);
840 
841  buf = next_buf;
842  }
843 
844  /*
845  * lock the bucket page to clear the garbage flag and squeeze the bucket.
846  * if the current buffer is same as bucket buffer, then we already have
847  * lock on bucket page.
848  */
849  if (buf != bucket_buf)
850  {
851  _hash_relbuf(rel, buf);
852  LockBuffer(bucket_buf, BUFFER_LOCK_EXCLUSIVE);
853  }
854 
855  /*
856  * Clear the garbage flag from bucket after deleting the tuples that are
857  * moved by split. We purposefully clear the flag before squeeze bucket,
858  * so that after restart, vacuum shouldn't again try to delete the moved
859  * by split tuples.
860  */
861  if (split_cleanup)
862  {
863  HashPageOpaque bucket_opaque;
864  Page page;
865 
866  page = BufferGetPage(bucket_buf);
867  bucket_opaque = (HashPageOpaque) PageGetSpecialPointer(page);
868 
869  bucket_opaque->hasho_flag &= ~LH_BUCKET_NEEDS_SPLIT_CLEANUP;
870  MarkBufferDirty(bucket_buf);
871  }
872 
873  /*
874  * If we have deleted anything, try to compact free space. For squeezing
875  * the bucket, we must have a cleanup lock, else it can impact the
876  * ordering of tuples for a scan that has started before it.
877  */
878  if (bucket_dirty && IsBufferCleanupOK(bucket_buf))
879  _hash_squeezebucket(rel, cur_bucket, bucket_blkno, bucket_buf,
880  bstrategy);
881  else
882  LockBuffer(bucket_buf, BUFFER_LOCK_UNLOCK);
883 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:124
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
#define MaxOffsetNumber
Definition: off.h:28
Buffer _hash_getbuf_with_strategy(Relation rel, BlockNumber blkno, int access, int flags, BufferAccessStrategy bstrategy)
Definition: hashpage.c:218
ItemPointerData t_tid
Definition: itup.h:37
uint32 BlockNumber
Definition: block.h:31
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:89
#define LH_BUCKET_NEEDS_SPLIT_CLEANUP
Definition: hash.h:59
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:354
uint16 OffsetNumber
Definition: off.h:24
uint32 Bucket
Definition: hash.h:34
#define InvalidBucket
Definition: hash.h:36
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:49
static char * buf
Definition: pg_test_fsync.c:65
#define HASH_WRITE
Definition: hash.h:255
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
Bucket _hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket, uint32 lowmask, uint32 maxbucket)
Definition: hashutil.c:435
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
bool IsBufferCleanupOK(Buffer buffer)
Definition: bufmgr.c:3757
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:232
#define LH_OVERFLOW_PAGE
Definition: hash.h:53
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3529
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define Assert(condition)
Definition: c.h:671
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
Definition: bufpage.c:809
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define PageGetSpecialPointer(page)
Definition: bufpage.h:323
HashPageOpaqueData * HashPageOpaque
Definition: hash.h:84
void _hash_squeezebucket(Relation rel, Bucket bucket, BlockNumber bucket_blkno, Buffer bucket_buf, BufferAccessStrategy bstrategy)
Definition: hashovfl.c:629
uint16 hasho_flag
Definition: hash.h:80
BlockNumber hasho_nextblkno
Definition: hash.h:78
void vacuum_delay_point(void)
Definition: vacuum.c:1515
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:986
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:337
Pointer Page
Definition: bufpage.h:74
IndexBuildResult* hashbuild ( Relation  heap,
Relation  index,
struct IndexInfo indexInfo 
)

Definition at line 101 of file hash.c.

References _h_indexbuild(), _h_spooldestroy(), _h_spoolinit(), _hash_metapinit(), elog, ERROR, estimate_rel_size(), hashbuildCallback(), IndexBuildResult::heap_tuples, IndexBuildResult::index_tuples, IndexBuildHeapScan(), HashBuildState::indtuples, MAIN_FORKNUM, maintenance_work_mem, Min, NBuffers, NLocBuffer, NULL, palloc(), RelationData::rd_rel, RelationGetNumberOfBlocks, RelationGetRelationName, RELPERSISTENCE_TEMP, and HashBuildState::spool.

Referenced by hashhandler().

102 {
103  IndexBuildResult *result;
104  BlockNumber relpages;
105  double reltuples;
106  double allvisfrac;
107  uint32 num_buckets;
108  long sort_threshold;
109  HashBuildState buildstate;
110 
111  /*
112  * We expect to be called exactly once for any index relation. If that's
113  * not the case, big trouble's what we have.
114  */
115  if (RelationGetNumberOfBlocks(index) != 0)
116  elog(ERROR, "index \"%s\" already contains data",
117  RelationGetRelationName(index));
118 
119  /* Estimate the number of rows currently present in the table */
120  estimate_rel_size(heap, NULL, &relpages, &reltuples, &allvisfrac);
121 
122  /* Initialize the hash index metadata page and initial buckets */
123  num_buckets = _hash_metapinit(index, reltuples, MAIN_FORKNUM);
124 
125  /*
126  * If we just insert the tuples into the index in scan order, then
127  * (assuming their hash codes are pretty random) there will be no locality
128  * of access to the index, and if the index is bigger than available RAM
129  * then we'll thrash horribly. To prevent that scenario, we can sort the
130  * tuples by (expected) bucket number. However, such a sort is useless
131  * overhead when the index does fit in RAM. We choose to sort if the
132  * initial index size exceeds maintenance_work_mem, or the number of
133  * buffers usable for the index, whichever is less. (Limiting by the
134  * number of buffers should reduce thrashing between PG buffers and kernel
135  * buffers, which seems useful even if no physical I/O results. Limiting
136  * by maintenance_work_mem is useful to allow easy testing of the sort
137  * code path, and may be useful to DBAs as an additional control knob.)
138  *
139  * NOTE: this test will need adjustment if a bucket is ever different from
140  * one page. Also, "initial index size" accounting does not include the
141  * metapage, nor the first bitmap page.
142  */
143  sort_threshold = (maintenance_work_mem * 1024L) / BLCKSZ;
144  if (index->rd_rel->relpersistence != RELPERSISTENCE_TEMP)
145  sort_threshold = Min(sort_threshold, NBuffers);
146  else
147  sort_threshold = Min(sort_threshold, NLocBuffer);
148 
149  if (num_buckets >= (uint32) sort_threshold)
150  buildstate.spool = _h_spoolinit(heap, index, num_buckets);
151  else
152  buildstate.spool = NULL;
153 
154  /* prepare to build the index */
155  buildstate.indtuples = 0;
156 
157  /* do the heap scan */
158  reltuples = IndexBuildHeapScan(heap, index, indexInfo, true,
159  hashbuildCallback, (void *) &buildstate);
160 
161  if (buildstate.spool)
162  {
163  /* sort the tuples and insert them into the index */
164  _h_indexbuild(buildstate.spool);
165  _h_spooldestroy(buildstate.spool);
166  }
167 
168  /*
169  * Return statistics
170  */
171  result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
172 
173  result->heap_tuples = reltuples;
174  result->index_tuples = buildstate.indtuples;
175 
176  return result;
177 }
static void hashbuildCallback(Relation index, HeapTuple htup, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
Definition: hash.c:192
#define Min(x, y)
Definition: c.h:802
double indtuples
Definition: hash.c:37
uint32 BlockNumber
Definition: block.h:31
Form_pg_class rd_rel
Definition: rel.h:113
#define ERROR
Definition: elog.h:43
int NLocBuffer
Definition: localbuf.c:41
#define RelationGetRelationName(relation)
Definition: rel.h:433
unsigned int uint32
Definition: c.h:265
void estimate_rel_size(Relation rel, int32 *attr_widths, BlockNumber *pages, double *tuples, double *allvisfrac)
Definition: plancat.c:901
HSpool * spool
Definition: hash.c:36
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:199
int maintenance_work_mem
Definition: globals.c:113
#define NULL
Definition: c.h:226
void _h_indexbuild(HSpool *hspool)
Definition: hashsort.c:104
uint32 _hash_metapinit(Relation rel, double num_tuples, ForkNumber forkNum)
Definition: hashpage.c:306
void _h_spooldestroy(HSpool *hspool)
Definition: hashsort.c:83
double IndexBuildHeapScan(Relation heapRelation, Relation indexRelation, IndexInfo *indexInfo, bool allow_sync, IndexBuildCallback callback, void *callback_state)
Definition: index.c:2169
void * palloc(Size size)
Definition: mcxt.c:891
int NBuffers
Definition: globals.c:122
#define elog
Definition: elog.h:219
HSpool * _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
Definition: hashsort.c:48
#define RELPERSISTENCE_TEMP
Definition: pg_class.h:172
double index_tuples
Definition: genam.h:33
double heap_tuples
Definition: genam.h:32
void hashbuildempty ( Relation  index)

Definition at line 183 of file hash.c.

References _hash_metapinit(), and INIT_FORKNUM.

Referenced by hashhandler().

184 {
185  _hash_metapinit(index, 0, INIT_FORKNUM);
186 }
uint32 _hash_metapinit(Relation rel, double num_tuples, ForkNumber forkNum)
Definition: hashpage.c:306
IndexBulkDeleteResult* hashbulkdelete ( IndexVacuumInfo info,
IndexBulkDeleteResult stats,
IndexBulkDeleteCallback  callback,
void *  callback_state 
)

Definition at line 502 of file hash.c.

References _hash_checkpage(), _hash_dropbuf(), _hash_getbuf(), _hash_getcachedmetap(), _hash_relbuf(), Assert, GistBDItem::blkno, BUCKET_TO_BLKNO, buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage, BufferIsInvalid, IndexBulkDeleteResult::estimated_count, H_BUCKET_BEING_SPLIT, H_NEEDS_SPLIT_CLEANUP, HASH_METAPAGE, HASH_NOLOCK, hashbucketcleanup(), HashMetaPageData::hashm_highmask, HashMetaPageData::hashm_lowmask, HashMetaPageData::hashm_maxbucket, HashMetaPageData::hashm_ntuples, HashPageOpaqueData::hasho_prevblkno, HashPageGetMeta, IndexVacuumInfo::index, InvalidBlockNumber, InvalidBuffer, LH_BUCKET_PAGE, LH_META_PAGE, LockBuffer(), LockBufferForCleanup(), MAIN_FORKNUM, MarkBufferDirty(), NULL, IndexBulkDeleteResult::num_index_tuples, PageGetSpecialPointer, palloc0(), RBM_NORMAL, ReadBufferExtended(), IndexVacuumInfo::strategy, and IndexBulkDeleteResult::tuples_removed.

Referenced by hashhandler().

504 {
505  Relation rel = info->index;
506  double tuples_removed;
507  double num_index_tuples;
508  double orig_ntuples;
509  Bucket orig_maxbucket;
510  Bucket cur_maxbucket;
511  Bucket cur_bucket;
512  Buffer metabuf = InvalidBuffer;
513  HashMetaPage metap;
514  HashMetaPage cachedmetap;
515 
516  tuples_removed = 0;
517  num_index_tuples = 0;
518 
519  /*
520  * We need a copy of the metapage so that we can use its hashm_spares[]
521  * values to compute bucket page addresses, but a cached copy should be
522  * good enough. (If not, we'll detect that further down and refresh the
523  * cache as necessary.)
524  */
525  cachedmetap = _hash_getcachedmetap(rel, &metabuf, false);
526  Assert(cachedmetap != NULL);
527 
528  orig_maxbucket = cachedmetap->hashm_maxbucket;
529  orig_ntuples = cachedmetap->hashm_ntuples;
530 
531  /* Scan the buckets that we know exist */
532  cur_bucket = 0;
533  cur_maxbucket = orig_maxbucket;
534 
535 loop_top:
536  while (cur_bucket <= cur_maxbucket)
537  {
538  BlockNumber bucket_blkno;
539  BlockNumber blkno;
540  Buffer bucket_buf;
541  Buffer buf;
542  HashPageOpaque bucket_opaque;
543  Page page;
544  bool split_cleanup = false;
545 
546  /* Get address of bucket's start page */
547  bucket_blkno = BUCKET_TO_BLKNO(cachedmetap, cur_bucket);
548 
549  blkno = bucket_blkno;
550 
551  /*
552  * We need to acquire a cleanup lock on the primary bucket page to out
553  * wait concurrent scans before deleting the dead tuples.
554  */
555  buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL, info->strategy);
557  _hash_checkpage(rel, buf, LH_BUCKET_PAGE);
558 
559  page = BufferGetPage(buf);
560  bucket_opaque = (HashPageOpaque) PageGetSpecialPointer(page);
561 
562  /*
563  * If the bucket contains tuples that are moved by split, then we need
564  * to delete such tuples. We can't delete such tuples if the split
565  * operation on bucket is not finished as those are needed by scans.
566  */
567  if (!H_BUCKET_BEING_SPLIT(bucket_opaque) &&
568  H_NEEDS_SPLIT_CLEANUP(bucket_opaque))
569  {
570  split_cleanup = true;
571 
572  /*
573  * This bucket might have been split since we last held a lock on
574  * the metapage. If so, hashm_maxbucket, hashm_highmask and
575  * hashm_lowmask might be old enough to cause us to fail to remove
576  * tuples left behind by the most recent split. To prevent that,
577  * now that the primary page of the target bucket has been locked
578  * (and thus can't be further split), check whether we need to
579  * update our cached metapage data.
580  *
581  * NB: The check for InvalidBlockNumber is only needed for
582  * on-disk compatibility with indexes created before we started
583  * storing hashm_maxbucket in the primary page's hasho_prevblkno.
584  */
585  if (bucket_opaque->hasho_prevblkno != InvalidBlockNumber &&
586  bucket_opaque->hasho_prevblkno > cachedmetap->hashm_maxbucket)
587  {
588  cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
589  Assert(cachedmetap != NULL);
590  }
591  }
592 
593  bucket_buf = buf;
594 
595  hashbucketcleanup(rel, cur_bucket, bucket_buf, blkno, info->strategy,
596  cachedmetap->hashm_maxbucket,
597  cachedmetap->hashm_highmask,
598  cachedmetap->hashm_lowmask, &tuples_removed,
599  &num_index_tuples, split_cleanup,
600  callback, callback_state);
601 
602  _hash_dropbuf(rel, bucket_buf);
603 
604  /* Advance to next bucket */
605  cur_bucket++;
606  }
607 
608  if (BufferIsInvalid(metabuf))
610 
611  /* Write-lock metapage and check for split since we started */
613  metap = HashPageGetMeta(BufferGetPage(metabuf));
614 
615  if (cur_maxbucket != metap->hashm_maxbucket)
616  {
617  /* There's been a split, so process the additional bucket(s) */
618  LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
619  cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
620  Assert(cachedmetap != NULL);
621  cur_maxbucket = cachedmetap->hashm_maxbucket;
622  goto loop_top;
623  }
624 
625  /* Okay, we're really done. Update tuple count in metapage. */
626 
627  if (orig_maxbucket == metap->hashm_maxbucket &&
628  orig_ntuples == metap->hashm_ntuples)
629  {
630  /*
631  * No one has split or inserted anything since start of scan, so
632  * believe our count as gospel.
633  */
634  metap->hashm_ntuples = num_index_tuples;
635  }
636  else
637  {
638  /*
639  * Otherwise, our count is untrustworthy since we may have
640  * double-scanned tuples in split buckets. Proceed by dead-reckoning.
641  * (Note: we still return estimated_count = false, because using this
642  * count is better than not updating reltuples at all.)
643  */
644  if (metap->hashm_ntuples > tuples_removed)
645  metap->hashm_ntuples -= tuples_removed;
646  else
647  metap->hashm_ntuples = 0;
648  num_index_tuples = metap->hashm_ntuples;
649  }
650 
651  MarkBufferDirty(metabuf);
652  _hash_relbuf(rel, metabuf);
653 
654  /* return statistics */
655  if (stats == NULL)
657  stats->estimated_count = false;
658  stats->num_index_tuples = num_index_tuples;
659  stats->tuples_removed += tuples_removed;
660  /* hashvacuumcleanup will fill in num_pages */
661 
662  return stats;
663 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
void LockBufferForCleanup(Buffer buffer)
Definition: bufmgr.c:3586
double tuples_removed
Definition: genam.h:77
#define LH_META_PAGE
Definition: hash.h:56
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1445
Buffer ReadBufferExtended(Relation reln, ForkNumber forkNum, BlockNumber blockNum, ReadBufferMode mode, BufferAccessStrategy strategy)
Definition: bufmgr.c:640
BufferAccessStrategy strategy
Definition: genam.h:51
uint32 hashm_highmask
Definition: hash.h:185
#define InvalidBuffer
Definition: buf.h:25
Relation index
Definition: genam.h:46
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: hash.c:711