nbtsort.c 18.9 KB
Newer Older
1
/*-------------------------------------------------------------------------
2 3
 * nbtsort.c
 *		Build a btree from sorted input by loading leaf pages sequentially.
4 5 6
 *
 * NOTES
 *
7 8
 * We use tuplesort.c to sort the given index tuples into order.
 * Then we scan the index tuples in order and build the btree pages
9
 * for each level.	We load source tuples into leaf-level pages.
10 11 12 13 14
 * Whenever we fill a page at one level, we add a link to it to its
 * parent level (starting a new parent level if necessary).  When
 * done, we write out each final page on each level, adding it to
 * its parent level.  When we have only one page on a level, it must be
 * the root -- it can be attached to the btree metapage and we are done.
15
 *
16 17
 * This code is moderately slow (~10% slower) compared to the regular
 * btree (insertion) build code on sorted or well-clustered data.  On
18 19
 * random data, however, the insertion build code is unusable -- the
 * difference on a 60MB heap is a factor of 15 because the random
20 21 22 23
 * probes into the btree thrash the buffer pool.  (NOTE: the above
 * "10%" estimate is probably obsolete, since it refers to an old and
 * not very good external sort implementation that used to exist in
 * this module.  tuplesort.c is almost certainly faster.)
24
 *
25 26 27 28 29 30 31
 * It is not wise to pack the pages entirely full, since then *any*
 * insertion would cause a split (and not only of the leaf page; the need
 * for a split would cascade right up the tree).  The steady-state load
 * factor for btrees is usually estimated at 70%.  We choose to pack leaf
 * pages to 90% and upper pages to 70%.  This gives us reasonable density
 * (there aren't many upper pages if the keys are reasonable-size) without
 * incurring a lot of cascading splits during early insertions.
32
 *
33
 *
34
 * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
Bruce Momjian's avatar
Add:  
Bruce Momjian committed
35
 * Portions Copyright (c) 1994, Regents of the University of California
36 37
 *
 * IDENTIFICATION
38
 *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.63 2001/11/10 23:51:13 tgl Exp $
39
 *
40 41 42
 *-------------------------------------------------------------------------
 */

43
#include "postgres.h"
44

45
#include "access/nbtree.h"
46
#include "utils/tuplesort.h"
47

48

49
/*
50
 * Status record for spooling.
51
 */
52
struct BTSpool
53
{
54 55
	Tuplesortstate *sortstate;	/* state data for tuplesort.c */
	Relation	index;
56
	bool		isunique;
57
};
58

59
/*
60
 * Status record for a btree page being built.	We have one of these
61
 * for each active tree level.
62 63 64 65 66 67 68 69 70
 *
 * The reason we need to store a copy of the minimum key is that we'll
 * need to propagate it to the parent node when this page is linked
 * into its parent.  However, if the page is not a leaf page, the first
 * entry on the page doesn't need to contain a key, so we will not have
 * stored the key itself on the page.  (You might think we could skip
 * copying the minimum key on leaf pages, but actually we must have a
 * writable copy anyway because we'll poke the page's address into it
 * before passing it up to the parent...)
71 72 73 74 75
 */
typedef struct BTPageState
{
	Buffer		btps_buf;		/* current buffer & page */
	Page		btps_page;
76 77
	BTItem		btps_minkey;	/* copy of minimum key (first item) on
								 * page */
78
	OffsetNumber btps_lastoff;	/* last item offset loaded */
79
	int			btps_level;		/* tree level (0 = leaf) */
80 81 82
	Size		btps_full;		/* "full" if less than this much free
								 * space */
	struct BTPageState *btps_next;		/* link to parent level, if any */
83 84 85
} BTPageState;


86 87 88 89 90 91
#define BTITEMSZ(btitem) \
	((btitem) ? \
	 (IndexTupleDSize((btitem)->bti_itup) + \
	  (sizeof(BTItemData) - sizeof(IndexTupleData))) : \
	 0)

92

