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 "storage/buf_internals.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, 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	_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 25 of file hashutil.c.

Function Documentation

_hash_binsearch()

OffsetNumber _hash_binsearch	(	Page	page,
		uint32	hash_value
	)

Definition at line 351 of file hashutil.c.

{
    OffsetNumber upper;
    OffsetNumber lower;
 
    /* Loop invariant: lower <= desired place <= upper */
    upper = PageGetMaxOffsetNumber(page) + 1;
    lower = FirstOffsetNumber;
 
    while (upper > lower)
    {
        OffsetNumber off;
        IndexTuple  itup;
        uint32      hashkey;
 
        off = (upper + lower) / 2;
        Assert(OffsetNumberIsValid(off));
 
        itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
        hashkey = _hash_get_indextuple_hashkey(itup);
        if (hashkey < hash_value)
            lower = off + 1;
        else
            upper = off;
    }
 
    return lower;
}

References _hash_get_indextuple_hashkey(), Assert(), 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 389 of file hashutil.c.

{
    OffsetNumber upper;
    OffsetNumber lower;
 
    /* Loop invariant: lower <= desired place <= upper */
    upper = PageGetMaxOffsetNumber(page);
    lower = FirstOffsetNumber - 1;
 
    while (upper > lower)
    {
        IndexTuple  itup;
        OffsetNumber off;
        uint32      hashkey;
 
        off = (upper + lower + 1) / 2;
        Assert(OffsetNumberIsValid(off));
 
        itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
        hashkey = _hash_get_indextuple_hashkey(itup);
        if (hashkey > hash_value)
            upper = off - 1;
        else
            lower = off;
    }
 
    return lower;
}

References _hash_get_indextuple_hashkey(), Assert(), 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 211 of file hashutil.c.

{
    Page        page = BufferGetPage(buf);
 
    /*
     * ReadBuffer verifies that every newly-read page passes
     * PageHeaderIsValid, which means it either contains a reasonably sane
     * page header or is all-zero.  We have to defend against the all-zero
     * case, however.
     */
    if (PageIsNew(page))
        ereport(ERROR,
                (errcode(ERRCODE_INDEX_CORRUPTED),
                 errmsg("index \"%s\" contains unexpected zero page at block %u",
                        RelationGetRelationName(rel),
                        BufferGetBlockNumber(buf)),
                 errhint("Please REINDEX it.")));
 
    /*
     * Additionally check that the special area looks sane.
     */
    if (PageGetSpecialSize(page) != MAXALIGN(sizeof(HashPageOpaqueData)))
        ereport(ERROR,
                (errcode(ERRCODE_INDEX_CORRUPTED),
                 errmsg("index \"%s\" contains corrupted page at block %u",
                        RelationGetRelationName(rel),
                        BufferGetBlockNumber(buf)),
                 errhint("Please REINDEX it.")));
 
    if (flags)
    {
        HashPageOpaque opaque = HashPageGetOpaque(page);
 
        if ((opaque->hasho_flag & flags) == 0)
            ereport(ERROR,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg("index \"%s\" contains corrupted page at block %u",
                            RelationGetRelationName(rel),
                            BufferGetBlockNumber(buf)),
                     errhint("Please REINDEX it.")));
    }
 
    /*
     * When checking the metapage, also verify magic number and version.
     */
    if (flags == LH_META_PAGE)
    {
        HashMetaPage metap = HashPageGetMeta(page);
 
        if (metap->hashm_magic != HASH_MAGIC)
            ereport(ERROR,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg("index \"%s\" is not a hash index",
                            RelationGetRelationName(rel))));
 
        if (metap->hashm_version != HASH_VERSION)
            ereport(ERROR,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg("index \"%s\" has wrong hash version",
                            RelationGetRelationName(rel)),
                     errhint("Please REINDEX it.")));
    }
}

References buf, BufferGetBlockNumber(), BufferGetPage(), ereport, errcode(), errhint(), errmsg(), ERROR, HASH_MAGIC, HASH_VERSION, HashMetaPageData::hashm_magic, HashMetaPageData::hashm_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 32 of file hashutil.c.

{
    /*
     * Currently, we can't check any of the scan conditions since we do not
     * have the original index entry value to supply to the sk_func. Always
     * return true; we expect that hashgettuple already set the recheck flag
     * to make the main indexscan code do it.
     */
#ifdef NOT_USED
    TupleDesc   tupdesc = RelationGetDescr(scan->indexRelation);
    ScanKey     key = scan->keyData;
    int         scanKeySize = scan->numberOfKeys;
 
    while (scanKeySize > 0)
    {
        Datum       datum;
        bool        isNull;
        Datum       test;
 
        datum = index_getattr(itup,
                              key->sk_attno,
                              tupdesc,
                              &isNull);
 
        /* assume sk_func is strict */
        if (isNull)
            return false;
        if (key->sk_flags & SK_ISNULL)
            return false;
 
        test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
                                 datum, key->sk_argument);
 
        if (!DatumGetBool(test))
            return false;
 
        key++;
        scanKeySize--;
    }
#endif
 
    return true;
}

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

