Skip to content

Commit b0d5036

Browse files
author
Hiroshi Inoue
committed
CREATE btree INDEX takes dead tuples into account when old transactions
are running.
1 parent 5ab40f0 commit b0d5036

File tree

3 files changed

+162
-28
lines changed

3 files changed

+162
-28
lines changed

‎src/backend/access/nbtree/nbtree.c

Lines changed: 58 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
* Portions Copyright (c) 1994, Regents of the University of California
1313
*
1414
* IDENTIFICATION
15-
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.62 2000/07/21 06:42:32 tgl Exp $
15+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.63 2000/08/10 02:33:20 inoue Exp $
1616
*
1717
*-------------------------------------------------------------------------
1818
*/
@@ -25,6 +25,7 @@
2525
#include "catalog/index.h"
2626
#include "executor/executor.h"
2727
#include "miscadmin.h"
28+
#include "storage/sinval.h"
2829

2930

3031
bool BuildingBtree = false; /* see comment in btbuild() */
@@ -70,6 +71,16 @@ btbuild(PG_FUNCTION_ARGS)
7071
BTSpool *spool = NULL;
7172
BTItem btitem;
7273
bool usefast;
74+
Snapshot snapshot;
75+
TransactionId XmaxRecent;
76+
/*
77+
* spool2 is needed only when the index is an unique index.
78+
* Dead tuples are put into spool2 instead of spool in
79+
* order to avoid uniqueness check.
80+
*/
81+
BTSpool *spool2 = NULL;
82+
bool tupleIsAlive;
83+
int dead_count;
7384

7485
/* note that this is a new btree */
7586
BuildingBtree = true;
@@ -135,13 +146,41 @@ btbuild(PG_FUNCTION_ARGS)
135146
nhtups = nitups = 0;
136147

137148
if (usefast)
149+
{
138150
spool = _bt_spoolinit(index, indexInfo->ii_Unique);
151+
/*
152+
* Different from spool,the uniqueness isn't checked
153+
* for spool2.
154+
*/
155+
if (indexInfo->ii_Unique)
156+
spool2 = _bt_spoolinit(index, false);
157+
}
139158

140159
/* start a heap scan */
141-
hscan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
160+
dead_count = 0;
161+
snapshot = (IsBootstrapProcessingMode() ? SnapshotNow : SnapshotAny);
162+
hscan = heap_beginscan(heap, 0, snapshot, 0, (ScanKey) NULL);
163+
XmaxRecent = 0;
164+
if (snapshot == SnapshotAny)
165+
GetXmaxRecent(&XmaxRecent);
142166

143167
while (HeapTupleIsValid(htup = heap_getnext(hscan, 0)))
144168
{
169+
if (snapshot == SnapshotAny)
170+
{
171+
tupleIsAlive = HeapTupleSatisfiesNow(htup->t_data);
172+
if (!tupleIsAlive)
173+
{
174+
if ((htup->t_data->t_infomask & HEAP_XMIN_INVALID) != 0)
175+
continue;
176+
if (htup->t_data->t_infomask & HEAP_XMAX_COMMITTED &&
177+
htup->t_data->t_xmax < XmaxRecent)
178+
continue;
179+
}
180+
}
181+
else
182+
tupleIsAlive = true;
183+
145184
MemoryContextReset(econtext->ecxt_per_tuple_memory);
146185

147186
nhtups++;
@@ -222,7 +261,15 @@ btbuild(PG_FUNCTION_ARGS)
222261
* into the btree.
223262
*/
224263
if (usefast)
225-
_bt_spool(btitem, spool);
264+
{
265+
if (tupleIsAlive || !spool2)
266+
_bt_spool(btitem, spool);
267+
else /* dead tuples are put into spool2 */
268+
{
269+
dead_count++;
270+
_bt_spool(btitem, spool2);
271+
}
272+
}
226273
else
227274
res = _bt_doinsert(index, btitem, indexInfo->ii_Unique, heap);
228275

@@ -234,6 +281,11 @@ btbuild(PG_FUNCTION_ARGS)
234281

235282
/* okay, all heap tuples are indexed */
236283
heap_endscan(hscan);
284+
if (spool2 && !dead_count) /* spool2 was found to be unnecessary */
285+
{
286+
_bt_spooldestroy(spool2);
287+
spool2 = NULL;
288+
}
237289

238290
#ifndef OMIT_PARTIAL_INDEX
239291
if (pred != NULL || oldPred != NULL)
@@ -250,8 +302,10 @@ btbuild(PG_FUNCTION_ARGS)
250302
*/
251303
if (usefast)
252304
{
253-
_bt_leafbuild(spool);
305+
_bt_leafbuild(spool, spool2);
254306
_bt_spooldestroy(spool);
307+
if (spool2)
308+
_bt_spooldestroy(spool2);
255309
}
256310

257311
#ifdef BTREE_BUILD_STATS

‎src/backend/access/nbtree/nbtsort.c

Lines changed: 102 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@
3535
* Portions Copyright (c) 1994, Regents of the University of California
3636
*
3737
* IDENTIFICATION
38-
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.56 2000/07/21 22:14:09 tgl Exp $
38+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.57 2000/08/10 02:33:20 inoue Exp $
3939
*
4040
*-------------------------------------------------------------------------
4141
*/
@@ -95,7 +95,7 @@ static void _bt_sortaddtup(Page page, Size itemsize,
9595
BTItem btitem, OffsetNumber itup_off);
9696
static void _bt_buildadd(Relation index, BTPageState *state, BTItem bti);
9797
static void _bt_uppershutdown(Relation index, BTPageState *state);
98-
static void _bt_load(Relation index, BTSpool *btspool);
98+
static void _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2);
9999

