PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hashinsert.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * hashinsert.c
4  * Item insertion in hash tables for Postgres.
5  *
6  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/access/hash/hashinsert.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 
16 #include "postgres.h"
17 
18 #include "access/hash.h"
19 #include "utils/rel.h"
20 
21 
22 /*
23  * _hash_doinsert() -- Handle insertion of a single index tuple.
24  *
25  * This routine is called by the public interface routines, hashbuild
26  * and hashinsert. By here, itup is completely filled in.
27  */
28 void
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 }
198 
199 /*
200  * _hash_pgaddtup() -- add a tuple to a particular page in the index.
201  *
202  * This routine adds the tuple to the page as requested; it does not write out
203  * the page. It is an error to call pgaddtup() without pin and write lock on
204  * the target buffer.
205  *
206  * Returns the offset number at which the tuple was inserted. This function
207  * is responsible for preserving the condition that tuples in a hash index
208  * page are sorted by hashkey value.
209  */
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 }
#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
Pointer Item
Definition: item.h:17
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
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:413
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
uint16 OffsetNumber
Definition: off.h:24
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
#define RelationGetRelationName(relation)
Definition: rel.h:433
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
void _hash_doinsert(Relation rel, IndexTuple itup)
Definition: hashinsert.c:29
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition: hashutil.c:158
#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
#define InvalidOffsetNumber
Definition: off.h:26
void _hash_relbuf(Relation rel, Buffer buf)
Definition: hashpage.c:245
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
OffsetNumber _hash_binsearch(Page page, uint32 hash_value)
Definition: hashutil.c:291
#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:670
Bucket hasho_bucket
Definition: hash.h:79
size_t Size
Definition: c.h:352
#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:583
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
#define elog
Definition: elog.h:219
int Buffer
Definition: buf.h:23
Pointer Page
Definition: bufpage.h:74