hash.c 12.1 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * hash.c
4
 *	  Implementation of Margo Seltzer's Hashing package for postgres.
5
 *
6
 * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
7
 * Portions Copyright (c) 1994, Regents of the University of California
8 9 10
 *
 *
 * IDENTIFICATION
11
 *	  $Header: /cvsroot/pgsql/src/backend/access/hash/hash.c,v 1.49 2001/02/22 21:48:49 momjian Exp $
12 13
 *
 * NOTES
14
 *	  This file contains only the public interface routines.
15 16 17 18
 *
 *-------------------------------------------------------------------------
 */

19
#include "postgres.h"
20

Bruce Momjian's avatar
Bruce Momjian committed
21
#include "access/genam.h"
22 23 24
#include "access/hash.h"
#include "access/heapam.h"
#include "catalog/index.h"
Bruce Momjian's avatar
Bruce Momjian committed
25
#include "executor/executor.h"
26
#include "miscadmin.h"
Marc G. Fournier's avatar
Marc G. Fournier committed
27

28
bool		BuildingHash = false;
29

Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
30 31 32
#include "access/xlogutils.h"


33
/*
34
 *	hashbuild() -- build a new hash index.
35
 *
36 37 38 39
 *		We use a global variable to record the fact that we're creating
 *		a new index.  This is used to avoid high-concurrency locking,
 *		since the index won't be visible until this transaction commits
 *		and since building is guaranteed to be single-threaded.
40
 */
41 42
Datum
hashbuild(PG_FUNCTION_ARGS)
43
{
44 45
	Relation		heap = (Relation) PG_GETARG_POINTER(0);
	Relation		index = (Relation) PG_GETARG_POINTER(1);
46 47
	IndexInfo	   *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
	Node		   *oldPred = (Node *) PG_GETARG_POINTER(3);
48
#ifdef NOT_USED
49
	IndexStrategy	istrat = (IndexStrategy) PG_GETARG_POINTER(4);
50
#endif
51 52 53 54 55
	HeapScanDesc hscan;
	HeapTuple	htup;
	IndexTuple	itup;
	TupleDesc	htupdesc,
				itupdesc;
56 57
	Datum		attdata[INDEX_MAX_KEYS];
	char		nulls[INDEX_MAX_KEYS];
58 59 60
	int			nhtups,
				nitups;
	HashItem	hitem;
61
	Node	   *pred = indexInfo->ii_Predicate;
62
#ifndef OMIT_PARTIAL_INDEX
63
	TupleTable	tupleTable;
64
	TupleTableSlot *slot;
65
#endif
66 67
	ExprContext *econtext;
	InsertIndexResult res = NULL;
68

69
	/* note that this is a new hash */
70 71 72 73 74 75 76
	BuildingHash = true;

	/* initialize the hash index metadata page (if this is a new index) */
	if (oldPred == NULL)
		_hash_metapinit(index);

	/* get tuple descriptors for heap and index relations */
77 78
	htupdesc = RelationGetDescr(heap);
	itupdesc = RelationGetDescr(index);
79 80 81 82 83 84

	/*
	 * If this is a predicate (partial) index, we will need to evaluate
	 * the predicate using ExecQual, which requires the current tuple to
	 * be in a slot of a TupleTable.  In addition, ExecQual must have an
	 * ExprContext referring to that slot.	Here, we initialize dummy
85 86 87 88
	 * TupleTable and ExprContext objects for this purpose. --Nels, Feb 92
	 *
	 * We construct the ExprContext anyway since we need a per-tuple
	 * temporary memory context for function evaluation -- tgl July 00
89
	 */
90
#ifndef OMIT_PARTIAL_INDEX
91 92 93 94
	if (pred != NULL || oldPred != NULL)
	{
		tupleTable = ExecCreateTupleTable(1);
		slot = ExecAllocTableSlot(tupleTable);
95
		ExecSetSlotDescriptor(slot, htupdesc, false);
96 97
	}
	else
98
	{
99 100
		tupleTable = NULL;
		slot = NULL;
101
	}
102 103 104
	econtext = MakeExprContext(slot, TransactionCommandContext);
#else
	econtext = MakeExprContext(NULL, TransactionCommandContext);
105
#endif	 /* OMIT_PARTIAL_INDEX */
106 107 108 109

	/* build the index */
	nhtups = nitups = 0;

110 111 112 113
	/* start a heap scan */
	hscan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);

	while (HeapTupleIsValid(htup = heap_getnext(hscan, 0)))
