spgdoinsert.c File Reference
#include "postgres.h"#include "access/genam.h"#include "access/spgist_private.h"#include "access/spgxlog.h"#include "access/xloginsert.h"#include "common/int.h"#include "common/pg_prng.h"#include "miscadmin.h"#include "storage/bufmgr.h"#include "utils/rel.h"
Include dependency graph for spgdoinsert.c:
Go to the source code of this file.
Data Structures | |
| struct | SPPageDesc |
Typedefs | |
| typedef struct SPPageDesc | SPPageDesc |
Typedef Documentation
◆ SPPageDesc
| typedef struct SPPageDesc SPPageDesc |
Function Documentation
◆ addLeafTuple()
|
static |
Definition at line 203 of file spgdoinsert.c.
205{
206 spgxlogAddLeaf xlrec;
207
208 xlrec.newPage = isNew;
209 xlrec.storesNulls = isNulls;
210
211 /* these will be filled below as needed */
215 xlrec.nodeI = 0;
216
217 START_CRIT_SECTION();
218
221 {
222 /* Tuple is not part of a chain */
225 (Item) leafTuple, leafTuple->size,
226 NULL, false);
227
229
230 /* Must update parent's downlink if any */
232 {
235
237 }
238 }
239 else
240 {
241 /*
242 * Tuple must be inserted into existing chain. We mustn't change the
243 * chain's head address, but we don't need to chase the entire chain
244 * to put the tuple at the end; we can insert it second.
245 *
246 * Also, it's possible that the "chain" consists only of a DEAD tuple,
247 * in which case we should replace the DEAD tuple in-place.
248 */
249 SpGistLeafTuple head;
250 OffsetNumber offnum;
251
255 {
258 (Item) leafTuple, leafTuple->size,
259 NULL, false);
260
261 /*
262 * re-get head of list because it could have been moved on page,
263 * and set new second element
264 */
267 SGLT_SET_NEXTOFFSET(head, offnum);
268
269 xlrec.offnumLeaf = offnum;
271 }
273 {
277 (Item) leafTuple, leafTuple->size,
280 leafTuple->size);
281
282 /* WAL replay distinguishes this case by equal offnums */
285 }
286 else
288 }
289
291
293 {
294 XLogRecPtr recptr;
295 int flags;
296
297 XLogBeginInsert();
300
301 flags = REGBUF_STANDARD;
303 flags |= REGBUF_WILL_INIT;
307
309
311
312 /* update parent only if we actually changed it */
314 {
316 }
317 }
318
319 END_CRIT_SECTION();
320}
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
Definition: bufpage.c:1051
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
Definition: bufpage.h:354
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:244
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:472
static void saveNodeLink(Relation index, SPPageDesc *parent, BlockNumber blkno, OffsetNumber offnum)
Definition: spgdoinsert.c:186
#define SGLT_SET_NEXTOFFSET(spgLeafTuple, offsetNumber)
Definition: spgist_private.h:398
OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page, Item item, Size size, OffsetNumber *startOffset, bool errorOK)
Definition: spgutils.c:1203
Definition: spgist_private.h:383
Definition: spgxlog.h:47
Definition: regguts.h:323
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
Definition: xloginsert.c:242
References SPPageDesc::blkno, SPPageDesc::buffer, elog, END_CRIT_SECTION, ERROR, InvalidBuffer, InvalidOffsetNumber, MarkBufferDirty(), spgxlogAddLeaf::newPage, SPPageDesc::node, spgxlogAddLeaf::nodeI, SPPageDesc::offnum, spgxlogAddLeaf::offnumHeadLeaf, spgxlogAddLeaf::offnumLeaf, spgxlogAddLeaf::offnumParent, SPPageDesc::page, PageAddItem, PageGetItem(), PageGetItemId(), PageIndexTupleDelete(), PageSetLSN(), REGBUF_STANDARD, REGBUF_WILL_INIT, RelationNeedsWAL, saveNodeLink(), SGLT_GET_NEXTOFFSET, SGLT_SET_NEXTOFFSET, SpGistLeafTupleData::size, SPGIST_DEAD, SPGIST_LIVE, SpGistBlockIsRoot, SpGistPageAddNewItem(), START_CRIT_SECTION, spgxlogAddLeaf::storesNulls, SpGistLeafTupleData::tupstate, XLOG_SPGIST_ADD_LEAF, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by spgdoinsert().
◆ addNode()
|
static |
Definition at line 80 of file spgdoinsert.c.
81{
82 SpGistNodeTuple node,
83 *nodes;
85
86 /* if offset is negative, insert at end */
87 if (offset < 0)
88 offset = tuple->nNodes;
91
94 {
96 nodes[i] = node;
97 else
98 nodes[i + 1] = node;
99 }
100
102
104 (tuple->prefixSize > 0),
106 tuple->nNodes + 1,
107 nodes);
108}
SpGistInnerTuple spgFormInnerTuple(SpGistState *state, bool hasPrefix, Datum prefix, int nNodes, SpGistNodeTuple *nodes)
Definition: spgutils.c:1002
SpGistNodeTuple spgFormNodeTuple(SpGistState *state, Datum label, bool isnull)
Definition: spgutils.c:960
Definition: itup.h:36
References elog, ERROR, i, label, SpGistInnerTupleData::nNodes, palloc(), SpGistInnerTupleData::prefixSize, SGITDATUM, SGITITERATE, spgFormInnerTuple(), and spgFormNodeTuple().
Referenced by spgAddNodeAction().
◆ checkAllTheSame()
|
static |
Definition at line 599 of file spgdoinsert.c.
601{
602 int theNode;
603 int limit;
605
606 /* For the moment, assume we can include the new leaf tuple */
607 *includeNew = true;
608
609 /* If there's only the new leaf tuple, don't select allTheSame mode */
611 return false;
612
613 /* If tuple set doesn't fit on one page, ignore the new tuple in test */
615
616 /* Check to see if more than one node is populated */
617 theNode = out->mapTuplesToNodes[0];
619 {
621 return false;
622 }
623
624 /* Nope, so override the picksplit function's decisions */
625
626 /* If the new tuple is in its own node, it can't be included in split */
628 *includeNew = false;
629
631
632 /* Random assignment of tuples to nodes (note we include new tuple) */
635
636 /* The opclass may not use node labels, but if it does, duplicate 'em */
638 {
640
644 }
645
646 /* We don't touch the prefix or the leaf tuple datum assignments */
647
648 return true;
649}
References i, if(), spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, and palloc().
Referenced by doPickSplit().
◆ checkSplitConditions()
|
static |
Definition at line 333 of file spgdoinsert.c.
335{
337 n = 0,
338 totalSize = 0;
339
341 {
342 /* return impossible values to force split */
343 *nToSplit = BLCKSZ;
344 return BLCKSZ;
345 }
346
349 {
350 SpGistLeafTuple it;
351
357 {
358 n++;
360 }
362 {
363 /* We could see a DEAD tuple as first/only chain item */
366 /* Don't count it in result, because it won't go to other page */
367 }
368 else
370
372 }
373
374 *nToSplit = n;
375
376 return totalSize;
377}
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition: bufpage.h:372
Assert(PointerIsAligned(start, uint64))
struct ItemIdData ItemIdData
References Assert(), SPPageDesc::blkno, elog, ERROR, FirstOffsetNumber, i, InvalidOffsetNumber, SPPageDesc::offnum, SPPageDesc::page, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), SGLT_GET_NEXTOFFSET, SpGistLeafTupleData::size, SPGIST_DEAD, SPGIST_LIVE, SpGistBlockIsRoot, and SpGistLeafTupleData::tupstate.
Referenced by spgdoinsert().
◆ cmpOffsetNumbers()
|
static |
Definition at line 112 of file spgdoinsert.c.
113{
115}
References a, b, and pg_cmp_u16().
Referenced by spgPageIndexMultiDelete().
◆ doPickSplit()
|
static |
Definition at line 677 of file spgdoinsert.c.
681{
682 bool insertedNew = false;
683 spgPickSplitIn in;
684 spgPickSplitOut out;
685 FmgrInfo *procinfo;
686 bool includeNew;
688 max,
689 n;
690 SpGistInnerTuple innerTuple;
691 SpGistNodeTuple node,
692 *nodes;
693 Buffer newInnerBuffer,
694 newLeafBuffer;
695 uint8 *leafPageSelect;
696 int *leafSizes;
697 OffsetNumber *toDelete;
698 OffsetNumber *toInsert;
700 OffsetNumber startOffsets[2];
701 SpGistLeafTuple *oldLeafs;
702 SpGistLeafTuple *newLeafs;
705 int spaceToDelete;
706 int currentFreeSpace;
707 int totalLeafSizes;
708 bool allTheSame;
709 spgxlogPickSplit xlrec;
710 char *leafdata,
711 *leafptr;
712 SPPageDesc saveCurrent;
713 int nToDelete,
714 nToInsert,
715 maxToInclude;
716
717 in.level = level;
718
719 /*
720 * Allocate per-leaf-tuple work arrays with max possible size
721 */
723 n = max + 1;
730
732
733 /*
734 * Form list of leaf tuples which will be distributed as split result;
735 * also, count up the amount of space that will be freed from current.
736 * (Note that in the non-root case, we won't actually delete the old
737 * tuples, only replace them with redirects or placeholders.)
738 */
739 nToInsert = 0;
740 nToDelete = 0;
741 spaceToDelete = 0;
743 {
744 /*
745 * We are splitting the root (which up to now is also a leaf page).
746 * Its tuples are not linked, so scan sequentially to get them all. We
747 * ignore the original value of current->offnum.
748 */
750 {
751 SpGistLeafTuple it;
752
756 {
757 in.datums[nToInsert] =
759 oldLeafs[nToInsert] = it;
760 nToInsert++;
761 toDelete[nToDelete] = i;
762 nToDelete++;
763 /* we will delete the tuple altogether, so count full space */
765 }
766 else /* tuples on root should be live */
768 }
769 }
770 else
771 {
772 /* Normal case, just collect the leaf tuples in the chain */
775 {
776 SpGistLeafTuple it;
777
782 {
783 in.datums[nToInsert] =
785 oldLeafs[nToInsert] = it;
786 nToInsert++;
787 toDelete[nToDelete] = i;
788 nToDelete++;
789 /* we will not delete the tuple, only replace with dead */
792 }
794 {
795 /* We could see a DEAD tuple as first/only chain item */
798 toDelete[nToDelete] = i;
799 nToDelete++;
800 /* replacing it with redirect will save no space */
801 }
802 else
804
806 }
807 }
808 in.nTuples = nToInsert;
809
810 /*
811 * We may not actually insert new tuple because another picksplit may be
812 * necessary due to too large value, but we will try to allocate enough
813 * space to include it; and in any case it has to be included in the input
814 * for the picksplit function. So don't increment nToInsert yet.
815 */
818 oldLeafs[in.nTuples] = newLeafTuple;
819 in.nTuples++;
820
821 memset(&out, 0, sizeof(out));
822
823 if (!isNulls)
824 {
825 /*
826 * Perform split using user-defined method.
827 */
829 FunctionCall2Coll(procinfo,
830 index->rd_indcollation[0],
831 PointerGetDatum(&in),
832 PointerGetDatum(&out));
833
834 /*
835 * Form new leaf tuples and count up the total space needed.
836 */
837 totalLeafSizes = 0;
839 {
842 state->leafTupDesc,
843 leafDatums,
844 leafIsnulls,
845 isNulls);
846
849
851 leafDatums,
852 leafIsnulls);
854 }
855 }
856 else
857 {
858 /*
859 * Perform dummy split that puts all tuples into one node.
860 * checkAllTheSame will override this and force allTheSame mode.
861 */
863 out.nNodes = 1;
864 out.nodeLabels = NULL;
866
867 /*
868 * Form new leaf tuples and count up the total space needed.
869 */
870 totalLeafSizes = 0;
872 {
875 state->leafTupDesc,
876 leafDatums,
877 leafIsnulls,
878 isNulls);
879
880 /*
881 * Nulls tree can contain only null key values.
882 */
885
887 leafDatums,
888 leafIsnulls);
890 }
891 }
892
893 /*
894 * Check to see if the picksplit function failed to separate the values,
895 * ie, it put them all into the same child node. If so, select allTheSame
896 * mode and create a random split instead. See comments for
897 * checkAllTheSame as to why we need to know if the new leaf tuples could
898 * fit on one page.
899 */
900 allTheSame = checkAllTheSame(&in, &out,
901 totalLeafSizes > SPGIST_PAGE_CAPACITY,
902 &includeNew);
903
904 /*
905 * If checkAllTheSame decided we must exclude the new tuple, don't
906 * consider it any further.
907 */
908 if (includeNew)
909 maxToInclude = in.nTuples;
910 else
911 {
912 maxToInclude = in.nTuples - 1;
914 }
915
916 /*
917 * Allocate per-node work arrays. Since checkAllTheSame could replace
918 * out.nNodes with a value larger than the number of tuples on the input
919 * page, we can't allocate these arrays before here.
920 */
923
924 /*
925 * Form nodes of inner tuple and inner tuple itself
926 */
928 {
931
932 if (!labelisnull)
935 }
938 out.nNodes, nodes);
939 innerTuple->allTheSame = allTheSame;
940
941 /*
942 * Update nodes[] array to point into the newly formed innerTuple, so that
943 * we can adjust their downlinks below.
944 */
946 {
947 nodes[i] = node;
948 }
949
950 /*
951 * Re-scan new leaf tuples and count up the space needed under each node.
952 */
954 {
959 }
960
961 /*
962 * To perform the split, we must insert a new inner tuple, which can't go
963 * on a leaf page; and unless we are splitting the root page, we must then
964 * update the parent tuple's downlink to point to the inner tuple. If
965 * there is room, we'll put the new inner tuple on the same page as the
966 * parent tuple, otherwise we need another non-leaf buffer. But if the
967 * parent page is the root, we can't add the new inner tuple there,
968 * because the root page must have only one inner tuple.
969 */
975 {
976 /* New inner tuple will fit on parent page */
977 newInnerBuffer = parent->buffer;
978 }
980 {
981 /* Send tuple to page with next triple parity (see README) */
984 (isNulls ? GBUF_NULLS : 0),
986 &xlrec.initInner);
987 }
988 else
989 {
990 /* Root page split ... inner tuple will go to root page */
991 newInnerBuffer = InvalidBuffer;
992 }
993
994 /*
995 * The new leaf tuples converted from the existing ones should require the
996 * same or less space, and therefore should all fit onto one page
997 * (although that's not necessarily the current page, since we can't
998 * delete the old tuples but only replace them with placeholders).
999 * However, the incoming new tuple might not also fit, in which case we
1000 * might need another picksplit cycle to reduce it some more.
1001 *
1002 * If there's not room to put everything back onto the current page, then
1003 * we decide on a per-node basis which tuples go to the new page. (We do
1004 * it like that because leaf tuple chains can't cross pages, so we must
1005 * place all leaf tuples belonging to the same parent node on the same
1006 * page.)
1007 *
1008 * If we are splitting the root page (turning it from a leaf page into an
1009 * inner page), then no leaf tuples can go back to the current page; they
1010 * must all go somewhere else.
1011 */
1014 else
1015 currentFreeSpace = 0; /* prevent assigning any tuples to current */
1016
1018
1019 if (totalLeafSizes <= currentFreeSpace)
1020 {
1021 /* All the leaf tuples will fit on current page */
1022 newLeafBuffer = InvalidBuffer;
1023 /* mark new leaf tuple as included in insertions, if allowed */
1024 if (includeNew)
1025 {
1026 nToInsert++;
1027 insertedNew = true;
1028 }
1031 }
1033 {
1034 /*
1035 * We're trying to split up a long value by repeated suffixing, but
1036 * it's not going to fit yet. Don't bother allocating a second leaf
1037 * buffer that we won't be able to use.
1038 */
1039 newLeafBuffer = InvalidBuffer;
1040 Assert(includeNew);
1041 Assert(nToInsert == 0);
1042 }
1043 else
1044 {
1045 /* We will need another leaf page */
1046 uint8 *nodePageSelect;
1047 int curspace;
1048 int newspace;
1049
1052 Min(totalLeafSizes,
1053 SPGIST_PAGE_CAPACITY),
1054 &xlrec.initDest);
1055
1056 /*
1057 * Attempt to assign node groups to the two pages. We might fail to
1058 * do so, even if totalLeafSizes is less than the available space,
1059 * because we can't split a group across pages.
1060 */
1062
1063 curspace = currentFreeSpace;
1066 {
1068 {
1070 curspace -= leafSizes[i];
1071 }
1072 else
1073 {
1075 newspace -= leafSizes[i];
1076 }
1077 }
1078 if (curspace >= 0 && newspace >= 0)
1079 {
1080 /* Successful assignment, so we can include the new leaf tuple */
1081 if (includeNew)
1082 {
1083 nToInsert++;
1084 insertedNew = true;
1085 }
1086 }
1087 else if (includeNew)
1088 {
1089 /* We must exclude the new leaf tuple from the split */
1091
1092 leafSizes[nodeOfNewTuple] -=
1094
1095 /* Repeat the node assignment process --- should succeed now */
1096 curspace = currentFreeSpace;
1099 {
1101 {
1103 curspace -= leafSizes[i];
1104 }
1105 else
1106 {
1108 newspace -= leafSizes[i];
1109 }
1110 }
1111 if (curspace < 0 || newspace < 0)
1113 }
1114 else
1115 {
1116 /* oops, we already excluded new tuple ... should not get here */
1118 }
1119 /* Expand the per-node assignments to be shown per leaf tuple */
1121 {
1123 leafPageSelect[i] = nodePageSelect[n];
1124 }
1125 }
1126
1127 /* Start preparing WAL record */
1128 xlrec.nDelete = 0;
1129 xlrec.initSrc = isNew;
1130 xlrec.storesNulls = isNulls;
1132
1134
1135 /* Here we begin making the changes to the target pages */
1136 START_CRIT_SECTION();
1137
1138 /*
1139 * Delete old leaf tuples from current buffer, except when we're splitting
1140 * the root; in that case there's no need because we'll re-init the page
1141 * below. We do this first to make room for reinserting new leaf tuples.
1142 */
1144 {
1145 /*
1146 * Init buffer instead of deleting individual tuples, but only if
1147 * there aren't any other live tuples and only during build; otherwise
1148 * we need to set a redirection tuple for concurrent scans.
1149 */
1153 {
1157 }
1158 else if (isNew)
1159 {
1160 /* don't expose the freshly init'd buffer as a backup block */
1161 Assert(nToDelete == 0);
1162 }
1163 else
1164 {
1165 xlrec.nDelete = nToDelete;
1166
1168 {
1169 /*
1170 * Need to create redirect tuple (it will point to new inner
1171 * tuple) but right now the new tuple's location is not known
1172 * yet. So, set the redirection pointer to "impossible" value
1173 * and remember its position to update tuple later.
1174 */
1175 if (nToDelete > 0)
1176 redirectTuplePos = toDelete[0];
1178 toDelete, nToDelete,
1179 SPGIST_REDIRECT,
1180 SPGIST_PLACEHOLDER,
1181 SPGIST_METAPAGE_BLKNO,
1182 FirstOffsetNumber);
1183 }
1184 else
1185 {
1186 /*
1187 * During index build there is not concurrent searches, so we
1188 * don't need to create redirection tuple.
1189 */
1191 toDelete, nToDelete,
1192 SPGIST_PLACEHOLDER,
1193 SPGIST_PLACEHOLDER,
1194 InvalidBlockNumber,
1195 InvalidOffsetNumber);
1196 }
1197 }
1198 }
1199
1200 /*
1201 * Put leaf tuples on proper pages, and update downlinks in innerTuple's
1202 * nodes.
1203 */
1204 startOffsets[0] = startOffsets[1] = InvalidOffsetNumber;
1206 {
1208 Buffer leafBuffer;
1209 BlockNumber leafBlock;
1210 OffsetNumber newoffset;
1211
1212 /* Which page is it going to? */
1214 leafBlock = BufferGetBlockNumber(leafBuffer);
1215
1216 /* Link tuple into correct chain for its node */
1218
1220 {
1223 }
1224 else
1226
1227 /* Insert it on page */
1229 (Item) it, it->size,
1230 &startOffsets[leafPageSelect[i]],
1231 false);
1232 toInsert[i] = newoffset;
1233
1234 /* ... and complete the chain linking */
1235 ItemPointerSet(&nodes[n]->t_tid, leafBlock, newoffset);
1236
1237 /* Also copy leaf tuple into WAL data */
1240 }
1241
1242 /*
1243 * We're done modifying the other leaf buffer (if any), so mark it dirty.
1244 * current->buffer will be marked below, after we're entirely done
1245 * modifying it.
1246 */
1248 {
1249 MarkBufferDirty(newLeafBuffer);
1250 }
1251
1252 /* Remember current buffer, since we're about to change "current" */
1253 saveCurrent = *current;
1254
1255 /*
1256 * Store the new innerTuple
1257 */
1259 {
1260 /*
1261 * new inner tuple goes to parent page
1262 */
1264
1265 /* Repoint "current" at the new inner tuple */
1271 (Item) innerTuple, innerTuple->size,
1272 NULL, false);
1273
1274 /*
1275 * Update parent node link and mark parent page dirty
1276 */
1281
1282 /*
1283 * Update redirection link (in old current buffer)
1284 */
1286 setRedirectionTuple(&saveCurrent, redirectTuplePos,
1288
1289 /* Done modifying old current buffer, mark it dirty */
1291 }
1293 {
1294 /*
1295 * new inner tuple will be stored on a new page
1296 */
1298
1299 /* Repoint "current" at the new inner tuple */
1300 current->buffer = newInnerBuffer;
1305 (Item) innerTuple, innerTuple->size,
1306 NULL, false);
1307
1308 /* Done modifying new current buffer, mark it dirty */
1310
1311 /*
1312 * Update parent node link and mark parent page dirty
1313 */
1318
1319 /*
1320 * Update redirection link (in old current buffer)
1321 */
1323 setRedirectionTuple(&saveCurrent, redirectTuplePos,
1325
1326 /* Done modifying old current buffer, mark it dirty */
1328 }
1329 else
1330 {
1331 /*
1332 * Splitting root page, which was a leaf but now becomes inner page
1333 * (and so "current" continues to point at it)
1334 */
1337
1341
1347 innerTuple->size);
1348
1349 /* No parent link to update, nor redirection to do */
1351 xlrec.nodeI = 0;
1352
1353 /* Done modifying new current buffer, mark it dirty */
1355
1356 /* saveCurrent doesn't represent a different buffer */
1358 }
1359
1361 {
1362 XLogRecPtr recptr;
1363 int flags;
1364
1365 XLogBeginInsert();
1366
1367 xlrec.nInsert = nToInsert;
1369
1370 XLogRegisterData(toDelete,
1372 XLogRegisterData(toInsert,
1374 XLogRegisterData(leafPageSelect,
1377 XLogRegisterData(leafdata, leafptr - leafdata);
1378
1379 /* Old leaf page */
1381 {
1382 flags = REGBUF_STANDARD;
1384 flags |= REGBUF_WILL_INIT;
1386 }
1387
1388 /* New leaf page */
1390 {
1391 flags = REGBUF_STANDARD;
1393 flags |= REGBUF_WILL_INIT;
1394 XLogRegisterBuffer(1, newLeafBuffer, flags);
1395 }
1396
1397 /* Inner page */
1398 flags = REGBUF_STANDARD;
1400 flags |= REGBUF_WILL_INIT;
1402
1403 /* Parent page, if different from inner page */
1405 {
1408 else
1410 }
1411
1412 /* Issue the WAL record */
1414
1415 /* Update page LSNs on all affected pages */
1417 {
1419
1420 PageSetLSN(page, recptr);
1421 }
1422
1424 {
1426
1427 PageSetLSN(page, recptr);
1428 }
1429
1431
1433 {
1435 }
1436 }
1437
1438 END_CRIT_SECTION();
1439
1440 /* Update local free-space cache and unlock buffers */
1442 {
1444 UnlockReleaseBuffer(newLeafBuffer);
1445 }
1447 {
1450 }
1451
1452 return insertedNew;
1453}
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1149
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:907
static void ItemPointerSet(ItemPointerData *pointer, BlockNumber blockNumber, OffsetNumber offNum)
Definition: itemptr.h:135
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition: itemptr.h:83
static void setRedirectionTuple(SPPageDesc *current, OffsetNumber position, BlockNumber blkno, OffsetNumber offnum)
Definition: spgdoinsert.c:568
static bool checkAllTheSame(spgPickSplitIn *in, spgPickSplitOut *out, bool tooBig, bool *includeNew)
Definition: spgdoinsert.c:599
void spgPageIndexMultiDelete(SpGistState *state, Page page, OffsetNumber *itemnos, int nitems, int firststate, int reststate, BlockNumber blkno, OffsetNumber offnum)
Definition: spgdoinsert.c:131
SpGistLeafTuple spgFormLeafTuple(SpGistState *state, ItemPointer heapPtr, const Datum *datums, const bool *isnulls)
Definition: spgutils.c:871
void spgDeformLeafTuple(SpGistLeafTuple tup, TupleDesc tupleDescriptor, Datum *datums, bool *isnulls, bool keyColumnIsNull)
Definition: spgutils.c:1115
Buffer SpGistGetBuffer(Relation index, int flags, int needSpace, bool *isNew)
Definition: spgutils.c:569
void SpGistSetLastUsedPage(Relation index, Buffer buffer)
Definition: spgutils.c:673
Definition: itemid.h:26
Definition: spgdoinsert.c:37
Definition: spgist_private.h:293
Definition: spgist.h:111
Definition: spgist.h:118
Definition: spgxlog.h:166
References SpGistInnerTupleData::allTheSame, Assert(), SPPageDesc::blkno, SPPageDesc::buffer, BufferGetBlockNumber(), BufferGetPage(), BufferIsValid(), checkAllTheSame(), spgPickSplitIn::datums, elog, END_CRIT_SECTION, ERROR, FirstOffsetNumber, FunctionCall2Coll(), GBUF_INNER_PARITY, GBUF_LEAF, GBUF_NULLS, spgPickSplitOut::hasPrefix, i, index_getprocinfo(), INDEX_MAX_KEYS, spgxlogPickSplit::initDest, spgxlogPickSplit::initInner, spgxlogPickSplit::initSrc, spgxlogPickSplit::innerIsParent, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, spgxlogPickSplit::isRootSplit, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), ItemPointerIsValid(), ItemPointerSet(), label, spgPickSplitOut::leafTupleDatums, spgPickSplitIn::level, spgPickSplitOut::mapTuplesToNodes, MarkBufferDirty(), Min, spgxlogPickSplit::nDelete, spgxlogPickSplit::nInsert, spgPickSplitOut::nNodes, SPPageDesc::node, spgxlogPickSplit::nodeI, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, SPPageDesc::offnum, spgxlogPickSplit::offnumInner, spgxlogPickSplit::offnumParent, SPPageDesc::page, PageAddItem, PageGetExactFreeSpace(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), PageSetLSN(), palloc(), palloc0(), PointerGetDatum(), spgPickSplitOut::prefixDatum, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationNeedsWAL, saveNodeLink(), setRedirectionTuple(), SGDTSIZE, SGITITERATE, SGLT_GET_NEXTOFFSET, SGLT_SET_NEXTOFFSET, SGLTDATUM, SpGistInnerTupleData::size, SpGistLeafTupleData::size, SizeOfSpgxlogPickSplit, spgDeformLeafTuple(), spgFormInnerTuple(), spgFormLeafTuple(), spgFormNodeTuple(), SPGIST_DEAD, SPGIST_LEAF, SPGIST_LIVE, SPGIST_METAPAGE_BLKNO, SPGIST_NULLS, SPGIST_PAGE_CAPACITY, SPGIST_PICKSPLIT_PROC, SPGIST_PLACEHOLDER, SPGIST_REDIRECT, SpGistBlockIsRoot, SpGistGetBuffer(), SpGistInitBuffer(), SpGistPageAddNewItem(), SpGistPageGetFreeSpace, SpGistPageGetOpaque, SpGistSetLastUsedPage(), spgKeyColumn, spgPageIndexMultiDelete(), START_CRIT_SECTION, spgxlogPickSplit::stateSrc, STORE_STATE, spgxlogPickSplit::storesNulls, SpGistLeafTupleData::tupstate, UnlockReleaseBuffer(), XLOG_SPGIST_PICKSPLIT, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by spgdoinsert().
◆ moveLeafs()
|
static |
Definition at line 387 of file spgdoinsert.c.
390{
392 nDelete,
393 nInsert,
394 size;
395 Buffer nbuf;
396 Page npage;
398 startOffset = InvalidOffsetNumber;
399 bool replaceDead = false;
400 OffsetNumber *toDelete;
401 OffsetNumber *toInsert;
402 BlockNumber nblkno;
403 spgxlogMoveLeafs xlrec;
404 char *leafdata,
405 *leafptr;
406
407 /* This doesn't work on root page */
410
411 /* Locate the tuples to be moved, and count up the space needed */
415
417
418 nDelete = 0;
421 {
422 SpGistLeafTuple it;
423
428
430 {
431 toDelete[nDelete] = i;
433 nDelete++;
434 }
436 {
437 /* We could see a DEAD tuple as first/only chain item */
440 /* We don't want to move it, so don't count it in size */
441 toDelete[nDelete] = i;
442 nDelete++;
443 replaceDead = true;
444 }
445 else
447
449 }
450
451 /* Find a leaf page that will hold them */
453 size, &xlrec.newPage);
454 npage = BufferGetPage(nbuf);
455 nblkno = BufferGetBlockNumber(nbuf);
457
458 leafdata = leafptr = palloc(size);
459
460 START_CRIT_SECTION();
461
462 /* copy all the old tuples to new page, unless they're dead */
463 nInsert = 0;
464 if (!replaceDead)
465 {
467 {
468 SpGistLeafTuple it;
469
473
474 /*
475 * Update chain link (notice the chain order gets reversed, but we
476 * don't care). We're modifying the tuple on the source page
477 * here, but it's okay since we're about to delete it.
478 */
479 SGLT_SET_NEXTOFFSET(it, r);
480
482 &startOffset, false);
483
484 toInsert[nInsert] = r;
485 nInsert++;
486
487 /* save modified tuple into leafdata as well */
488 memcpy(leafptr, it, it->size);
489 leafptr += it->size;
490 }
491 }
492
493 /* add the new tuple as well */
494 SGLT_SET_NEXTOFFSET(newLeafTuple, r);
496 (Item) newLeafTuple, newLeafTuple->size,
497 &startOffset, false);
498 toInsert[nInsert] = r;
499 nInsert++;
500 memcpy(leafptr, newLeafTuple, newLeafTuple->size);
501 leafptr += newLeafTuple->size;
502
503 /*
504 * Now delete the old tuples, leaving a redirection pointer behind for the
505 * first one, unless we're doing an index build; in which case there can't
506 * be any concurrent scan so we need not provide a redirect.
507 */
510 SPGIST_PLACEHOLDER,
511 nblkno, r);
512
513 /* Update parent's downlink and mark parent page dirty */
515
516 /* Mark the leaf pages too */
518 MarkBufferDirty(nbuf);
519
521 {
522 XLogRecPtr recptr;
523
524 /* prepare WAL info */
526
527 xlrec.nMoves = nDelete;
528 xlrec.replaceDead = replaceDead;
529 xlrec.storesNulls = isNulls;
530
533
534 XLogBeginInsert();
536 XLogRegisterData(toDelete,
538 XLogRegisterData(toInsert,
540 XLogRegisterData(leafdata, leafptr - leafdata);
541
545
547
549 PageSetLSN(npage, recptr);
551 }
552
553 END_CRIT_SECTION();
554
555 /* Update local free-space cache and release new buffer */
557 UnlockReleaseBuffer(nbuf);
558}
Definition: spgxlog.h:65
References Assert(), SPPageDesc::blkno, SPPageDesc::buffer, BufferGetBlockNumber(), BufferGetPage(), elog, END_CRIT_SECTION, ERROR, FirstOffsetNumber, GBUF_LEAF, GBUF_NULLS, i, InvalidBuffer, InvalidOffsetNumber, MarkBufferDirty(), spgxlogMoveLeafs::newPage, spgxlogMoveLeafs::nMoves, SPPageDesc::node, spgxlogMoveLeafs::nodeI, SPPageDesc::offnum, spgxlogMoveLeafs::offnumParent, SPPageDesc::page, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), PageSetLSN(), palloc(), REGBUF_STANDARD, REGBUF_WILL_INIT, RelationNeedsWAL, spgxlogMoveLeafs::replaceDead, saveNodeLink(), SGLT_GET_NEXTOFFSET, SGLT_SET_NEXTOFFSET, SpGistLeafTupleData::size, SizeOfSpgxlogMoveLeafs, SPGIST_DEAD, SPGIST_LIVE, SPGIST_PLACEHOLDER, SPGIST_REDIRECT, SpGistGetBuffer(), SpGistPageAddNewItem(), SpGistSetLastUsedPage(), spgPageIndexMultiDelete(), START_CRIT_SECTION, spgxlogMoveLeafs::stateSrc, STORE_STATE, spgxlogMoveLeafs::storesNulls, SpGistLeafTupleData::tupstate, UnlockReleaseBuffer(), XLOG_SPGIST_MOVE_LEAFS, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by spgdoinsert().
◆ saveNodeLink()
|
static |
Definition at line 186 of file spgdoinsert.c.
188{
189 SpGistInnerTuple innerTuple;
190
193
195
197}
void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN, BlockNumber blkno, OffsetNumber offset)
Definition: spgdoinsert.c:52
References SPPageDesc::buffer, MarkBufferDirty(), SPPageDesc::node, SPPageDesc::offnum, SPPageDesc::page, PageGetItem(), PageGetItemId(), and spgUpdateNodeLink().
Referenced by addLeafTuple(), doPickSplit(), moveLeafs(), and spgAddNodeAction().
◆ setRedirectionTuple()
|
static |
Definition at line 568 of file spgdoinsert.c.
References Assert(), ItemPointerGetBlockNumber(), ItemPointerSet(), SPPageDesc::page, PageGetItem(), PageGetItemId(), SpGistDeadTupleData::pointer, SPGIST_METAPAGE_BLKNO, SPGIST_REDIRECT, and SpGistDeadTupleData::tupstate.
Referenced by doPickSplit().
◆ spgAddNodeAction()
|
static |
Definition at line 1513 of file spgdoinsert.c.
1517{
1518 SpGistInnerTuple newInnerTuple;
1519 spgxlogAddNode xlrec;
1520
1521 /* Should not be applied to nulls */
1523
1524 /* Construct new inner tuple with additional node */
1526
1527 /* Prepare WAL record */
1530
1531 /* we don't fill these unless we need to change the parent downlink */
1532 xlrec.parentBlk = -1;
1534 xlrec.nodeI = 0;
1535
1536 /* we don't fill these unless tuple has to be moved */
1539
1542 {
1543 /*
1544 * We can replace the inner tuple by new version in-place
1545 */
1546 START_CRIT_SECTION();
1547
1550 (Item) newInnerTuple, newInnerTuple->size,
1553 newInnerTuple->size);
1554
1556
1558 {
1559 XLogRecPtr recptr;
1560
1561 XLogBeginInsert();
1563 XLogRegisterData(newInnerTuple, newInnerTuple->size);
1564
1566
1568
1570 }
1571
1572 END_CRIT_SECTION();
1573 }
1574 else
1575 {
1576 /*
1577 * move inner tuple to another page, and update parent
1578 */
1579 SpGistDeadTuple dt;
1580 SPPageDesc saveCurrent;
1581
1582 /*
1583 * It should not be possible to get here for the root page, since we
1584 * allow only one inner tuple on the root page, and spgFormInnerTuple
1585 * always checks that inner tuples don't exceed the size of a page.
1586 */
1590
1591 saveCurrent = *current;
1592
1595
1596 /*
1597 * obtain new buffer with the same parity as current, since it will be
1598 * a child of same parent tuple
1599 */
1603 &xlrec.newPage);
1606
1607 /*
1608 * Let's just make real sure new current isn't same as old. Right now
1609 * that's impossible, but if SpGistGetBuffer ever got smart enough to
1610 * delete placeholder tuples before checking space, maybe it wouldn't
1611 * be impossible. The case would appear to work except that WAL
1612 * replay would be subtly wrong, so I think a mere assert isn't enough
1613 * here.
1614 */
1617
1618 /*
1619 * New current and parent buffer will both be modified; but note that
1620 * parent buffer could be same as either new or old current.
1621 */
1623 xlrec.parentBlk = 0;
1625 xlrec.parentBlk = 1;
1626 else
1627 xlrec.parentBlk = 2;
1628
1629 START_CRIT_SECTION();
1630
1631 /* insert new ... */
1634 (Item) newInnerTuple, newInnerTuple->size,
1635 NULL, false);
1636
1638
1639 /* update parent's downlink and mark parent page dirty */
1641
1642 /*
1643 * Replace old tuple with a placeholder or redirection tuple. Unless
1644 * doing an index build, we have to insert a redirection tuple for
1645 * possible concurrent scans. We can't just delete it in any case,
1646 * because that could change the offsets of other tuples on the page,
1647 * breaking downlinks from their parents.
1648 */
1652 else
1655
1658 saveCurrent.offnum,
1661 dt->size);
1662
1665 else
1667
1669
1671 {
1672 XLogRecPtr recptr;
1673 int flags;
1674
1675 XLogBeginInsert();
1676
1677 /* orig page */
1679 /* new page */
1680 flags = REGBUF_STANDARD;
1682 flags |= REGBUF_WILL_INIT;
1684 /* parent page (if different from orig and new) */
1687
1689 XLogRegisterData(newInnerTuple, newInnerTuple->size);
1690
1692
1693 /* we don't bother to check if any of these are redundant */
1697 }
1698
1699 END_CRIT_SECTION();
1700
1701 /* Release saveCurrent if it's not same as current or parent */
1704 {
1707 }
1708 }
1709}
static SpGistInnerTuple addNode(SpGistState *state, SpGistInnerTuple tuple, Datum label, int offset)
Definition: spgdoinsert.c:80
SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate, BlockNumber blkno, OffsetNumber offnum)
Definition: spgutils.c:1085
Definition: spgxlog.h:100
References addNode(), Assert(), SPPageDesc::blkno, SPPageDesc::buffer, BufferGetBlockNumber(), BufferGetPage(), elog, END_CRIT_SECTION, ERROR, GBUF_INNER_PARITY, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, MarkBufferDirty(), spgxlogAddNode::newPage, SPPageDesc::node, spgxlogAddNode::nodeI, SPPageDesc::offnum, spgxlogAddNode::offnum, spgxlogAddNode::offnumNew, spgxlogAddNode::offnumParent, SPPageDesc::page, PageAddItem, PageGetExactFreeSpace(), PageIndexTupleDelete(), PageSetLSN(), spgxlogAddNode::parentBlk, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationNeedsWAL, saveNodeLink(), SpGistInnerTupleData::size, SpGistDeadTupleData::size, spgFormDeadTuple(), SPGIST_PLACEHOLDER, SPGIST_REDIRECT, SpGistBlockIsRoot, SpGistGetBuffer(), SpGistPageAddNewItem(), SpGistPageGetOpaque, SpGistPageStoresNulls, SpGistSetLastUsedPage(), START_CRIT_SECTION, spgxlogAddNode::stateSrc, STORE_STATE, UnlockReleaseBuffer(), XLOG_SPGIST_ADD_NODE, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by spgdoinsert().
◆ spgdoinsert()
| bool spgdoinsert | ( | Relation | index, |
| SpGistState * | state, | ||
| ItemPointer | heapPtr, | ||
| Datum * | datums, | ||
| bool * | isnulls | ||
| ) |
Definition at line 1914 of file spgdoinsert.c.
1916{
1917 bool result = true;
1920 int level = 0;
1922 int leafSize;
1923 int bestLeafSize;
1924 int numNoProgressCycles = 0;
1925 SPPageDesc current,
1926 parent;
1927 FmgrInfo *procinfo = NULL;
1928
1929 /*
1930 * Look up FmgrInfo of the user-defined choose function once, to save
1931 * cycles in the loop below.
1932 */
1933 if (!isnull)
1935
1936 /*
1937 * Prepare the leaf datum to insert.
1938 *
1939 * If an optional "compress" method is provided, then call it to form the
1940 * leaf key datum from the input datum. Otherwise, store the input datum
1941 * as is. Since we don't use index_form_tuple in this AM, we have to make
1942 * sure value to be inserted is not toasted; FormIndexDatum doesn't
1943 * guarantee that. But we assume the "compress" method to return an
1944 * untoasted value.
1945 */
1946 if (!isnull)
1947 {
1949 {
1950 FmgrInfo *compressProcinfo = NULL;
1951
1953 leafDatums[spgKeyColumn] =
1954 FunctionCall1Coll(compressProcinfo,
1956 datums[spgKeyColumn]);
1957 }
1958 else
1959 {
1961
1963 leafDatums[spgKeyColumn] =
1965 else
1967 }
1968 }
1969 else
1971
1972 /* Likewise, ensure that any INCLUDE values are not toasted */
1974 {
1976 {
1979 else
1981 }
1982 else
1984 }
1985
1986 /*
1987 * Compute space needed for a leaf tuple containing the given data.
1988 */
1989 leafSize = SpGistGetLeafTupleSize(leafDescriptor, leafDatums, isnulls);
1990 /* Account for an item pointer, too */
1992
1993 /*
1994 * If it isn't gonna fit, and the opclass can't reduce the datum size by
1995 * suffixing, bail out now rather than doing a lot of useless work.
1996 */
1998 (isnull || !state->config.longValuesOK))
2000 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2006 bestLeafSize = leafSize;
2007
2008 /* Initialize "current" to the appropriate root page */
2011 current.page = NULL;
2013 current.node = -1;
2014
2015 /* "parent" is invalid for the moment */
2018 parent.page = NULL;
2020 parent.node = -1;
2021
2022 /*
2023 * Before entering the loop, try to clear any pending interrupt condition.
2024 * If a query cancel is pending, we might as well accept it now not later;
2025 * while if a non-canceling condition is pending, servicing it here avoids
2026 * having to restart the insertion and redo all the work so far.
2027 */
2028 CHECK_FOR_INTERRUPTS();
2029
2030 for (;;)
2031 {
2032 bool isNew = false;
2033
2034 /*
2035 * Bail out if query cancel is pending. We must have this somewhere
2036 * in the loop since a broken opclass could produce an infinite
2037 * picksplit loop. However, because we'll be holding buffer lock(s)
2038 * after the first iteration, ProcessInterrupts() wouldn't be able to
2039 * throw a cancel error here. Hence, if we see that an interrupt is
2040 * pending, break out of the loop and deal with the situation below.
2041 * Set result = false because we must restart the insertion if the
2042 * interrupt isn't a query-cancel-or-die case.
2043 */
2045 {
2046 result = false;
2047 break;
2048 }
2049
2051 {
2052 /*
2053 * Create a leaf page. If leafSize is too large to fit on a page,
2054 * we won't actually use the page yet, but it simplifies the API
2055 * for doPickSplit to always have a leaf page at hand; so just
2056 * quietly limit our request to a page size.
2057 */
2058 current.buffer =
2062 &isNew);
2064 }
2066 {
2067 /* we hold no parent-page lock, so no deadlock is possible */
2070 }
2072 {
2073 /* descend to a new child page */
2075
2076 /*
2077 * Attempt to acquire lock on child page. We must beware of
2078 * deadlock against another insertion process descending from that
2079 * page to our parent page (see README). If we fail to get lock,
2080 * abandon the insertion and tell our caller to start over.
2081 *
2082 * XXX this could be improved, because failing to get lock on a
2083 * buffer is not proof of a deadlock situation; the lock might be
2084 * held by a reader, or even just background writer/checkpointer
2085 * process. Perhaps it'd be worth retrying after sleeping a bit?
2086 */
2088 {
2091 return false;
2092 }
2093 }
2094 else
2095 {
2096 /* inner tuple can be stored on the same page as parent one */
2098 }
2100
2101 /* should not arrive at a page of the wrong type */
2105 current.blkno);
2106
2108 {
2109 SpGistLeafTuple leafTuple;
2110 int nToSplit,
2111 sizeToSplit;
2112
2116 {
2117 /* it fits on page, so insert it and we're done */
2119 ¤t, &parent, isnull, isNew);
2120 break;
2121 }
2122 else if ((sizeToSplit =
2124 &nToSplit)) < SPGIST_PAGE_CAPACITY / 2 &&
2125 nToSplit < 64 &&
2127 {
2128 /*
2129 * the amount of data is pretty small, so just move the whole
2130 * chain to another leaf page rather than splitting it.
2131 */
2132 Assert(!isNew);
2134 break; /* we're done */
2135 }
2136 else
2137 {
2138 /* picksplit */
2140 leafTuple, level, isnull, isNew))
2141 break; /* doPickSplit installed new tuples */
2142
2143 /* leaf tuple will not be inserted yet */
2144 pfree(leafTuple);
2145
2146 /*
2147 * current now describes new inner tuple, go insert into it
2148 */
2150 goto process_inner_tuple;
2151 }
2152 }
2153 else /* non-leaf page */
2154 {
2155 /*
2156 * Apply the opclass choose function to figure out how to insert
2157 * the given datum into the current inner tuple.
2158 */
2159 SpGistInnerTuple innerTuple;
2160 spgChooseIn in;
2161 spgChooseOut out;
2162
2163 /*
2164 * spgAddNode and spgSplitTuple cases will loop back to here to
2165 * complete the insertion operation. Just in case the choose
2166 * function is broken and produces add or split requests
2167 * repeatedly, check for query cancel (see comments above).
2168 */
2169 process_inner_tuple:
2171 {
2172 result = false;
2173 break;
2174 }
2175
2178
2181 in.level = level;
2187
2188 memset(&out, 0, sizeof(out));
2189
2190 if (!isnull)
2191 {
2192 /* use user-defined choose method */
2193 FunctionCall2Coll(procinfo,
2194 index->rd_indcollation[0],
2195 PointerGetDatum(&in),
2196 PointerGetDatum(&out));
2197 }
2198 else
2199 {
2200 /* force "match" action (to insert to random subnode) */
2202 }
2203
2205 {
2206 /*
2207 * It's not allowed to do an AddNode at an allTheSame tuple.
2208 * Opclass must say "match", in which case we choose a random
2209 * one of the nodes to descend into, or "split".
2210 */
2216 0, innerTuple->nNodes - 1);
2217 }
2218
2220 {
2222 /* Descend to N'th child node */
2224 ¤t, &parent,
2226 /* Adjust level as per opclass request */
2228 /* Replace leafDatum and recompute leafSize */
2229 if (!isnull)
2230 {
2232 leafSize = SpGistGetLeafTupleSize(leafDescriptor,
2233 leafDatums, isnulls);
2235 }
2236
2237 /*
2238 * Check new tuple size; fail if it can't fit, unless the
2239 * opclass says it can handle the situation by suffixing.
2240 *
2241 * However, the opclass can only shorten the leaf datum,
2242 * which may not be enough to ever make the tuple fit,
2243 * since INCLUDE columns might alone use more than a page.
2244 * Depending on the opclass' behavior, that could lead to
2245 * an infinite loop --- spgtextproc.c, for example, will
2246 * just repeatedly generate an empty-string leaf datum
2247 * once it runs out of data. Actual bugs in opclasses
2248 * might cause infinite looping, too. To detect such a
2249 * loop, check to see if we are making progress by
2250 * reducing the leafSize in each pass. This is a bit
2251 * tricky though. Because of alignment considerations,
2252 * the total tuple size might not decrease on every pass.
2253 * Also, there are edge cases where the choose method
2254 * might seem to not make progress for a cycle or two.
2255 * Somewhat arbitrarily, we allow up to 10 no-progress
2256 * iterations before failing. (This limit should be more
2257 * than MAXALIGN, to accommodate opclasses that trim one
2258 * byte from the leaf datum per pass.)
2259 */
2261 {
2262 bool ok = false;
2263
2265 {
2266 if (leafSize < bestLeafSize)
2267 {
2268 ok = true;
2269 bestLeafSize = leafSize;
2270 numNoProgressCycles = 0;
2271 }
2272 else if (++numNoProgressCycles < 10)
2273 ok = true;
2274 }
2275 if (!ok)
2277 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2283 }
2284
2285 /*
2286 * Loop around and attempt to insert the new leafDatum at
2287 * "current" (which might reference an existing child
2288 * tuple, or might be invalid to force us to find a new
2289 * page for the tuple).
2290 */
2291 break;
2293 /* AddNode is not sensible if nodes don't have labels */
2296 /* Add node to inner tuple, per request */
2298 ¤t, &parent,
2301
2302 /*
2303 * Retry insertion into the enlarged node. We assume that
2304 * we'll get a MatchNode result this time.
2305 */
2306 goto process_inner_tuple;
2307 break;
2309 /* Split inner tuple, per request */
2311 ¤t, &out);
2312
2313 /* Retry insertion into the split node */
2314 goto process_inner_tuple;
2315 break;
2316 default:
2319 break;
2320 }
2321 }
2322 } /* end loop */
2323
2324 /*
2325 * Release any buffers we're still holding. Beware of possibility that
2326 * current and parent reference same buffer.
2327 */
2329 {
2332 }
2335 {
2338 }
2339
2340 /*
2341 * We do not support being called while some outer function is holding a
2342 * buffer lock (or any other reason to postpone query cancels). If that
2343 * were the case, telling the caller to retry would create an infinite
2344 * loop.
2345 */
2347
2348 /*
2349 * Finally, check for interrupts again. If there was a query cancel,
2350 * ProcessInterrupts() will be able to throw the error here. If it was
2351 * some other kind of interrupt that can just be cleared, return false to
2352 * tell our caller to retry.
2353 */
2354 CHECK_FOR_INTERRUPTS();
2355
2356 return result;
2357}
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1129
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:873
uint64 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
Definition: pg_prng.c:144
static void spgAddNodeAction(Relation index, SpGistState *state, SpGistInnerTuple innerTuple, SPPageDesc *current, SPPageDesc *parent, int nodeN, Datum nodeLabel)
Definition: spgdoinsert.c:1513
static void spgSplitNodeAction(Relation index, SpGistState *state, SpGistInnerTuple innerTuple, SPPageDesc *current, spgChooseOut *out)
Definition: spgdoinsert.c:1715
static void spgMatchNodeAction(Relation index, SpGistState *state, SpGistInnerTuple innerTuple, SPPageDesc *current, SPPageDesc *parent, int nodeN)
Definition: spgdoinsert.c:1459
static bool doPickSplit(Relation index, SpGistState *state, SPPageDesc *current, SPPageDesc *parent, SpGistLeafTuple newLeafTuple, int level, bool isNulls, bool isNew)
Definition: spgdoinsert.c:677
static void moveLeafs(Relation index, SpGistState *state, SPPageDesc *current, SPPageDesc *parent, SpGistLeafTuple newLeafTuple, bool isNulls)
Definition: spgdoinsert.c:387
static int checkSplitConditions(Relation index, SpGistState *state, SPPageDesc *current, int *nToSplit)
Definition: spgdoinsert.c:333
static void addLeafTuple(Relation index, SpGistState *state, SpGistLeafTuple leafTuple, SPPageDesc *current, SPPageDesc *parent, bool isNulls, bool isNew)
Definition: spgdoinsert.c:203
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:1160
Size SpGistGetLeafTupleSize(TupleDesc tupleDescriptor, const Datum *datums, const bool *isnulls)
Definition: spgutils.c:818
Definition: tupdesc.h:136
Definition: spgist.h:54
Definition: spgist.h:75
struct spgChooseOut::@51::@53 addNode
struct spgChooseOut::@51::@52 matchNode
union spgChooseOut::@51 result
static CompactAttribute * TupleDescCompactAttr(TupleDesc tupdesc, int i)
Definition: tupdesc.h:175
References addLeafTuple(), spgChooseOut::addNode, spgChooseIn::allTheSame, SpGistInnerTupleData::allTheSame, Assert(), CompactAttribute::attlen, SPPageDesc::blkno, SPPageDesc::buffer, BUFFER_LOCK_EXCLUSIVE, BufferGetBlockNumber(), BufferGetPage(), CHECK_FOR_INTERRUPTS, checkSplitConditions(), ConditionalLockBuffer(), spgChooseIn::datum, doPickSplit(), elog, ereport, errcode(), errhint(), errmsg(), ERROR, FirstOffsetNumber, FunctionCall1Coll(), FunctionCall2Coll(), GBUF_LEAF, GBUF_NULLS, spgChooseIn::hasPrefix, i, index_getprocid(), index_getprocinfo(), INDEX_MAX_KEYS, INTERRUPTS_CAN_BE_PROCESSED, INTERRUPTS_PENDING_CONDITION, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, spgChooseIn::leafDatum, spgChooseIn::level, spgChooseOut::levelAdd, LockBuffer(), spgChooseOut::matchNode, Min, moveLeafs(), TupleDescData::natts, spgChooseIn::nNodes, SpGistInnerTupleData::nNodes, SPPageDesc::node, spgChooseOut::nodeLabel, spgChooseIn::nodeLabels, spgChooseOut::nodeN, SPPageDesc::offnum, OidIsValid, SPPageDesc::page, PageGetItem(), PageGetItemId(), pfree(), PG_DETOAST_DATUM, pg_global_prng_state, pg_prng_uint64_range(), PointerGetDatum(), spgChooseIn::prefixDatum, SpGistInnerTupleData::prefixSize, ReadBuffer(), RelationGetRelationName, ReleaseBuffer(), spgChooseOut::restDatum, spgChooseOut::result, spgChooseOut::resultType, SGITDATUM, SpGistLeafTupleData::size, spgAddNode, spgAddNodeAction(), spgExtractNodeLabels(), spgFirstIncludeColumn, spgFormLeafTuple(), SPGIST_CHOOSE_PROC, SPGIST_COMPRESS_PROC, SPGIST_NULL_BLKNO, SPGIST_PAGE_CAPACITY, SPGIST_ROOT_BLKNO, SpGistGetBuffer(), SpGistGetLeafTupleSize(), SpGistPageGetFreeSpace, SpGistPageIsLeaf, SpGistPageStoresNulls, SpGistSetLastUsedPage(), spgKeyColumn, spgMatchNode, spgMatchNodeAction(), spgSplitNodeAction(), spgSplitTuple, TupleDescCompactAttr(), and UnlockReleaseBuffer().
Referenced by spginsert(), and spgistBuildCallback().
◆ spgMatchNodeAction()
|
static |
Definition at line 1459 of file spgdoinsert.c.
1462{
1464 SpGistNodeTuple node;
1465
1466 /* Release previous parent buffer if any */
1469 {
1472 }
1473
1474 /* Repoint parent to specified node of current inner tuple */
1479 parent->node = nodeN;
1480
1481 /* Locate that node */
1483 {
1485 break;
1486 }
1487
1490 nodeN);
1491
1492 /* Point current to the downlink location, if any */
1494 {
1497 }
1498 else
1499 {
1500 /* Downlink is empty, so we'll need to find a new page */
1503 }
1504
1506 current->page = NULL;
1507}
References SPPageDesc::blkno, SPPageDesc::buffer, elog, ERROR, i, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), ItemPointerIsValid(), SPPageDesc::node, SPPageDesc::offnum, SPPageDesc::page, SGITITERATE, SpGistSetLastUsedPage(), IndexTupleData::t_tid, and UnlockReleaseBuffer().
Referenced by spgdoinsert().
◆ spgPageIndexMultiDelete()
| void spgPageIndexMultiDelete | ( | SpGistState * | state, |
| Page | page, | ||
| OffsetNumber * | itemnos, | ||
| int | nitems, | ||
| int | firststate, | ||
| int | reststate, | ||
| BlockNumber | blkno, | ||
| OffsetNumber | offnum | ||
| ) |
Definition at line 131 of file spgdoinsert.c.
135{
136 OffsetNumber firstItem;
138 SpGistDeadTuple tuple = NULL;
140
142 return; /* nothing to do */
143
144 /*
145 * For efficiency we want to use PageIndexMultiDelete, which requires the
146 * targets to be listed in sorted order, so we have to sort the itemnos
147 * array. (This also greatly simplifies the math for reinserting the
148 * replacement tuples.) However, we must not scribble on the caller's
149 * array, so we have to make a copy.
150 */
154
156
157 firstItem = itemnos[0];
158
160 {
162 int tupstate;
163
164 tupstate = (itemno == firstItem) ? firststate : reststate;
167
169 itemno, false, false) != itemno)
171 tuple->size);
172
174 SpGistPageGetOpaque(page)->nRedirection++;
176 SpGistPageGetOpaque(page)->nPlaceholder++;
177 }
178}
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
Definition: bufpage.c:1160
static int cmpOffsetNumbers(const void *a, const void *b)
Definition: spgdoinsert.c:112
References cmpOffsetNumbers(), elog, ERROR, i, MaxIndexTuplesPerPage, nitems, PageAddItem, PageIndexMultiDelete(), qsort, SpGistDeadTupleData::size, spgFormDeadTuple(), SPGIST_PLACEHOLDER, SPGIST_REDIRECT, SpGistPageGetOpaque, and SpGistDeadTupleData::tupstate.
Referenced by doPickSplit(), moveLeafs(), spgRedoMoveLeafs(), spgRedoPickSplit(), spgRedoVacuumLeaf(), and vacuumLeafPage().
◆ spgSplitNodeAction()
|
static |
Definition at line 1715 of file spgdoinsert.c.
1718{
1719 SpGistInnerTuple prefixTuple,
1720 postfixTuple;
1721 SpGistNodeTuple node,
1722 *nodes;
1723 BlockNumber postfixBlkno;
1724 OffsetNumber postfixOffset;
1726 spgxlogSplitTuple xlrec;
1728
1729 /* Should not be applied to nulls */
1731
1732 /* Check opclass gave us sane values */
1742
1743 /*
1744 * Construct new prefix tuple with requested number of nodes. We'll fill
1745 * in the childNodeN'th node's downlink below.
1746 */
1749
1751 {
1753 bool labelisnull;
1754
1756 if (!labelisnull)
1759 }
1760
1765 nodes);
1766
1767 /* it must fit in the space that innerTuple now occupies */
1770
1771 /*
1772 * Construct new postfix tuple, containing all nodes of innerTuple with
1773 * same node datums, but with the prefix specified by the picksplit
1774 * function.
1775 */
1778 {
1779 nodes[i] = node;
1780 }
1781
1785 innerTuple->nNodes, nodes);
1786
1787 /* Postfix tuple is allTheSame if original tuple was */
1789
1790 /* prep data for WAL record */
1792
1793 /*
1794 * If we can't fit both tuples on the current page, get a new page for the
1795 * postfix tuple. In particular, can't split to the root page.
1796 *
1797 * For the space calculation, note that prefixTuple replaces innerTuple
1798 * but postfixTuple will be a new entry.
1799 */
1803 {
1804 /*
1805 * Choose page with next triple parity, because postfix tuple is a
1806 * child of prefix one
1807 */
1811 &xlrec.newPage);
1812 }
1813
1814 START_CRIT_SECTION();
1815
1816 /*
1817 * Replace old tuple by prefix tuple
1818 */
1821 (Item) prefixTuple, prefixTuple->size,
1825 prefixTuple->size);
1826
1827 /*
1828 * put postfix tuple into appropriate page
1829 */
1831 {
1832 postfixBlkno = current->blkno;
1833 xlrec.offnumPostfix = postfixOffset =
1835 (Item) postfixTuple, postfixTuple->size,
1836 NULL, false);
1838 }
1839 else
1840 {
1841 postfixBlkno = BufferGetBlockNumber(newBuffer);
1842 xlrec.offnumPostfix = postfixOffset =
1844 (Item) postfixTuple, postfixTuple->size,
1845 NULL, false);
1846 MarkBufferDirty(newBuffer);
1848 }
1849
1850 /*
1851 * And set downlink pointer in the prefix tuple to point to postfix tuple.
1852 * (We can't avoid this step by doing the above two steps in opposite
1853 * order, because there might not be enough space on the page to insert
1854 * the postfix tuple first.) We have to update the local copy of the
1855 * prefixTuple too, because that's what will be written to WAL.
1856 */
1858 postfixBlkno, postfixOffset);
1862 postfixBlkno, postfixOffset);
1863
1865
1867 {
1868 XLogRecPtr recptr;
1869
1870 XLogBeginInsert();
1874
1877 {
1878 int flags;
1879
1880 flags = REGBUF_STANDARD;
1882 flags |= REGBUF_WILL_INIT;
1883 XLogRegisterBuffer(1, newBuffer, flags);
1884 }
1885
1887
1889
1891 {
1893 }
1894 }
1895
1896 END_CRIT_SECTION();
1897
1898 /* Update local free-space cache and release buffer */
1900 {
1902 UnlockReleaseBuffer(newBuffer);
1903 }
1904}
struct spgChooseOut::@51::@54 splitTuple
Definition: spgxlog.h:142
References SpGistInnerTupleData::allTheSame, Assert(), SPPageDesc::blkno, SPPageDesc::buffer, BufferGetBlockNumber(), BufferGetPage(), spgChooseOut::childNodeN, elog, END_CRIT_SECTION, ERROR, GBUF_INNER_PARITY, i, InvalidBuffer, label, MarkBufferDirty(), spgxlogSplitTuple::newPage, SpGistInnerTupleData::nNodes, SPPageDesc::offnum, spgxlogSplitTuple::offnumPostfix, spgxlogSplitTuple::offnumPrefix, SPPageDesc::page, PageAddItem, PageGetItem(), PageGetItemId(), PageIndexTupleDelete(), PageSetLSN(), palloc(), spgxlogSplitTuple::postfixBlkSame, spgChooseOut::postfixHasPrefix, spgChooseOut::postfixPrefixDatum, spgChooseOut::prefixHasPrefix, spgChooseOut::prefixNNodes, spgChooseOut::prefixNodeLabels, spgChooseOut::prefixPrefixDatum, REGBUF_STANDARD, REGBUF_WILL_INIT, RelationNeedsWAL, spgChooseOut::result, SGITITERATE, SGITMAXNNODES, SpGistInnerTupleData::size, spgFormInnerTuple(), spgFormNodeTuple(), SpGistBlockIsRoot, SpGistGetBuffer(), SpGistPageAddNewItem(), SpGistPageGetFreeSpace, SpGistPageStoresNulls, SpGistSetLastUsedPage(), spgUpdateNodeLink(), spgChooseOut::splitTuple, START_CRIT_SECTION, UnlockReleaseBuffer(), XLOG_SPGIST_SPLIT_TUPLE, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by spgdoinsert().
◆ spgUpdateNodeLink()
| void spgUpdateNodeLink | ( | SpGistInnerTuple | tup, |
| int | nodeN, | ||
| BlockNumber | blkno, | ||
| OffsetNumber | offset | ||
| ) |
Definition at line 52 of file spgdoinsert.c.
References elog, ERROR, i, ItemPointerSet(), SGITITERATE, and IndexTupleData::t_tid.
Referenced by saveNodeLink(), spgRedoAddLeaf(), spgRedoAddNode(), spgRedoMoveLeafs(), spgRedoPickSplit(), and spgSplitNodeAction().
