diff options
Diffstat (limited to 'src/backend/access/nbtree/nbtsort.c')
| -rw-r--r-- | src/backend/access/nbtree/nbtsort.c | 1000 |
1 files changed, 89 insertions, 911 deletions
diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c index c1564544b0..48386c113f 100644 --- a/src/backend/access/nbtree/nbtsort.c +++ b/src/backend/access/nbtree/nbtsort.c @@ -1,68 +1,47 @@ /*------------------------------------------------------------------------- - * btsort.c - * - * Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $Id: nbtsort.c,v 1.46 1999/07/19 07:07:19 momjian Exp $ + * nbtsort.c + * Build a btree from sorted input by loading leaf pages sequentially. * * NOTES * - * what we do is: - * - generate a set of initial one-block runs, distributed round-robin - * between the output tapes. - * - for each pass, - * - swap input and output tape sets, rewinding both and truncating - * the output tapes. - * - merge the current run in each input tape to the current output - * tape. - * - when each input run has been exhausted, switch to another output - * tape and start processing another run. - * - when we have fewer runs than tapes, we know we are ready to start - * merging into the btree leaf pages. (i.e., we do not have to wait - * until we have exactly one tape.) - * - as we extract tuples from the final runs, we build the pages for - * each 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. - * - * conventions: - * - external interface routines take in and return "void *" for their - * opaque handles. this is for modularity reasons. + * 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 + * for each 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. * * this code is moderately slow (~10% slower) compared to the regular * btree (insertion) build code on sorted or well-clustered data. on * random data, however, the insertion build code is unusable -- the * difference on a 60MB heap is a factor of 15 because the random - * probes into the btree thrash the buffer pool. + * 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.) * * this code currently packs the pages to 100% of capacity. this is * not wise, since *any* insertion will cause splitting. filling to * something like the standard 70% steady-state load factor for btrees * would probably be better. * - * somebody desperately needs to figure out how to do a better job of - * balancing the merge passes -- the fan-in on the final merges can be - * pretty poor, which is bad for performance. + * + * Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.47 1999/10/17 22:15:04 tgl Exp $ + * *------------------------------------------------------------------------- */ -#include <fcntl.h> - #include "postgres.h" #include "access/nbtree.h" +#include "utils/tuplesort.h" #ifdef BTREE_BUILD_STATS #define ShowExecutorStats pg_options[TRACE_EXECUTORSTATS] #endif -static BTItem _bt_buildadd(Relation index, void *pstate, BTItem bti, int flags); -static BTItem _bt_minitem(Page opage, BlockNumber oblkno, int atend); -static void *_bt_pagestate(Relation index, int flags, int level, bool doupper); -static void _bt_uppershutdown(Relation index, BTPageState *state); - /* * turn on debugging output. * @@ -70,689 +49,108 @@ static void _bt_uppershutdown(Relation index, BTPageState *state); * only really useful for integer keys. */ /*#define FASTBUILD_DEBUG*/ -#define FASTBUILD_SPOOL -#define FASTBUILD_MERGE - -#define MAXTAPES (7) -#define TAPEBLCKSZ (BLCKSZ << 2) - -extern int NDirectFileRead; -extern int NDirectFileWrite; - -/* - * this is what we use to shovel BTItems in and out of memory. it's - * bigger than a standard block because we are doing a lot of strictly - * sequential i/o. this is obviously something of a tradeoff since we - * are potentially reading a bunch of zeroes off of disk in many - * cases. - * - * BTItems are packed in and MAXALIGN'd. - * - * the fd should not be going out to disk, strictly speaking, but it's - * the only thing like that so i'm not going to worry about wasting a - * few bytes. - */ -typedef struct -{ - int bttb_magic; /* magic number */ - File bttb_fd; /* file descriptor */ - int bttb_top; /* top of free space within bttb_data */ - short bttb_ntup; /* number of tuples in this block */ - short bttb_eor; /* End-Of-Run marker */ - char bttb_data[TAPEBLCKSZ - 2 * sizeof(double)]; -} BTTapeBlock; /* - * this structure holds the bookkeeping for a simple balanced multiway - * merge. (polyphase merging is hairier than i want to get into right - * now, and i don't see why i have to care how many "tapes" i use - * right now. though if psort was in a condition that i could hack it - * to do this, you bet i would.) + * Status record for spooling. */ -typedef struct +struct BTSpool { - int bts_ntapes; - int bts_tape; - BTTapeBlock **bts_itape; /* input tape blocks */ - BTTapeBlock **bts_otape; /* output tape blocks */ + Tuplesortstate *sortstate; /* state data for tuplesort.c */ + Relation index; bool isunique; -} BTSpool; - -/*------------------------------------------------------------------------- - * sorting comparison routine - returns {-1,0,1} depending on whether - * the key in the left BTItem is {<,=,>} the key in the right BTItem. - * - * we want to use _bt_isortcmp as a comparison function for qsort(3), - * but it needs extra arguments, so we "pass them in" as global - * variables. ick. fortunately, they are the same throughout the - * build, so we need do this only once. this is why you must call - * _bt_isortcmpinit before the call to qsort(3). - * - * a NULL BTItem is always assumed to be greater than any actual - * value; our heap routines (see below) assume that the smallest - * element in the heap is returned. that way, NULL values from the - * exhausted tapes can sift down to the bottom of the heap. in point - * of fact we just don't replace the elements of exhausted tapes, but - * what the heck. - * *------------------------------------------------------------------------- - */ -typedef struct -{ - Datum *btsk_datum; - char *btsk_nulls; - BTItem btsk_item; -} BTSortKey; - -static Relation _bt_sortrel; -static int _bt_nattr; -static BTSpool *_bt_inspool; - -static void -_bt_isortcmpinit(Relation index, BTSpool *spool) -{ - _bt_sortrel = index; - _bt_inspool = spool; - _bt_nattr = index->rd_att->natts; -} - -static int -_bt_isortcmp(BTSortKey *k1, BTSortKey *k2) -{ - Datum *k1_datum = k1->btsk_datum; - Datum *k2_datum = k2->btsk_datum; - char *k1_nulls = k1->btsk_nulls; - char *k2_nulls = k2->btsk_nulls; - bool equal_isnull = false; - int i; - - if (k1->btsk_item == (BTItem) NULL) - { - if (k2->btsk_item == (BTItem) NULL) - return 0; /* 1 = 2 */ - return 1; /* 1 > 2 */ - } - else if (k2->btsk_item == (BTItem) NULL) - return -1; /* 1 < 2 */ - - for (i = 0; i < _bt_nattr; i++) - { - if (k1_nulls[i] != ' ') /* k1 attr is NULL */ - { - if (k2_nulls[i] != ' ') /* the same for k2 */ - { - equal_isnull = true; - continue; - } - return 1; /* NULL ">" NOT_NULL */ - } - else if (k2_nulls[i] != ' ') /* k2 attr is NULL */ - return -1; /* NOT_NULL "<" NULL */ - - if (_bt_invokestrat(_bt_sortrel, i + 1, BTGreaterStrategyNumber, - k1_datum[i], k2_datum[i])) - return 1; /* 1 > 2 */ - else if (_bt_invokestrat(_bt_sortrel, i + 1, BTGreaterStrategyNumber, - k2_datum[i], k1_datum[i])) - return -1; /* 1 < 2 */ - } - - if (_bt_inspool->isunique && !equal_isnull) - { - _bt_spooldestroy((void *) _bt_inspool); - elog(ERROR, "Cannot create unique index. Table contains non-unique values"); - } - return 0; /* 1 = 2 */ -} - -static void -_bt_setsortkey(Relation index, BTItem bti, BTSortKey *sk) -{ - sk->btsk_item = (BTItem) NULL; - sk->btsk_datum = (Datum *) NULL; - sk->btsk_nulls = (char *) NULL; - - if (bti != (BTItem) NULL) - { - IndexTuple it = &(bti->bti_itup); - TupleDesc itdesc = index->rd_att; - Datum *dp = (Datum *) palloc(_bt_nattr * sizeof(Datum)); - char *np = (char *) palloc(_bt_nattr * sizeof(char)); - bool isnull; - int i; - - for (i = 0; i < _bt_nattr; i++) - { - dp[i] = index_getattr(it, i + 1, itdesc, &isnull); - if (isnull) - np[i] = 'n'; - else - np[i] = ' '; - } - sk->btsk_item = bti; - sk->btsk_datum = dp; - sk->btsk_nulls = np; - } -} - -/*------------------------------------------------------------------------- - * priority queue methods - * - * these were more-or-less lifted from the heap section of the 1984 - * edition of gonnet's book on algorithms and data structures. they - * are coded so that the smallest element in the heap is returned (we - * use them for merging sorted runs). - * - * XXX these probably ought to be generic library functions. - *------------------------------------------------------------------------- - */ -typedef struct -{ - int btpqe_tape; /* tape identifier */ - BTSortKey btpqe_item; /* pointer to BTItem in tape buffer */ -} BTPriQueueElem; - -#define MAXELEM MAXTAPES -typedef struct -{ - int btpq_nelem; - BTPriQueueElem btpq_queue[MAXELEM]; - Relation btpq_rel; -} BTPriQueue; - -/* be sure to call _bt_isortcmpinit first */ -#define GREATER(a, b) \ - (_bt_isortcmp(&((a)->btpqe_item), &((b)->btpqe_item)) > 0) - -static void -_bt_pqsift(BTPriQueue *q, int parent) -{ - int child; - BTPriQueueElem e; - - for (child = parent * 2 + 1; - child < q->btpq_nelem; - child = parent * 2 + 1) - { - if (child < q->btpq_nelem - 1) - { - if (GREATER(&(q->btpq_queue[child]), &(q->btpq_queue[child + 1]))) - ++child; - } - if (GREATER(&(q->btpq_queue[parent]), &(q->btpq_queue[child]))) - { - e = q->btpq_queue[child]; /* struct = */ - q->btpq_queue[child] = q->btpq_queue[parent]; /* struct = */ - q->btpq_queue[parent] = e; /* struct = */ - parent = child; - } - else - parent = child + 1; - } -} - -static int -_bt_pqnext(BTPriQueue *q, BTPriQueueElem *e) -{ - if (q->btpq_nelem < 1) - { /* already empty */ - return -1; - } - *e = q->btpq_queue[0]; /* struct = */ - - if (--q->btpq_nelem < 1) - { /* now empty, don't sift */ - return 0; - } - q->btpq_queue[0] = q->btpq_queue[q->btpq_nelem]; /* struct = */ - _bt_pqsift(q, 0); - return 0; -} - -static void -_bt_pqadd(BTPriQueue *q, BTPriQueueElem *e) -{ - int child, - parent; - - if (q->btpq_nelem >= MAXELEM) - elog(ERROR, "_bt_pqadd: queue overflow"); - - child = q->btpq_nelem++; - while (child > 0) - { - parent = child / 2; - if (GREATER(e, &(q->btpq_queue[parent]))) - break; - else - { - q->btpq_queue[child] = q->btpq_queue[parent]; /* struct = */ - child = parent; - } - } - - q->btpq_queue[child] = *e; /* struct = */ -} - -/*------------------------------------------------------------------------- - * tape methods - *------------------------------------------------------------------------- - */ +}; #define BTITEMSZ(btitem) \ ((btitem) ? \ (IndexTupleDSize((btitem)->bti_itup) + \ (sizeof(BTItemData) - sizeof(IndexTupleData))) : \ 0) -#define SPCLEFT(tape) \ - (sizeof((tape)->bttb_data) - (tape)->bttb_top) -#define EMPTYTAPE(tape) \ - ((tape)->bttb_ntup <= 0) -#define BTTAPEMAGIC 0x19660226 - -/* - * reset the tape header for its next use without doing anything to - * the physical tape file. (setting bttb_top to 0 makes the block - * empty.) - */ -static void -_bt_tapereset(BTTapeBlock *tape) -{ - tape->bttb_eor = 0; - tape->bttb_top = 0; - tape->bttb_ntup = 0; -} - -/* - * rewind the physical tape file. - */ -static void -_bt_taperewind(BTTapeBlock *tape) -{ - FileSeek(tape->bttb_fd, 0L, SEEK_SET); -} - -/* - * destroy the contents of the physical tape file without destroying - * the tape data structure or removing the physical tape file. - * - * we use the VFD version of ftruncate(2) to do this rather than - * unlinking and recreating the file. you still have to wait while - * the OS frees up all of the file system blocks and stuff, but at - * least you don't have to delete and reinsert the directory entries. - */ -static void -_bt_tapeclear(BTTapeBlock *tape) -{ - /* blow away the contents of the old file */ - _bt_taperewind(tape); -#ifdef NOT_USED - FileSync(tape->bttb_fd); -#endif - FileTruncate(tape->bttb_fd, 0); - - /* reset the buffer */ - _bt_tapereset(tape); -} - -/* - * create a new BTTapeBlock, allocating memory for the data structure - * as well as opening a physical tape file. - */ -static BTTapeBlock * -_bt_tapecreate(void) -{ - BTTapeBlock *tape = (BTTapeBlock *) palloc(sizeof(BTTapeBlock)); - - if (tape == (BTTapeBlock *) NULL) - elog(ERROR, "_bt_tapecreate: out of memory"); - - tape->bttb_magic = BTTAPEMAGIC; - - tape->bttb_fd = OpenTemporaryFile(); - Assert(tape->bttb_fd >= 0); - - /* initialize the buffer */ - _bt_tapereset(tape); - - return tape; -} - -/* - * destroy the BTTapeBlock structure and its physical tape file. - */ -static void -_bt_tapedestroy(BTTapeBlock *tape) -{ - FileUnlink(tape->bttb_fd); - pfree((void *) tape); -} - -/* - * flush the tape block to the file, marking End-Of-Run if requested. - */ -static void -_bt_tapewrite(BTTapeBlock *tape, int eor) -{ - tape->bttb_eor = eor; - FileWrite(tape->bttb_fd, (char *) tape, TAPEBLCKSZ); - NDirectFileWrite += TAPEBLCKSZ / BLCKSZ; - _bt_tapereset(tape); -} - -/* - * read a tape block from the file, overwriting the current contents - * of the buffer. - * - * returns: - * - 0 if there are no more blocks in the tape or in this run (call - * _bt_tapereset to clear the End-Of-Run marker) - * - 1 if a valid block was read - */ -static int -_bt_taperead(BTTapeBlock *tape) -{ - File fd; - int nread; - - if (tape->bttb_eor) - { - return 0; /* we are already at End-Of-Run */ - } - - /* - * we're clobbering the old tape block, but we do need to save the VFD - * (the one in the block we're reading is bogus). - */ - fd = tape->bttb_fd; - nread = FileRead(fd, (char *) tape, TAPEBLCKSZ); - tape->bttb_fd = fd; - if (nread != TAPEBLCKSZ) - { - Assert(nread == 0); /* we are at EOF */ - return 0; - } - Assert(tape->bttb_magic == BTTAPEMAGIC); - NDirectFileRead += TAPEBLCKSZ / BLCKSZ; - return 1; -} -/* - * get the next BTItem from a tape block. - * - * returns: - * - NULL if we have run out of BTItems - * - a pointer to the BTItemData in the block otherwise - * - * side effects: - * - sets 'pos' to the current position within the block. - */ -static BTItem -_bt_tapenext(BTTapeBlock *tape, char **pos) -{ - Size itemsz; - BTItem bti; +static void _bt_load(Relation index, BTSpool *btspool); +static BTItem _bt_buildadd(Relation index, BTPageState *state, BTItem bti, + int flags); +static BTItem _bt_minitem(Page opage, BlockNumber oblkno, int atend); +static BTPageState *_bt_pagestate(Relation index, int flags, + int level, bool doupper); +static void _bt_uppershutdown(Relation index, BTPageState *state); - if (*pos >= tape->bttb_data + tape->bttb_top) - return (BTItem) NULL; - bti = (BTItem) *pos; - itemsz = BTITEMSZ(bti); - *pos += MAXALIGN(itemsz); - return bti; -} /* - * copy a BTItem into a tape block. - * - * assumes that we have already checked to see if the block has enough - * space for the item. - * - * side effects: - * - * - advances the 'top' pointer in the tape block header to point to - * the beginning of free space. + * Interface routines */ -static void -_bt_tapeadd(BTTapeBlock *tape, BTItem item, int itemsz) -{ - memcpy(tape->bttb_data + tape->bttb_top, item, itemsz); - ++tape->bttb_ntup; - tape->bttb_top += MAXALIGN(itemsz); -} -/*------------------------------------------------------------------------- - * spool methods - *------------------------------------------------------------------------- - */ /* - * create and initialize a spool structure, including the underlying - * files. + * create and initialize a spool structure */ -void * -_bt_spoolinit(Relation index, int ntapes, bool isunique) +BTSpool * +_bt_spoolinit(Relation index, bool isunique) { BTSpool *btspool = (BTSpool *) palloc(sizeof(BTSpool)); - int i; - if (btspool == (BTSpool *) NULL) - elog(ERROR, "_bt_spoolinit: out of memory"); MemSet((char *) btspool, 0, sizeof(BTSpool)); - btspool->bts_ntapes = ntapes; - btspool->bts_tape = 0; - btspool->isunique = isunique; - btspool->bts_itape = (BTTapeBlock **) palloc(sizeof(BTTapeBlock *) * ntapes); - btspool->bts_otape = (BTTapeBlock **) palloc(sizeof(BTTapeBlock *) * ntapes); - if (btspool->bts_itape == (BTTapeBlock **) NULL || - btspool->bts_otape == (BTTapeBlock **) NULL) - elog(ERROR, "_bt_spoolinit: out of memory"); + btspool->index = index; + btspool->isunique = isunique; - for (i = 0; i < ntapes; ++i) - { - btspool->bts_itape[i] = _bt_tapecreate(); - btspool->bts_otape[i] = _bt_tapecreate(); - } + btspool->sortstate = tuplesort_begin_index(index, isunique, false); - _bt_isortcmpinit(index, btspool); + /* + * 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. + */ + Assert(sizeof(BTItemData) == sizeof(IndexTupleData)); - return (void *) btspool; + return btspool; } /* * clean up a spool structure and its substructures. */ void -_bt_spooldestroy(void *spool) +_bt_spooldestroy(BTSpool *btspool) { - BTSpool *btspool = (BTSpool *) spool; - int i; - - for (i = 0; i < btspool->bts_ntapes; ++i) - { - _bt_tapedestroy(btspool->bts_otape[i]); - _bt_tapedestroy(btspool->bts_itape[i]); - } + tuplesort_end(btspool->sortstate); pfree((void *) btspool); } /* - * flush out any dirty output tape blocks + * spool a btitem into the sort file. */ -static void -_bt_spoolflush(BTSpool *btspool) +void +_bt_spool(BTItem btitem, BTSpool *btspool) { - int i; - - for (i = 0; i < btspool->bts_ntapes; ++i) - { - if (!EMPTYTAPE(btspool->bts_otape[i])) - _bt_tapewrite(btspool->bts_otape[i], 1); - } + /* A BTItem is really just an IndexTuple */ + tuplesort_puttuple(btspool->sortstate, (void *) btitem); } /* - * swap input tapes and output tapes by swapping their file - * descriptors. additional preparation for the next merge pass - * includes rewinding the new input tapes and clearing out the new - * output tapes. + * given a spool loaded by successive calls to _bt_spool, + * create an entire btree. */ -static void -_bt_spoolswap(BTSpool *btspool) +void +_bt_leafbuild(BTSpool *btspool) { - File tmpfd; - BTTapeBlock *itape; - BTTapeBlock *otape; - int i; - - for (i = 0; i < btspool->bts_ntapes; ++i) +#ifdef BTREE_BUILD_STATS + if (ShowExecutorStats) { - itape = btspool->bts_itape[i]; - otape = btspool->bts_otape[i]; - - /* - * swap the input and output VFDs. - */ - tmpfd = itape->bttb_fd; - itape->bttb_fd = otape->bttb_fd; - otape->bttb_fd = tmpfd; - - /* - * rewind the new input tape. - */ - _bt_taperewind(itape); - _bt_tapereset(itape); - - /* - * clear the new output tape -- it's ok to throw away the old - * inputs. - */ - _bt_tapeclear(otape); + fprintf(stderr, "! BtreeBuild (Spool) Stats:\n"); + ShowUsage(); + ResetUsage(); } +#endif + tuplesort_performsort(btspool->sortstate); + + _bt_load(btspool->index, btspool); } -/*------------------------------------------------------------------------- - * sorting routines - *------------------------------------------------------------------------- - */ /* - * spool 'btitem' into an initial run. as tape blocks are filled, the - * block BTItems are qsorted and written into some output tape (it - * doesn't matter which; we go round-robin for simplicity). the - * initial runs are therefore always just one block. + * Internal routines. */ -void -_bt_spool(Relation index, BTItem btitem, void *spool) -{ - BTSpool *btspool = (BTSpool *) spool; - BTTapeBlock *itape; - Size itemsz; - - _bt_isortcmpinit(index, btspool); - itape = btspool->bts_itape[btspool->bts_tape]; - itemsz = BTITEMSZ(btitem); - itemsz = MAXALIGN(itemsz); - - /* - * if this buffer is too full for this BTItemData, or if we have run - * out of BTItems, we need to sort the buffer and write it out. in - * this case, the BTItemData will go into the next tape's buffer. - */ - if (btitem == (BTItem) NULL || SPCLEFT(itape) < itemsz) - { - BTSortKey *parray = (BTSortKey *) NULL; - BTTapeBlock *otape; - BTItem bti; - char *pos; - int btisz; - int it_ntup = itape->bttb_ntup; - int i; - - /* - * build an array of pointers to the BTItemDatas on the input - * block. - */ - if (it_ntup > 0) - { - parray = (BTSortKey *) palloc(it_ntup * sizeof(BTSortKey)); - pos = itape->bttb_data; - for (i = 0; i < it_ntup; ++i) - _bt_setsortkey(index, _bt_tapenext(itape, &pos), &(parray[i])); - - /* - * qsort the pointer array. - */ - qsort((void *) parray, it_ntup, sizeof(BTSortKey), - (int (*) (const void *, const void *)) _bt_isortcmp); - } - - /* - * write the spooled run into the output tape. we copy the - * BTItemDatas in the order dictated by the sorted array of - * BTItems, not the original order. - * - * (since everything was MAXALIGN'd and is all on a single tape - * block, everything had *better* still fit on one tape block..) - */ - otape = btspool->bts_otape[btspool->bts_tape]; - for (i = 0; i < it_ntup; ++i) - { - bti = parray[i].btsk_item; - btisz = BTITEMSZ(bti); - btisz = MAXALIGN(btisz); - _bt_tapeadd(otape, bti, btisz); -#if defined(FASTBUILD_DEBUG) && defined(FASTBUILD_SPOOL) - { - bool isnull; - Datum d = index_getattr(&(bti->bti_itup), 1, index->rd_att, - &isnull); - - printf("_bt_spool: inserted <%x> into output tape %d\n", - d, btspool->bts_tape); - } -#endif /* FASTBUILD_DEBUG && FASTBUILD_SPOOL */ - } - - /* - * the initial runs are always single tape blocks. flush the - * output block, marking End-Of-Run. - */ - _bt_tapewrite(otape, 1); - - /* - * reset the input buffer for the next run. we don't have to - * write it out or anything -- we only use it to hold the unsorted - * BTItemDatas, the output tape contains all the sorted stuff. - * - * changing bts_tape changes the output tape and input tape; we - * change itape for the code below. - */ - _bt_tapereset(itape); - btspool->bts_tape = (btspool->bts_tape + 1) % btspool->bts_ntapes; - itape = btspool->bts_itape[btspool->bts_tape]; - - /* - * destroy the pointer array. - */ - if (parray != (BTSortKey *) NULL) - { - for (i = 0; i < it_ntup; i++) - { - if (parray[i].btsk_datum != (Datum *) NULL) - pfree((void *) (parray[i].btsk_datum)); - if (parray[i].btsk_nulls != (char *) NULL) - pfree((void *) (parray[i].btsk_nulls)); - } - pfree((void *) parray); - } - } - - /* insert this item into the current buffer */ - if (btitem != (BTItem) NULL) - _bt_tapeadd(itape, btitem, itemsz); -} /* * allocate a new, clean btree page, not linked to any siblings. @@ -805,7 +203,7 @@ _bt_slideleft(Relation index, Buffer buf, Page page) * allocate and initialize a new BTPageState. the returned structure * is suitable for immediate use by _bt_buildadd. */ -static void * +static BTPageState * _bt_pagestate(Relation index, int flags, int level, bool doupper) { BTPageState *state = (BTPageState *) palloc(sizeof(BTPageState)); @@ -819,7 +217,7 @@ _bt_pagestate(Relation index, int flags, int level, bool doupper) state->btps_level = level; state->btps_doupper = doupper; - return (void *) state; + return state; } /* @@ -883,9 +281,8 @@ _bt_minitem(Page opage, BlockNumber oblkno, int atend) * if all keys are unique, 'first' will always be the same as 'last'. */ static BTItem -_bt_buildadd(Relation index, void *pstate, BTItem bti, int flags) +_bt_buildadd(Relation index, BTPageState *state, BTItem bti, int flags) { - BTPageState *state = (BTPageState *) pstate; Buffer nbuf; Page npage; BTItem last_bti; @@ -944,8 +341,7 @@ _bt_buildadd(Relation index, void *pstate, BTItem bti, int flags) if (PageAddItem(npage, PageGetItem(opage, ii), ii->lp_len, n, LP_USED) == InvalidOffsetNumber) elog(FATAL, "btree: failed to add item to the page in _bt_sort (1)"); -#ifdef NOT_USED -#if defined(FASTBUILD_DEBUG) && defined(FASTBUILD_MERGE) +#ifdef FASTBUILD_DEBUG { bool isnull; BTItem tmpbti = @@ -956,7 +352,6 @@ _bt_buildadd(Relation index, void *pstate, BTItem bti, int flags) printf("_bt_buildadd: moved <%x> to offset %d at level %d\n", d, n, state->btps_level); } -#endif /* FASTBUILD_DEBUG && FASTBUILD_MERGE */ #endif } @@ -989,7 +384,7 @@ _bt_buildadd(Relation index, void *pstate, BTItem bti, int flags) nopaque->btpo_prev = BufferGetBlockNumber(obuf); nopaque->btpo_next = P_NONE; - if (_bt_itemcmp(index, _bt_nattr, + if (_bt_itemcmp(index, index->rd_att->natts, (BTItem) PageGetItem(opage, PageGetItemId(opage, P_HIKEY)), (BTItem) PageGetItem(opage, PageGetItemId(opage, P_FIRSTKEY)), BTEqualStrategyNumber)) @@ -1030,8 +425,7 @@ _bt_buildadd(Relation index, void *pstate, BTItem bti, int flags) off = OffsetNumberNext(last_off); if (PageAddItem(npage, (Item) bti, btisz, off, LP_USED) == InvalidOffsetNumber) elog(FATAL, "btree: failed to add item to the page in _bt_sort (2)"); -#ifdef NOT_USED -#if defined(FASTBUILD_DEBUG) && defined(FASTBUILD_MERGE) +#ifdef FASTBUILD_DEBUG { bool isnull; Datum d = index_getattr(&(bti->bti_itup), 1, index->rd_att, &isnull); @@ -1039,11 +433,10 @@ _bt_buildadd(Relation index, void *pstate, BTItem bti, int flags) printf("_bt_buildadd: inserted <%x> at offset %d at level %d\n", d, off, state->btps_level); } -#endif /* FASTBUILD_DEBUG && FASTBUILD_MERGE */ #endif if (last_bti == (BTItem) NULL) first_off = P_FIRSTKEY; - else if (!_bt_itemcmp(index, _bt_nattr, + else if (!_bt_itemcmp(index, index->rd_att->natts, bti, last_bti, BTEqualStrategyNumber)) first_off = off; last_off = off; @@ -1103,224 +496,31 @@ _bt_uppershutdown(Relation index, BTPageState *state) } /* - * take the input tapes stored by 'btspool' and perform successive - * merging passes until at most one run is left in each tape. at that - * point, merge the final tape runs into a set of btree leaves. - * - * XXX three nested loops? gross. cut me up into smaller routines. + * Read tuples in correct sort order from tuplesort, and load them into + * btree leaves. */ static void -_bt_merge(Relation index, BTSpool *btspool) +_bt_load(Relation index, BTSpool *btspool) { BTPageState *state; - BTPriQueue q; - BTPriQueueElem e; - BTSortKey btsk; BTItem bti; - BTTapeBlock *itape; - BTTapeBlock *otape; - char *tapepos[MAXTAPES]; - int tapedone[MAXTAPES]; - int t; - int goodtapes; - int npass; - int nruns; - Size btisz; - bool doleaf = false; + bool should_free; /* * initialize state needed for the merge into the btree leaf pages. */ - state = (BTPageState *) _bt_pagestate(index, BTP_LEAF, 0, true); - - npass = 0; - do - { /* pass */ - - /* - * each pass starts by flushing the previous outputs and swapping - * inputs and outputs. flushing sets End-of-Run for any dirty - * output tapes. swapping clears the new output tapes and rewinds - * the new input tapes. - */ - btspool->bts_tape = btspool->bts_ntapes - 1; - _bt_spoolflush(btspool); - _bt_spoolswap(btspool); - - ++npass; - nruns = 0; - - for (;;) - { /* run */ - - /* - * each run starts by selecting a new output tape. the merged - * results of a given run are always sent to this one tape. - */ - btspool->bts_tape = (btspool->bts_tape + 1) % btspool->bts_ntapes; - otape = btspool->bts_otape[btspool->bts_tape]; - - /* - * initialize the priority queue by loading it with the first - * element of the given run in each tape. since we are - * starting a new run, we reset the tape (clearing the - * End-Of-Run marker) before reading it. this means that - * _bt_taperead will return 0 only if the tape is actually at - * EOF. - */ - MemSet((char *) &q, 0, sizeof(BTPriQueue)); - goodtapes = 0; - for (t = 0; t < btspool->bts_ntapes; ++t) - { - itape = btspool->bts_itape[t]; - tapepos[t] = itape->bttb_data; - tapedone[t] = 0; - _bt_tapereset(itape); - do - { - if (_bt_taperead(itape) == 0) - tapedone[t] = 1; - } while (!tapedone[t] && EMPTYTAPE(itape)); - if (!tapedone[t]) - { - ++goodtapes; - e.btpqe_tape = t; - _bt_setsortkey(index, _bt_tapenext(itape, &tapepos[t]), - &(e.btpqe_item)); - if (e.btpqe_item.btsk_item != (BTItem) NULL) - _bt_pqadd(&q, &e); - } - } - - /* - * if we don't have any tapes with any input (i.e., they are - * all at EOF), there is no work to do in this run -- we must - * be done with this pass. - */ - if (goodtapes == 0) - { - break; /* for */ - } - ++nruns; - - /* - * output the smallest element from the queue until there are - * no more. - */ - while (_bt_pqnext(&q, &e) >= 0) - { /* item */ - - /* - * replace the element taken from priority queue, fetching - * a new block if needed. a tape can run out if it hits - * either End-Of-Run or EOF. - */ - t = e.btpqe_tape; - btsk = e.btpqe_item; - bti = btsk.btsk_item; - if (bti != (BTItem) NULL) - { - btisz = BTITEMSZ(bti); - btisz = MAXALIGN(btisz); - if (doleaf) - { - _bt_buildadd(index, state, bti, BTP_LEAF); -#if defined(FASTBUILD_DEBUG) && defined(FASTBUILD_MERGE) - { - bool isnull; - Datum d = index_getattr(&(bti->bti_itup), 1, - index->rd_att, &isnull); - - printf("_bt_merge: [pass %d run %d] inserted <%x> from tape %d into block %d\n", - npass, nruns, d, t, - BufferGetBlockNumber(state->btps_buf)); - } -#endif /* FASTBUILD_DEBUG && FASTBUILD_MERGE */ - } - else - { - if (SPCLEFT(otape) < btisz) - { - - /* - * if it's full, write it out and add the item - * to the next block. (since we will be - * adding another tuple immediately after - * this, we can be sure that there will be at - * least one more block in this run and so we - * know we do *not* want to set End-Of-Run - * here.) - */ - _bt_tapewrite(otape, 0); - } - _bt_tapeadd(otape, bti, btisz); -#if defined(FASTBUILD_DEBUG) && defined(FASTBUILD_MERGE) - { - bool isnull; - Datum d = index_getattr(&(bti->bti_itup), 1, - index->rd_att, &isnull); - - printf("_bt_merge: [pass %d run %d] inserted <%x> from tape %d into output tape %d\n", - npass, nruns, d, t, - btspool->bts_tape); - } -#endif /* FASTBUILD_DEBUG && FASTBUILD_MERGE */ - } - - if (btsk.btsk_datum != (Datum *) NULL) - pfree((void *) (btsk.btsk_datum)); - if (btsk.btsk_nulls != (char *) NULL) - pfree((void *) (btsk.btsk_nulls)); - - } - itape = btspool->bts_itape[t]; - if (!tapedone[t]) - { - BTItem newbti = _bt_tapenext(itape, &tapepos[t]); - - if (newbti == (BTItem) NULL) - { - do - { - if (_bt_taperead(itape) == 0) - tapedone[t] = 1; - } while (!tapedone[t] && EMPTYTAPE(itape)); - if (!tapedone[t]) - { - tapepos[t] = itape->bttb_data; - newbti = _bt_tapenext(itape, &tapepos[t]); - } - } - if (newbti != (BTItem) NULL) - { - BTPriQueueElem nexte; - - nexte.btpqe_tape = t; - _bt_setsortkey(index, newbti, &(nexte.btpqe_item)); - _bt_pqadd(&q, &nexte); - } - } - } /* item */ - - /* - * that's it for this run. flush the output tape, marking - * End-of-Run. - */ - _bt_tapewrite(otape, 1); - } /* run */ + state = _bt_pagestate(index, BTP_LEAF, 0, true); - /* - * we are here because we ran out of input on all of the input - * tapes. - * - * if this pass did not generate more actual output runs than we have - * tapes, we know we have at most one run in each tape. this - * means that we are ready to merge into the final btree leaf - * pages instead of merging into a tape file. - */ - if (nruns <= btspool->bts_ntapes) - doleaf = true; - } while (nruns > 0); /* pass */ + for (;;) + { + bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, + &should_free); + if (bti == (BTItem) NULL) + break; + _bt_buildadd(index, state, bti, BTP_LEAF); + if (should_free) + pfree((void *) bti); + } _bt_uppershutdown(index, state); } @@ -1359,7 +559,7 @@ _bt_upperbuild(Relation index) ropaque->btpo_flags &= ~BTP_ROOT; _bt_wrtbuf(index, rbuf); - state = (BTPageState *) _bt_pagestate(index, 0, 0, true); + state = _bt_pagestate(index, 0, 0, true); /* for each page... */ do @@ -1380,7 +580,7 @@ _bt_upperbuild(Relation index) * the lower page and insert it into a page at this level. */ nbti = _bt_minitem(rpage, blk, P_RIGHTMOST(ropaque)); -#if defined(FASTBUILD_DEBUG) && defined(FASTBUILD_MERGE) +#ifdef FASTBUILD_DEBUG { bool isnull; Datum d = index_getattr(&(nbti->bti_itup), 1, index->rd_att, @@ -1389,7 +589,7 @@ _bt_upperbuild(Relation index) printf("_bt_upperbuild: inserting <%x> at %d\n", d, state->btps_level); } -#endif /* FASTBUILD_DEBUG && FASTBUILD_MERGE */ +#endif _bt_buildadd(index, state, nbti, 0); pfree((void *) nbti); } @@ -1401,25 +601,3 @@ _bt_upperbuild(Relation index) } #endif - -/* - * given a spool loading by successive calls to _bt_spool, create an - * entire btree. - */ -void -_bt_leafbuild(Relation index, void *spool) -{ - _bt_isortcmpinit(index, (BTSpool *) spool); - -#ifdef BTREE_BUILD_STATS - if (ShowExecutorStats) - { - fprintf(stderr, "! BtreeBuild (Spool) Stats:\n"); - ShowUsage(); - ResetUsage(); - } -#endif - - _bt_merge(index, (BTSpool *) spool); - -} |