PostgreSQL Source Code: src/backend/access/gist/gistbuild.c Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
34
35#include <math.h>
36
46
50
51
52#define BUFFERING_MODE_SWITCH_CHECK_STEP 256
53
54
55
56
57
58
59
60#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096
61
62
63
64
65
66
67typedef enum
68{
71
73
74
76
77
80
81
82typedef struct
83{
87
89
91
93
94
95
96
97
98
102
103
104
105
107
109
112
113#define GIST_SORTED_BUILD_PAGE_NUM 4
114
115
116
117
118
119
120
121
122
124{
130
131
132
135 bool tupleIsAlive, void *state);
142
148 bool *isnull,
149 bool tupleIsAlive,
156 Buffer buffer, int level,
166
173
174
175
176
177
180{
182 double reltuples;
188
189
190
191
192
194 elog(ERROR, "index \"%s\" already contains data",
196
198 buildstate.heaprel = heap;
201
202
203
204
205
206
208
209
210
211
212
213
215 {
220 else
222 }
223 else
224 {
226 }
227
228
229
230
232 {
233 bool hasallsortsupports = true;
235
236 for (int i = 0; i < keyscount; i++)
237 {
241 {
242 hasallsortsupports = false;
243 break;
244 }
245 }
246 if (hasallsortsupports)
248 }
249
250
251
252
255
256
257
258
261
263 {
264
265
266
270 NULL,
272
273
276 &buildstate, NULL);
277
278
279
280
282
284
286 }
287 else
288 {
289
290
291
292
295
296
300
302
304
307
309
311
312
315 &buildstate, NULL);
316
317
318
319
320
322 {
323 elog(DEBUG1, "all tuples processed, emptying buffers");
326 }
327
328
329
330
331
333 {
336 true);
337 }
338 }
339
340
343
345
346
347
348
350
353
354 return result;
355}
356
357
358
359
360
361
362
363
364
365static void
369 bool *isnull,
370 bool tupleIsAlive,
372{
376
378
379
382 true, compressed_values);
383
386 tid,
387 compressed_values, isnull);
388
391
392
394}
395
396
397
398
399static void
401{
405
406
407 state->pages_allocated = 1;
408
410
411
414 levelstate->parent = NULL;
416
417
418
419
421 {
424 }
425
426
427
428
429
430
431
433 {
435
441 pfree(levelstate);
443 }
444
445
448 memcpy(rootbuf, levelstate->pages[0], BLCKSZ);
450
451 pfree(levelstate);
452
454}
455
456
457
458
459
460static void
464{
465 Size sizeNeeded;
466
467
470 {
471 Page newPage;
474
476 {
478 }
479 else
481
484
487 }
488
490}
491
492static void
495{
502 int vect_len;
504
506
508
509
512 {
513
515 {
516 int len_local;
518
519 itvec = gistjoinvector(itvec, &vect_len, itvec_local, len_local);
520 pfree(itvec_local);
521 }
522
523
525 }
526 else
527 {
528
530 union_tuple = gistunion(state->indexrel, itvec, vect_len,
531 state->giststate);
532 dist->itup = union_tuple;
535 }
536
538
539
541
542
543 for (; dist != NULL; dist = dist->next)
544 {
548
549
551
552
553 data = (char *) (dist->list);
557 for (int i = 0; i < dist->block.num; i++)
558 {
560
563
565 }
566 union_tuple = dist->itup;
567
568
569
570
571
572
573
574
575
576
577
578
579
582
583
584
585
586
587 blkno = state->pages_allocated++;
592
593
594
595
596
599 {
604
606 }
608 }
609}
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625static void
627{
629 int pagesPerBuffer;
630 Size pageFreeSpace;
631 Size itupAvgSize,
632 itupMinSize;
633 double avgIndexTuplesPerPage,
634 maxIndexTuplesPerPage;
635 int i;
636 int levelStep;
637
638
642
643
644
645
646
647 itupAvgSize = (double) buildstate->indtuplesSize /
649
650
651
652
653
654
655
656
658 for (i = 0; i < index->rd_att->natts; i++)
659 {
661
662 if (attr->attlen < 0)
664 else
665 itupMinSize += attr->attlen;
666 }
667
668
669 avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
670 maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719 levelStep = 1;
720 for (;;)
721 {
722 double subtreesize;
723 double maxlowestlevelpages;
724
725
726 subtreesize =
727 (1 - pow(avgIndexTuplesPerPage, (double) (levelStep + 1))) /
728 (1 - avgIndexTuplesPerPage);
729
730
731 maxlowestlevelpages = pow(maxIndexTuplesPerPage, (double) levelStep);
732
733
735 break;
736
737
739 break;
740
741
742 levelStep++;
743 }
744
745
746
747
748
749 levelStep--;
750
751
752
753
754
755 if (levelStep <= 0)
756 {
757 elog(DEBUG1, "failed to switch to buffered GiST build");
759 return;
760 }
761
762
763
764
765
766
768
769
772
774
776
777 elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
778 levelStep, pagesPerBuffer);
779}
780
781
782
783
784
785
786
787
788static int
790{
791 double pagesPerBuffer;
792 double avgIndexTuplesPerPage;
793 double itupAvgSize;
794 Size pageFreeSpace;
795
796
800
801
802
803
804
805 itupAvgSize = (double) buildstate->indtuplesSize /
807
808 avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
809
810
811
812
813 pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
814
815 return (int) rint(pagesPerBuffer);
816}
817
818
819
820
821static void
825 bool *isnull,
826 bool tupleIsAlive,
828{
832
834
835
838 true);
839 itup->t_tid = *tid;
840
841
844
845
846
847
848
849
850
851
852
853
855 {
856
858 }
859 else
860 {
861
862
863
864
867 }
868
871
874 {
875
878 }
879
880
881
882
883
884
885
886
887
888
889
896 {
897
898
899
900
902 }
903}
904
905
906
907
908static void
910{
911
913
914
916}
917
918
919
920
921
922
923
924static bool
927{
933 bool result = false;
935 int level;
938
940
941
942
943
944
945
946 blkno = startblkno;
947 level = startlevel;
948 for (;;)
949 {
952 newtup;
955
956
958 break;
959
960
961 if (level == 0)
962 break;
963
964
965
966
967
968
969 buffer = ReadBuffer(indexrel, blkno);
971
973 childoffnum = gistchoose(indexrel, page, itup, giststate);
977
978 if (level > 1)
980
981
982
983
984
985 newtup = gistgetadjusted(indexrel, idxtuple, itup, giststate);
986 if (newtup)
987 {
989 buffer,
990 level,
991 &newtup,
992 1,
993 childoffnum,
996
997 }
998 else
1000
1001
1002 parentblkno = blkno;
1003 blkno = childblkno;
1004 downlinkoffnum = childoffnum;
1006 level--;
1007 }
1008
1010 {
1011
1012
1013
1014
1016
1017
1018 childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, blkno, level);
1019
1020
1022
1024 result = true;
1025 }
1026 else
1027 {
1028
1029
1030
1032 buffer = ReadBuffer(indexrel, blkno);
1036 parentblkno, downlinkoffnum);
1037
1038 }
1039
1040 return result;
1041}
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1059{
1061 List *splitinfo;
1062 bool is_split;
1064
1068 buffer,
1069 itup, ntup, oldoffnum, &placed_to_blk,
1071 &splitinfo,
1072 false,
1073 buildstate->heaprel, true);
1074
1075
1076
1077
1078
1079
1080
1082 {
1086
1089
1090 elog(DEBUG2, "splitting GiST root page, now %d levels deep", gfbb->rootlevel);
1091
1092
1093
1094
1095
1096
1098 {
1101 {
1106
1110
1111
1112
1113
1114
1116 }
1117 }
1118 }
1119
1120 if (splitinfo)
1121 {
1122
1123
1124
1125
1126
1127
1129 int ndownlinks,
1130 i;
1131 Buffer parentBuffer;
1133
1134
1135 parentBuffer =
1138 level,
1139 &parentblk,
1140 &downlinkoffnum);
1141
1142
1143
1144
1145
1146
1147
1148
1152 level,
1153 buffer, splitinfo);
1154
1155
1158 i = 0;
1159 foreach(lc, splitinfo)
1160 {
1162
1163
1164
1165
1166
1167
1168
1169
1170 if (level > 0)
1174
1175
1176
1177
1178
1179
1180
1181 if (level > 1)
1183
1184
1185
1186
1187
1189 downlinks[i++] = splitinfo->downlink;
1190 }
1191
1192
1194 downlinks, ndownlinks, downlinkoffnum,
1196
1197 list_free_deep(splitinfo);
1198 }
1199 else
1201
1202 return placed_to_blk;
1203}
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1229{
1235
1236 if (level > 0)
1238 else
1239 {
1240
1241
1242
1243
1245 elog(ERROR, "no parent buffer provided of child %u", childblkno);
1246 parent = *parentblkno;
1247 }
1248
1254
1255
1258 {
1261
1263 {
1264
1265 return buffer;
1266 }
1267 }
1268
1269
1270
1271
1272
1273
1274
1275
1277 {
1280
1282 {
1283
1284 *downlinkoffnum = off;
1285 return buffer;
1286 }
1287 }
1288
1289 elog(ERROR, "failed to re-find parent for block %u", childblkno);
1291}
1292
1293
1294
1295
1296
1297
1298static void
1300{
1302
1303
1305 {
1307
1308
1312
1313
1314
1315
1316
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331 while (true)
1332 {
1334
1335
1337 break;
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1350 {
1351
1352
1353
1354
1355 break;
1356 }
1357
1358
1360 }
1361 }
1362}
1363
1364
1365
1366
1367
1368
1369
1370
1371static void
1373{
1376 int i;
1377
1379
1380
1381
1382
1384 {
1385
1386
1387
1388
1389
1390
1391
1393 {
1395
1397
1399 {
1400
1401
1402
1403
1405 {
1411 }
1413 }
1414 else
1417 }
1418 elog(DEBUG2, "emptied all buffers at level %d", i);
1419 }
1421}
1422
1423
1424
1425
1426static int
1428{
1429 int maxLevel;
1431
1432
1433
1434
1435
1436 maxLevel = 0;
1438 while (true)
1439 {
1443
1445
1446
1447
1448
1449
1452
1454 {
1455
1457 break;
1458 }
1459
1460
1461
1462
1463
1464
1469
1470
1471
1472
1473
1474 maxLevel++;
1475 }
1476 return maxLevel;
1477}
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509typedef struct
1510{
1514
1515static void
1517{
1519
1524 1024,
1525 &hashCtl,
1527}
1528
1529static void
1531{
1533 bool found;
1534
1536 &child,
1538 &found);
1540}
1541
1542
1543
1544
1545static void
1547{
1552
1554
1557 {
1561
1563 }
1564}
1565
1568{
1570 bool found;
1571
1572
1574 &child,
1576 &found);
1577 if (!found)
1578 elog(ERROR, "could not find parent of block %u in lookup table", child);
1579
1581}
#define InvalidBlockNumber
static Datum values[MAXATTR]
BlockNumber BufferGetBlockNumber(Buffer buffer)
void UnlockReleaseBuffer(Buffer buffer)
void MarkBufferDirty(Buffer buffer)
void LockBuffer(Buffer buffer, int mode)
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
#define RelationGetNumberOfBlocks(reln)
static Page BufferGetPage(Buffer buffer)
Size PageGetFreeSpace(const PageData *page)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
#define SizeOfPageHeaderData
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
BulkWriteState * smgr_bulk_start_rel(Relation rel, ForkNumber forknum)
void smgr_bulk_write(BulkWriteState *bulkstate, BlockNumber blocknum, BulkWriteBuffer buf, bool page_std)
BulkWriteBuffer smgr_bulk_get_buf(BulkWriteState *bulkstate)
void smgr_bulk_finish(BulkWriteState *bulkstate)
#define OidIsValid(objectId)
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
SplitPageLayout * gistSplit(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
GISTSTATE * initGISTstate(Relation index)
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright, Relation heapRel, bool is_build)
MemoryContext createTempGistContext(void)
void freeGISTstate(GISTSTATE *giststate)
#define GIST_SORTSUPPORT_PROC
struct GISTPageOpaqueData GISTPageOpaqueData
#define GistPageIsLeaf(page)
#define GistPageGetOpaque(page)
#define LEVEL_HAS_BUFFERS(nlevel, gfbb)
@ GIST_OPTION_BUFFERING_OFF
@ GIST_OPTION_BUFFERING_ON
#define GIST_DEFAULT_FILLFACTOR
#define BUFFER_OVERFLOWED(nodeBuffer, gfbb)
@ GIST_BUFFERING_DISABLED
static BlockNumber gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, int level, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber parentblk, OffsetNumber downlinkoffnum)
static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parentbuf)
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
static void gist_indexsortbuild_levelstate_flush(GISTBuildState *state, GistSortedBuildLevelState *levelstate)
#define BUFFERING_MODE_SWITCH_CHECK_STEP
static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblkno, OffsetNumber *downlinkoffnum)
static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
static void gist_indexsortbuild_levelstate_add(GISTBuildState *state, GistSortedBuildLevelState *levelstate, IndexTuple itup)
static void gist_indexsortbuild(GISTBuildState *state)
static void gistInitParentMap(GISTBuildState *buildstate)
static void gistBuildCallback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
IndexBuildResult * gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
static void gistSortedBuildCallback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
#define GIST_SORTED_BUILD_PAGE_NUM
static void gistEmptyAllBuffers(GISTBuildState *buildstate)
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET
static void gistInitBuffering(GISTBuildState *buildstate)
static void gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup)
static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child)
static int gistGetMaxLevel(Relation index)
struct GistSortedBuildLevelState GistSortedBuildLevelState
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple itup)
void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, Relation r, int level, Buffer buffer, List *splitinfo)
GISTBuildBuffers * gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel)
void gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple *itup)
GISTNodeBuffer * gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, BlockNumber nodeBlocknum, int level)
void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb)
Buffer gistNewBuffer(Relation r, Relation heaprel)
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf)
IndexTuple * gistextractpage(Page page, int *len)
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
void gistCompressValues(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf, Datum *compatt)
IndexTuple * gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
void gistinitpage(Page page, uint32 f)
IndexTuple gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
void GISTInitBuffer(Buffer b, uint32 f)
void gistcheckpage(Relation rel, Buffer buf)
IndexTupleData * gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
Assert(PointerIsAligned(start, uint64))
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
if(TABLE==NULL||TABLE_index==NULL)
struct ItemIdData ItemIdData
static void ItemPointerSetBlockNumber(ItemPointerData *pointer, BlockNumber blockNumber)
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
IndexTupleData * IndexTuple
static Size IndexTupleSize(const IndexTupleData *itup)
List * list_delete_first(List *list)
List * lcons(void *datum, List *list)
void list_free_deep(List *list)
void MemoryContextReset(MemoryContext context)
void pfree(void *pointer)
void * palloc0(Size size)
MemoryContext CurrentMemoryContext
void MemoryContextDelete(MemoryContext context)
#define START_CRIT_SECTION()
#define CHECK_FOR_INTERRUPTS()
#define END_CRIT_SECTION()
#define InvalidOffsetNumber
#define OffsetNumberNext(offsetNumber)
#define FirstOffsetNumber
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
static int list_length(const List *l)
static SMgrRelation RelationGetSmgr(Relation rel)
#define RelationGetRelationName(relation)
#define RelationNeedsWAL(relation)
#define IndexRelationGetNumberOfKeyAttributes(relation)
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
List * bufferEmptyingQueue
BlockNumber pages_allocated
BulkWriteState * bulkstate
Tuplesortstate * sortstate
Page pages[GIST_SORTED_BUILD_PAGE_NUM]
struct GistSortedBuildLevelState * parent
struct SplitPageLayout * next
static double table_index_build_scan(Relation table_rel, Relation index_rel, struct IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
static CompactAttribute * TupleDescCompactAttr(TupleDesc tupdesc, int i)
void tuplesort_performsort(Tuplesortstate *state)
void tuplesort_end(Tuplesortstate *state)
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, const Datum *values, const bool *isnull)
Tuplesortstate * tuplesort_begin_index_gist(Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
void log_newpage_range(Relation rel, ForkNumber forknum, BlockNumber startblk, BlockNumber endblk, bool page_std)