93
static void _bt_blnewpage(Relation index, Buffer *buf, Page *page, int flags);
94
static BTPageState *_bt_pagestate(Relation index, int flags, int level);
95 96
static void _bt_slideleft(Relation index, Buffer buf, Page page);
static void _bt_sortaddtup(Page page, Size itemsize,
97
			   BTItem btitem, OffsetNumber itup_off);
98
static void _bt_buildadd(Relation index, BTPageState *state, BTItem bti);
99
static void _bt_uppershutdown(Relation index, BTPageState *state);
100
static void _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2);
101

102 103

/*
104
 * Interface routines
105 106 107 108
 */


/*
109
 * create and initialize a spool structure
110
 */
111
BTSpool *
112
_bt_spoolinit(Relation index, bool isunique)
113
{
114
	BTSpool    *btspool = (BTSpool *) palloc(sizeof(BTSpool));
115

Bruce Momjian's avatar
Bruce Momjian committed
116
	MemSet((char *) btspool, 0, sizeof(BTSpool));
117

118 119
	btspool->index = index;
	btspool->isunique = isunique;
120

121
	btspool->sortstate = tuplesort_begin_index(index, isunique, false);
122

123
	/*
124 125 126
	 * Currently, tuplesort provides sort functions on IndexTuples. If we
	 * kept anything in a BTItem other than a regular IndexTuple, we'd
	 * need to modify tuplesort to understand BTItems as such.
127 128
	 */
	Assert(sizeof(BTItemData) == sizeof(IndexTupleData));
129

130
	return btspool;
131 132 133 134 135 136
}

/*
 * clean up a spool structure and its substructures.
 */
void
137
_bt_spooldestroy(BTSpool *btspool)
138
{
139
	tuplesort_end(btspool->sortstate);
140
	pfree((void *) btspool);
141 142 143
}

/*
144
 * spool a btitem into the sort file.
145
 */
146 147
void
_bt_spool(BTItem btitem, BTSpool *btspool)
148
{
149 150
	/* A BTItem is really just an IndexTuple */
	tuplesort_puttuple(btspool->sortstate, (void *) btitem);
151 152 153
}

/*
154 155
 * given a spool loaded by successive calls to _bt_spool,
 * create an entire btree.
156
 */
157
void
158
_bt_leafbuild(BTSpool *btspool, BTSpool *btspool2)
159
{
160
#ifdef BTREE_BUILD_STATS
161
	if (Show_btree_build_stats)
162
	{
163
		ShowUsage("BTREE BUILD (Spool) STATISTICS");
164
		ResetUsage();
165
	}
166
#endif   /* BTREE_BUILD_STATS */
167 168
	tuplesort_performsort(btspool->sortstate);

169 170 171
	if (btspool2)
		tuplesort_performsort(btspool2->sortstate);
	_bt_load(btspool->index, btspool, btspool2);
172 173 174 175
}


/*
176
 * Internal routines.
177
 */
178

179 180 181 182 183

/*
 * allocate a new, clean btree page, not linked to any siblings.
 */
static void
184
_bt_blnewpage(Relation index, Buffer *buf, Page *page, int flags)
185
{
186
	BTPageOpaque opaque;
187

188 189 190 191 192 193
	*buf = _bt_getbuf(index, P_NEW, BT_WRITE);
	*page = BufferGetPage(*buf);
	_bt_pageinit(*page, BufferGetPageSize(*buf));
	opaque = (BTPageOpaque) PageGetSpecialPointer(*page);
	opaque->btpo_prev = opaque->btpo_next = P_NONE;
	opaque->btpo_flags = flags;
194 195
}

196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
/*
 * allocate and initialize a new BTPageState.  the returned structure
 * is suitable for immediate use by _bt_buildadd.
 */
