PostgreSQL Source Code git master
Loading...
Searching...
No Matches
Macros | Functions
hashutil.c File Reference
#include "postgres.h"
#include "access/hash.h"
#include "access/reloptions.h"
#include "access/relscan.h"
#include "port/pg_bitutils.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
Include dependency graph for hashutil.c:

Go to the source code of this file.

Macros

#define CALC_NEW_BUCKET(old_bucket, lowmask)    old_bucket | (lowmask + 1)
 

Functions

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_spareindex (uint32 num_bucket)
 
uint32 _hash_get_totalbuckets (uint32 splitpoint_phase)
 
void _hash_checkpage (Relation rel, Buffer buf, int flags)
 
bytea * hashoptions (Datum reloptions, bool validate)
 
uint32 _hash_get_indextuple_hashkey (IndexTuple itup)
 
bool _hash_convert_tuple (Relation index, const Datum *user_values, const 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 _hash_kill_items (IndexScanDesc scan)
 

Macro Definition Documentation

◆ CALC_NEW_BUCKET

#define CALC_NEW_BUCKET (   old_bucket,
  lowmask 
)     old_bucket | (lowmask + 1)

Definition at line 24 of file hashutil.c.

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}
73
74/*
75 * _hash_datum2hashkey -- given a Datum, call the index's hash function
76 *
77 * The Datum is assumed to be of the index's column type, so we can use the
78 * "primary" hash function that's tracked for us by the generic index code.
79 */
80uint32
81_hash_datum2hashkey(Relation rel, Datum key)
82{
83 FmgrInfo *procinfo;
84 Oid collation;
85
86 /* XXX assumes index has only one attribute */
87 procinfo = index_getprocinfo(rel, 1, HASHSTANDARD_PROC);
88 collation = rel->rd_indcollation[0];
89
90 return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
91}
92
93/*
94 * _hash_datum2hashkey_type -- given a Datum of a specified type,
95 * hash it in a fashion compatible with this index
96 *
97 * This is much more expensive than _hash_datum2hashkey, so use it only in
98 * cross-type situations.
99 */
100uint32
101_hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype)
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 HASHSTANDARD_PROC);
111 if (!RegProcedureIsValid(hash_proc))
112 elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
113 HASHSTANDARD_PROC, keytype, keytype,
114 RelationGetRelationName(rel));
115 collation = rel->rd_indcollation[0];
116
117 return DatumGetUInt32(OidFunctionCall1Coll(hash_proc, collation, key));
118}
119
120/*
121 * _hash_hashkey2bucket -- determine which bucket the hashkey maps to.
122 */
123Bucket
124_hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
125 uint32 highmask, uint32 lowmask)
126{
127 Bucket bucket;
128
129 bucket = hashkey & highmask;
130 if (bucket > maxbucket)
131 bucket = bucket & lowmask;
132
133 return bucket;
134}
135
136/*
137 * _hash_spareindex -- returns spare index / global splitpoint phase of the
138 * bucket
139 */
140uint32
141_hash_spareindex(uint32 num_bucket)
142{
143 uint32 splitpoint_group;
144 uint32 splitpoint_phases;
145
146 splitpoint_group = pg_ceil_log2_32(num_bucket);
147
148 if (splitpoint_group < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
149 return splitpoint_group;
150
151 /* account for single-phase groups */
152 splitpoint_phases = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
153
154 /* account for multi-phase groups before splitpoint_group */
155 splitpoint_phases +=
156 ((splitpoint_group - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) <<
157 HASH_SPLITPOINT_PHASE_BITS);
158
159 /* account for phases within current group */
160 splitpoint_phases +=
161 (((num_bucket - 1) >>
162 (splitpoint_group - (HASH_SPLITPOINT_PHASE_BITS + 1))) &
163 HASH_SPLITPOINT_PHASE_MASK); /* to 0-based value. */
164
165 return splitpoint_phases;
166}
167
168/*
169 * _hash_get_totalbuckets -- returns total number of buckets allocated till
170 * the given splitpoint phase.
171 */
172uint32
173_hash_get_totalbuckets(uint32 splitpoint_phase)
174{
175 uint32 splitpoint_group;
176 uint32 total_buckets;
177 uint32 phases_within_splitpoint_group;
178
179 if (splitpoint_phase < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
180 return (1 << splitpoint_phase);
181
182 /* get splitpoint's group */
183 splitpoint_group = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
184 splitpoint_group +=
185 ((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) >>
186 HASH_SPLITPOINT_PHASE_BITS);
187
188 /* account for buckets before splitpoint_group */
189 total_buckets = (1 << (splitpoint_group - 1));
190
191 /* account for buckets within splitpoint_group */
192 phases_within_splitpoint_group =
193 (((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) &
194 HASH_SPLITPOINT_PHASE_MASK) + 1); /* from 0-based to 1-based */
195 total_buckets +=
196 (((1 << (splitpoint_group - 1)) >> HASH_SPLITPOINT_PHASE_BITS) *
197 phases_within_splitpoint_group);
198
199 return total_buckets;
200}
201
202/*
203 * _hash_checkpage -- sanity checks on the format of all hash pages
204 *
205 * If flags is not zero, it is a bitwise OR of the acceptable page types
206 * (values of hasho_flag & LH_PAGE_TYPE).
207 */
208void
209_hash_checkpage(Relation rel, Buffer buf, int flags)
210{
211 Page page = BufferGetPage(buf);
212
213 /*
214 * ReadBuffer verifies that every newly-read page passes
215 * PageHeaderIsValid, which means it either contains a reasonably sane
216 * page header or is all-zero. We have to defend against the all-zero
217 * case, however.
218 */
219 if (PageIsNew(page))
220 ereport(ERROR,
221 (errcode(ERRCODE_INDEX_CORRUPTED),
222 errmsg("index \"%s\" contains unexpected zero page at block %u",
223 RelationGetRelationName(rel),
224 BufferGetBlockNumber(buf)),
225 errhint("Please REINDEX it.")));
226
227 /*
228 * Additionally check that the special area looks sane.
229 */
230 if (PageGetSpecialSize(page) != MAXALIGN(sizeof(HashPageOpaqueData)))
231 ereport(ERROR,
232 (errcode(ERRCODE_INDEX_CORRUPTED),
233 errmsg("index \"%s\" contains corrupted page at block %u",
234 RelationGetRelationName(rel),
235 BufferGetBlockNumber(buf)),
236 errhint("Please REINDEX it.")));
237
238 if (flags)
239 {
240 HashPageOpaque opaque = HashPageGetOpaque(page);
241
242 if ((opaque->hasho_flag & flags) == 0)
243 ereport(ERROR,
244 (errcode(ERRCODE_INDEX_CORRUPTED),
245 errmsg("index \"%s\" contains corrupted page at block %u",
246 RelationGetRelationName(rel),
247 BufferGetBlockNumber(buf)),
248 errhint("Please REINDEX it.")));
249 }
250
251 /*
252 * When checking the metapage, also verify magic number and version.
253 */
254 if (flags == LH_META_PAGE)
255 {
256 HashMetaPage metap = HashPageGetMeta(page);
257
258 if (metap->hashm_magic != HASH_MAGIC)
259 ereport(ERROR,
260 (errcode(ERRCODE_INDEX_CORRUPTED),
261 errmsg("index \"%s\" is not a hash index",
262 RelationGetRelationName(rel))));
263
264 if (metap->hashm_version != HASH_VERSION)
265 ereport(ERROR,
266 (errcode(ERRCODE_INDEX_CORRUPTED),
267 errmsg("index \"%s\" has wrong hash version",
268 RelationGetRelationName(rel)),
269 errhint("Please REINDEX it.")));
270 }
271}
272
273bytea *
274hashoptions(Datum reloptions, bool validate)
275{
276 static const relopt_parse_elt tab[] = {
277 {"fillfactor", RELOPT_TYPE_INT, offsetof(HashOptions, fillfactor)},
278 };
279
280 return (bytea *) build_reloptions(reloptions, validate,
281 RELOPT_KIND_HASH,
282 sizeof(HashOptions),
283 tab, lengthof(tab));
284}
285
286/*
287 * _hash_get_indextuple_hashkey - get the hash index tuple's hash key value
288 */
289uint32
290_hash_get_indextuple_hashkey(IndexTuple itup)
291{
292 char *attp;
293
294 /*
295 * We assume the hash key is the first attribute and can't be null, so
296 * this can be done crudely but very very cheaply ...
297 */
298 attp = (char *) itup + IndexInfoFindDataOffset(itup->t_info);
299 return *((uint32 *) attp);
300}
301
302/*
303 * _hash_convert_tuple - convert raw index data to hash key
304 *
305 * Inputs: values and isnull arrays for the user data column(s)
306 * Outputs: values and isnull arrays for the index tuple, suitable for
307 * passing to index_form_tuple().
308 *
309 * Returns true if successful, false if not (because there are null values).
310 * On a false result, the given data need not be indexed.
311 *
312 * Note: callers know that the index-column arrays are always of length 1.
313 * In principle, there could be more than one input column, though we do not
314 * currently support that.
315 */
316bool
317_hash_convert_tuple(Relation index,
318 const Datum *user_values, const bool *user_isnull,
319 Datum *index_values, bool *index_isnull)
320{
321 uint32 hashkey;
322
323 /*
324 * We do not insert null values into hash indexes. This is okay because
325 * the only supported search operator is '=', and we assume it is strict.
326 */
327 if (user_isnull[0])
328 return false;
329
330 hashkey = _hash_datum2hashkey(index, user_values[0]);
331 index_values[0] = UInt32GetDatum(hashkey);
332 index_isnull[0] = false;
333 return true;
334}
335
336/*
337 * _hash_binsearch - Return the offset number in the page where the
338 * specified hash value should be sought or inserted.
339 *
340 * We use binary search, relying on the assumption that the existing entries
341 * are ordered by hash key.
342 *
343 * Returns the offset of the first index entry having hashkey >= hash_value,
344 * or the page's max offset plus one if hash_value is greater than all
345 * existing hash keys in the page. This is the appropriate place to start
346 * a search, or to insert a new item.
347 */
348OffsetNumber
349_hash_binsearch(Page page, uint32 hash_value)
350{
351 OffsetNumber upper;
352 OffsetNumber lower;
353
354 /* Loop invariant: lower <= desired place <= upper */
355 upper = PageGetMaxOffsetNumber(page) + 1;
356 lower = FirstOffsetNumber;
357
358 while (upper > lower)
359 {
360 OffsetNumber off;
361 IndexTuple itup;
362 uint32 hashkey;
363
364 off = (upper + lower) / 2;
365 Assert(OffsetNumberIsValid(off));
366
367 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
368 hashkey = _hash_get_indextuple_hashkey(itup);
369 if (hashkey < hash_value)
370 lower = off + 1;
371 else
372 upper = off;
373 }
374
375 return lower;
376}
377
378/*
379 * _hash_binsearch_last
380 *
381 * Same as above, except that if there are multiple matching items in the
382 * page, we return the offset of the last one instead of the first one,
383 * and the possible range of outputs is 0..maxoffset not 1..maxoffset+1.
384 * This is handy for starting a new page in a backwards scan.
385 */
386OffsetNumber
387_hash_binsearch_last(Page page, uint32 hash_value)
388{
389 OffsetNumber upper;
390 OffsetNumber lower;
391
392 /* Loop invariant: lower <= desired place <= upper */
393 upper = PageGetMaxOffsetNumber(page);
394 lower = FirstOffsetNumber - 1;
395
396 while (upper > lower)
397 {
398 IndexTuple itup;
399 OffsetNumber off;
400 uint32 hashkey;
401
402 off = (upper + lower + 1) / 2;
403 Assert(OffsetNumberIsValid(off));
404
405 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
406 hashkey = _hash_get_indextuple_hashkey(itup);
407 if (hashkey > hash_value)
408 upper = off - 1;
409 else
410 lower = off;
411 }
412
413 return lower;
414}
415
416/*
417 * _hash_get_oldblock_from_newbucket() -- get the block number of a bucket
418 * from which current (new) bucket is being split.
419 */
420BlockNumber
421_hash_get_oldblock_from_newbucket(Relation rel, Bucket new_bucket)
422{
423 Bucket old_bucket;
424 uint32 mask;
425 Buffer metabuf;
426 HashMetaPage metap;
427 BlockNumber blkno;
428
429 /*
430 * To get the old bucket from the current bucket, we need a mask to modulo
431 * into lower half of table. This mask is stored in meta page as
432 * hashm_lowmask, but here we can't rely on the same, because we need a
433 * value of lowmask that was prevalent at the time when bucket split was
434 * started. Masking the most significant bit of new bucket would give us
435 * old bucket.
436 */
437 mask = (((uint32) 1) << pg_leftmost_one_pos32(new_bucket)) - 1;
438 old_bucket = new_bucket & mask;
439
440 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
441 metap = HashPageGetMeta(BufferGetPage(metabuf));
442
443 blkno = BUCKET_TO_BLKNO(metap, old_bucket);
444
445 _hash_relbuf(rel, metabuf);
446
447 return blkno;
448}
449
450/*
451 * _hash_get_newblock_from_oldbucket() -- get the block number of a bucket
452 * that will be generated after split from old bucket.
453 *
454 * This is used to find the new bucket from old bucket based on current table
455 * half. It is mainly required to finish the incomplete splits where we are
456 * sure that not more than one bucket could have split in progress from old
457 * bucket.
458 */
459BlockNumber
460_hash_get_newblock_from_oldbucket(Relation rel, Bucket old_bucket)
461{
462 Bucket new_bucket;
463 Buffer metabuf;
464 HashMetaPage metap;
465 BlockNumber blkno;
466
467 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
468 metap = HashPageGetMeta(BufferGetPage(metabuf));
469
470 new_bucket = _hash_get_newbucket_from_oldbucket(rel, old_bucket,
471 metap->hashm_lowmask,
472 metap->hashm_maxbucket);
473 blkno = BUCKET_TO_BLKNO(metap, new_bucket);
474
475 _hash_relbuf(rel, metabuf);
476
477 return blkno;
478}
479
480/*
481 * _hash_get_newbucket_from_oldbucket() -- get the new bucket that will be
482 * generated after split from current (old) bucket.
483 *
484 * This is used to find the new bucket from old bucket. New bucket can be
485 * obtained by OR'ing old bucket with most significant bit of current table
486 * half (lowmask passed in this function can be used to identify msb of
487 * current table half). There could be multiple buckets that could have
488 * been split from current bucket. We need the first such bucket that exists.
489 * Caller must ensure that no more than one split has happened from old
490 * bucket.
491 */
492Bucket
493_hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket,
494 uint32 lowmask, uint32 maxbucket)
495{
496 Bucket new_bucket;
497
498 new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
499 if (new_bucket > maxbucket)
500 {
501 lowmask = lowmask >> 1;
502 new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
503 }
504
505 return new_bucket;
506}
507
508/*
509 * _hash_kill_items - set LP_DEAD state for items an indexscan caller has
510 * told us were killed.
511 *
512 * scan->opaque, referenced locally through so, contains information about the
513 * current page and killed tuples thereon (generally, this should only be
514 * called if so->numKilled > 0).
515 *
516 * The caller does not have a lock on the page and may or may not have the
517 * page pinned in a buffer. Note that read-lock is sufficient for setting
518 * LP_DEAD status (which is only a hint).
519 *
520 * The caller must have pin on bucket buffer, but may or may not have pin
521 * on overflow buffer, as indicated by HashScanPosIsPinned(so->currPos).
522 *
523 * We match items by heap TID before assuming they are the right ones to
524 * delete.
525 *
526 * There are never any scans active in a bucket at the time VACUUM begins,
527 * because VACUUM takes a cleanup lock on the primary bucket page and scans
528 * hold a pin. A scan can begin after VACUUM leaves the primary bucket page
529 * but before it finishes the entire bucket, but it can never pass VACUUM,
530 * because VACUUM always locks the next page before releasing the lock on
531 * the previous one. Therefore, we don't have to worry about accidentally
532 * killing a TID that has been reused for an unrelated tuple.
533 */
534void
535_hash_kill_items(IndexScanDesc scan)
536{
537 HashScanOpaque so = (HashScanOpaque) scan->opaque;
538 Relation rel = scan->indexRelation;
539 BlockNumber blkno;
540 Buffer buf;
541 Page page;
542 HashPageOpaque opaque;
543 OffsetNumber offnum,
544 maxoff;
545 int numKilled = so->numKilled;
546 int i;
547 bool killedsomething = false;
548 bool havePin = false;
549
550 Assert(so->numKilled > 0);
551 Assert(so->killedItems != NULL);
552 Assert(HashScanPosIsValid(so->currPos));
553
554 /*
555 * Always reset the scan state, so we don't look for same items on other
556 * pages.
557 */
558 so->numKilled = 0;
559
560 blkno = so->currPos.currPage;
561 if (HashScanPosIsPinned(so->currPos))
562 {
563 /*
564 * We already have pin on this buffer, so, all we need to do is
565 * acquire lock on it.
566 */
567 havePin = true;
568 buf = so->currPos.buf;
569 LockBuffer(buf, BUFFER_LOCK_SHARE);
570 }
571 else
572 buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
573
574 page = BufferGetPage(buf);
575 opaque = HashPageGetOpaque(page);
576 maxoff = PageGetMaxOffsetNumber(page);
577
578 for (i = 0; i < numKilled; i++)
579 {
580 int itemIndex = so->killedItems[i];
581 HashScanPosItem *currItem = &so->currPos.items[itemIndex];
582
583 offnum = currItem->indexOffset;
584
585 Assert(itemIndex >= so->currPos.firstItem &&
586 itemIndex <= so->currPos.lastItem);
587
588 while (offnum <= maxoff)
589 {
590 ItemId iid = PageGetItemId(page, offnum);
591 IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
592
593 if (ItemPointerEquals(&ituple->t_tid, &currItem->heapTid))
594 {
595 /* found the item */
596 ItemIdMarkDead(iid);
597 killedsomething = true;
598 break; /* out of inner search loop */
599 }
600 offnum = OffsetNumberNext(offnum);
601 }
602 }
603
604 /*
605 * Since this can be redone later if needed, mark as dirty hint. Whenever
606 * we mark anything LP_DEAD, we also set the page's
607 * LH_PAGE_HAS_DEAD_TUPLES flag, which is likewise just a hint.
608 */
609 if (killedsomething)
610 {
611 opaque->hasho_flag |= LH_PAGE_HAS_DEAD_TUPLES;
612 MarkBufferDirtyHint(buf, true);
613 }
614
615 if (so->hashso_bucket_buf == so->currPos.buf ||
616 havePin)
617 LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
618 else
619 _hash_relbuf(rel, buf);
620}
validate
static bool validate(Port *port, const char *auth)
Definition auth-oauth.c:638
BlockNumber
uint32 BlockNumber
Definition block.h:31
Buffer
int Buffer
Definition buf.h:23
BufferGetBlockNumber
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition bufmgr.c:4356
MarkBufferDirtyHint
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition bufmgr.c:5565
BufferGetPage
static Page BufferGetPage(Buffer buffer)
Definition bufmgr.h:466
BUFFER_LOCK_SHARE
@ BUFFER_LOCK_SHARE
Definition bufmgr.h:210
BUFFER_LOCK_UNLOCK
@ BUFFER_LOCK_UNLOCK
Definition bufmgr.h:205
LockBuffer
static void LockBuffer(Buffer buffer, BufferLockMode mode)
Definition bufmgr.h:328
PageGetSpecialSize
static uint16 PageGetSpecialSize(const PageData *page)
Definition bufpage.h:316
PageIsNew
static bool PageIsNew(const PageData *page)
Definition bufpage.h:233
PageGetItemId
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition bufpage.h:243
PageGetItem
static void * PageGetItem(PageData *page, const ItemIdData *itemId)
Definition bufpage.h:353
Page
PageData * Page
Definition bufpage.h:81
PageGetMaxOffsetNumber
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition bufpage.h:371
RegProcedureIsValid
#define RegProcedureIsValid(p)
Definition c.h:792
MAXALIGN
#define MAXALIGN(LEN)
Definition c.h:826
Assert
#define Assert(condition)
Definition c.h:873
RegProcedure
regproc RegProcedure
Definition c.h:664
uint32
uint32_t uint32
Definition c.h:546
lengthof
#define lengthof(array)
Definition c.h:803
errhint
int errhint(const char *fmt,...)
Definition elog.c:1330
errcode
int errcode(int sqlerrcode)
Definition elog.c:863
errmsg
int errmsg(const char *fmt,...)
Definition elog.c:1080
ERROR
#define ERROR
Definition elog.h:39
elog
#define elog(elevel,...)
Definition elog.h:226
ereport
#define ereport(elevel,...)
Definition elog.h:150
FunctionCall2Coll
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition fmgr.c:1150
OidFunctionCall1Coll
Datum OidFunctionCall1Coll(Oid functionId, Oid collation, Datum arg1)
Definition fmgr.c:1412
FunctionCall1Coll
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition fmgr.c:1130
HashPageGetOpaque
#define HashPageGetOpaque(page)
Definition hash.h:88
HASHSTANDARD_PROC
#define HASHSTANDARD_PROC
Definition hash.h:355
HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE
#define HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE
Definition hash.h:235
HASH_VERSION
#define HASH_VERSION
Definition hash.h:201
HashScanPosIsPinned
#define HashScanPosIsPinned(scanpos)
Definition hash.h:130
LH_META_PAGE
#define LH_META_PAGE
Definition hash.h:57
HashPageGetMeta
#define HashPageGetMeta(page)
Definition hash.h:323
HASH_READ
#define HASH_READ
Definition hash.h:339
BUCKET_TO_BLKNO
#define BUCKET_TO_BLKNO(metap, B)
Definition hash.h:39
HASH_SPLITPOINT_PHASE_MASK
#define HASH_SPLITPOINT_PHASE_MASK
Definition hash.h:234
HASH_METAPAGE
#define HASH_METAPAGE
Definition hash.h:198
Bucket
uint32 Bucket
Definition hash.h:35
HashScanOpaque
HashScanOpaqueData * HashScanOpaque
Definition hash.h:192
HashScanPosIsValid
#define HashScanPosIsValid(scanpos)
Definition hash.h:137
HASH_SPLITPOINT_PHASE_BITS
#define HASH_SPLITPOINT_PHASE_BITS
Definition hash.h:232
LH_PAGE_HAS_DEAD_TUPLES
#define LH_PAGE_HAS_DEAD_TUPLES
Definition hash.h:61
HASH_MAGIC
#define HASH_MAGIC
Definition hash.h:200
LH_OVERFLOW_PAGE
#define LH_OVERFLOW_PAGE
Definition hash.h:54
_hash_relbuf
void _hash_relbuf(Relation rel, Buffer buf)
Definition hashpage.c:266
_hash_getbuf
Buffer _hash_getbuf(Relation rel, BlockNumber blkno, int access, int flags)
Definition hashpage.c:70
_hash_spareindex
uint32 _hash_spareindex(uint32 num_bucket)
Definition hashutil.c:142
_hash_get_newblock_from_oldbucket
BlockNumber _hash_get_newblock_from_oldbucket(Relation rel, Bucket old_bucket)
Definition hashutil.c:461
_hash_get_totalbuckets
uint32 _hash_get_totalbuckets(uint32 splitpoint_phase)
Definition hashutil.c:174
_hash_get_indextuple_hashkey
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition hashutil.c:291
_hash_binsearch
OffsetNumber _hash_binsearch(Page page, uint32 hash_value)
Definition hashutil.c:350
_hash_datum2hashkey
uint32 _hash_datum2hashkey(Relation rel, Datum key)
Definition hashutil.c:82
_hash_hashkey2bucket
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition hashutil.c:125
_hash_binsearch_last
OffsetNumber _hash_binsearch_last(Page page, uint32 hash_value)
Definition hashutil.c:388
_hash_checkpage
void _hash_checkpage(Relation rel, Buffer buf, int flags)
Definition hashutil.c:210
_hash_get_newbucket_from_oldbucket
Bucket _hash_get_newbucket_from_oldbucket(Relation rel, Bucket old_bucket, uint32 lowmask, uint32 maxbucket)
Definition hashutil.c:494
hashoptions
bytea * hashoptions(Datum reloptions, bool validate)
Definition hashutil.c:275
_hash_get_oldblock_from_newbucket
BlockNumber _hash_get_oldblock_from_newbucket(Relation rel, Bucket new_bucket)
Definition hashutil.c:422
_hash_datum2hashkey_type
uint32 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype)
Definition hashutil.c:102
_hash_convert_tuple
bool _hash_convert_tuple(Relation index, const Datum *user_values, const bool *user_isnull, Datum *index_values, bool *index_isnull)
Definition hashutil.c:318
_hash_kill_items
void _hash_kill_items(IndexScanDesc scan)
Definition hashutil.c:536
CALC_NEW_BUCKET
#define CALC_NEW_BUCKET(old_bucket, lowmask)
Definition hashutil.c:24
index_getprocinfo
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition indexam.c:917
i
int i
Definition isn.c:77
ItemIdMarkDead
#define ItemIdMarkDead(itemId)
Definition itemid.h:179
ItemPointerEquals
bool ItemPointerEquals(const ItemPointerData *pointer1, const ItemPointerData *pointer2)
Definition itemptr.c:35
IndexTuple
IndexTupleData * IndexTuple
Definition itup.h:53
index_getattr
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition itup.h:131
IndexInfoFindDataOffset
static Size IndexInfoFindDataOffset(unsigned short t_info)
Definition itup.h:112
get_opfamily_proc
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
Definition lsyscache.c:872
OffsetNumberIsValid
#define OffsetNumberIsValid(offsetNumber)
Definition off.h:39
OffsetNumberNext
#define OffsetNumberNext(offsetNumber)
Definition off.h:52
OffsetNumber
uint16 OffsetNumber
Definition off.h:24
FirstOffsetNumber
#define FirstOffsetNumber
Definition off.h:27
lower
Datum lower(PG_FUNCTION_ARGS)
Definition oracle_compat.c:49
upper
Datum upper(PG_FUNCTION_ARGS)
Definition oracle_compat.c:80
pg_leftmost_one_pos32
static int pg_leftmost_one_pos32(uint32 word)
Definition pg_bitutils.h:41
pg_ceil_log2_32
static uint32 pg_ceil_log2_32(uint32 num)
Definition pg_bitutils.h:258
buf
static char buf[DEFAULT_XLOG_SEG_SIZE]
Definition pg_test_fsync.c:71
fillfactor
static int fillfactor
Definition pgbench.c:188
DatumGetUInt32
static uint32 DatumGetUInt32(Datum X)
Definition postgres.h:232
DatumGetBool
static bool DatumGetBool(Datum X)
Definition postgres.h:100
Datum
uint64_t Datum
Definition postgres.h:70
UInt32GetDatum
static Datum UInt32GetDatum(uint32 X)
Definition postgres.h:242
Oid
unsigned int Oid
Definition postgres_ext.h:32
test
static void test(void)
Definition preproc-autoprep.c:26
fb
static int fb(int x)
Definition preproc-init.c:92
RelationGetDescr
#define RelationGetDescr(relation)
Definition rel.h:540
RelationGetRelationName
#define RelationGetRelationName(relation)
Definition rel.h:548
build_reloptions
void * build_reloptions(Datum reloptions, bool validate, relopt_kind kind, Size relopt_struct_size, const relopt_parse_elt *relopt_elems, int num_relopt_elems)
Definition reloptions.c:2041
RELOPT_KIND_HASH
@ RELOPT_KIND_HASH
Definition reloptions.h:46
RELOPT_TYPE_INT
@ RELOPT_TYPE_INT
Definition reloptions.h:33
SK_ISNULL
#define SK_ISNULL
Definition skey.h:115
HashPageOpaqueData::hasho_flag
uint16 hasho_flag
Definition hash.h:82
HashScanPosItem::indexOffset
OffsetNumber indexOffset
Definition hash.h:106
IndexTupleData::t_info
unsigned short t_info
Definition itup.h:49
RelationData::rd_opfamily
Oid * rd_opfamily
Definition rel.h:207
RelationData::rd_indcollation
Oid * rd_indcollation
Definition rel.h:217
index
Definition type.h:96
relopt_parse_elt
Definition reloptions.h:159
varlena
Definition c.h:706