Referenced by _hash_load_qualified_items().

_hash_convert_tuple()

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

Definition at line 319 of file hashutil.c.

{
    uint32      hashkey;
 
    /*
     * We do not insert null values into hash indexes.  This is okay because
     * the only supported search operator is '=', and we assume it is strict.
     */
    if (user_isnull[0])
        return false;
 
    hashkey = _hash_datum2hashkey(index, user_values[0]);
    index_values[0] = UInt32GetDatum(hashkey);
    index_isnull[0] = false;
    return true;
}

References _hash_datum2hashkey(), and UInt32GetDatum().

Referenced by hashbuildCallback(), and hashinsert().

_hash_datum2hashkey()

uint32 _hash_datum2hashkey	(	Relation	rel,
		Datum	key
	)

Definition at line 83 of file hashutil.c.

{
    FmgrInfo   *procinfo;
    Oid         collation;
 
    /* XXX assumes index has only one attribute */
    procinfo = index_getprocinfo(rel, 1, HASHSTANDARD_PROC);
    collation = rel->rd_indcollation[0];
 
    return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
}

References DatumGetUInt32(), FunctionCall1Coll(), HASHSTANDARD_PROC, index_getprocinfo(), sort-test::key, 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 103 of file hashutil.c.

{
    RegProcedure hash_proc;
    Oid         collation;
 
    /* XXX assumes index has only one attribute */
    hash_proc = get_opfamily_proc(rel->rd_opfamily[0],
                                  keytype,
                                  keytype,
                                  HASHSTANDARD_PROC);
    if (!RegProcedureIsValid(hash_proc))
        elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
             HASHSTANDARD_PROC, keytype, keytype,
             RelationGetRelationName(rel));
    collation = rel->rd_indcollation[0];
 
    return DatumGetUInt32(OidFunctionCall1Coll(hash_proc, collation, key));
}

References DatumGetUInt32(), elog(), ERROR, get_opfamily_proc(), HASHSTANDARD_PROC, sort-test::key, 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 292 of file hashutil.c.

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

References 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 462 of file hashutil.c.

{
    Bucket      new_bucket;
    Buffer      metabuf;
    HashMetaPage metap;
    BlockNumber blkno;
 
    metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));
 
    new_bucket = _hash_get_newbucket_from_oldbucket(rel, old_bucket,
                                                    metap->hashm_lowmask,
                                                    metap->hashm_maxbucket);
    blkno = BUCKET_TO_BLKNO(metap, new_bucket);
 
    _hash_relbuf(rel, metabuf);
 
    return blkno;
}

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().

_hash_get_newbucket_from_oldbucket()

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

Definition at line 495 of file hashutil.c.

{
    Bucket      new_bucket;
 
    new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
    if (new_bucket > maxbucket)
    {
        lowmask = lowmask >> 1;
        new_bucket = CALC_NEW_BUCKET(old_bucket, lowmask);
    }
 
    return new_bucket;
}

References CALC_NEW_BUCKET.

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 423 of file hashutil.c.

{
    Bucket      old_bucket;
    uint32      mask;
    Buffer      metabuf;
    HashMetaPage metap;
    BlockNumber blkno;
 
    /*
     * To get the old bucket from the current bucket, we need a mask to modulo
     * into lower half of table.  This mask is stored in meta page as
     * hashm_lowmask, but here we can't rely on the same, because we need a
     * value of lowmask that was prevalent at the time when bucket split was
     * started.  Masking the most significant bit of new bucket would give us
     * old bucket.
     */
    mask = (((uint32) 1) << pg_leftmost_one_pos32(new_bucket)) - 1;
    old_bucket = new_bucket & mask;
 
    metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ, LH_META_PAGE);
    metap = HashPageGetMeta(BufferGetPage(metabuf));
 
    blkno = BUCKET_TO_BLKNO(metap, old_bucket);
 
    _hash_relbuf(rel, metabuf);
 
    return blkno;
}

References _hash_getbuf(), _hash_relbuf(), BUCKET_TO_BLKNO, BufferGetPage(), 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 175 of file hashutil.c.