static BTPageState *
_bt_pagestate(Relation index, int flags, int level)
{
	BTPageState *state = (BTPageState *) palloc(sizeof(BTPageState));

	MemSet((char *) state, 0, sizeof(BTPageState));

	/* create initial page */
	_bt_blnewpage(index, &(state->btps_buf), &(state->btps_page), flags);

	state->btps_minkey = (BTItem) NULL;
	/* initialize lastoff so first item goes into P_FIRSTKEY */
	state->btps_lastoff = P_HIKEY;
	state->btps_level = level;
	/* set "full" threshold based on level.  See notes at head of file. */
	if (level > 0)
		state->btps_full = (PageGetPageSize(state->btps_page) * 3) / 10;
	else
		state->btps_full = PageGetPageSize(state->btps_page) / 10;
	/* no parent level, yet */
	state->btps_next = (BTPageState *) NULL;

	return state;
}

225 226
/*
 * slide an array of ItemIds back one slot (from P_FIRSTKEY to
227 228 229
 * P_HIKEY, overwriting P_HIKEY).  we need to do this when we discover
 * that we have built an ItemId array in what has turned out to be a
 * P_RIGHTMOST page.
230 231 232 233
 */
static void
_bt_slideleft(Relation index, Buffer buf, Page page)
{
234 235 236 237
	OffsetNumber off;
	OffsetNumber maxoff;
	ItemId		previi;
	ItemId		thisii;
238 239 240 241 242 243 244 245 246 247 248 249

	if (!PageIsEmpty(page))
	{
		maxoff = PageGetMaxOffsetNumber(page);
		previi = PageGetItemId(page, P_HIKEY);
		for (off = P_FIRSTKEY; off <= maxoff; off = OffsetNumberNext(off))
		{
			thisii = PageGetItemId(page, off);
			*previi = *thisii;
			previi = thisii;
		}
		((PageHeader) page)->pd_lower -= sizeof(ItemIdData);
250
	}
251 252
}

253
/*
254 255 256 257 258 259 260 261 262 263 264
 * Add an item to a page being built.
 *
 * The main difference between this routine and a bare PageAddItem call
 * is that this code knows that the leftmost data item on a non-leaf
 * btree page doesn't need to have a key.  Therefore, it strips such
 * items down to just the item header.
 *
 * This is almost like nbtinsert.c's _bt_pgaddtup(), but we can't use
 * that because it assumes that P_RIGHTMOST() will return the correct
 * answer for the page.  Here, we don't know yet if the page will be
 * rightmost.  Offset P_FIRSTKEY is always the first data key.
265
 */
266 267 268 269 270
static void
_bt_sortaddtup(Page page,
			   Size itemsize,
			   BTItem btitem,
			   OffsetNumber itup_off)
271
{
272
	BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
273
	BTItemData	truncitem;
274

275
	if (!P_ISLEAF(opaque) && itup_off == P_FIRSTKEY)
276 277 278 279 280 281
	{
		memcpy(&truncitem, btitem, sizeof(BTItemData));
		truncitem.bti_itup.t_info = sizeof(BTItemData);
		btitem = &truncitem;
		itemsize = sizeof(BTItemData);
	}
282

283 284 285
	if (PageAddItem(page, (Item) btitem, itemsize, itup_off,
					LP_USED) == InvalidOffsetNumber)
		elog(FATAL, "btree: failed to add item to the page in _bt_sort");
286 287
}

288 289
/*----------
 * Add an item to a disk page from the sort output.
290
 *
291 292 293
 * We must be careful to observe the page layout conventions of nbtsearch.c:
 * - rightmost pages start data items at P_HIKEY instead of at P_FIRSTKEY.
 * - on non-leaf pages, the key portion of the first item need not be
294
 *	 stored, we should store only the link.
295
 *
296
 * A leaf page being built looks like:
297 298
 *
 * +----------------+---------------------------------+
299
 * | PageHeaderData | linp0 linp1 linp2 ...			  |
300
 * +-----------+----+---------------------------------+
301
 * | ... linpN |									  |
302
 * +-----------+--------------------------------------+
303 304
 * |	 ^ last										  |
 * |												  |
305
 * +-------------+------------------------------------+
306
 * |			 | itemN ...						  |
307
 * +-------------+------------------+-----------------+
308
 * |		  ... item3 item2 item1 | "special space" |
309 310
 * +--------------------------------+-----------------+
 *
311 312
 * Contrast this with the diagram in bufpage.h; note the mismatch
 * between linps and items.  This is because we reserve linp0 as a
313 314
 * placeholder for the pointer to the "high key" item; when we have
 * filled up the page, we will set linp0 to point to itemN and clear
315 316
 * linpN.  On the other hand, if we find this is the last (rightmost)
 * page, we leave the items alone and slide the linp array over.
317
 *
318
 * 'last' pointer indicates the last offset added to the page.
319
 *----------
320
 */