Function Documentation

◆ _hash_binsearch()

OffsetNumber _hash_binsearch ( Page  page,
uint32  hash_value 
)

Definition at line 350 of file hashutil.c.

351{
352 OffsetNumber upper;
353 OffsetNumber lower;
354
355 /* Loop invariant: lower <= desired place <= upper */
356 upper = PageGetMaxOffsetNumber(page) + 1;
357 lower = FirstOffsetNumber;
358
359 while (upper > lower)
360 {
361 OffsetNumber off;
362 IndexTuple itup;
363 uint32 hashkey;
364
365 off = (upper + lower) / 2;
366 Assert(OffsetNumberIsValid(off));
367
368 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
369 hashkey = _hash_get_indextuple_hashkey(itup);
370 if (hashkey < hash_value)
371 lower = off + 1;
372 else
373 upper = off;
374 }
375
376 return lower;
377}

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

Referenced by _hash_pgaddmultitup(), _hash_pgaddtup(), and _hash_readpage().

◆ _hash_binsearch_last()

OffsetNumber _hash_binsearch_last ( Page  page,
uint32  hash_value 
)

Definition at line 388 of file hashutil.c.

389{
390 OffsetNumber upper;
391 OffsetNumber lower;
392
393 /* Loop invariant: lower <= desired place <= upper */
394 upper = PageGetMaxOffsetNumber(page);
395 lower = FirstOffsetNumber - 1;
396
397 while (upper > lower)
398 {
399 IndexTuple itup;
400 OffsetNumber off;
401 uint32 hashkey;
402
403 off = (upper + lower + 1) / 2;
404 Assert(OffsetNumberIsValid(off));
405
406 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
407 hashkey = _hash_get_indextuple_hashkey(itup);
408 if (hashkey > hash_value)
409 upper = off - 1;
410 else
411 lower = off;
412 }
413
414 return lower;
415}

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

