1 /*-------------------------------------------------------------------------
4 * Utility code for Postgres hash implementation.
6 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/access/hash/hashutil.c
13 *-------------------------------------------------------------------------
17 #include "access/hash.h"
18 #include "access/reloptions.h"
19 #include "access/relscan.h"
20 #include "utils/lsyscache.h"
21 #include "utils/rel.h"
25 * _hash_checkqual -- does the index tuple satisfy the scan conditions?
28 _hash_checkqual(IndexScanDesc scan, IndexTuple itup)
31 * Currently, we can't check any of the scan conditions since we do not
32 * have the original index entry value to supply to the sk_func. Always
33 * return true; we expect that hashgettuple already set the recheck flag
34 * to make the main indexscan code do it.
37 TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
38 ScanKey key = scan->keyData;
39 int scanKeySize = scan->numberOfKeys;
41 while (scanKeySize > 0)
47 datum = index_getattr(itup,
52 /* assume sk_func is strict */
55 if (key->sk_flags & SK_ISNULL)
58 test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
59 datum, key->sk_argument);
61 if (!DatumGetBool(test))
73 * _hash_datum2hashkey -- given a Datum, call the index's hash procedure
75 * The Datum is assumed to be of the index's column type, so we can use the
76 * "primary" hash procedure that's tracked for us by the generic index code.
79 _hash_datum2hashkey(Relation rel, Datum key)
84 /* XXX assumes index has only one attribute */
85 procinfo = index_getprocinfo(rel, 1, HASHPROC);
86 collation = rel->rd_indcollation[0];
88 return DatumGetUInt32(FunctionCall1Coll(procinfo, collation, key));
92 * _hash_datum2hashkey_type -- given a Datum of a specified type,
93 * hash it in a fashion compatible with this index
95 * This is much more expensive than _hash_datum2hashkey, so use it only in
96 * cross-type situations.
99 _hash_datum2hashkey_type(Relation rel, Datum key, Oid keytype)
101 RegProcedure hash_proc;
104 /* XXX assumes index has only one attribute */
105 hash_proc = get_opfamily_proc(rel->rd_opfamily[0],
109 if (!RegProcedureIsValid(hash_proc))
110 elog(ERROR, "missing support function %d(%u,%u) for index \"%s\"",
111 HASHPROC, keytype, keytype,
112 RelationGetRelationName(rel));
113 collation = rel->rd_indcollation[0];
115 return DatumGetUInt32(OidFunctionCall1Coll(hash_proc, collation, key));
119 * _hash_hashkey2bucket -- determine which bucket the hashkey maps to.
122 _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
123 uint32 highmask, uint32 lowmask)
127 bucket = hashkey & highmask;
128 if (bucket > maxbucket)
129 bucket = bucket & lowmask;
135 * _hash_log2 -- returns ceil(lg2(num))
138 _hash_log2(uint32 num)
144 for (i = 0; limit < num; limit <<= 1, i++)
150 * _hash_checkpage -- sanity checks on the format of all hash pages
152 * If flags is not zero, it is a bitwise OR of the acceptable values of
156 _hash_checkpage(Relation rel, Buffer buf, int flags)
158 Page page = BufferGetPage(buf);
161 * ReadBuffer verifies that every newly-read page passes
162 * PageHeaderIsValid, which means it either contains a reasonably sane
163 * page header or is all-zero. We have to defend against the all-zero
168 (errcode(ERRCODE_INDEX_CORRUPTED),
169 errmsg("index \"%s\" contains unexpected zero page at block %u",
170 RelationGetRelationName(rel),
171 BufferGetBlockNumber(buf)),
172 errhint("Please REINDEX it.")));
175 * Additionally check that the special area looks sane.
177 if (PageGetSpecialSize(page) != MAXALIGN(sizeof(HashPageOpaqueData)))
179 (errcode(ERRCODE_INDEX_CORRUPTED),
180 errmsg("index \"%s\" contains corrupted page at block %u",
181 RelationGetRelationName(rel),
182 BufferGetBlockNumber(buf)),
183 errhint("Please REINDEX it.")));
187 HashPageOpaque opaque = (HashPageOpaque) PageGetSpecialPointer(page);
189 if ((opaque->hasho_flag & flags) == 0)
191 (errcode(ERRCODE_INDEX_CORRUPTED),
192 errmsg("index \"%s\" contains corrupted page at block %u",
193 RelationGetRelationName(rel),
194 BufferGetBlockNumber(buf)),
195 errhint("Please REINDEX it.")));
199 * When checking the metapage, also verify magic number and version.
201 if (flags == LH_META_PAGE)
203 HashMetaPage metap = HashPageGetMeta(page);
205 if (metap->hashm_magic != HASH_MAGIC)
207 (errcode(ERRCODE_INDEX_CORRUPTED),
208 errmsg("index \"%s\" is not a hash index",
209 RelationGetRelationName(rel))));
211 if (metap->hashm_version != HASH_VERSION)
213 (errcode(ERRCODE_INDEX_CORRUPTED),
214 errmsg("index \"%s\" has wrong hash version",
215 RelationGetRelationName(rel)),
216 errhint("Please REINDEX it.")));
221 hashoptions(PG_FUNCTION_ARGS)
223 Datum reloptions = PG_GETARG_DATUM(0);
224 bool validate = PG_GETARG_BOOL(1);
227 result = default_reloptions(reloptions, validate, RELOPT_KIND_HASH);
230 PG_RETURN_BYTEA_P(result);
235 * _hash_get_indextuple_hashkey - get the hash index tuple's hash key value
238 _hash_get_indextuple_hashkey(IndexTuple itup)
243 * We assume the hash key is the first attribute and can't be null, so
244 * this can be done crudely but very very cheaply ...
246 attp = (char *) itup + IndexInfoFindDataOffset(itup->t_info);
247 return *((uint32 *) attp);
251 * _hash_form_tuple - form an index tuple containing hash code only
254 _hash_form_tuple(Relation index, Datum *values, bool *isnull)
262 hashkeydatum = (Datum) 0;
265 hashkey = _hash_datum2hashkey(index, values[0]);
266 hashkeydatum = UInt32GetDatum(hashkey);
268 hashdesc = RelationGetDescr(index);
269 Assert(hashdesc->natts == 1);
270 itup = index_form_tuple(hashdesc, &hashkeydatum, isnull);
275 * _hash_binsearch - Return the offset number in the page where the
276 * specified hash value should be sought or inserted.
278 * We use binary search, relying on the assumption that the existing entries
279 * are ordered by hash key.
281 * Returns the offset of the first index entry having hashkey >= hash_value,
282 * or the page's max offset plus one if hash_value is greater than all
283 * existing hash keys in the page. This is the appropriate place to start
284 * a search, or to insert a new item.
287 _hash_binsearch(Page page, uint32 hash_value)
292 /* Loop invariant: lower <= desired place <= upper */
293 upper = PageGetMaxOffsetNumber(page) + 1;
294 lower = FirstOffsetNumber;
296 while (upper > lower)
302 off = (upper + lower) / 2;
303 Assert(OffsetNumberIsValid(off));
305 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
306 hashkey = _hash_get_indextuple_hashkey(itup);
307 if (hashkey < hash_value)
317 * _hash_binsearch_last
319 * Same as above, except that if there are multiple matching items in the
320 * page, we return the offset of the last one instead of the first one,
321 * and the possible range of outputs is 0..maxoffset not 1..maxoffset+1.
322 * This is handy for starting a new page in a backwards scan.
325 _hash_binsearch_last(Page page, uint32 hash_value)
330 /* Loop invariant: lower <= desired place <= upper */
331 upper = PageGetMaxOffsetNumber(page);
332 lower = FirstOffsetNumber - 1;
334 while (upper > lower)
340 off = (upper + lower + 1) / 2;
341 Assert(OffsetNumberIsValid(off));
343 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
344 hashkey = _hash_get_indextuple_hashkey(itup);
345 if (hashkey > hash_value)