321
static void
322
_bt_buildadd(Relation index, BTPageState *state, BTItem bti)
323
{
324 325 326 327 328
	Buffer		nbuf;
	Page		npage;
	OffsetNumber last_off;
	Size		pgspc;
	Size		btisz;
329 330 331 332 333 334 335

	nbuf = state->btps_buf;
	npage = state->btps_page;
	last_off = state->btps_lastoff;

	pgspc = PageGetFreeSpace(npage);
	btisz = BTITEMSZ(bti);
336
	btisz = MAXALIGN(btisz);
337 338

	/*
339 340 341 342 343
	 * Check whether the item can fit on a btree page at all. (Eventually,
	 * we ought to try to apply TOAST methods if not.) We actually need to
	 * be able to fit three items on every page, so restrict any one item
	 * to 1/3 the per-page available space. Note that at this point, btisz
	 * doesn't include the ItemId.
344 345
	 *
	 * NOTE: similar code appears in _bt_insertonpg() to defend against
346 347
	 * oversize items being inserted into an already-existing index. But
	 * during creation of an index, we don't go through there.
348
	 */
349
	if (btisz > (PageGetPageSize(npage) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) / 3 - sizeof(ItemIdData))
350
		elog(ERROR, "btree: index item size %lu exceeds maximum %ld",
351 352
			 (unsigned long) btisz,
			 (PageGetPageSize(npage) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) / 3 - sizeof(ItemIdData));
353

354
	if (pgspc < btisz || pgspc < state->btps_full)
355
	{
356
		/*
357 358
		 * Item won't fit on this page, or we feel the page is full enough
		 * already.  Finish off the page and write it out.
359
		 */
360 361 362 363
		Buffer		obuf = nbuf;
		Page		opage = npage;
		ItemId		ii;
		ItemId		hii;
364
		BTItem		obti;
365

366 367 368
		/* Create new page */
		_bt_blnewpage(index, &nbuf, &npage,
					  (state->btps_level > 0) ? 0 : BTP_LEAF);
369 370

		/*
371 372
		 * We copy the last item on the page into the new page, and then
		 * rearrange the old page so that the 'last item' becomes its high
373 374 375 376
		 * key rather than a true data item.  There had better be at least
		 * two items on the page already, else the page would be empty of
		 * useful data.  (Hence, we must allow pages to be packed at least
		 * 2/3rds full; the 70% figure used above is close to minimum.)
377
		 */
378
		Assert(last_off > P_FIRSTKEY);
379
		ii = PageGetItemId(opage, last_off);
380 381
		obti = (BTItem) PageGetItem(opage, ii);
		_bt_sortaddtup(npage, ItemIdGetLength(ii), obti, P_FIRSTKEY);
382

383
		/*
384
		 * Move 'last' into the high key position on opage
385 386 387 388 389
		 */
		hii = PageGetItemId(opage, P_HIKEY);
		*hii = *ii;
		ii->lp_flags &= ~LP_USED;
		((PageHeader) opage)->pd_lower -= sizeof(ItemIdData);
390

391
		/*
392 393 394
		 * Link the old buffer into its parent, using its minimum key. If
		 * we don't have a parent, we have to create one; this adds a new
		 * btree level.
395
		 */
396 397 398 399 400 401 402 403 404 405
		if (state->btps_next == (BTPageState *) NULL)
		{
			state->btps_next =
				_bt_pagestate(index, 0, state->btps_level + 1);
		}
		Assert(state->btps_minkey != NULL);
		ItemPointerSet(&(state->btps_minkey->bti_itup.t_tid),
					   BufferGetBlockNumber(obuf), P_HIKEY);
		_bt_buildadd(index, state->btps_next, state->btps_minkey);
		pfree((void *) state->btps_minkey);
406

407
		/*
408
		 * Save a copy of the minimum key for the new page.  We have to
409 410
		 * copy it off the old page, not the new one, in case we are not
		 * at leaf level.
411 412 413 414 415 416 417
		 */
		state->btps_minkey = _bt_formitem(&(obti->bti_itup));

		/*
		 * Set the sibling links for both pages, and parent links too.
		 *
		 * It's not necessary to set the parent link at all, because it's
418 419 420 421 422 423 424
		 * only used for handling concurrent root splits, but we may as
		 * well do it as a debugging aid.  Note we set new page's link as
		 * well as old's, because if the new page turns out to be the last
		 * of the level, _bt_uppershutdown won't change it.  The links may
		 * be out of date by the time the build finishes, but that's OK;
		 * they need only point to a left-sibling of the true parent.  See
		 * the README file for more info.
425 426
		 */
		{
427 428
			BTPageOpaque oopaque = (BTPageOpaque) PageGetSpecialPointer(opage);
			BTPageOpaque nopaque = (BTPageOpaque) PageGetSpecialPointer(npage);
429 430 431 432

			oopaque->btpo_next = BufferGetBlockNumber(nbuf);
			nopaque->btpo_prev = BufferGetBlockNumber(obuf);
			nopaque->btpo_next = P_NONE;
433 434
			oopaque->btpo_parent = nopaque->btpo_parent =
				BufferGetBlockNumber(state->btps_next->btps_buf);
435 436 437
		}

		/*
438
		 * Write out the old page.	We never want to see it again, so we
439 440
		 * can give up our lock (if we had one; most likely BuildingBtree
		 * is set, so we aren't locking).
441
		 */
442
		_bt_wrtbuf(index, obuf);
443 444

		/*
445
		 * Reset last_off to point to new page
446
		 */
447
		last_off = P_FIRSTKEY;
448 449
	}

450
	/*
451 452
	 * If the new item is the first for its page, stash a copy for later.
	 * Note this will only happen for the first item on a level; on later
453 454
	 * pages, the first item for a page is copied from the prior page in
	 * the code above.
455
	 */
456
	if (last_off == P_HIKEY)
457
	{
458 459
		Assert(state->btps_minkey == NULL);
		state->btps_minkey = _bt_formitem(&(bti->bti_itup));
460
	}
461 462 463 464 465 466

	/*
	 * Add the new item into the current page.
	 */
	last_off = OffsetNumberNext(last_off);
	_bt_sortaddtup(npage, btisz, bti, last_off);
467 468 469 470

	state->btps_buf = nbuf;
	state->btps_page = npage;
	state->btps_lastoff = last_off;
471 472
}