{
    uint32      splitpoint_group;
    uint32      total_buckets;
    uint32      phases_within_splitpoint_group;
 
    if (splitpoint_phase < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
        return (1 << splitpoint_phase);
 
    /* get splitpoint's group */
    splitpoint_group = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
    splitpoint_group +=
        ((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) >>
         HASH_SPLITPOINT_PHASE_BITS);
 
    /* account for buckets before splitpoint_group */
    total_buckets = (1 << (splitpoint_group - 1));
 
    /* account for buckets within splitpoint_group */
    phases_within_splitpoint_group =
        (((splitpoint_phase - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) &
          HASH_SPLITPOINT_PHASE_MASK) + 1); /* from 0-based to 1-based */
    total_buckets +=
        (((1 << (splitpoint_group - 1)) >> HASH_SPLITPOINT_PHASE_BITS) *
         phases_within_splitpoint_group);
 
    return total_buckets;
}

References 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 126 of file hashutil.c.

{
    Bucket      bucket;
 
    bucket = hashkey & highmask;
    if (bucket > maxbucket)
        bucket = bucket & lowmask;
 
    return bucket;
}

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 537 of file hashutil.c.

{
    HashScanOpaque so = (HashScanOpaque) scan->opaque;
    Relation    rel = scan->indexRelation;
    BlockNumber blkno;
    Buffer      buf;
    Page        page;
    HashPageOpaque opaque;
    OffsetNumber offnum,
                maxoff;
    int         numKilled = so->numKilled;
    int         i;
    bool        killedsomething = false;
    bool        havePin = false;
 
    Assert(so->numKilled > 0);
    Assert(so->killedItems != NULL);
    Assert(HashScanPosIsValid(so->currPos));
 
    /*
     * Always reset the scan state, so we don't look for same items on other
     * pages.
     */
    so->numKilled = 0;
 
    blkno = so->currPos.currPage;
    if (HashScanPosIsPinned(so->currPos))
    {
        /*
         * We already have pin on this buffer, so, all we need to do is
         * acquire lock on it.
         */
        havePin = true;
        buf = so->currPos.buf;
        LockBuffer(buf, BUFFER_LOCK_SHARE);
    }
    else
        buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
 
    page = BufferGetPage(buf);
    opaque = HashPageGetOpaque(page);
    maxoff = PageGetMaxOffsetNumber(page);
 
    for (i = 0; i < numKilled; i++)
    {
        int         itemIndex = so->killedItems[i];
        HashScanPosItem *currItem = &so->currPos.items[itemIndex];
 
        offnum = currItem->indexOffset;
 
        Assert(itemIndex >= so->currPos.firstItem &&
               itemIndex <= so->currPos.lastItem);
 
        while (offnum <= maxoff)
        {
            ItemId      iid = PageGetItemId(page, offnum);
            IndexTuple  ituple = (IndexTuple) PageGetItem(page, iid);
 
            if (ItemPointerEquals(&ituple->t_tid, &currItem->heapTid))
            {
                /* found the item */
                ItemIdMarkDead(iid);
                killedsomething = true;
                break;          /* out of inner search loop */
            }
            offnum = OffsetNumberNext(offnum);
        }
    }
 
    /*
     * Since this can be redone later if needed, mark as dirty hint. Whenever
     * we mark anything LP_DEAD, we also set the page's
     * LH_PAGE_HAS_DEAD_TUPLES flag, which is likewise just a hint.
     */
    if (killedsomething)
    {
        opaque->hasho_flag |= LH_PAGE_HAS_DEAD_TUPLES;
        MarkBufferDirtyHint(buf, true);
    }
 
    if (so->hashso_bucket_buf == so->currPos.buf ||
        havePin)
        LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
    else
        _hash_relbuf(rel, buf);
}

References _hash_getbuf(), _hash_relbuf(), Assert(), buf, HashScanPosData::buf, BUFFER_LOCK_SHARE, BUFFER_LOCK_UNLOCK, BufferGetPage(), HashScanPosData::currPage, HashScanOpaqueData::currPos, HashScanPosData::firstItem, HASH_READ, HashPageGetOpaque, HashScanPosIsPinned, HashScanPosIsValid, HashScanOpaqueData::hashso_bucket_buf, HashScanPosItem::heapTid, i, HashScanPosItem::indexOffset, IndexScanDescData::indexRelation, ItemIdMarkDead, ItemPointerEquals(), HashScanPosData::items, HashScanOpaqueData::killedItems, LH_OVERFLOW_PAGE, LH_PAGE_HAS_DEAD_TUPLES, LockBuffer(), MarkBufferDirtyHint(), HashScanOpaqueData::numKilled, OffsetNumberNext, IndexScanDescData::opaque, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and IndexTupleData::t_tid.

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

_hash_spareindex()

uint32 _hash_spareindex

(

uint32

num_bucket

)

Definition at line 143 of file hashutil.c.

{
    uint32      splitpoint_group;
    uint32      splitpoint_phases;
 
    splitpoint_group = pg_ceil_log2_32(num_bucket);
 
    if (splitpoint_group < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
        return splitpoint_group;
 
    /* account for single-phase groups */
    splitpoint_phases = HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE;
 
    /* account for multi-phase groups before splitpoint_group */
    splitpoint_phases +=
        ((splitpoint_group - HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE) <<
         HASH_SPLITPOINT_PHASE_BITS);
 
    /* account for phases within current group */
    splitpoint_phases +=
        (((num_bucket - 1) >>
          (splitpoint_group - (HASH_SPLITPOINT_PHASE_BITS + 1))) &
         HASH_SPLITPOINT_PHASE_MASK);   /* to 0-based value. */
 
    return splitpoint_phases;
}

References 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 276 of file hashutil.c.

{
    static const relopt_parse_elt tab[] = {
        {"fillfactor", RELOPT_TYPE_INT, offsetof(HashOptions, fillfactor)},
    };
 
    return (bytea *) build_reloptions(reloptions, validate,
                                      RELOPT_KIND_HASH,
                                      sizeof(HashOptions),
                                      tab, lengthof(tab));
}

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

Referenced by hashhandler().