Referenced by _hash_readpage().

◆ _hash_checkpage()

void _hash_checkpage ( Relation  rel,
Buffer  buf,
int  flags 
)

Definition at line 210 of file hashutil.c.

211{
212 Page page = BufferGetPage(buf);
213
214 /*
215 * ReadBuffer verifies that every newly-read page passes
216 * PageHeaderIsValid, which means it either contains a reasonably sane
217 * page header or is all-zero. We have to defend against the all-zero
218 * case, however.
219 */
220 if (PageIsNew(page))
221 ereport(ERROR,
222 (errcode(ERRCODE_INDEX_CORRUPTED),
223 errmsg("index \"%s\" contains unexpected zero page at block %u",
224 RelationGetRelationName(rel),
225 BufferGetBlockNumber(buf)),
226 errhint("Please REINDEX it.")));
227
228 /*
229 * Additionally check that the special area looks sane.
230 */
231 if (PageGetSpecialSize(page) != MAXALIGN(sizeof(HashPageOpaqueData)))
232 ereport(ERROR,
233 (errcode(ERRCODE_INDEX_CORRUPTED),
234 errmsg("index \"%s\" contains corrupted page at block %u",
235 RelationGetRelationName(rel),
236 BufferGetBlockNumber(buf)),
237 errhint("Please REINDEX it.")));
238
239 if (flags)
240 {
241 HashPageOpaque opaque = HashPageGetOpaque(page);
242
243 if ((opaque->hasho_flag & flags) == 0)
244 ereport(ERROR,
245 (errcode(ERRCODE_INDEX_CORRUPTED),
246 errmsg("index \"%s\" contains corrupted page at block %u",
247 RelationGetRelationName(rel),
248 BufferGetBlockNumber(buf)),
249 errhint("Please REINDEX it.")));
250 }
251
252 /*
253 * When checking the metapage, also verify magic number and version.
254 */
255 if (flags == LH_META_PAGE)
256 {
257 HashMetaPage metap = HashPageGetMeta(page);
258
259 if (metap->hashm_magic != HASH_MAGIC)
260 ereport(ERROR,
261 (errcode(ERRCODE_INDEX_CORRUPTED),
262 errmsg("index \"%s\" is not a hash index",
263 RelationGetRelationName(rel))));
264
265 if (metap->hashm_version != HASH_VERSION)
266 ereport(ERROR,
267 (errcode(ERRCODE_INDEX_CORRUPTED),
268 errmsg("index \"%s\" has wrong hash version",
269 RelationGetRelationName(rel)),
270 errhint("Please REINDEX it.")));
271 }
272}