473 474 475
/*
 * Finish writing out the completed btree.
 */
476
static void
477
_bt_uppershutdown(Relation index, BTPageState *state)
478
{
479
	BTPageState *s;
480

481 482 483
	/*
	 * Each iteration of this loop completes one more level of the tree.
	 */
484 485
	for (s = state; s != (BTPageState *) NULL; s = s->btps_next)
	{
486 487 488
		BlockNumber blkno;
		BTPageOpaque opaque;

489 490
		blkno = BufferGetBlockNumber(s->btps_buf);
		opaque = (BTPageOpaque) PageGetSpecialPointer(s->btps_page);
491

492
		/*
493 494 495 496
		 * We have to link the last page on this level to somewhere.
		 *
		 * If we're at the top, it's the root, so attach it to the metapage.
		 * Otherwise, add an entry for it to its parent using its minimum
497 498
		 * key.  This may cause the last page of the parent level to
		 * split, but that's not a problem -- we haven't gotten to it yet.
499
		 */
500
		if (s->btps_next == (BTPageState *) NULL)
501
		{
502 503 504 505 506
			opaque->btpo_flags |= BTP_ROOT;
			_bt_metaproot(index, blkno, s->btps_level + 1);
		}
		else
		{
507 508 509 510 511 512
			Assert(s->btps_minkey != NULL);
			ItemPointerSet(&(s->btps_minkey->bti_itup.t_tid),
						   blkno, P_HIKEY);
			_bt_buildadd(index, s->btps_next, s->btps_minkey);
			pfree((void *) s->btps_minkey);
			s->btps_minkey = NULL;
513
		}
514

515
		/*
516
		 * This is the rightmost page, so the ItemId array needs to be
517
		 * slid back one slot.	Then we can dump out the page.
518 519 520 521
		 */
		_bt_slideleft(index, s->btps_buf, s->btps_page);
		_bt_wrtbuf(index, s->btps_buf);
	}
522 523 524
}