114
	{
115 116
		MemoryContextReset(econtext->ecxt_per_tuple_memory);

117 118
		nhtups++;

119
#ifndef OMIT_PARTIAL_INDEX
120 121 122 123 124 125 126
		/*
		 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
		 * this tuple if it was already in the existing partial index
		 */
		if (oldPred != NULL)
		{
			slot->val = htup;
127
			if (ExecQual((List *) oldPred, econtext, false))
128 129 130 131 132 133 134 135 136 137 138 139 140
			{
				nitups++;
				continue;
			}
		}

		/*
		 * Skip this tuple if it doesn't satisfy the partial-index
		 * predicate
		 */
		if (pred != NULL)
		{
			slot->val = htup;
141
			if (!ExecQual((List *) pred, econtext, false))
142 143
				continue;
		}
144
#endif	 /* OMIT_PARTIAL_INDEX */
145

146
		nitups++;
147 148 149 150 151

		/*
		 * For the current heap tuple, extract all the attributes we use
		 * in this index, and note which are null.
		 */
152 153 154 155 156 157
		FormIndexDatum(indexInfo,
					   htup,
					   htupdesc,
					   econtext->ecxt_per_tuple_memory,
					   attdata,
					   nulls);
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172

		/* form an index tuple and point it at the heap tuple */
		itup = index_formtuple(itupdesc, attdata, nulls);

		/*
		 * If the single index key is null, we don't insert it into the
		 * index.  Hash tables support scans on '='. Relational algebra
		 * says that A = B returns null if either A or B is null.  This
		 * means that no qualification used in an index scan could ever
		 * return true on a null attribute.  It also means that indices
		 * can't be used by ISNULL or NOTNULL scans, but that's an
		 * artifact of the strategy map architecture chosen in 1986, not
		 * of the way nulls are handled here.
		 */

173
		if (IndexTupleHasNulls(itup))
174 175 176 177 178
		{
			pfree(itup);
			continue;
		}

179
		itup->t_tid = htup->t_self;
180
		hitem = _hash_formitem(itup);
181

182
		res = _hash_doinsert(index, hitem);
183

184 185 186
		pfree(hitem);
		pfree(itup);
		pfree(res);
187
	}
188 189 190 191

	/* okay, all heap tuples are indexed */
	heap_endscan(hscan);

192
#ifndef OMIT_PARTIAL_INDEX
193 194
	if (pred != NULL || oldPred != NULL)
	{
195
		ExecDropTupleTable(tupleTable, true);
196
	}
197
#endif	 /* OMIT_PARTIAL_INDEX */
198
	FreeExprContext(econtext);
199

200
	/*
201 202
	 * Since we just counted the tuples in the heap, we update its stats
	 * in pg_class to guarantee that the planner takes advantage of the
203 204 205 206 207 208 209
	 * index we just created.  But, only update statistics during normal
	 * index definitions, not for indices on system catalogs created
	 * during bootstrap processing.  We must close the relations before
	 * updating statistics to guarantee that the relcache entries are
	 * flushed when we increment the command counter in UpdateStats(). But
	 * we do not release any locks on the relations; those will be held
	 * until end of transaction.
210
	 */
211
	if (IsNormalProcessingMode())
212
	{
213 214
		Oid			hrelid = RelationGetRelid(heap);
		Oid			irelid = RelationGetRelid(index);
215 216

		heap_close(heap, NoLock);
217
		index_close(index);
218 219 220
		UpdateStats(hrelid, nhtups);
		UpdateStats(irelid, nitups);
		if (oldPred != NULL)
221 222 223 224 225
		{
			if (nitups == nhtups)
				pred = NULL;
			UpdateIndexPredicate(irelid, oldPred, pred);
		}
226
	}
227 228 229

	/* all done */
	BuildingHash = false;
230

231
	PG_RETURN_VOID();
232 233 234
}

/*
235
 *	hashinsert() -- insert an index tuple into a hash table.
236
 *
237 238 239
 *	Hash on the index tuple's key, find the appropriate location
 *	for the new tuple, put it there, and return an InsertIndexResult
 *	to the caller.
240
 */
241 242
Datum
hashinsert(PG_FUNCTION_ARGS)
243
{
244 245 246 247 248 249 250 251
	Relation		rel = (Relation) PG_GETARG_POINTER(0);
	Datum		   *datum = (Datum *) PG_GETARG_POINTER(1);
	char		   *nulls = (char *) PG_GETARG_POINTER(2);
	ItemPointer		ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);