References buf, BufferGetBlockNumber(), BufferGetPage(), ereport, errcode(), errhint(), errmsg(), ERROR, fb(), HASH_MAGIC, HASH_VERSION, HashPageOpaqueData::hasho_flag, HashPageGetMeta, HashPageGetOpaque, LH_META_PAGE, MAXALIGN, PageGetSpecialSize(), PageIsNew(), and RelationGetRelationName.

Referenced by _hash_addovflpage(), _hash_expandtable(), _hash_freeovflpage(), _hash_getbuf(), _hash_getbuf_with_condlock_cleanup(), _hash_getbuf_with_strategy(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_readpage(), and hashbulkdelete().

◆ _hash_checkqual()

bool _hash_checkqual ( IndexScanDesc  scan,
IndexTuple  itup 
)

Definition at line 31 of file hashutil.c.

32{
33 /*
34 * Currently, we can't check any of the scan conditions since we do not
35 * have the original index entry value to supply to the sk_func. Always
36 * return true; we expect that hashgettuple already set the recheck flag
37 * to make the main indexscan code do it.
38 */
39#ifdef NOT_USED
40 TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
41 ScanKey key = scan->keyData;
42 int scanKeySize = scan->numberOfKeys;
43
44 while (scanKeySize > 0)
45 {
46 Datum datum;
47 bool isNull;
48 Datum test;
49
50 datum = index_getattr(itup,
51 key->sk_attno,
52 tupdesc,
53 &isNull);
54
55 /* assume sk_func is strict */
56 if (isNull)
57 return false;
58 if (key->sk_flags & SK_ISNULL)
59 return false;
60
61 test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
62 datum, key->sk_argument);
63
64 if (!DatumGetBool(test))
65 return false;
66
67 key++;
68 scanKeySize--;
69 }
70#endif
71
72 return true;
73}
IndexScanDescData::keyData
struct ScanKeyData * keyData
Definition relscan.h:142
IndexScanDescData::indexRelation
Relation indexRelation
Definition relscan.h:138

