1 /*-------------------------------------------------------------------------
4 * Hash table page management code for the Postgres hash access method
6 * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/access/hash/hashpage.c,v 1.58 2006/07/02 02:23:18 momjian Exp $
14 * Postgres hash pages look like ordinary relation pages. The opaque
15 * data at high addresses includes information about the page including
16 * whether a page is an overflow page or a true bucket, the bucket
17 * number, and the block numbers of the preceding and following pages
20 * The first page in a hash relation, page zero, is special -- it stores
21 * information describing the hash table; it is referred to as the
22 * "meta page." Pages one and higher store the actual data.
24 * There are also bitmap pages, which are not manipulated here;
27 *-------------------------------------------------------------------------
31 #include "access/genam.h"
32 #include "access/hash.h"
33 #include "catalog/index.h"
34 #include "miscadmin.h"
35 #include "storage/lmgr.h"
36 #include "utils/lsyscache.h"
39 static void _hash_splitbucket(Relation rel, Buffer metabuf,
40 Bucket obucket, Bucket nbucket,
41 BlockNumber start_oblkno,
42 BlockNumber start_nblkno,
44 uint32 highmask, uint32 lowmask);
48 * We use high-concurrency locking on hash indexes (see README for an overview
49 * of the locking rules). However, we can skip taking lmgr locks when the
50 * index is local to the current backend (ie, either temp or new in the
51 * current transaction). No one else can see it, so there's no reason to
52 * take locks. We still take buffer-level locks, but not lmgr locks.
54 #define USELOCKING(rel) (!RELATION_IS_LOCAL(rel))
58 * _hash_getlock() -- Acquire an lmgr lock.
60 * 'whichlock' should be zero to acquire the split-control lock, or the
61 * block number of a bucket's primary bucket page to acquire the per-bucket
62 * lock. (See README for details of the use of these locks.)
64 * 'access' must be HASH_SHARE or HASH_EXCLUSIVE.
67 _hash_getlock(Relation rel, BlockNumber whichlock, int access)
70 LockPage(rel, whichlock, access);
74 * _hash_try_getlock() -- Acquire an lmgr lock, but only if it's free.
76 * Same as above except we return FALSE without blocking if lock isn't free.
79 _hash_try_getlock(Relation rel, BlockNumber whichlock, int access)
82 return ConditionalLockPage(rel, whichlock, access);
88 * _hash_droplock() -- Release an lmgr lock.
91 _hash_droplock(Relation rel, BlockNumber whichlock, int access)
94 UnlockPage(rel, whichlock, access);
98 * _hash_getbuf() -- Get a buffer by block number for read or write.
100 * 'access' must be HASH_READ, HASH_WRITE, or HASH_NOLOCK.
102 * When this routine returns, the appropriate lock is set on the
103 * requested buffer and its reference count has been incremented
104 * (ie, the buffer is "locked and pinned").
106 * XXX P_NEW is not used because, unlike the tree structures, we
107 * need the bucket blocks to be at certain block numbers.
109 * All call sites should call either _hash_pageinit or _hash_checkpage
110 * on the returned page, depending on whether the block is expected
114 _hash_getbuf(Relation rel, BlockNumber blkno, int access)
119 elog(ERROR, "hash AM does not use P_NEW");
121 buf = ReadBuffer(rel, blkno);
123 if (access != HASH_NOLOCK)
124 LockBuffer(buf, access);
126 /* ref count and lock type are correct */
131 * _hash_relbuf() -- release a locked buffer.
133 * Lock and pin (refcount) are both dropped.
136 _hash_relbuf(Relation rel, Buffer buf)
138 UnlockReleaseBuffer(buf);
142 * _hash_dropbuf() -- release an unlocked buffer.
144 * This is used to unpin a buffer on which we hold no lock.
147 _hash_dropbuf(Relation rel, Buffer buf)
153 * _hash_wrtbuf() -- write a hash page to disk.
155 * This routine releases the lock held on the buffer and our refcount
156 * for it. It is an error to call _hash_wrtbuf() without a write lock
157 * and a pin on the buffer.
159 * NOTE: this routine should go away when/if hash indexes are WAL-ified.
160 * The correct sequence of operations is to mark the buffer dirty, then
161 * write the WAL record, then release the lock and pin; so marking dirty
162 * can't be combined with releasing.
165 _hash_wrtbuf(Relation rel, Buffer buf)
167 MarkBufferDirty(buf);
168 UnlockReleaseBuffer(buf);
172 * _hash_chgbufaccess() -- Change the lock type on a buffer, without
173 * dropping our pin on it.
175 * from_access and to_access may be HASH_READ, HASH_WRITE, or HASH_NOLOCK,
176 * the last indicating that no buffer-level lock is held or wanted.
178 * When from_access == HASH_WRITE, we assume the buffer is dirty and tell
179 * bufmgr it must be written out. If the caller wants to release a write
180 * lock on a page that's not been modified, it's okay to pass from_access
181 * as HASH_READ (a bit ugly, but handy in some places).
184 _hash_chgbufaccess(Relation rel,
189 if (from_access == HASH_WRITE)
190 MarkBufferDirty(buf);
191 if (from_access != HASH_NOLOCK)
192 LockBuffer(buf, BUFFER_LOCK_UNLOCK);
193 if (to_access != HASH_NOLOCK)
194 LockBuffer(buf, to_access);
199 * _hash_metapinit() -- Initialize the metadata page of a hash index,
200 * the two buckets that we begin with and the initial
203 * We are fairly cavalier about locking here, since we know that no one else
204 * could be accessing this index. In particular the rule about not holding
205 * multiple buffer locks is ignored.
208 _hash_metapinit(Relation rel)
211 HashPageOpaque pageopaque;
221 if (RelationGetNumberOfBlocks(rel) != 0)
222 elog(ERROR, "cannot initialize non-empty hash index \"%s\"",
223 RelationGetRelationName(rel));
226 * Determine the target fill factor (tuples per bucket) for this index.
227 * The idea is to make the fill factor correspond to pages about 3/4ths
228 * full. We can compute it exactly if the index datatype is fixed-width,
229 * but for var-width there's some guessing involved.
231 data_width = get_typavgwidth(RelationGetDescr(rel)->attrs[0]->atttypid,
232 RelationGetDescr(rel)->attrs[0]->atttypmod);
233 item_width = MAXALIGN(sizeof(IndexTupleData)) + MAXALIGN(data_width) +
234 sizeof(ItemIdData); /* include the line pointer */
235 ffactor = BLCKSZ * IndexGetFillFactor(rel) / 100 / item_width;
236 /* keep to a sane range */
240 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_WRITE);
241 pg = BufferGetPage(metabuf);
242 _hash_pageinit(pg, BufferGetPageSize(metabuf));
244 pageopaque = (HashPageOpaque) PageGetSpecialPointer(pg);
245 pageopaque->hasho_prevblkno = InvalidBlockNumber;
246 pageopaque->hasho_nextblkno = InvalidBlockNumber;
247 pageopaque->hasho_bucket = -1;
248 pageopaque->hasho_flag = LH_META_PAGE;
249 pageopaque->hasho_filler = HASHO_FILL;
251 metap = (HashMetaPage) pg;
253 metap->hashm_magic = HASH_MAGIC;
254 metap->hashm_version = HASH_VERSION;
255 metap->hashm_ntuples = 0;
256 metap->hashm_nmaps = 0;
257 metap->hashm_ffactor = ffactor;
258 metap->hashm_bsize = BufferGetPageSize(metabuf);
259 /* find largest bitmap array size that will fit in page size */
260 for (i = _hash_log2(metap->hashm_bsize); i > 0; --i)
262 if ((1 << i) <= (metap->hashm_bsize -
263 (MAXALIGN(sizeof(PageHeaderData)) +
264 MAXALIGN(sizeof(HashPageOpaqueData)))))
268 metap->hashm_bmsize = 1 << i;
269 metap->hashm_bmshift = i + BYTE_TO_BIT;
270 Assert((1 << BMPG_SHIFT(metap)) == (BMPG_MASK(metap) + 1));
272 metap->hashm_procid = index_getprocid(rel, 1, HASHPROC);
275 * We initialize the index with two buckets, 0 and 1, occupying physical
276 * blocks 1 and 2. The first freespace bitmap page is in block 3.
278 metap->hashm_maxbucket = metap->hashm_lowmask = 1; /* nbuckets - 1 */
279 metap->hashm_highmask = 3; /* (nbuckets << 1) - 1 */
281 MemSet(metap->hashm_spares, 0, sizeof(metap->hashm_spares));
282 MemSet(metap->hashm_mapp, 0, sizeof(metap->hashm_mapp));
284 metap->hashm_spares[1] = 1; /* the first bitmap page is only spare */
285 metap->hashm_ovflpoint = 1;
286 metap->hashm_firstfree = 0;
289 * Initialize the first two buckets
291 for (i = 0; i <= 1; i++)
293 buf = _hash_getbuf(rel, BUCKET_TO_BLKNO(metap, i), HASH_WRITE);
294 pg = BufferGetPage(buf);
295 _hash_pageinit(pg, BufferGetPageSize(buf));
296 pageopaque = (HashPageOpaque) PageGetSpecialPointer(pg);
297 pageopaque->hasho_prevblkno = InvalidBlockNumber;
298 pageopaque->hasho_nextblkno = InvalidBlockNumber;
299 pageopaque->hasho_bucket = i;
300 pageopaque->hasho_flag = LH_BUCKET_PAGE;
301 pageopaque->hasho_filler = HASHO_FILL;
302 _hash_wrtbuf(rel, buf);
306 * Initialize first bitmap page. Can't do this until we create the first
307 * two buckets, else smgr will complain.
309 _hash_initbitmap(rel, metap, 3);
312 _hash_wrtbuf(rel, metabuf);
316 * _hash_pageinit() -- Initialize a new hash index page.
319 _hash_pageinit(Page page, Size size)
321 Assert(PageIsNew(page));
322 PageInit(page, size, sizeof(HashPageOpaqueData));
326 * Attempt to expand the hash table by creating one new bucket.
328 * This will silently do nothing if it cannot get the needed locks.
330 * The caller should hold no locks on the hash index.
332 * The caller must hold a pin, but no lock, on the metapage buffer.
333 * The buffer is returned in the same state.
336 _hash_expandtable(Relation rel, Buffer metabuf)
342 BlockNumber start_oblkno;
343 BlockNumber start_nblkno;
349 * Obtain the page-zero lock to assert the right to begin a split (see
352 * Note: deadlock should be impossible here. Our own backend could only be
353 * holding bucket sharelocks due to stopped indexscans; those will not
354 * block other holders of the page-zero lock, who are only interested in
355 * acquiring bucket sharelocks themselves. Exclusive bucket locks are
356 * only taken here and in hashbulkdelete, and neither of these operations
357 * needs any additional locks to complete. (If, due to some flaw in this
358 * reasoning, we manage to deadlock anyway, it's okay to error out; the
359 * index will be left in a consistent state.)
361 _hash_getlock(rel, 0, HASH_EXCLUSIVE);
363 /* Write-lock the meta page */
364 _hash_chgbufaccess(rel, metabuf, HASH_NOLOCK, HASH_WRITE);
366 _hash_checkpage(rel, metabuf, LH_META_PAGE);
367 metap = (HashMetaPage) BufferGetPage(metabuf);
370 * Check to see if split is still needed; someone else might have already
371 * done one while we waited for the lock.
373 * Make sure this stays in sync with _hash_doinsert()
375 if (metap->hashm_ntuples <=
376 (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1))
380 * Determine which bucket is to be split, and attempt to lock the old
381 * bucket. If we can't get the lock, give up.
383 * The lock protects us against other backends, but not against our own
384 * backend. Must check for active scans separately.
386 * Ideally we would lock the new bucket too before proceeding, but if we
387 * are about to cross a splitpoint then the BUCKET_TO_BLKNO mapping isn't
388 * correct yet. For simplicity we update the metapage first and then
389 * lock. This should be okay because no one else should be trying to lock
390 * the new bucket yet...
392 new_bucket = metap->hashm_maxbucket + 1;
393 old_bucket = (new_bucket & metap->hashm_lowmask);
395 start_oblkno = BUCKET_TO_BLKNO(metap, old_bucket);
397 if (_hash_has_active_scan(rel, old_bucket))
400 if (!_hash_try_getlock(rel, start_oblkno, HASH_EXCLUSIVE))
404 * Okay to proceed with split. Update the metapage bucket mapping info.
406 * Since we are scribbling on the metapage data right in the shared
407 * buffer, any failure in this next little bit leaves us with a big
408 * problem: the metapage is effectively corrupt but could get written back
409 * to disk. We don't really expect any failure, but just to be sure,
410 * establish a critical section.
412 START_CRIT_SECTION();
414 metap->hashm_maxbucket = new_bucket;
416 if (new_bucket > metap->hashm_highmask)
418 /* Starting a new doubling */
419 metap->hashm_lowmask = metap->hashm_highmask;
420 metap->hashm_highmask = new_bucket | metap->hashm_lowmask;
424 * If the split point is increasing (hashm_maxbucket's log base 2
425 * increases), we need to adjust the hashm_spares[] array and
426 * hashm_ovflpoint so that future overflow pages will be created beyond
427 * this new batch of bucket pages.
429 * XXX should initialize new bucket pages to prevent out-of-order page
430 * creation? Don't wanna do it right here though.
432 spare_ndx = _hash_log2(metap->hashm_maxbucket + 1);
433 if (spare_ndx > metap->hashm_ovflpoint)
435 Assert(spare_ndx == metap->hashm_ovflpoint + 1);
436 metap->hashm_spares[spare_ndx] = metap->hashm_spares[metap->hashm_ovflpoint];
437 metap->hashm_ovflpoint = spare_ndx;
440 /* now we can compute the new bucket's primary block number */
441 start_nblkno = BUCKET_TO_BLKNO(metap, new_bucket);
443 Assert(!_hash_has_active_scan(rel, new_bucket));
445 if (!_hash_try_getlock(rel, start_nblkno, HASH_EXCLUSIVE))
446 elog(PANIC, "could not get lock on supposedly new bucket");
448 /* Done mucking with metapage */
452 * Copy bucket mapping info now; this saves re-accessing the meta page
453 * inside _hash_splitbucket's inner loop. Note that once we drop the
454 * split lock, other splits could begin, so these values might be out of
455 * date before _hash_splitbucket finishes. That's okay, since all it
456 * needs is to tell which of these two buckets to map hashkeys into.
458 maxbucket = metap->hashm_maxbucket;
459 highmask = metap->hashm_highmask;
460 lowmask = metap->hashm_lowmask;
462 /* Write out the metapage and drop lock, but keep pin */
463 _hash_chgbufaccess(rel, metabuf, HASH_WRITE, HASH_NOLOCK);
465 /* Release split lock; okay for other splits to occur now */
466 _hash_droplock(rel, 0, HASH_EXCLUSIVE);
468 /* Relocate records to the new bucket */
469 _hash_splitbucket(rel, metabuf, old_bucket, new_bucket,
470 start_oblkno, start_nblkno,
471 maxbucket, highmask, lowmask);
473 /* Release bucket locks, allowing others to access them */
474 _hash_droplock(rel, start_oblkno, HASH_EXCLUSIVE);
475 _hash_droplock(rel, start_nblkno, HASH_EXCLUSIVE);
479 /* Here if decide not to split or fail to acquire old bucket lock */
482 /* We didn't write the metapage, so just drop lock */
483 _hash_chgbufaccess(rel, metabuf, HASH_READ, HASH_NOLOCK);
485 /* Release split lock */
486 _hash_droplock(rel, 0, HASH_EXCLUSIVE);
491 * _hash_splitbucket -- split 'obucket' into 'obucket' and 'nbucket'
493 * We are splitting a bucket that consists of a base bucket page and zero
494 * or more overflow (bucket chain) pages. We must relocate tuples that
495 * belong in the new bucket, and compress out any free space in the old
498 * The caller must hold exclusive locks on both buckets to ensure that
499 * no one else is trying to access them (see README).
501 * The caller must hold a pin, but no lock, on the metapage buffer.
502 * The buffer is returned in the same state. (The metapage is only
503 * touched if it becomes necessary to add or remove overflow pages.)
506 _hash_splitbucket(Relation rel,
510 BlockNumber start_oblkno,
511 BlockNumber start_nblkno,
523 HashPageOpaque oopaque;
524 HashPageOpaque nopaque;
527 OffsetNumber ooffnum;
528 OffsetNumber noffnum;
529 OffsetNumber omaxoffnum;
532 TupleDesc itupdesc = RelationGetDescr(rel);
535 * It should be okay to simultaneously write-lock pages from each bucket,
536 * since no one else can be trying to acquire buffer lock on pages of
539 oblkno = start_oblkno;
540 obuf = _hash_getbuf(rel, oblkno, HASH_WRITE);
541 _hash_checkpage(rel, obuf, LH_BUCKET_PAGE);
542 opage = BufferGetPage(obuf);
543 oopaque = (HashPageOpaque) PageGetSpecialPointer(opage);
545 nblkno = start_nblkno;
546 nbuf = _hash_getbuf(rel, nblkno, HASH_WRITE);
547 npage = BufferGetPage(nbuf);
549 /* initialize the new bucket's primary page */
550 _hash_pageinit(npage, BufferGetPageSize(nbuf));
551 nopaque = (HashPageOpaque) PageGetSpecialPointer(npage);
552 nopaque->hasho_prevblkno = InvalidBlockNumber;
553 nopaque->hasho_nextblkno = InvalidBlockNumber;
554 nopaque->hasho_bucket = nbucket;
555 nopaque->hasho_flag = LH_BUCKET_PAGE;
556 nopaque->hasho_filler = HASHO_FILL;
559 * Partition the tuples in the old bucket between the old bucket and the
560 * new bucket, advancing along the old bucket's overflow bucket chain and
561 * adding overflow pages to the new bucket as needed.
563 ooffnum = FirstOffsetNumber;
564 omaxoffnum = PageGetMaxOffsetNumber(opage);
568 * at each iteration through this loop, each of these variables should
569 * be up-to-date: obuf opage oopaque ooffnum omaxoffnum
572 /* check if we're at the end of the page */
573 if (ooffnum > omaxoffnum)
575 /* at end of page, but check for an(other) overflow page */
576 oblkno = oopaque->hasho_nextblkno;
577 if (!BlockNumberIsValid(oblkno))
581 * we ran out of tuples on this particular page, but we have more
582 * overflow pages; advance to next page.
584 _hash_wrtbuf(rel, obuf);
586 obuf = _hash_getbuf(rel, oblkno, HASH_WRITE);
587 _hash_checkpage(rel, obuf, LH_OVERFLOW_PAGE);
588 opage = BufferGetPage(obuf);
589 oopaque = (HashPageOpaque) PageGetSpecialPointer(opage);
590 ooffnum = FirstOffsetNumber;
591 omaxoffnum = PageGetMaxOffsetNumber(opage);
596 * Re-hash the tuple to determine which bucket it now belongs in.
598 * It is annoying to call the hash function while holding locks, but
599 * releasing and relocking the page for each tuple is unappealing too.
601 itup = (IndexTuple) PageGetItem(opage, PageGetItemId(opage, ooffnum));
602 datum = index_getattr(itup, 1, itupdesc, &null);
605 bucket = _hash_hashkey2bucket(_hash_datum2hashkey(rel, datum),
606 maxbucket, highmask, lowmask);
608 if (bucket == nbucket)
611 * insert the tuple into the new bucket. if it doesn't fit on the
612 * current page in the new bucket, we must allocate a new overflow
613 * page and place the tuple on that page instead.
615 itemsz = IndexTupleDSize(*itup);
616 itemsz = MAXALIGN(itemsz);
618 if (PageGetFreeSpace(npage) < itemsz)
620 /* write out nbuf and drop lock, but keep pin */
621 _hash_chgbufaccess(rel, nbuf, HASH_WRITE, HASH_NOLOCK);
622 /* chain to a new overflow page */
623 nbuf = _hash_addovflpage(rel, metabuf, nbuf);
624 _hash_checkpage(rel, nbuf, LH_OVERFLOW_PAGE);
625 npage = BufferGetPage(nbuf);
626 /* we don't need nopaque within the loop */
629 noffnum = OffsetNumberNext(PageGetMaxOffsetNumber(npage));
630 if (PageAddItem(npage, (Item) itup, itemsz, noffnum, LP_USED)
631 == InvalidOffsetNumber)
632 elog(ERROR, "failed to add index item to \"%s\"",
633 RelationGetRelationName(rel));
636 * now delete the tuple from the old bucket. after this section
637 * of code, 'ooffnum' will actually point to the ItemId to which
638 * we would point if we had advanced it before the deletion
639 * (PageIndexTupleDelete repacks the ItemId array). this also
640 * means that 'omaxoffnum' is exactly one less than it used to be,
641 * so we really can just decrement it instead of calling
642 * PageGetMaxOffsetNumber.
644 PageIndexTupleDelete(opage, ooffnum);
645 omaxoffnum = OffsetNumberPrev(omaxoffnum);
650 * the tuple stays on this page. we didn't move anything, so we
651 * didn't delete anything and therefore we don't have to change
654 Assert(bucket == obucket);
655 ooffnum = OffsetNumberNext(ooffnum);
660 * We're at the end of the old bucket chain, so we're done partitioning
661 * the tuples. Before quitting, call _hash_squeezebucket to ensure the
662 * tuples remaining in the old bucket (including the overflow pages) are
663 * packed as tightly as possible. The new bucket is already tight.
665 _hash_wrtbuf(rel, obuf);
666 _hash_wrtbuf(rel, nbuf);
668 _hash_squeezebucket(rel, obucket, start_oblkno);