#ifdef NOT_USED
	Relation		heapRel = (Relation) PG_GETARG_POINTER(4);
#endif
	InsertIndexResult res;
252 253
	HashItem	hitem;
	IndexTuple	itup;
254 255

	/* generate an index tuple */
256
	itup = index_formtuple(RelationGetDescr(rel), datum, nulls);
257 258
	itup->t_tid = *ht_ctid;

259
	if (IndexTupleHasNulls(itup))
260
		PG_RETURN_POINTER((InsertIndexResult) NULL);
261 262 263 264 265 266 267 268

	hitem = _hash_formitem(itup);

	res = _hash_doinsert(rel, hitem);

	pfree(hitem);
	pfree(itup);

269
	PG_RETURN_POINTER(res);
270 271 272 273
}


/*
274
 *	hashgettuple() -- Get the next tuple in the scan.
275
 */
276 277
Datum
hashgettuple(PG_FUNCTION_ARGS)
278
{
279 280
	IndexScanDesc		scan = (IndexScanDesc) PG_GETARG_POINTER(0);
	ScanDirection		dir = (ScanDirection) PG_GETARG_INT32(1);
281 282 283 284 285 286 287 288 289 290 291 292 293
	RetrieveIndexResult res;

	/*
	 * If we've already initialized this scan, we can just advance it in
	 * the appropriate direction.  If we haven't done so yet, we call a
	 * routine to get the first item in the scan.
	 */

	if (ItemPointerIsValid(&(scan->currentItemData)))
		res = _hash_next(scan, dir);
	else
		res = _hash_first(scan, dir);

294
	PG_RETURN_POINTER(res);
295 296 297 298
}


/*
299
 *	hashbeginscan() -- start a scan on a hash index
300
 */
301 302
Datum
hashbeginscan(PG_FUNCTION_ARGS)
303
{
304 305 306 307
	Relation	rel = (Relation) PG_GETARG_POINTER(0);
	bool		fromEnd = PG_GETARG_BOOL(1);
	uint16		keysz = PG_GETARG_UINT16(2);
	ScanKey		scankey = (ScanKey) PG_GETARG_POINTER(3);
308 309
	IndexScanDesc scan;
	HashScanOpaque so;
310 311 312 313 314 315 316 317 318 319

	scan = RelationGetIndexScan(rel, fromEnd, keysz, scankey);
	so = (HashScanOpaque) palloc(sizeof(HashScanOpaqueData));
	so->hashso_curbuf = so->hashso_mrkbuf = InvalidBuffer;
	scan->opaque = so;
	scan->flags = 0x0;

	/* register scan in case we change pages it's using */
	_hash_regscan(scan);

320
	PG_RETURN_POINTER(scan);
321 322 323
}

/*
324
 *	hashrescan() -- rescan an index relation
325
 */
326 327
Datum
hashrescan(PG_FUNCTION_ARGS)
328
{
329 330 331 332 333
	IndexScanDesc	scan = (IndexScanDesc) PG_GETARG_POINTER(0);
#ifdef NOT_USED					/* XXX surely it's wrong to ignore this? */
	bool			fromEnd = PG_GETARG_BOOL(1);
#endif
	ScanKey			scankey = (ScanKey) PG_GETARG_POINTER(2);
334 335
	ItemPointer iptr;
	HashScanOpaque so;
336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359

	so = (HashScanOpaque) scan->opaque;

	/* we hold a read lock on the current page in the scan */
	if (ItemPointerIsValid(iptr = &(scan->currentItemData)))
	{
		_hash_relbuf(scan->relation, so->hashso_curbuf, HASH_READ);
		so->hashso_curbuf = InvalidBuffer;
		ItemPointerSetInvalid(iptr);
	}
	if (ItemPointerIsValid(iptr = &(scan->currentMarkData)))
	{
		_hash_relbuf(scan->relation, so->hashso_mrkbuf, HASH_READ);
		so->hashso_mrkbuf = InvalidBuffer;
		ItemPointerSetInvalid(iptr);
	}

	/* reset the scan key */
	if (scan->numberOfKeys > 0)
	{
		memmove(scan->keyData,
				scankey,
				scan->numberOfKeys * sizeof(ScanKeyData));
	}
360

361
	PG_RETURN_VOID();
362 363 364
}

/*
365
 *	hashendscan() -- close down a scan
366
 */