References DatumGetBool(), fb(), FunctionCall2Coll(), index_getattr(), IndexScanDescData::indexRelation, IndexScanDescData::keyData, IndexScanDescData::numberOfKeys, RelationGetDescr, SK_ISNULL, and test().

Referenced by _hash_load_qualified_items().

◆ _hash_convert_tuple()

bool _hash_convert_tuple ( Relation  index,
const Datum *  user_values,
const bool *  user_isnull,
Datum *  index_values,
bool *  index_isnull 
)

Definition at line 318 of file hashutil.c.

321{
322 uint32 hashkey;
323
324 /*
325 * We do not insert null values into hash indexes. This is okay because
326 * the only supported search operator is '=', and we assume it is strict.
327 */
328 if (user_isnull[0])
329 return false;
330
331 hashkey = _hash_datum2hashkey(index, user_values[0]);
332 index_values[0] = UInt32GetDatum(hashkey);
333 index_isnull[0] = false;
334 return true;
335}

References _hash_datum2hashkey(), fb(), and UInt32GetDatum().

Referenced by hashbuildCallback(), and hashinsert().

◆ _hash_datum2hashkey()

uint32 _hash_datum2hashkey ( Relation  rel,
Datum  key 
)

Definition at line 82 of file hashutil.c.

83{
84 FmgrInfo *procinfo;
85 Oid collation;
86
87 /* XXX assumes index has only one attribute */
88 procinfo = index_getprocinfo(rel, 1, HASHSTANDARD_PROC);
89 collation = rel->rd_indcollation[0];
90
91 return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
92}

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

