Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * gistbuild.c
4 : : * build algorithm for GiST indexes implementation.
5 : : *
6 : : * There are two different strategies:
7 : : *
8 : : * 1. Sort all input tuples, pack them into GiST leaf pages in the sorted
9 : : * order, and create downlinks and internal pages as we go. This builds
10 : : * the index from the bottom up, similar to how B-tree index build
11 : : * works.
12 : : *
13 : : * 2. Start with an empty index, and insert all tuples one by one.
14 : : *
15 : : * The sorted method is used if the operator classes for all columns have
16 : : * a 'sortsupport' defined. Otherwise, we resort to the second strategy.
17 : : *
18 : : * The second strategy can optionally use buffers at different levels of
19 : : * the tree to reduce I/O, see "Buffering build algorithm" in the README
20 : : * for a more detailed explanation. It initially calls insert over and
21 : : * over, but switches to the buffered algorithm after a certain number of
22 : : * tuples (unless buffering mode is disabled).
23 : : *
24 : : *
25 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
26 : : * Portions Copyright (c) 1994, Regents of the University of California
27 : : *
28 : : * IDENTIFICATION
29 : : * src/backend/access/gist/gistbuild.c
30 : : *
31 : : *-------------------------------------------------------------------------
32 : : */
33 : : #include "postgres.h"
34 : :
35 : : #include <math.h>
36 : :
37 : : #include "access/genam.h"
38 : : #include "access/gist_private.h"
39 : : #include "access/tableam.h"
40 : : #include "access/xloginsert.h"
41 : : #include "miscadmin.h"
42 : : #include "nodes/execnodes.h"
43 : : #include "optimizer/optimizer.h"
44 : : #include "storage/bufmgr.h"
45 : : #include "storage/bulk_write.h"
46 : :
47 : : #include "utils/memutils.h"
48 : : #include "utils/rel.h"
49 : : #include "utils/tuplesort.h"
50 : :
51 : : /* Step of index tuples for check whether to switch to buffering build mode */
52 : : #define BUFFERING_MODE_SWITCH_CHECK_STEP 256
53 : :
54 : : /*
55 : : * Number of tuples to process in the slow way before switching to buffering
56 : : * mode, when buffering is explicitly turned on. Also, the number of tuples
57 : : * to process between readjusting the buffer size parameter, while in
58 : : * buffering mode.
59 : : */
60 : : #define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096
61 : :
62 : : /*
63 : : * Strategy used to build the index. It can change between the
64 : : * GIST_BUFFERING_* modes on the fly, but if the Sorted method is used,
65 : : * that needs to be decided up-front and cannot be changed afterwards.
66 : : */
67 : : typedef enum
68 : : {
69 : : GIST_SORTED_BUILD, /* bottom-up build by sorting */
70 : : GIST_BUFFERING_DISABLED, /* in regular build mode and aren't going to
71 : : * switch */
72 : : GIST_BUFFERING_AUTO, /* in regular build mode, but will switch to
73 : : * buffering build mode if the index grows too
74 : : * big */
75 : : GIST_BUFFERING_STATS, /* gathering statistics of index tuple size
76 : : * before switching to the buffering build
77 : : * mode */
78 : : GIST_BUFFERING_ACTIVE, /* in buffering build mode */
79 : : } GistBuildMode;
80 : :
81 : : /* Working state for gistbuild and its callback */
82 : : typedef struct
83 : : {
84 : : Relation indexrel;
85 : : Relation heaprel;
86 : : GISTSTATE *giststate;
87 : :
88 : : Size freespace; /* amount of free space to leave on pages */
89 : :
90 : : GistBuildMode buildMode;
91 : :
92 : : int64 indtuples; /* number of tuples indexed */
93 : :
94 : : /*
95 : : * Extra data structures used during a buffering build. 'gfbb' contains
96 : : * information related to managing the build buffers. 'parentMap' is a
97 : : * lookup table of the parent of each internal page.
98 : : */
99 : : int64 indtuplesSize; /* total size of all indexed tuples */
100 : : GISTBuildBuffers *gfbb;
101 : : HTAB *parentMap;
102 : :
103 : : /*
104 : : * Extra data structures used during a sorting build.
105 : : */
106 : : Tuplesortstate *sortstate; /* state data for tuplesort.c */
107 : :
108 : : BlockNumber pages_allocated;
109 : :
110 : : BulkWriteState *bulkstate;
111 : : } GISTBuildState;
112 : :
113 : : #define GIST_SORTED_BUILD_PAGE_NUM 4
114 : :
115 : : /*
116 : : * In sorted build, we use a stack of these structs, one for each level,
117 : : * to hold an in-memory buffer of last pages at the level.
118 : : *
119 : : * Sorting GiST build requires good linearization of the sort opclass. This is
120 : : * not always the case in multidimensional data. To tackle the anomalies, we
121 : : * buffer index tuples and apply picksplit that can be multidimension-aware.
122 : : */
123 : : typedef struct GistSortedBuildLevelState
124 : : {
125 : : int current_page;
126 : : BlockNumber last_blkno;
127 : : struct GistSortedBuildLevelState *parent; /* Upper level, if any */
128 : : Page pages[GIST_SORTED_BUILD_PAGE_NUM];
129 : : } GistSortedBuildLevelState;
130 : :
131 : : /* prototypes for private functions */
132 : :
133 : : static void gistSortedBuildCallback(Relation index, ItemPointer tid,
134 : : Datum *values, bool *isnull,
135 : : bool tupleIsAlive, void *state);
136 : : static void gist_indexsortbuild(GISTBuildState *state);
137 : : static void gist_indexsortbuild_levelstate_add(GISTBuildState *state,
138 : : GistSortedBuildLevelState *levelstate,
139 : : IndexTuple itup);
140 : : static void gist_indexsortbuild_levelstate_flush(GISTBuildState *state,
141 : : GistSortedBuildLevelState *levelstate);
142 : :
143 : : static void gistInitBuffering(GISTBuildState *buildstate);
144 : : static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep);
145 : : static void gistBuildCallback(Relation index,
146 : : ItemPointer tid,
147 : : Datum *values,
148 : : bool *isnull,
149 : : bool tupleIsAlive,
150 : : void *state);
151 : : static void gistBufferingBuildInsert(GISTBuildState *buildstate,
152 : : IndexTuple itup);
153 : : static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup,
154 : : BlockNumber startblkno, int startlevel);
155 : : static BlockNumber gistbufferinginserttuples(GISTBuildState *buildstate,
156 : : Buffer buffer, int level,
157 : : IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
158 : : BlockNumber parentblk, OffsetNumber downlinkoffnum);
159 : : static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate,
160 : : BlockNumber childblkno, int level,
161 : : BlockNumber *parentblkno,
162 : : OffsetNumber *downlinkoffnum);
163 : : static void gistProcessEmptyingQueue(GISTBuildState *buildstate);
164 : : static void gistEmptyAllBuffers(GISTBuildState *buildstate);
165 : : static int gistGetMaxLevel(Relation index);
166 : :
167 : : static void gistInitParentMap(GISTBuildState *buildstate);
168 : : static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child,
169 : : BlockNumber parent);
170 : : static void gistMemorizeAllDownlinks(GISTBuildState *buildstate,
171 : : Buffer parentbuf);
172 : : static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child);
173 : :
174 : :
175 : : /*
176 : : * Main entry point to GiST index build.
177 : : */
178 : : IndexBuildResult *
3010 tgl@sss.pgh.pa.us 179 :CBC 594 : gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
180 : : {
181 : : IndexBuildResult *result;
182 : : double reltuples;
183 : : GISTBuildState buildstate;
4602 heikki.linnakangas@i 184 : 594 : MemoryContext oldcxt = CurrentMemoryContext;
185 : : int fillfactor;
186 : : Oid SortSupportFnOids[INDEX_MAX_KEYS];
1280 tgl@sss.pgh.pa.us 187 : 594 : GiSTOptions *options = (GiSTOptions *) index->rd_options;
188 : :
189 : : /*
190 : : * We expect to be called exactly once for any index relation. If that's
191 : : * not the case, big trouble's what we have.
192 : : */
1305 heikki.linnakangas@i 193 [ - + ]: 594 : if (RelationGetNumberOfBlocks(index) != 0)
1305 heikki.linnakangas@i 194 [ # # ]:UBC 0 : elog(ERROR, "index \"%s\" already contains data",
195 : : RelationGetRelationName(index));
196 : :
4602 heikki.linnakangas@i 197 :CBC 594 : buildstate.indexrel = index;
1941 akorotkov@postgresql 198 : 594 : buildstate.heaprel = heap;
1305 heikki.linnakangas@i 199 : 594 : buildstate.sortstate = NULL;
200 : 594 : buildstate.giststate = initGISTstate(index);
201 : :
202 : : /*
203 : : * Create a temporary memory context that is reset once for each tuple
204 : : * processed. (Note: we don't bother to make this a child of the
205 : : * giststate's scanCxt, so we have to delete it separately at the end.)
206 : : */
207 : 594 : buildstate.giststate->tempCxt = createTempGistContext();
208 : :
209 : : /*
210 : : * Choose build strategy. First check whether the user specified to use
211 : : * buffering mode. (The use-case for that in the field is somewhat
212 : : * questionable perhaps, but it's important for testing purposes.)
213 : : */
1280 tgl@sss.pgh.pa.us 214 [ + + ]: 594 : if (options)
215 : : {
1663 alvherre@alvh.no-ip. 216 [ + + ]: 16 : if (options->buffering_mode == GIST_OPTION_BUFFERING_ON)
1305 heikki.linnakangas@i 217 : 6 : buildstate.buildMode = GIST_BUFFERING_STATS;
1663 alvherre@alvh.no-ip. 218 [ + + ]: 10 : else if (options->buffering_mode == GIST_OPTION_BUFFERING_OFF)
1305 heikki.linnakangas@i 219 : 3 : buildstate.buildMode = GIST_BUFFERING_DISABLED;
220 : : else /* must be "auto" */
221 : 7 : buildstate.buildMode = GIST_BUFFERING_AUTO;
222 : : }
223 : : else
224 : : {
225 : 578 : buildstate.buildMode = GIST_BUFFERING_AUTO;
226 : : }
227 : :
228 : : /*
229 : : * Unless buffering mode was forced, see if we can use sorting instead.
230 : : */
1280 tgl@sss.pgh.pa.us 231 [ + + ]: 594 : if (buildstate.buildMode != GIST_BUFFERING_STATS)
232 : : {
233 : 588 : bool hasallsortsupports = true;
234 : 588 : int keyscount = IndexRelationGetNumberOfKeyAttributes(index);
235 : :
236 [ + + ]: 666 : for (int i = 0; i < keyscount; i++)
237 : : {
238 : 591 : SortSupportFnOids[i] = index_getprocid(index, i + 1,
239 : : GIST_SORTSUPPORT_PROC);
240 [ + + ]: 591 : if (!OidIsValid(SortSupportFnOids[i]))
241 : : {
242 : 513 : hasallsortsupports = false;
243 : 513 : break;
244 : : }
245 : : }
246 [ + + ]: 588 : if (hasallsortsupports)
247 : 75 : buildstate.buildMode = GIST_SORTED_BUILD;
248 : : }
249 : :
250 : : /*
251 : : * Calculate target amount of free space to leave on pages.
252 : : */
1305 heikki.linnakangas@i 253 [ + + ]: 594 : fillfactor = options ? options->fillfactor : GIST_DEFAULT_FILLFACTOR;
4602 254 : 594 : buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100;
255 : :
256 : : /*
257 : : * Build the index using the chosen strategy.
258 : : */
1305 259 : 594 : buildstate.indtuples = 0;
260 : 594 : buildstate.indtuplesSize = 0;
261 : :
262 [ + + ]: 594 : if (buildstate.buildMode == GIST_SORTED_BUILD)
263 : : {
264 : : /*
265 : : * Sort all data, build the index from bottom up.
266 : : */
267 : 75 : buildstate.sortstate = tuplesort_begin_index_gist(heap,
268 : : index,
269 : : maintenance_work_mem,
270 : : NULL,
271 : : TUPLESORT_NONE);
272 : :
273 : : /* Scan the table, adding all tuples to the tuplesort */
274 : 75 : reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
275 : : gistSortedBuildCallback,
276 : : (void *) &buildstate, NULL);
277 : :
278 : : /*
279 : : * Perform the sort and build index pages.
280 : : */
281 : 75 : tuplesort_performsort(buildstate.sortstate);
282 : :
283 : 75 : gist_indexsortbuild(&buildstate);
284 : :
285 : 75 : tuplesort_end(buildstate.sortstate);
286 : : }
287 : : else
288 : : {
289 : : /*
290 : : * Initialize an empty index and insert all tuples, possibly using
291 : : * buffers on intermediate levels.
292 : : */
293 : : Buffer buffer;
294 : : Page page;
295 : :
296 : : /* initialize the root page */
379 andres@anarazel.de 297 : 519 : buffer = gistNewBuffer(index, heap);
1305 heikki.linnakangas@i 298 [ - + ]: 519 : Assert(BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO);
299 : 519 : page = BufferGetPage(buffer);
300 : :
301 : 519 : START_CRIT_SECTION();
302 : :
303 : 519 : GISTInitBuffer(buffer, F_LEAF);
304 : :
305 : 519 : MarkBufferDirty(buffer);
306 : 519 : PageSetLSN(page, GistBuildLSN);
307 : :
308 : 519 : UnlockReleaseBuffer(buffer);
309 : :
310 [ - + ]: 519 : END_CRIT_SECTION();
311 : :
312 : : /* Scan the table, inserting all the tuples to the index. */
313 : 519 : reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
314 : : gistBuildCallback,
315 : : (void *) &buildstate, NULL);
316 : :
317 : : /*
318 : : * If buffering was used, flush out all the tuples that are still in
319 : : * the buffers.
320 : : */
321 [ + + ]: 519 : if (buildstate.buildMode == GIST_BUFFERING_ACTIVE)
322 : : {
323 [ - + ]: 3 : elog(DEBUG1, "all tuples processed, emptying buffers");
324 : 3 : gistEmptyAllBuffers(&buildstate);
325 : 3 : gistFreeBuildBuffers(buildstate.gfbb);
326 : : }
327 : :
328 : : /*
329 : : * We didn't write WAL records as we built the index, so if
330 : : * WAL-logging is required, write all pages to the WAL now.
331 : : */
332 [ + + + + : 519 : if (RelationNeedsWAL(index))
+ + + + ]
333 : : {
334 : 323 : log_newpage_range(index, MAIN_FORKNUM,
335 : : 0, RelationGetNumberOfBlocks(index),
336 : : true);
337 : : }
338 : : }
339 : :
340 : : /* okay, all heap tuples are indexed */
341 : 594 : MemoryContextSwitchTo(oldcxt);
342 : 594 : MemoryContextDelete(buildstate.giststate->tempCxt);
343 : :
344 : 594 : freeGISTstate(buildstate.giststate);
345 : :
346 : : /*
347 : : * Return statistics
348 : : */
349 : 594 : result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
350 : :
351 : 594 : result->heap_tuples = reltuples;
352 : 594 : result->index_tuples = (double) buildstate.indtuples;
353 : :
354 : 594 : return result;
355 : : }
356 : :
357 : : /*-------------------------------------------------------------------------
358 : : * Routines for sorted build
359 : : *-------------------------------------------------------------------------
360 : : */
361 : :
362 : : /*
363 : : * Per-tuple callback for table_index_build_scan.
364 : : */
365 : : static void
366 : 98072 : gistSortedBuildCallback(Relation index,
367 : : ItemPointer tid,
368 : : Datum *values,
369 : : bool *isnull,
370 : : bool tupleIsAlive,
371 : : void *state)
372 : : {
373 : 98072 : GISTBuildState *buildstate = (GISTBuildState *) state;
374 : : MemoryContext oldCtx;
375 : : Datum compressed_values[INDEX_MAX_KEYS];
376 : :
377 : 98072 : oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
378 : :
379 : : /* Form an index tuple and point it at the heap tuple */
380 : 98072 : gistCompressValues(buildstate->giststate, index,
381 : : values, isnull,
382 : : true, compressed_values);
383 : :
384 : 98072 : tuplesort_putindextuplevalues(buildstate->sortstate,
385 : : buildstate->indexrel,
386 : : tid,
387 : : compressed_values, isnull);
388 : :
389 : 98072 : MemoryContextSwitchTo(oldCtx);
390 : 98072 : MemoryContextReset(buildstate->giststate->tempCxt);
391 : :
392 : : /* Update tuple count. */
393 : 98072 : buildstate->indtuples += 1;
394 : 98072 : }
395 : :
396 : : /*
397 : : * Build GiST index from bottom up from pre-sorted tuples.
398 : : */
399 : : static void
400 : 75 : gist_indexsortbuild(GISTBuildState *state)
401 : : {
402 : : IndexTuple itup;
403 : : GistSortedBuildLevelState *levelstate;
404 : : BulkWriteBuffer rootbuf;
405 : :
406 : : /* Reserve block 0 for the root page */
51 heikki.linnakangas@i 407 :GNC 75 : state->pages_allocated = 1;
408 : :
409 : 75 : state->bulkstate = smgr_bulk_start_rel(state->indexrel, MAIN_FORKNUM);
410 : :
411 : : /* Allocate a temporary buffer for the first leaf page batch. */
797 akorotkov@postgresql 412 :CBC 75 : levelstate = palloc0(sizeof(GistSortedBuildLevelState));
51 heikki.linnakangas@i 413 :GNC 75 : levelstate->pages[0] = palloc(BLCKSZ);
797 akorotkov@postgresql 414 :CBC 75 : levelstate->parent = NULL;
51 heikki.linnakangas@i 415 :GNC 75 : gistinitpage(levelstate->pages[0], F_LEAF);
416 : :
417 : : /*
418 : : * Fill index pages with tuples in the sorted order.
419 : : */
1305 heikki.linnakangas@i 420 [ + + ]:CBC 98147 : while ((itup = tuplesort_getindextuple(state->sortstate, true)) != NULL)
421 : : {
797 akorotkov@postgresql 422 : 98072 : gist_indexsortbuild_levelstate_add(state, levelstate, itup);
1305 heikki.linnakangas@i 423 : 98072 : MemoryContextReset(state->giststate->tempCxt);
424 : : }
425 : :
426 : : /*
427 : : * Write out the partially full non-root pages.
428 : : *
429 : : * Keep in mind that flush can build a new root. If number of pages is > 1
430 : : * then new root is required.
431 : : */
797 akorotkov@postgresql 432 [ + + - + ]: 89 : while (levelstate->parent != NULL || levelstate->current_page != 0)
433 : : {
434 : : GistSortedBuildLevelState *parent;
435 : :
436 : 14 : gist_indexsortbuild_levelstate_flush(state, levelstate);
437 : 14 : parent = levelstate->parent;
438 [ + + ]: 70 : for (int i = 0; i < GIST_SORTED_BUILD_PAGE_NUM; i++)
439 [ + - ]: 56 : if (levelstate->pages[i])
440 : 56 : pfree(levelstate->pages[i]);
441 : 14 : pfree(levelstate);
442 : 14 : levelstate = parent;
443 : : }
444 : :
445 : : /* Write out the root */
446 : 75 : PageSetLSN(levelstate->pages[0], GistBuildLSN);
51 heikki.linnakangas@i 447 :GNC 75 : rootbuf = smgr_bulk_get_buf(state->bulkstate);
448 : 75 : memcpy(rootbuf, levelstate->pages[0], BLCKSZ);
449 : 75 : smgr_bulk_write(state->bulkstate, GIST_ROOT_BLKNO, rootbuf, true);
450 : :
797 akorotkov@postgresql 451 :CBC 75 : pfree(levelstate);
452 : :
51 heikki.linnakangas@i 453 :GNC 75 : smgr_bulk_finish(state->bulkstate);
1305 heikki.linnakangas@i 454 :CBC 75 : }
455 : :
456 : : /*
457 : : * Add tuple to a page. If the pages are full, write them out and re-initialize
458 : : * a new page first.
459 : : */
460 : : static void
797 akorotkov@postgresql 461 : 98779 : gist_indexsortbuild_levelstate_add(GISTBuildState *state,
462 : : GistSortedBuildLevelState *levelstate,
463 : : IndexTuple itup)
464 : : {
465 : : Size sizeNeeded;
466 : :
467 : : /* Check if tuple can be added to the current page */
468 : 98779 : sizeNeeded = IndexTupleSize(itup) + sizeof(ItemIdData); /* fillfactor ignored */
469 [ + + ]: 98779 : if (PageGetFreeSpace(levelstate->pages[levelstate->current_page]) < sizeNeeded)
470 : : {
471 : : Page newPage;
472 : 528 : Page old_page = levelstate->pages[levelstate->current_page];
473 : 528 : uint16 old_page_flags = GistPageGetOpaque(old_page)->flags;
474 : :
475 [ + + ]: 528 : if (levelstate->current_page + 1 == GIST_SORTED_BUILD_PAGE_NUM)
476 : : {
477 : 128 : gist_indexsortbuild_levelstate_flush(state, levelstate);
478 : : }
479 : : else
480 : 400 : levelstate->current_page++;
481 : :
482 [ + + ]: 528 : if (levelstate->pages[levelstate->current_page] == NULL)
51 heikki.linnakangas@i 483 :GNC 42 : levelstate->pages[levelstate->current_page] = palloc0(BLCKSZ);
484 : :
797 akorotkov@postgresql 485 :CBC 528 : newPage = levelstate->pages[levelstate->current_page];
486 : 528 : gistinitpage(newPage, old_page_flags);
487 : : }
488 : :
489 : 98779 : gistfillbuffer(levelstate->pages[levelstate->current_page], &itup, 1, InvalidOffsetNumber);
1305 heikki.linnakangas@i 490 : 98779 : }
491 : :
492 : : static void
797 akorotkov@postgresql 493 : 142 : gist_indexsortbuild_levelstate_flush(GISTBuildState *state,
494 : : GistSortedBuildLevelState *levelstate)
495 : : {
496 : : GistSortedBuildLevelState *parent;
497 : : BlockNumber blkno;
498 : : MemoryContext oldCtx;
499 : : IndexTuple union_tuple;
500 : : SplitPageLayout *dist;
501 : : IndexTuple *itvec;
502 : : int vect_len;
503 : 142 : bool isleaf = GistPageIsLeaf(levelstate->pages[0]);
504 : :
1305 heikki.linnakangas@i 505 [ - + ]: 142 : CHECK_FOR_INTERRUPTS();
506 : :
797 akorotkov@postgresql 507 : 142 : oldCtx = MemoryContextSwitchTo(state->giststate->tempCxt);
508 : :
509 : : /* Get index tuples from first page */
510 : 142 : itvec = gistextractpage(levelstate->pages[0], &vect_len);
511 [ + + ]: 142 : if (levelstate->current_page > 0)
512 : : {
513 : : /* Append tuples from each page */
514 [ + + ]: 539 : for (int i = 1; i < levelstate->current_page + 1; i++)
515 : : {
516 : : int len_local;
517 : 400 : IndexTuple *itvec_local = gistextractpage(levelstate->pages[i], &len_local);
518 : :
519 : 400 : itvec = gistjoinvector(itvec, &vect_len, itvec_local, len_local);
520 : 400 : pfree(itvec_local);
521 : : }
522 : :
523 : : /* Apply picksplit to list of all collected tuples */
524 : 139 : dist = gistSplit(state->indexrel, levelstate->pages[0], itvec, vect_len, state->giststate);
525 : : }
526 : : else
527 : : {
528 : : /* Create split layout from single page */
103 rhaas@postgresql.org 529 :GNC 3 : dist = (SplitPageLayout *) palloc0(sizeof(SplitPageLayout));
797 akorotkov@postgresql 530 :CBC 3 : union_tuple = gistunion(state->indexrel, itvec, vect_len,
531 : : state->giststate);
532 : 3 : dist->itup = union_tuple;
533 : 3 : dist->list = gistfillitupvec(itvec, vect_len, &(dist->lenlist));
534 : 3 : dist->block.num = vect_len;
535 : : }
536 : :
1305 heikki.linnakangas@i 537 : 142 : MemoryContextSwitchTo(oldCtx);
538 : :
539 : : /* Reset page counter */
797 akorotkov@postgresql 540 : 142 : levelstate->current_page = 0;
541 : :
542 : : /* Create pages for all partitions in split result */
543 [ + + ]: 849 : for (; dist != NULL; dist = dist->next)
544 : : {
545 : : char *data;
546 : : BulkWriteBuffer buf;
547 : : Page target;
548 : :
549 : : /* check once per page */
550 [ - + ]: 707 : CHECK_FOR_INTERRUPTS();
551 : :
552 : : /* Create page and copy data */
553 : 707 : data = (char *) (dist->list);
51 heikki.linnakangas@i 554 :GNC 707 : buf = smgr_bulk_get_buf(state->bulkstate);
555 : 707 : target = (Page) buf;
797 akorotkov@postgresql 556 :CBC 707 : gistinitpage(target, isleaf ? F_LEAF : 0);
557 [ + + ]: 98713 : for (int i = 0; i < dist->block.num; i++)
558 : : {
559 : 98006 : IndexTuple thistup = (IndexTuple) data;
560 : :
561 [ - + ]: 98006 : if (PageAddItem(target, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
797 akorotkov@postgresql 562 [ # # ]:UBC 0 : elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(state->indexrel));
563 : :
797 akorotkov@postgresql 564 :CBC 98006 : data += IndexTupleSize(thistup);
565 : : }
566 : 707 : union_tuple = dist->itup;
567 : :
568 : : /*
569 : : * Set the right link to point to the previous page. This is just for
570 : : * debugging purposes: GiST only follows the right link if a page is
571 : : * split concurrently to a scan, and that cannot happen during index
572 : : * build.
573 : : *
574 : : * It's a bit counterintuitive that we set the right link on the new
575 : : * page to point to the previous page, not the other way around. But
576 : : * GiST pages are not ordered like B-tree pages are, so as long as the
577 : : * right-links form a chain through all the pages at the same level,
578 : : * the order doesn't matter.
579 : : */
580 [ + + ]: 707 : if (levelstate->last_blkno)
581 : 693 : GistPageGetOpaque(target)->rightlink = levelstate->last_blkno;
582 : :
583 : : /*
584 : : * The page is now complete. Assign a block number to it, and pass it
585 : : * to the bulk writer.
586 : : */
51 heikki.linnakangas@i 587 :GNC 707 : blkno = state->pages_allocated++;
588 : 707 : PageSetLSN(target, GistBuildLSN);
589 : 707 : smgr_bulk_write(state->bulkstate, blkno, buf, true);
590 : 707 : ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno);
797 akorotkov@postgresql 591 :CBC 707 : levelstate->last_blkno = blkno;
592 : :
593 : : /*
594 : : * Insert the downlink to the parent page. If this was the root,
595 : : * create a new page as the parent, which becomes the new root.
596 : : */
597 : 707 : parent = levelstate->parent;
598 [ + + ]: 707 : if (parent == NULL)
599 : : {
600 : 14 : parent = palloc0(sizeof(GistSortedBuildLevelState));
51 heikki.linnakangas@i 601 :GNC 14 : parent->pages[0] = palloc(BLCKSZ);
797 akorotkov@postgresql 602 :CBC 14 : parent->parent = NULL;
603 : 14 : gistinitpage(parent->pages[0], 0);
604 : :
605 : 14 : levelstate->parent = parent;
606 : : }
607 : 707 : gist_indexsortbuild_levelstate_add(state, parent, union_tuple);
608 : : }
1305 heikki.linnakangas@i 609 : 142 : }
610 : :
611 : :
612 : : /*-------------------------------------------------------------------------
613 : : * Routines for non-sorted build
614 : : *-------------------------------------------------------------------------
615 : : */
616 : :
617 : : /*
618 : : * Attempt to switch to buffering mode.
619 : : *
620 : : * If there is not enough memory for buffering build, sets bufferingMode
621 : : * to GIST_BUFFERING_DISABLED, so that we don't bother to try the switch
622 : : * anymore. Otherwise initializes the build buffers, and sets bufferingMode to
623 : : * GIST_BUFFERING_ACTIVE.
624 : : */
625 : : static void
4602 626 : 3 : gistInitBuffering(GISTBuildState *buildstate)
627 : : {
628 : 3 : Relation index = buildstate->indexrel;
629 : : int pagesPerBuffer;
630 : : Size pageFreeSpace;
631 : : Size itupAvgSize,
632 : : itupMinSize;
633 : : double avgIndexTuplesPerPage,
634 : : maxIndexTuplesPerPage;
635 : : int i;
636 : : int levelStep;
637 : :
638 : : /* Calc space of index page which is available for index tuples */
639 : 3 : pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
640 : : - sizeof(ItemIdData)
641 : 3 : - buildstate->freespace;
642 : :
643 : : /*
644 : : * Calculate average size of already inserted index tuples using gathered
645 : : * statistics.
646 : : */
647 : 3 : itupAvgSize = (double) buildstate->indtuplesSize /
648 : 3 : (double) buildstate->indtuples;
649 : :
650 : : /*
651 : : * Calculate minimal possible size of index tuple by index metadata.
652 : : * Minimal possible size of varlena is VARHDRSZ.
653 : : *
654 : : * XXX: that's not actually true, as a short varlen can be just 2 bytes.
655 : : * And we should take padding into account here.
656 : : */
657 : 3 : itupMinSize = (Size) MAXALIGN(sizeof(IndexTupleData));
658 [ + + ]: 6 : for (i = 0; i < index->rd_att->natts; i++)
659 : : {
2429 andres@anarazel.de 660 [ - + ]: 3 : if (TupleDescAttr(index->rd_att, i)->attlen < 0)
4602 heikki.linnakangas@i 661 :UBC 0 : itupMinSize += VARHDRSZ;
662 : : else
2429 andres@anarazel.de 663 :CBC 3 : itupMinSize += TupleDescAttr(index->rd_att, i)->attlen;
664 : : }
665 : :
666 : : /* Calculate average and maximal number of index tuples which fit to page */
4602 heikki.linnakangas@i 667 : 3 : avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
668 : 3 : maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;
669 : :
670 : : /*
671 : : * We need to calculate two parameters for the buffering algorithm:
672 : : * levelStep and pagesPerBuffer.
673 : : *
674 : : * levelStep determines the size of subtree that we operate on, while
675 : : * emptying a buffer. A higher value is better, as you need fewer buffer
676 : : * emptying steps to build the index. However, if you set it too high, the
677 : : * subtree doesn't fit in cache anymore, and you quickly lose the benefit
678 : : * of the buffers.
679 : : *
680 : : * In Arge et al's paper, levelStep is chosen as logB(M/4B), where B is
681 : : * the number of tuples on page (ie. fanout), and M is the amount of
682 : : * internal memory available. Curiously, they doesn't explain *why* that
683 : : * setting is optimal. We calculate it by taking the highest levelStep so
684 : : * that a subtree still fits in cache. For a small B, our way of
685 : : * calculating levelStep is very close to Arge et al's formula. For a
686 : : * large B, our formula gives a value that is 2x higher.
687 : : *
688 : : * The average size (in pages) of a subtree of depth n can be calculated
689 : : * as a geometric series:
690 : : *
691 : : * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)
692 : : *
693 : : * where B is the average number of index tuples on page. The subtree is
694 : : * cached in the shared buffer cache and the OS cache, so we choose
695 : : * levelStep so that the subtree size is comfortably smaller than
696 : : * effective_cache_size, with a safety factor of 4.
697 : : *
698 : : * The estimate on the average number of index tuples on page is based on
699 : : * average tuple sizes observed before switching to buffered build, so the
700 : : * real subtree size can be somewhat larger. Also, it would selfish to
701 : : * gobble the whole cache for our index build. The safety factor of 4
702 : : * should account for those effects.
703 : : *
704 : : * The other limiting factor for setting levelStep is that while
705 : : * processing a subtree, we need to hold one page for each buffer at the
706 : : * next lower buffered level. The max. number of buffers needed for that
707 : : * is maxIndexTuplesPerPage^levelStep. This is very conservative, but
708 : : * hopefully maintenance_work_mem is set high enough that you're
709 : : * constrained by effective_cache_size rather than maintenance_work_mem.
710 : : *
711 : : * XXX: the buffer hash table consumes a fair amount of memory too per
712 : : * buffer, but that is not currently taken into account. That scales on
713 : : * the total number of buffers used, ie. the index size and on levelStep.
714 : : * Note that a higher levelStep *reduces* the amount of memory needed for
715 : : * the hash table.
716 : : */
717 : 3 : levelStep = 1;
718 : : for (;;)
719 : 3 : {
720 : : double subtreesize;
721 : : double maxlowestlevelpages;
722 : :
723 : : /* size of an average subtree at this levelStep (in pages). */
4338 724 : 6 : subtreesize =
725 : 6 : (1 - pow(avgIndexTuplesPerPage, (double) (levelStep + 1))) /
726 : 6 : (1 - avgIndexTuplesPerPage);
727 : :
728 : : /* max number of pages at the lowest level of a subtree */
729 : 6 : maxlowestlevelpages = pow(maxIndexTuplesPerPage, (double) levelStep);
730 : :
731 : : /* subtree must fit in cache (with safety factor of 4) */
732 [ - + ]: 6 : if (subtreesize > effective_cache_size / 4)
4338 heikki.linnakangas@i 733 :UBC 0 : break;
734 : :
735 : : /* each node in the lowest level of a subtree has one page in memory */
4338 heikki.linnakangas@i 736 [ + + ]:CBC 6 : if (maxlowestlevelpages > ((double) maintenance_work_mem * 1024) / BLCKSZ)
737 : 3 : break;
738 : :
739 : : /* Good, we can handle this levelStep. See if we can go one higher. */
4602 740 : 3 : levelStep++;
741 : : }
742 : :
743 : : /*
744 : : * We just reached an unacceptable value of levelStep in previous loop.
745 : : * So, decrease levelStep to get last acceptable value.
746 : : */
747 : 3 : levelStep--;
748 : :
749 : : /*
750 : : * If there's not enough cache or maintenance_work_mem, fall back to plain
751 : : * inserts.
752 : : */
753 [ - + ]: 3 : if (levelStep <= 0)
754 : : {
4602 heikki.linnakangas@i 755 [ # # ]:UBC 0 : elog(DEBUG1, "failed to switch to buffered GiST build");
1305 756 : 0 : buildstate->buildMode = GIST_BUFFERING_DISABLED;
4602 757 : 0 : return;
758 : : }
759 : :
760 : : /*
761 : : * The second parameter to set is pagesPerBuffer, which determines the
762 : : * size of each buffer. We adjust pagesPerBuffer also during the build,
763 : : * which is why this calculation is in a separate function.
764 : : */
4602 heikki.linnakangas@i 765 :CBC 3 : pagesPerBuffer = calculatePagesPerBuffer(buildstate, levelStep);
766 : :
767 : : /* Initialize GISTBuildBuffers with these parameters */
768 : 3 : buildstate->gfbb = gistInitBuildBuffers(pagesPerBuffer, levelStep,
769 : : gistGetMaxLevel(index));
770 : :
4337 771 : 3 : gistInitParentMap(buildstate);
772 : :
1305 773 : 3 : buildstate->buildMode = GIST_BUFFERING_ACTIVE;
774 : :
4602 775 [ - + ]: 3 : elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
776 : : levelStep, pagesPerBuffer);
777 : : }
778 : :
779 : : /*
780 : : * Calculate pagesPerBuffer parameter for the buffering algorithm.
781 : : *
782 : : * Buffer size is chosen so that assuming that tuples are distributed
783 : : * randomly, emptying half a buffer fills on average one page in every buffer
784 : : * at the next lower level.
785 : : */
786 : : static int
787 : 6 : calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
788 : : {
789 : : double pagesPerBuffer;
790 : : double avgIndexTuplesPerPage;
791 : : double itupAvgSize;
792 : : Size pageFreeSpace;
793 : :
794 : : /* Calc space of index page which is available for index tuples */
795 : 6 : pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
796 : : - sizeof(ItemIdData)
797 : 6 : - buildstate->freespace;
798 : :
799 : : /*
800 : : * Calculate average size of already inserted index tuples using gathered
801 : : * statistics.
802 : : */
803 : 6 : itupAvgSize = (double) buildstate->indtuplesSize /
804 : 6 : (double) buildstate->indtuples;
805 : :
806 : 6 : avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
807 : :
808 : : /*
809 : : * Recalculate required size of buffers.
810 : : */
811 : 6 : pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
812 : :
tgl@sss.pgh.pa.us 813 : 6 : return (int) rint(pagesPerBuffer);
814 : : }
815 : :
816 : : /*
817 : : * Per-tuple callback for table_index_build_scan.
818 : : */
819 : : static void
heikki.linnakangas@i 820 : 328979 : gistBuildCallback(Relation index,
821 : : ItemPointer tid,
822 : : Datum *values,
823 : : bool *isnull,
824 : : bool tupleIsAlive,
825 : : void *state)
826 : : {
827 : 328979 : GISTBuildState *buildstate = (GISTBuildState *) state;
828 : : IndexTuple itup;
829 : : MemoryContext oldCtx;
830 : :
4580 tgl@sss.pgh.pa.us 831 : 328979 : oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
832 : :
833 : : /* form an index tuple and point it at the heap tuple */
1305 heikki.linnakangas@i 834 : 328979 : itup = gistFormTuple(buildstate->giststate, index,
835 : : values, isnull,
836 : : true);
1619 andres@anarazel.de 837 : 328979 : itup->t_tid = *tid;
838 : :
839 : : /* Update tuple count and total size. */
382 tgl@sss.pgh.pa.us 840 : 328979 : buildstate->indtuples += 1;
841 : 328979 : buildstate->indtuplesSize += IndexTupleSize(itup);
842 : :
843 : : /*
844 : : * XXX In buffering builds, the tempCxt is also reset down inside
845 : : * gistProcessEmptyingQueue(). This is not great because it risks
846 : : * confusion and possible use of dangling pointers (for example, itup
847 : : * might be already freed when control returns here). It's generally
848 : : * better that a memory context be "owned" by only one function. However,
849 : : * currently this isn't causing issues so it doesn't seem worth the amount
850 : : * of refactoring that would be needed to avoid it.
851 : : */
1305 heikki.linnakangas@i 852 [ + + ]: 328979 : if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
853 : : {
854 : : /* We have buffers, so use them. */
4602 855 : 17715 : gistBufferingBuildInsert(buildstate, itup);
856 : : }
857 : : else
858 : : {
859 : : /*
860 : : * There's no buffers (yet). Since we already have the index relation
861 : : * locked, we call gistdoinsert directly.
862 : : */
863 : 311264 : gistdoinsert(index, itup, buildstate->freespace,
864 : : buildstate->giststate, buildstate->heaprel, true);
865 : : }
866 : :
867 : 328979 : MemoryContextSwitchTo(oldCtx);
4580 tgl@sss.pgh.pa.us 868 : 328979 : MemoryContextReset(buildstate->giststate->tempCxt);
869 : :
1305 heikki.linnakangas@i 870 [ + + ]: 328979 : if (buildstate->buildMode == GIST_BUFFERING_ACTIVE &&
4602 871 [ + + ]: 17715 : buildstate->indtuples % BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET == 0)
872 : : {
873 : : /* Adjust the target buffer size now */
874 : 3 : buildstate->gfbb->pagesPerBuffer =
875 : 3 : calculatePagesPerBuffer(buildstate, buildstate->gfbb->levelStep);
876 : : }
877 : :
878 : : /*
879 : : * In 'auto' mode, check if the index has grown too large to fit in cache,
880 : : * and switch to buffering mode if it has.
881 : : *
882 : : * To avoid excessive calls to smgrnblocks(), only check this every
883 : : * BUFFERING_MODE_SWITCH_CHECK_STEP index tuples.
884 : : *
885 : : * In 'stats' state, switch as soon as we have seen enough tuples to have
886 : : * some idea of the average tuple size.
887 : : */
1305 888 [ + + ]: 328979 : if ((buildstate->buildMode == GIST_BUFFERING_AUTO &&
4602 889 [ + + ]: 298976 : buildstate->indtuples % BUFFERING_MODE_SWITCH_CHECK_STEP == 0 &&
1007 tgl@sss.pgh.pa.us 890 [ + - ]: 1125 : effective_cache_size < smgrnblocks(RelationGetSmgr(index),
891 : 328979 : MAIN_FORKNUM)) ||
1305 heikki.linnakangas@i 892 [ + + ]: 328979 : (buildstate->buildMode == GIST_BUFFERING_STATS &&
4602 893 [ + + ]: 12288 : buildstate->indtuples >= BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET))
894 : : {
895 : : /*
896 : : * Index doesn't fit in effective cache anymore. Try to switch to
897 : : * buffering build mode.
898 : : */
899 : 3 : gistInitBuffering(buildstate);
900 : : }
901 : 328979 : }
902 : :
903 : : /*
904 : : * Insert function for buffering index build.
905 : : */
906 : : static void
907 : 17715 : gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup)
908 : : {
909 : : /* Insert the tuple to buffers. */
4337 910 : 17715 : gistProcessItup(buildstate, itup, 0, buildstate->gfbb->rootlevel);
911 : :
912 : : /* If we filled up (half of a) buffer, process buffer emptying. */
4602 913 : 17715 : gistProcessEmptyingQueue(buildstate);
914 : 17715 : }
915 : :
916 : : /*
917 : : * Process an index tuple. Runs the tuple down the tree until we reach a leaf
918 : : * page or node buffer, and inserts the tuple there. Returns true if we have
919 : : * to stop buffer emptying process (because one of child buffers can't take
920 : : * index tuples anymore).
921 : : */
922 : : static bool
923 : 34881 : gistProcessItup(GISTBuildState *buildstate, IndexTuple itup,
924 : : BlockNumber startblkno, int startlevel)
925 : : {
4580 tgl@sss.pgh.pa.us 926 : 34881 : GISTSTATE *giststate = buildstate->giststate;
4602 heikki.linnakangas@i 927 : 34881 : GISTBuildBuffers *gfbb = buildstate->gfbb;
928 : 34881 : Relation indexrel = buildstate->indexrel;
929 : : BlockNumber childblkno;
930 : : Buffer buffer;
931 : 34881 : bool result = false;
932 : : BlockNumber blkno;
933 : : int level;
4337 934 : 34881 : OffsetNumber downlinkoffnum = InvalidOffsetNumber;
935 : 34881 : BlockNumber parentblkno = InvalidBlockNumber;
936 : :
937 [ - + ]: 34881 : CHECK_FOR_INTERRUPTS();
938 : :
939 : : /*
940 : : * Loop until we reach a leaf page (level == 0) or a level with buffers
941 : : * (not including the level we start at, because we would otherwise make
942 : : * no progress).
943 : : */
944 : 34881 : blkno = startblkno;
945 : 34881 : level = startlevel;
946 : : for (;;)
4602 947 : 34881 : {
948 : : ItemId iid;
949 : : IndexTuple idxtuple,
950 : : newtup;
951 : : Page page;
952 : : OffsetNumber childoffnum;
953 : :
954 : : /* Have we reached a level with buffers? */
4337 955 [ + + + - : 69762 : if (LEVEL_HAS_BUFFERS(level, gfbb) && level != startlevel)
+ + + + ]
4602 956 : 17166 : break;
957 : :
958 : : /* Have we reached a leaf page? */
4337 959 [ + + ]: 52596 : if (level == 0)
4602 960 : 17715 : break;
961 : :
962 : : /*
963 : : * Nope. Descend down to the next level then. Choose a child to
964 : : * descend down to.
965 : : */
966 : :
4337 967 : 34881 : buffer = ReadBuffer(indexrel, blkno);
4602 968 : 34881 : LockBuffer(buffer, GIST_EXCLUSIVE);
969 : :
2916 kgrittn@postgresql.o 970 : 34881 : page = (Page) BufferGetPage(buffer);
4602 heikki.linnakangas@i 971 : 34881 : childoffnum = gistchoose(indexrel, page, itup, giststate);
972 : 34881 : iid = PageGetItemId(page, childoffnum);
973 : 34881 : idxtuple = (IndexTuple) PageGetItem(page, iid);
974 : 34881 : childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
975 : :
4337 976 [ + + ]: 34881 : if (level > 1)
977 : 17166 : gistMemorizeParent(buildstate, childblkno, blkno);
978 : :
979 : : /*
980 : : * Check that the key representing the target child node is consistent
981 : : * with the key we're inserting. Update it if it's not.
982 : : */
4602 983 : 34881 : newtup = gistgetadjusted(indexrel, idxtuple, itup, giststate);
984 [ + + ]: 34881 : if (newtup)
985 : : {
3970 sfrost@snowman.net 986 : 34473 : blkno = gistbufferinginserttuples(buildstate,
987 : : buffer,
988 : : level,
989 : : &newtup,
990 : : 1,
991 : : childoffnum,
992 : : InvalidBlockNumber,
993 : : InvalidOffsetNumber);
994 : : /* gistbufferinginserttuples() released the buffer */
995 : : }
996 : : else
4337 heikki.linnakangas@i 997 : 408 : UnlockReleaseBuffer(buffer);
998 : :
999 : : /* Descend to the child */
1000 : 34881 : parentblkno = blkno;
1001 : 34881 : blkno = childblkno;
1002 : 34881 : downlinkoffnum = childoffnum;
1003 [ - + ]: 34881 : Assert(level > 0);
1004 : 34881 : level--;
1005 : : }
1006 : :
1007 [ + + + - : 34881 : if (LEVEL_HAS_BUFFERS(level, gfbb))
+ - ]
4602 1008 : 17166 : {
1009 : : /*
1010 : : * We've reached level with buffers. Place the index tuple to the
1011 : : * buffer, and add the buffer to the emptying queue if it overflows.
1012 : : */
1013 : : GISTNodeBuffer *childNodeBuffer;
1014 : :
1015 : : /* Find the buffer or create a new one */
4337 1016 : 17166 : childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, blkno, level);
1017 : :
1018 : : /* Add index tuple to it */
4602 1019 : 17166 : gistPushItupToNodeBuffer(gfbb, childNodeBuffer, itup);
1020 : :
1021 [ - + ]: 17166 : if (BUFFER_OVERFLOWED(childNodeBuffer, gfbb))
4602 heikki.linnakangas@i 1022 :UBC 0 : result = true;
1023 : : }
1024 : : else
1025 : : {
1026 : : /*
1027 : : * We've reached a leaf page. Place the tuple here.
1028 : : */
4337 heikki.linnakangas@i 1029 [ - + ]:CBC 17715 : Assert(level == 0);
1030 : 17715 : buffer = ReadBuffer(indexrel, blkno);
4602 1031 : 17715 : LockBuffer(buffer, GIST_EXCLUSIVE);
4337 1032 : 17715 : gistbufferinginserttuples(buildstate, buffer, level,
1033 : : &itup, 1, InvalidOffsetNumber,
1034 : : parentblkno, downlinkoffnum);
1035 : : /* gistbufferinginserttuples() released the buffer */
1036 : : }
1037 : :
4602 1038 : 34881 : return result;
1039 : : }
1040 : :
1041 : : /*
1042 : : * Insert tuples to a given page.
1043 : : *
1044 : : * This is analogous with gistinserttuples() in the regular insertion code.
1045 : : *
1046 : : * Returns the block number of the page where the (first) new or updated tuple
1047 : : * was inserted. Usually that's the original page, but might be a sibling page
1048 : : * if the original page was split.
1049 : : *
1050 : : * Caller should hold a lock on 'buffer' on entry. This function will unlock
1051 : : * and unpin it.
1052 : : */
1053 : : static BlockNumber
4337 1054 : 52572 : gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, int level,
1055 : : IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
1056 : : BlockNumber parentblk, OffsetNumber downlinkoffnum)
1057 : : {
4602 1058 : 52572 : GISTBuildBuffers *gfbb = buildstate->gfbb;
1059 : : List *splitinfo;
1060 : : bool is_split;
3973 bruce@momjian.us 1061 : 52572 : BlockNumber placed_to_blk = InvalidBlockNumber;
1062 : :
4602 heikki.linnakangas@i 1063 : 52572 : is_split = gistplacetopage(buildstate->indexrel,
1064 : : buildstate->freespace,
1065 : : buildstate->giststate,
1066 : : buffer,
1067 : : itup, ntup, oldoffnum, &placed_to_blk,
1068 : : InvalidBuffer,
1069 : : &splitinfo,
1070 : : false,
1071 : : buildstate->heaprel, true);
1072 : :
1073 : : /*
1074 : : * If this is a root split, update the root path item kept in memory. This
1075 : : * ensures that all path stacks are always complete, including all parent
1076 : : * nodes up to the root. That simplifies the algorithm to re-find correct
1077 : : * parent.
1078 : : */
1079 [ + + + + ]: 52572 : if (is_split && BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO)
1080 : : {
2916 kgrittn@postgresql.o 1081 : 3 : Page page = BufferGetPage(buffer);
1082 : : OffsetNumber off;
1083 : : OffsetNumber maxoff;
1084 : :
4337 heikki.linnakangas@i 1085 [ - + ]: 3 : Assert(level == gfbb->rootlevel);
1086 : 3 : gfbb->rootlevel++;
1087 : :
1088 [ - + ]: 3 : elog(DEBUG2, "splitting GiST root page, now %d levels deep", gfbb->rootlevel);
1089 : :
1090 : : /*
1091 : : * All the downlinks on the old root page are now on one of the child
1092 : : * pages. Visit all the new child pages to memorize the parents of the
1093 : : * grandchildren.
1094 : : */
1095 [ + - ]: 3 : if (gfbb->rootlevel > 1)
1096 : : {
1097 : 3 : maxoff = PageGetMaxOffsetNumber(page);
1098 [ + + ]: 9 : for (off = FirstOffsetNumber; off <= maxoff; off++)
1099 : : {
4326 bruce@momjian.us 1100 : 6 : ItemId iid = PageGetItemId(page, off);
1101 : 6 : IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
4337 heikki.linnakangas@i 1102 : 6 : BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
4326 bruce@momjian.us 1103 : 6 : Buffer childbuf = ReadBuffer(buildstate->indexrel, childblkno);
1104 : :
4337 heikki.linnakangas@i 1105 : 6 : LockBuffer(childbuf, GIST_SHARE);
1106 : 6 : gistMemorizeAllDownlinks(buildstate, childbuf);
1107 : 6 : UnlockReleaseBuffer(childbuf);
1108 : :
1109 : : /*
1110 : : * Also remember that the parent of the new child page is the
1111 : : * root block.
1112 : : */
1113 : 6 : gistMemorizeParent(buildstate, childblkno, GIST_ROOT_BLKNO);
1114 : : }
1115 : : }
1116 : : }
1117 : :
4602 1118 [ + + ]: 52572 : if (splitinfo)
1119 : : {
1120 : : /*
1121 : : * Insert the downlinks to the parent. This is analogous with
1122 : : * gistfinishsplit() in the regular insertion code, but the locking is
1123 : : * simpler, and we have to maintain the buffers on internal nodes and
1124 : : * the parent map.
1125 : : */
1126 : : IndexTuple *downlinks;
1127 : : int ndownlinks,
1128 : : i;
1129 : : Buffer parentBuffer;
1130 : : ListCell *lc;
1131 : :
1132 : : /* Parent may have changed since we memorized this path. */
1133 : : parentBuffer =
4337 1134 : 384 : gistBufferingFindCorrectParent(buildstate,
1135 : : BufferGetBlockNumber(buffer),
1136 : : level,
1137 : : &parentblk,
1138 : : &downlinkoffnum);
1139 : :
1140 : : /*
1141 : : * If there's a buffer associated with this page, that needs to be
1142 : : * split too. gistRelocateBuildBuffersOnSplit() will also adjust the
1143 : : * downlinks in 'splitinfo', to make sure they're consistent not only
1144 : : * with the tuples already on the pages, but also the tuples in the
1145 : : * buffers that will eventually be inserted to them.
1146 : : */
4602 1147 : 384 : gistRelocateBuildBuffersOnSplit(gfbb,
1148 : : buildstate->giststate,
1149 : : buildstate->indexrel,
1150 : : level,
1151 : : buffer, splitinfo);
1152 : :
1153 : : /* Create an array of all the downlink tuples */
1154 : 384 : ndownlinks = list_length(splitinfo);
1155 : 384 : downlinks = (IndexTuple *) palloc(sizeof(IndexTuple) * ndownlinks);
1156 : 384 : i = 0;
1157 [ + - + + : 1152 : foreach(lc, splitinfo)
+ + ]
1158 : : {
1159 : 768 : GISTPageSplitInfo *splitinfo = lfirst(lc);
1160 : :
1161 : : /*
1162 : : * Remember the parent of each new child page in our parent map.
1163 : : * This assumes that the downlinks fit on the parent page. If the
1164 : : * parent page is split, too, when we recurse up to insert the
1165 : : * downlinks, the recursive gistbufferinginserttuples() call will
1166 : : * update the map again.
1167 : : */
4337 1168 [ + + ]: 768 : if (level > 0)
1169 : 12 : gistMemorizeParent(buildstate,
1170 : : BufferGetBlockNumber(splitinfo->buf),
1171 : : BufferGetBlockNumber(parentBuffer));
1172 : :
1173 : : /*
1174 : : * Also update the parent map for all the downlinks that got moved
1175 : : * to a different page. (actually this also loops through the
1176 : : * downlinks that stayed on the original page, but it does no
1177 : : * harm).
1178 : : */
1179 [ - + ]: 768 : if (level > 1)
4337 heikki.linnakangas@i 1180 :UBC 0 : gistMemorizeAllDownlinks(buildstate, splitinfo->buf);
1181 : :
1182 : : /*
1183 : : * Since there's no concurrent access, we can release the lower
1184 : : * level buffers immediately. This includes the original page.
1185 : : */
4337 heikki.linnakangas@i 1186 :CBC 768 : UnlockReleaseBuffer(splitinfo->buf);
4602 1187 : 768 : downlinks[i++] = splitinfo->downlink;
1188 : : }
1189 : :
1190 : : /* Insert them into parent. */
4337 1191 : 384 : gistbufferinginserttuples(buildstate, parentBuffer, level + 1,
1192 : : downlinks, ndownlinks, downlinkoffnum,
1193 : : InvalidBlockNumber, InvalidOffsetNumber);
1194 : :
2489 tgl@sss.pgh.pa.us 1195 : 384 : list_free_deep(splitinfo); /* we don't need this anymore */
1196 : : }
1197 : : else
4337 heikki.linnakangas@i 1198 : 52188 : UnlockReleaseBuffer(buffer);
1199 : :
4259 1200 : 52572 : return placed_to_blk;
1201 : : }
1202 : :
1203 : : /*
1204 : : * Find the downlink pointing to a child page.
1205 : : *
1206 : : * 'childblkno' indicates the child page to find the parent for. 'level' is
1207 : : * the level of the child. On entry, *parentblkno and *downlinkoffnum can
1208 : : * point to a location where the downlink used to be - we will check that
1209 : : * location first, and save some cycles if it hasn't moved. The function
1210 : : * returns a buffer containing the downlink, exclusively-locked, and
1211 : : * *parentblkno and *downlinkoffnum are set to the real location of the
1212 : : * downlink.
1213 : : *
1214 : : * If the child page is a leaf (level == 0), the caller must supply a correct
1215 : : * parentblkno. Otherwise we use the parent map hash table to find the parent
1216 : : * block.
1217 : : *
1218 : : * This function serves the same purpose as gistFindCorrectParent() during
1219 : : * normal index inserts, but this is simpler because we don't need to deal
1220 : : * with concurrent inserts.
1221 : : */
1222 : : static Buffer
4602 1223 : 384 : gistBufferingFindCorrectParent(GISTBuildState *buildstate,
1224 : : BlockNumber childblkno, int level,
1225 : : BlockNumber *parentblkno,
1226 : : OffsetNumber *downlinkoffnum)
1227 : : {
1228 : : BlockNumber parent;
1229 : : Buffer buffer;
1230 : : Page page;
1231 : : OffsetNumber maxoff;
1232 : : OffsetNumber off;
1233 : :
4337 1234 [ + + ]: 384 : if (level > 0)
1235 : 6 : parent = gistGetParent(buildstate, childblkno);
1236 : : else
1237 : : {
1238 : : /*
1239 : : * For a leaf page, the caller must supply a correct parent block
1240 : : * number.
1241 : : */
1242 [ - + ]: 378 : if (*parentblkno == InvalidBlockNumber)
1093 peter@eisentraut.org 1243 [ # # ]:UBC 0 : elog(ERROR, "no parent buffer provided of child %u", childblkno);
4337 heikki.linnakangas@i 1244 :CBC 378 : parent = *parentblkno;
1245 : : }
1246 : :
1247 : 384 : buffer = ReadBuffer(buildstate->indexrel, parent);
2916 kgrittn@postgresql.o 1248 : 384 : page = BufferGetPage(buffer);
4602 heikki.linnakangas@i 1249 : 384 : LockBuffer(buffer, GIST_EXCLUSIVE);
4337 1250 : 384 : gistcheckpage(buildstate->indexrel, buffer);
1251 : 384 : maxoff = PageGetMaxOffsetNumber(page);
1252 : :
1253 : : /* Check if it was not moved */
1254 [ + + + - ]: 384 : if (parent == *parentblkno && *parentblkno != InvalidBlockNumber &&
1255 [ + - + - ]: 378 : *downlinkoffnum != InvalidOffsetNumber && *downlinkoffnum <= maxoff)
1256 : : {
4326 bruce@momjian.us 1257 : 378 : ItemId iid = PageGetItemId(page, *downlinkoffnum);
1258 : 378 : IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1259 : :
4337 heikki.linnakangas@i 1260 [ + - ]: 378 : if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
1261 : : {
1262 : : /* Still there */
1263 : 378 : return buffer;
1264 : : }
1265 : : }
1266 : :
1267 : : /*
1268 : : * Downlink was not at the offset where it used to be. Scan the page to
1269 : : * find it. During normal gist insertions, it might've moved to another
1270 : : * page, to the right, but during a buffering build, we keep track of the
1271 : : * parent of each page in the lookup table so we should always know what
1272 : : * page it's on.
1273 : : */
1274 [ + - ]: 15 : for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))
1275 : : {
4326 bruce@momjian.us 1276 : 15 : ItemId iid = PageGetItemId(page, off);
1277 : 15 : IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1278 : :
4337 heikki.linnakangas@i 1279 [ + + ]: 15 : if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
1280 : : {
1281 : : /* yes!!, found it */
1282 : 6 : *downlinkoffnum = off;
1283 : 6 : return buffer;
1284 : : }
1285 : : }
1286 : :
4337 heikki.linnakangas@i 1287 [ # # ]:UBC 0 : elog(ERROR, "failed to re-find parent for block %u", childblkno);
1288 : : return InvalidBuffer; /* keep compiler quiet */
1289 : : }
1290 : :
1291 : : /*
1292 : : * Process buffers emptying stack. Emptying of one buffer can cause emptying
1293 : : * of other buffers. This function iterates until this cascading emptying
1294 : : * process finished, e.g. until buffers emptying stack is empty.
1295 : : */
1296 : : static void
4602 heikki.linnakangas@i 1297 :CBC 17724 : gistProcessEmptyingQueue(GISTBuildState *buildstate)
1298 : : {
1299 : 17724 : GISTBuildBuffers *gfbb = buildstate->gfbb;
1300 : :
1301 : : /* Iterate while we have elements in buffers emptying stack. */
1302 [ + + ]: 17733 : while (gfbb->bufferEmptyingQueue != NIL)
1303 : : {
1304 : : GISTNodeBuffer *emptyingNodeBuffer;
1305 : :
1306 : : /* Get node buffer from emptying stack. */
1307 : 9 : emptyingNodeBuffer = (GISTNodeBuffer *) linitial(gfbb->bufferEmptyingQueue);
1308 : 9 : gfbb->bufferEmptyingQueue = list_delete_first(gfbb->bufferEmptyingQueue);
1309 : 9 : emptyingNodeBuffer->queuedForEmptying = false;
1310 : :
1311 : : /*
1312 : : * We are going to load last pages of buffers where emptying will be
1313 : : * to. So let's unload any previously loaded buffers.
1314 : : */
1315 : 9 : gistUnloadNodeBuffers(gfbb);
1316 : :
1317 : : /*
1318 : : * Pop tuples from the buffer and run them down to the buffers at
1319 : : * lower level, or leaf pages. We continue until one of the lower
1320 : : * level buffers fills up, or this buffer runs empty.
1321 : : *
1322 : : * In Arge et al's paper, the buffer emptying is stopped after
1323 : : * processing 1/2 node buffer worth of tuples, to avoid overfilling
1324 : : * any of the lower level buffers. However, it's more efficient to
1325 : : * keep going until one of the lower level buffers actually fills up,
1326 : : * so that's what we do. This doesn't need to be exact, if a buffer
1327 : : * overfills by a few tuples, there's no harm done.
1328 : : */
1329 : : while (true)
1330 : 17166 : {
1331 : : IndexTuple itup;
1332 : :
1333 : : /* Get next index tuple from the buffer */
1334 [ + + ]: 17175 : if (!gistPopItupFromNodeBuffer(gfbb, emptyingNodeBuffer, &itup))
1335 : 9 : break;
1336 : :
1337 : : /*
1338 : : * Run it down to the underlying node buffer or leaf page.
1339 : : *
1340 : : * Note: it's possible that the buffer we're emptying splits as a
1341 : : * result of this call. If that happens, our emptyingNodeBuffer
1342 : : * points to the left half of the split. After split, it's very
1343 : : * likely that the new left buffer is no longer over the half-full
1344 : : * threshold, but we might as well keep flushing tuples from it
1345 : : * until we fill a lower-level buffer.
1346 : : */
4337 1347 [ - + ]: 17166 : if (gistProcessItup(buildstate, itup, emptyingNodeBuffer->nodeBlocknum, emptyingNodeBuffer->level))
1348 : : {
1349 : : /*
1350 : : * A lower level buffer filled up. Stop emptying this buffer,
1351 : : * to avoid overflowing the lower level buffer.
1352 : : */
4602 heikki.linnakangas@i 1353 :UBC 0 : break;
1354 : : }
1355 : :
1356 : : /* Free all the memory allocated during index tuple processing */
4580 tgl@sss.pgh.pa.us 1357 :CBC 17166 : MemoryContextReset(buildstate->giststate->tempCxt);
1358 : : }
1359 : : }
4602 heikki.linnakangas@i 1360 : 17724 : }
1361 : :
1362 : : /*
1363 : : * Empty all node buffers, from top to bottom. This is done at the end of
1364 : : * index build to flush all remaining tuples to the index.
1365 : : *
1366 : : * Note: This destroys the buffersOnLevels lists, so the buffers should not
1367 : : * be inserted to after this call.
1368 : : */
1369 : : static void
1370 : 3 : gistEmptyAllBuffers(GISTBuildState *buildstate)
1371 : : {
1372 : 3 : GISTBuildBuffers *gfbb = buildstate->gfbb;
1373 : : MemoryContext oldCtx;
1374 : : int i;
1375 : :
4580 tgl@sss.pgh.pa.us 1376 : 3 : oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1377 : :
1378 : : /*
1379 : : * Iterate through the levels from top to bottom.
1380 : : */
4602 heikki.linnakangas@i 1381 [ + + ]: 9 : for (i = gfbb->buffersOnLevelsLen - 1; i >= 0; i--)
1382 : : {
1383 : : /*
1384 : : * Empty all buffers on this level. Note that new buffers can pop up
1385 : : * in the list during the processing, as a result of page splits, so a
1386 : : * simple walk through the list won't work. We remove buffers from the
1387 : : * list when we see them empty; a buffer can't become non-empty once
1388 : : * it's been fully emptied.
1389 : : */
1390 [ + + ]: 24 : while (gfbb->buffersOnLevels[i] != NIL)
1391 : : {
1392 : : GISTNodeBuffer *nodeBuffer;
1393 : :
1394 : 18 : nodeBuffer = (GISTNodeBuffer *) linitial(gfbb->buffersOnLevels[i]);
1395 : :
1396 [ + + ]: 18 : if (nodeBuffer->blocksCount != 0)
1397 : : {
1398 : : /*
1399 : : * Add this buffer to the emptying queue, and proceed to empty
1400 : : * the queue.
1401 : : */
4598 1402 [ + - ]: 9 : if (!nodeBuffer->queuedForEmptying)
1403 : : {
1404 : 9 : MemoryContextSwitchTo(gfbb->context);
1405 : 9 : nodeBuffer->queuedForEmptying = true;
1406 : 9 : gfbb->bufferEmptyingQueue =
1407 : 9 : lcons(nodeBuffer, gfbb->bufferEmptyingQueue);
4580 tgl@sss.pgh.pa.us 1408 : 9 : MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1409 : : }
4602 heikki.linnakangas@i 1410 : 9 : gistProcessEmptyingQueue(buildstate);
1411 : : }
1412 : : else
1413 : 9 : gfbb->buffersOnLevels[i] =
1414 : 9 : list_delete_first(gfbb->buffersOnLevels[i]);
1415 : : }
4337 1416 [ - + ]: 6 : elog(DEBUG2, "emptied all buffers at level %d", i);
1417 : : }
4602 1418 : 3 : MemoryContextSwitchTo(oldCtx);
1419 : 3 : }
1420 : :
1421 : : /*
1422 : : * Get the depth of the GiST index.
1423 : : */
1424 : : static int
1425 : 3 : gistGetMaxLevel(Relation index)
1426 : : {
1427 : : int maxLevel;
1428 : : BlockNumber blkno;
1429 : :
1430 : : /*
1431 : : * Traverse down the tree, starting from the root, until we hit the leaf
1432 : : * level.
1433 : : */
1434 : 3 : maxLevel = 0;
1435 : 3 : blkno = GIST_ROOT_BLKNO;
1436 : : while (true)
1437 : 3 : {
1438 : : Buffer buffer;
1439 : : Page page;
1440 : : IndexTuple itup;
1441 : :
1442 : 6 : buffer = ReadBuffer(index, blkno);
1443 : :
1444 : : /*
1445 : : * There's no concurrent access during index build, so locking is just
1446 : : * pro forma.
1447 : : */
1448 : 6 : LockBuffer(buffer, GIST_SHARE);
2916 kgrittn@postgresql.o 1449 : 6 : page = (Page) BufferGetPage(buffer);
1450 : :
4602 heikki.linnakangas@i 1451 [ + + ]: 6 : if (GistPageIsLeaf(page))
1452 : : {
1453 : : /* We hit the bottom, so we're done. */
1454 : 3 : UnlockReleaseBuffer(buffer);
1455 : 3 : break;
1456 : : }
1457 : :
1458 : : /*
1459 : : * Pick the first downlink on the page, and follow it. It doesn't
1460 : : * matter which downlink we choose, the tree has the same depth
1461 : : * everywhere, so we just pick the first one.
1462 : : */
1463 : 3 : itup = (IndexTuple) PageGetItem(page,
1464 : : PageGetItemId(page, FirstOffsetNumber));
1465 : 3 : blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1466 : 3 : UnlockReleaseBuffer(buffer);
1467 : :
1468 : : /*
1469 : : * We're going down on the tree. It means that there is yet one more
1470 : : * level in the tree.
1471 : : */
1472 : 3 : maxLevel++;
1473 : : }
1474 : 3 : return maxLevel;
1475 : : }
1476 : :
1477 : :
1478 : : /*
1479 : : * Routines for managing the parent map.
1480 : : *
1481 : : * Whenever a page is split, we need to insert the downlinks into the parent.
1482 : : * We need to somehow find the parent page to do that. In normal insertions,
1483 : : * we keep a stack of nodes visited when we descend the tree. However, in
1484 : : * buffering build, we can start descending the tree from any internal node,
1485 : : * when we empty a buffer by cascading tuples to its children. So we don't
1486 : : * have a full stack up to the root available at that time.
1487 : : *
1488 : : * So instead, we maintain a hash table to track the parent of every internal
1489 : : * page. We don't need to track the parents of leaf nodes, however. Whenever
1490 : : * we insert to a leaf, we've just descended down from its parent, so we know
1491 : : * its immediate parent already. This helps a lot to limit the memory used
1492 : : * by this hash table.
1493 : : *
1494 : : * Whenever an internal node is split, the parent map needs to be updated.
1495 : : * the parent of the new child page needs to be recorded, and also the
1496 : : * entries for all page whose downlinks are moved to a new page at the split
1497 : : * needs to be updated.
1498 : : *
1499 : : * We also update the parent map whenever we descend the tree. That might seem
1500 : : * unnecessary, because we maintain the map whenever a downlink is moved or
1501 : : * created, but it is needed because we switch to buffering mode after
1502 : : * creating a tree with regular index inserts. Any pages created before
1503 : : * switching to buffering mode will not be present in the parent map initially,
1504 : : * but will be added there the first time we visit them.
1505 : : */
1506 : :
1507 : : typedef struct
1508 : : {
1509 : : BlockNumber childblkno; /* hash key */
1510 : : BlockNumber parentblkno;
1511 : : } ParentMapEntry;
1512 : :
1513 : : static void
4337 1514 : 3 : gistInitParentMap(GISTBuildState *buildstate)
1515 : : {
1516 : : HASHCTL hashCtl;
1517 : :
1518 : 3 : hashCtl.keysize = sizeof(BlockNumber);
1519 : 3 : hashCtl.entrysize = sizeof(ParentMapEntry);
1520 : 3 : hashCtl.hcxt = CurrentMemoryContext;
1521 : 3 : buildstate->parentMap = hash_create("gistbuild parent map",
1522 : : 1024,
1523 : : &hashCtl,
1524 : : HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
1525 : 3 : }
1526 : :
1527 : : static void
1528 : 17463 : gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
1529 : : {
1530 : : ParentMapEntry *entry;
1531 : : bool found;
1532 : :
1533 : 17463 : entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1534 : : &child,
1535 : : HASH_ENTER,
1536 : : &found);
1537 : 17463 : entry->parentblkno = parent;
1538 : 17463 : }
1539 : :
1540 : : /*
1541 : : * Scan all downlinks on a page, and memorize their parent.
1542 : : */
1543 : : static void
1544 : 6 : gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parentbuf)
1545 : : {
1546 : : OffsetNumber maxoff;
1547 : : OffsetNumber off;
1548 : 6 : BlockNumber parentblkno = BufferGetBlockNumber(parentbuf);
2916 kgrittn@postgresql.o 1549 : 6 : Page page = BufferGetPage(parentbuf);
1550 : :
4337 heikki.linnakangas@i 1551 [ - + ]: 6 : Assert(!GistPageIsLeaf(page));
1552 : :
1553 : 6 : maxoff = PageGetMaxOffsetNumber(page);
1554 [ + + ]: 285 : for (off = FirstOffsetNumber; off <= maxoff; off++)
1555 : : {
4326 bruce@momjian.us 1556 : 279 : ItemId iid = PageGetItemId(page, off);
1557 : 279 : IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
4337 heikki.linnakangas@i 1558 : 279 : BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
1559 : :
1560 : 279 : gistMemorizeParent(buildstate, childblkno, parentblkno);
1561 : : }
1562 : 6 : }
1563 : :
1564 : : static BlockNumber
1565 : 6 : gistGetParent(GISTBuildState *buildstate, BlockNumber child)
1566 : : {
1567 : : ParentMapEntry *entry;
1568 : : bool found;
1569 : :
1570 : : /* Find node buffer in hash table */
1571 : 6 : entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1572 : : &child,
1573 : : HASH_FIND,
1574 : : &found);
1575 [ - + ]: 6 : if (!found)
1093 peter@eisentraut.org 1576 [ # # ]:UBC 0 : elog(ERROR, "could not find parent of block %u in lookup table", child);
1577 : :
4337 heikki.linnakangas@i 1578 :CBC 6 : return entry->parentblkno;
1579 : : }
|