367 368
Datum
hashendscan(PG_FUNCTION_ARGS)
369
{
370
	IndexScanDesc	scan = (IndexScanDesc) PG_GETARG_POINTER(0);
371 372
	ItemPointer iptr;
	HashScanOpaque so;
373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396

	so = (HashScanOpaque) scan->opaque;

	/* release any locks we still hold */
	if (ItemPointerIsValid(iptr = &(scan->currentItemData)))
	{
		_hash_relbuf(scan->relation, so->hashso_curbuf, HASH_READ);
		so->hashso_curbuf = InvalidBuffer;
		ItemPointerSetInvalid(iptr);
	}

	if (ItemPointerIsValid(iptr = &(scan->currentMarkData)))
	{
		if (BufferIsValid(so->hashso_mrkbuf))
			_hash_relbuf(scan->relation, so->hashso_mrkbuf, HASH_READ);
		so->hashso_mrkbuf = InvalidBuffer;
		ItemPointerSetInvalid(iptr);
	}

	/* don't need scan registered anymore */
	_hash_dropscan(scan);

	/* be tidy */
	pfree(scan->opaque);
397

398
	PG_RETURN_VOID();
399 400 401
}

/*
402
 *	hashmarkpos() -- save current scan position
403 404
 *
 */
405 406
Datum
hashmarkpos(PG_FUNCTION_ARGS)
407
{
408
	IndexScanDesc	scan = (IndexScanDesc) PG_GETARG_POINTER(0);
409 410
	ItemPointer iptr;
	HashScanOpaque so;
411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429

	so = (HashScanOpaque) scan->opaque;

	/* release lock on old marked data, if any */
	if (ItemPointerIsValid(iptr = &(scan->currentMarkData)))
	{
		_hash_relbuf(scan->relation, so->hashso_mrkbuf, HASH_READ);
		so->hashso_mrkbuf = InvalidBuffer;
		ItemPointerSetInvalid(iptr);
	}

	/* bump lock on currentItemData and copy to currentMarkData */
	if (ItemPointerIsValid(&(scan->currentItemData)))
	{
		so->hashso_mrkbuf = _hash_getbuf(scan->relation,
								 BufferGetBlockNumber(so->hashso_curbuf),
										 HASH_READ);
		scan->currentMarkData = scan->currentItemData;
	}
430

431
	PG_RETURN_VOID();
432 433 434
}

/*
435
 *	hashrestrpos() -- restore scan to last saved position
436
 */
437 438
Datum
hashrestrpos(PG_FUNCTION_ARGS)
439
{
440
	IndexScanDesc	scan = (IndexScanDesc) PG_GETARG_POINTER(0);
441 442
	ItemPointer iptr;
	HashScanOpaque so;
443 444 445 446 447 448 449 450 451 452 453 454 455 456

	so = (HashScanOpaque) scan->opaque;

	/* release lock on current data, if any */
	if (ItemPointerIsValid(iptr = &(scan->currentItemData)))
	{
		_hash_relbuf(scan->relation, so->hashso_curbuf, HASH_READ);
		so->hashso_curbuf = InvalidBuffer;
		ItemPointerSetInvalid(iptr);
	}

	/* bump lock on currentMarkData and copy to currentItemData */
	if (ItemPointerIsValid(&(scan->currentMarkData)))
	{
Bruce Momjian's avatar
Bruce Momjian committed
457 458 459
		so->hashso_curbuf = _hash_getbuf(scan->relation,
								 BufferGetBlockNumber(so->hashso_mrkbuf),
										 HASH_READ);
460 461 462

		scan->currentItemData = scan->currentMarkData;
	}
463

464
	PG_RETURN_VOID();
465 466 467
}

/* stubs */
468 469
Datum
hashdelete(PG_FUNCTION_ARGS)
470
{
471 472 473
	Relation		rel = (Relation) PG_GETARG_POINTER(0);
	ItemPointer		tid = (ItemPointer) PG_GETARG_POINTER(1);

474 475
	/* adjust any active scans that will be affected by this deletion */
	_hash_adjscans(rel, tid);
476

477 478
	/* delete the data from the page */
	_hash_pagedel(rel, tid);
479

480
	PG_RETURN_VOID();
481
}
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498

void
hash_redo(XLogRecPtr lsn, XLogRecord *record)
{
	elog(STOP, "hash_redo: unimplemented");
}

void
hash_undo(XLogRecPtr lsn, XLogRecord *record)
{
	elog(STOP, "hash_undo: unimplemented");
}
 
void
hash_desc(char *buf, uint8 xl_info, char* rec)
{
}