Referenced by _hash_convert_tuple(), and _hash_first().

◆ _hash_datum2hashkey_type()

uint32 _hash_datum2hashkey_type ( Relation  rel,
Datum  key,
Oid  keytype 
)

Definition at line 102 of file hashutil.c.

103{
104 RegProcedure hash_proc;
105 Oid collation;
106
107 /* XXX assumes index has only one attribute */
108 hash_proc = get_opfamily_proc(rel->rd_opfamily[0],
109 keytype,
110 keytype,
111 HASHSTANDARD_PROC);
112 if (!RegProcedureIsValid(hash_proc))
113 elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
114 HASHSTANDARD_PROC, keytype, keytype,
115 RelationGetRelationName(rel));
116 collation = rel->rd_indcollation[0];
117
118 return DatumGetUInt32(OidFunctionCall1Coll(hash_proc, collation, key));
119}

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

Referenced by _hash_first().

◆ _hash_get_indextuple_hashkey()

uint32 _hash_get_indextuple_hashkey ( IndexTuple  itup)

Definition at line 291 of file hashutil.c.

292{
293 char *attp;
294
295 /*
296 * We assume the hash key is the first attribute and can't be null, so
297 * this can be done crudely but very very cheaply ...
298 */
299 attp = (char *) itup + IndexInfoFindDataOffset(itup->t_info);
300 return *((uint32 *) attp);
301}