/*
525 526
 * Read tuples in correct sort order from tuplesort, and load them into
 * btree leaves.
527
 */
528
static void
529
_bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2)
530
{
531
	BTPageState *state = NULL;
532
	bool		merge = (btspool2 != NULL);
533 534 535 536 537
	BTItem		bti,
				bti2 = NULL;
	bool		should_free,
				should_free2,
				load1;
538
	TupleDesc	tupdes = RelationGetDescr(index);
539 540
	int			i,
				keysz = RelationGetNumberOfAttributes(index);
541 542 543
	ScanKey		indexScanKey = NULL;

	if (merge)
544
	{
545
		/*
546 547 548 549 550 551 552 553 554
		 * Another BTSpool for dead tuples exists. Now we have to merge
		 * btspool and btspool2.
		 */
		ScanKey		entry;
		Datum		attrDatum1,
					attrDatum2;
		bool		isFirstNull,
					isSecondNull;
		int32		compare;
555 556 557 558 559 560 561

		/* the preparation of merge */
		bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free);
		bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate, true, &should_free2);
		indexScanKey = _bt_mkscankey_nodata(index);
		for (;;)
		{
562
			load1 = true;		/* load BTSpool next ? */
563 564 565 566 567 568 569 570 571 572 573
			if (NULL == bti2)
			{
				if (NULL == bti)
					break;
			}
			else if (NULL != bti)
			{

				for (i = 1; i <= keysz; i++)
				{
					entry = indexScanKey + i - 1;
574 575
					attrDatum1 = index_getattr((IndexTuple) bti, i, tupdes, &isFirstNull);
					attrDatum2 = index_getattr((IndexTuple) bti2, i, tupdes, &isSecondNull);
576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595
					if (isFirstNull)
					{
						if (!isSecondNull)
						{
							load1 = false;
							break;
						}
					}
					else if (isSecondNull)
						break;
					else
					{
						compare = DatumGetInt32(FunctionCall2(&entry->sk_func, attrDatum1, attrDatum2));
						if (compare > 0)
						{
							load1 = false;
							break;
						}
						else if (compare < 0)
							break;
596
					}
597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622
				}
			}
			else
				load1 = false;

			/* When we see first tuple, create first index page */
			if (state == NULL)
				state = _bt_pagestate(index, BTP_LEAF, 0);

			if (load1)
			{
				_bt_buildadd(index, state, bti);
				if (should_free)
					pfree((void *) bti);
				bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free);
			}
			else
			{
				_bt_buildadd(index, state, bti2);
				if (should_free2)
					pfree((void *) bti2);
				bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate, true, &should_free2);
			}
		}
		_bt_freeskey(indexScanKey);
	}
623 624
	else
/* merge is unnecessary */
625 626 627 628 629 630
	{
		while (bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free), bti != (BTItem) NULL)
		{
			/* When we see first tuple, create first index page */
			if (state == NULL)
				state = _bt_pagestate(index, BTP_LEAF, 0);
631

632 633 634 635
			_bt_buildadd(index, state, bti);
			if (should_free)
				pfree((void *) bti);
		}
636
	}
637

638
	/* Close down final pages, if we had any data at all */
639 640
	if (state != NULL)
		_bt_uppershutdown(index, state);
641
}