100100

101101
/*
@@ -153,7 +153,7 @@ _bt_spool(BTItem btitem, BTSpool *btspool)
153153
* create an entire btree.
154154
*/
155155
void
156-
_bt_leafbuild(BTSpool *btspool)
156+
_bt_leafbuild(BTSpool *btspool, BTSpool *btspool2)
157157
{
158158
#ifdef BTREE_BUILD_STATS
159159
if (Show_btree_build_stats)
@@ -165,7 +165,9 @@ _bt_leafbuild(BTSpool *btspool)
165165
#endif /* BTREE_BUILD_STATS */
166166
tuplesort_performsort(btspool->sortstate);
167167

168-
_bt_load(btspool->index, btspool);
168+
if (btspool2)
169+
tuplesort_performsort(btspool2->sortstate);
170+
_bt_load(btspool->index, btspool, btspool2);
169171
}
170172

171173

@@ -523,28 +525,106 @@ _bt_uppershutdown(Relation index, BTPageState *state)
523525
* btree leaves.
524526
*/
525527
static void
526-
_bt_load(Relation index, BTSpool *btspool)
528+
_bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2)
527529
{
528530
BTPageState *state = NULL;
529-
530-
for (;;)
531+
bool merge = (btspool2 != NULL);
532+
BTItem bti, bti2 = NULL;
533+
bool should_free, should_free2, load1;
534+
TupleDesc tupdes = RelationGetDescr(index);
535+
int i, keysz = RelationGetNumberOfAttributes(index);
536+
ScanKey indexScanKey = NULL;
537+
538+
if (merge)
531539
{
532-
BTItem bti;
533-
bool should_free;
534-
535-
bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true,
536-
&should_free);
537-
if (bti == (BTItem) NULL)
538-
break;
539-
540-
/* When we see first tuple, create first index page */
541-
if (state == NULL)
542-
state = _bt_pagestate(index, BTP_LEAF, 0);
543-
544-
_bt_buildadd(index, state, bti);
540+
/*
541+
* Another BTSpool for dead tuples exists.
542+
* Now we have to merge btspool and btspool2.
543+
*/
544+
ScanKey entry;
545+
Datum attrDatum1, attrDatum2;
546+
bool isFirstNull, isSecondNull;
547+
int32 compare;
548+
549+
/* the preparation of merge */
550+
bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free);
551+
bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate, true, &should_free2);
552+
indexScanKey = _bt_mkscankey_nodata(index);
553+
for (;;)
554+
{
555+
load1 = true; /* load BTSpool next ? */
556+
if (NULL == bti2)
557+
{
558+
if (NULL == bti)
559+
break;
560+
}
561+
else if (NULL != bti)
562+
{
563+
564+
for (i = 1; i <= keysz; i++)
565+
{
566+
entry = indexScanKey + i - 1;
567+
attrDatum1 = index_getattr((IndexTuple)bti, i, tupdes, &isFirstNull);
568+
attrDatum2 = index_getattr((IndexTuple)bti2, i, tupdes, &isSecondNull);
569+
if (isFirstNull)
570+
{
571+
if (!isSecondNull)
572+
{
573+
load1 = false;
574+
break;
575+
}
576+
}
577+
else if (isSecondNull)
578+
break;
579+
else
580+
{
581+
compare = DatumGetInt32(FunctionCall2(&entry->sk_func, attrDatum1, attrDatum2));
582+
if (compare > 0)
583+
{
584+
load1 = false;
585+
break;
586+
}
587+
else if (compare < 0)
588+
break;
589+
}
590+
}
591+
}
592+
else
593+
load1 = false;
594+
595+
/* When we see first tuple, create first index page */
596+
if (state == NULL)
597+
state = _bt_pagestate(index, BTP_LEAF, 0);
598+
599+
if (load1)
600+
{
601+
_bt_buildadd(index, state, bti);
602+
if (should_free)
603+
pfree((void *) bti);
604+
bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free);
605+
}
606+
else
607+
{
608+
_bt_buildadd(index, state, bti2);
609+
if (should_free2)
610+
pfree((void *) bti2);
611+
bti2 = (BTItem) tuplesort_getindextuple(btspool2->sortstate, true, &should_free2);
612+
}
613+
}
614+
_bt_freeskey(indexScanKey);
615+
}
616+
else /* merge is unnecessary */
617+
{
618+
while (bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free), bti != (BTItem) NULL)
619+
{
620+
/* When we see first tuple, create first index page */
621+
if (state == NULL)
622+
state = _bt_pagestate(index, BTP_LEAF, 0);
545623

546-
if (should_free)
547-
pfree((void *) bti);
624+
_bt_buildadd(index, state, bti);
625+
if (should_free)
626+
pfree((void *) bti);
627+
}
548628
}
549629

550630
/* Close down final pages, if we had any data at all */

‎src/include/access/nbtree.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2000, PostgreSQL, Inc
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: nbtree.h,v 1.40 2000/07/25 04:47:57 tgl Exp $
10+
* $Id: nbtree.h,v 1.41 2000/08/10 02:33:19 inoue Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -289,6 +289,6 @@ typedef struct BTSpool BTSpool; /* opaque type known only within nbtsort.c */
289289
extern BTSpool *_bt_spoolinit(Relation index, bool isunique);
290290
extern void _bt_spooldestroy(BTSpool *btspool);
291291
extern void _bt_spool(BTItem btitem, BTSpool *btspool);
292-
extern void _bt_leafbuild(BTSpool *btspool);
292+
extern void _bt_leafbuild(BTSpool *btspool, BTSpool *spool2);
293293

294294
#endif /* NBTREE_H */

0 commit comments

Comments
 (0)