References fb(), IndexInfoFindDataOffset(), and IndexTupleData::t_info.

Referenced by _h_indexbuild(), _hash_binsearch(), _hash_binsearch_last(), _hash_doinsert(), _hash_load_qualified_items(), _hash_pgaddmultitup(), _hash_pgaddtup(), _hash_splitbucket(), hash_page_items(), and hashbucketcleanup().

◆ _hash_get_newblock_from_oldbucket()

BlockNumber _hash_get_newblock_from_oldbucket ( Relation  rel,
Bucket  old_bucket 
)

Definition at line 461 of file hashutil.c.

462{
463 Bucket new_bucket;
464 Buffer metabuf;
465 HashMetaPage metap;
466 BlockNumber blkno;
467
468 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
469 metap = HashPageGetMeta(BufferGetPage(metabuf));
470
471 new_bucket = _hash_get_newbucket_from_oldbucket(rel, old_bucket,
472 metap->hashm_lowmask,
473 metap->hashm_maxbucket);
474 blkno = BUCKET_TO_BLKNO(metap, new_bucket);
475
476 _hash_relbuf(rel, metabuf);
477
478 return blkno;
479}

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

Referenced by _hash_finish_split().

◆ _hash_get_newbucket_from_oldbucket()

Bucket _hash_get_newbucket_from_oldbucket ( Relation  rel,
Bucket  old_bucket,
uint32  lowmask,
uint32  maxbucket 
)

Definition at line 494 of file hashutil.c.

496{
497 Bucket new_bucket;
498
499 new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
500 if (new_bucket > maxbucket)
501 {
502 lowmask = lowmask >> 1;
503 new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
504 }
505
506 return new_bucket;
507}

References CALC_NEW_BUCKET, and fb().

Referenced by _hash_get_newblock_from_oldbucket(), and hashbucketcleanup().

◆ _hash_get_oldblock_from_newbucket()

BlockNumber _hash_get_oldblock_from_newbucket ( Relation  rel,
Bucket  new_bucket 
)

Definition at line 422 of file hashutil.c.

423{
424 Bucket old_bucket;
425 uint32 mask;
426 Buffer metabuf;
427 HashMetaPage metap;
428 BlockNumber blkno;
429
430 /*
431 * To get the old bucket from the current bucket, we need a mask to modulo
432 * into lower half of table. This mask is stored in meta page as
433 * hashm_lowmask, but here we can't rely on the same, because we need a
434 * value of lowmask that was prevalent at the time when bucket split was
435 * started. Masking the most significant bit of new bucket would give us
436 * old bucket.
437 */
438 mask = (((uint32) 1) << pg_leftmost_one_pos32(new_bucket)) - 1;
439 old_bucket = new_bucket & mask;
440
441 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
442 metap = HashPageGetMeta(BufferGetPage(metabuf));
443
444 blkno = BUCKET_TO_BLKNO(metap, old_bucket);
445
446 _hash_relbuf(rel, metabuf);
447
448 return blkno;
449}

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

Referenced by _hash_first().

◆ _hash_get_totalbuckets()

uint32 _hash_get_totalbuckets ( uint32  splitpoint_phase)

Definition at line 174 of file hashutil.c.

175{
176 uint32 splitpoint_group;
177 uint32 total_buckets;
178 uint32 phases_within_splitpoint_group;
179
180 if (splitpoint_phase < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
181 return (1 << splitpoint_phase);
182
183 /* get splitpoint's group */
184 splitpoint_group = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
185 splitpoint_group +=
186 ((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) >>
187 HASH_SPLITPOINT_PHASE_BITS);
188
189 /* account for buckets before splitpoint_group */
190 total_buckets = (1 << (splitpoint_group - 1));
191
192 /* account for buckets within splitpoint_group */
193 phases_within_splitpoint_group =
194 (((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) &
195 HASH_SPLITPOINT_PHASE_MASK) + 1); /* from 0-based to 1-based */
196 total_buckets +=
197 (((1 << (splitpoint_group - 1)) >> HASH_SPLITPOINT_PHASE_BITS) *
198 phases_within_splitpoint_group);
199
200 return total_buckets;
201}

References fb(), HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE, HASH_SPLITPOINT_PHASE_BITS, and HASH_SPLITPOINT_PHASE_MASK.

Referenced by _hash_expandtable(), _hash_init_metabuffer(), _hash_ovflblkno_to_bitno(), and bitno_to_blkno().

◆ _hash_hashkey2bucket()

Bucket _hash_hashkey2bucket ( uint32  hashkey,
uint32  maxbucket,
uint32  highmask,
uint32  lowmask 
)

Definition at line 125 of file hashutil.c.

127{
128 Bucket bucket;
129
130 bucket = hashkey & highmask;
131 if (bucket > maxbucket)
132 bucket = bucket & lowmask;
133
134 return bucket;
135}

References fb().

Referenced by _h_indexbuild(), _hash_getbucketbuf_from_hashkey(), _hash_splitbucket(), comparetup_index_hash(), and hashbucketcleanup().

◆ _hash_kill_items()

void _hash_kill_items ( IndexScanDesc  scan)

Definition at line 536 of file hashutil.c.

537{
538 HashScanOpaque so = (HashScanOpaque) scan->opaque;
539 Relation rel = scan->indexRelation;
540 BlockNumber blkno;
541 Buffer buf;
542 Page page;
543 HashPageOpaque opaque;
544 OffsetNumber offnum,
545 maxoff;
546 int numKilled = so->numKilled;
547 int i;
548 bool killedsomething = false;
549 bool havePin = false;
550
551 Assert(so->numKilled > 0);
552 Assert(so->killedItems != NULL);
553 Assert(HashScanPosIsValid(so->currPos));
554
555 /*
556 * Always reset the scan state, so we don't look for same items on other
557 * pages.
558 */
559 so->numKilled = 0;
560
561 blkno = so->currPos.currPage;
562 if (HashScanPosIsPinned(so->currPos))
563 {
564 /*
565 * We already have pin on this buffer, so, all we need to do is
566 * acquire lock on it.
567 */
568 havePin = true;
569 buf = so->currPos.buf;
570 LockBuffer(buf, BUFFER_LOCK_SHARE);
571 }
572 else
573 buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
574
575 page = BufferGetPage(buf);
576 opaque = HashPageGetOpaque(page);
577 maxoff = PageGetMaxOffsetNumber(page);
578
579 for (i = 0; i < numKilled; i++)
580 {
581 int itemIndex = so->killedItems[i];
582 HashScanPosItem *currItem = &so->currPos.items[itemIndex];
583
584 offnum = currItem->indexOffset;
585
586 Assert(itemIndex >= so->currPos.firstItem &&
587 itemIndex <= so->currPos.lastItem);
588
589 while (offnum <= maxoff)
590 {
591 ItemId iid = PageGetItemId(page, offnum);
592 IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
593
594 if (ItemPointerEquals(&ituple->t_tid, &currItem->heapTid))
595 {
596 /* found the item */
597 ItemIdMarkDead(iid);
598 killedsomething = true;
599 break; /* out of inner search loop */
600 }
601 offnum = OffsetNumberNext(offnum);
602 }
603 }
604
605 /*
606 * Since this can be redone later if needed, mark as dirty hint. Whenever
607 * we mark anything LP_DEAD, we also set the page's
608 * LH_PAGE_HAS_DEAD_TUPLES flag, which is likewise just a hint.
609 */
610 if (killedsomething)
611 {
612 opaque->hasho_flag |= LH_PAGE_HAS_DEAD_TUPLES;
613 MarkBufferDirtyHint(buf, true);
614 }
615
616 if (so->hashso_bucket_buf == so->currPos.buf ||
617 havePin)
618 LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
619 else
620 _hash_relbuf(rel, buf);
621}

References _hash_getbuf(), _hash_relbuf(), Assert, buf, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage(), fb(), HASH_READ, HashPageOpaqueData::hasho_flag, HashPageGetOpaque, HashScanPosIsPinned, HashScanPosIsValid, i, HashScanPosItem::indexOffset, IndexScanDescData::indexRelation, ItemIdMarkDead, ItemPointerEquals(), LH_OVERFLOW_PAGE, LH_PAGE_HAS_DEAD_TUPLES, LockBuffer(), MarkBufferDirtyHint(), OffsetNumberNext, IndexScanDescData::opaque, PageGetItem(), PageGetItemId(), and PageGetMaxOffsetNumber().

Referenced by _hash_next(), _hash_readpage(), hashendscan(), and hashrescan().

◆ _hash_spareindex()

uint32 _hash_spareindex ( uint32  num_bucket)

Definition at line 142 of file hashutil.c.

143{
144 uint32 splitpoint_group;
145 uint32 splitpoint_phases;
146
147 splitpoint_group = pg_ceil_log2_32(num_bucket);
148
149 if (splitpoint_group < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
150 return splitpoint_group;
151
152 /* account for single-phase groups */
153 splitpoint_phases = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
154
155 /* account for multi-phase groups before splitpoint_group */
156 splitpoint_phases +=
157 ((splitpoint_group - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) <<
158 HASH_SPLITPOINT_PHASE_BITS);
159
160 /* account for phases within current group */
161 splitpoint_phases +=
162 (((num_bucket - 1) >>
163 (splitpoint_group - (HASH_SPLITPOINT_PHASE_BITS + 1))) &
164 HASH_SPLITPOINT_PHASE_MASK); /* to 0-based value. */
165
166 return splitpoint_phases;
167}

References fb(), HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE, HASH_SPLITPOINT_PHASE_BITS, HASH_SPLITPOINT_PHASE_MASK, and pg_ceil_log2_32().

Referenced by _hash_expandtable(), and _hash_init_metabuffer().

◆ hashoptions()

bytea * hashoptions ( Datum  reloptions,
bool  validate 
)

Definition at line 275 of file hashutil.c.

276{
277 static const relopt_parse_elt tab[] = {
278 {"fillfactor", RELOPT_TYPE_INT, offsetof(HashOptions, fillfactor)},
279 };
280
281 return (bytea *) build_reloptions(reloptions, validate,
282 RELOPT_KIND_HASH,
283 sizeof(HashOptions),
284 tab, lengthof(tab));
285}

References build_reloptions(), fb(), fillfactor, lengthof, RELOPT_KIND_HASH, RELOPT_TYPE_INT, and validate().

Referenced by hashhandler().