Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * gistbuildbuffers.c
4 : : * node buffer management functions for GiST buffering build algorithm.
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/gist/gistbuildbuffers.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include "access/gist_private.h"
18 : : #include "storage/buffile.h"
19 : : #include "storage/bufmgr.h"
20 : : #include "utils/rel.h"
21 : :
22 : : static GISTNodeBufferPage *gistAllocateNewPageBuffer(GISTBuildBuffers *gfbb);
23 : : static void gistAddLoadedBuffer(GISTBuildBuffers *gfbb,
24 : : GISTNodeBuffer *nodeBuffer);
25 : : static void gistLoadNodeBuffer(GISTBuildBuffers *gfbb,
26 : : GISTNodeBuffer *nodeBuffer);
27 : : static void gistUnloadNodeBuffer(GISTBuildBuffers *gfbb,
28 : : GISTNodeBuffer *nodeBuffer);
29 : : static void gistPlaceItupToPage(GISTNodeBufferPage *pageBuffer,
30 : : IndexTuple itup);
31 : : static void gistGetItupFromPage(GISTNodeBufferPage *pageBuffer,
32 : : IndexTuple *itup);
33 : : static long gistBuffersGetFreeBlock(GISTBuildBuffers *gfbb);
34 : : static void gistBuffersReleaseBlock(GISTBuildBuffers *gfbb, long blocknum);
35 : :
36 : : static void ReadTempFileBlock(BufFile *file, long blknum, void *ptr);
37 : : static void WriteTempFileBlock(BufFile *file, long blknum, const void *ptr);
38 : :
39 : :
40 : : /*
41 : : * Initialize GiST build buffers.
42 : : */
43 : : GISTBuildBuffers *
44 : 4 : gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel)
45 : : {
46 : : GISTBuildBuffers *gfbb;
47 : : HASHCTL hashCtl;
48 : :
49 : 4 : gfbb = palloc_object(GISTBuildBuffers);
50 : 4 : gfbb->pagesPerBuffer = pagesPerBuffer;
51 : 4 : gfbb->levelStep = levelStep;
52 : :
53 : : /*
54 : : * Create a temporary file to hold buffer pages that are swapped out of
55 : : * memory.
56 : : */
57 : 4 : gfbb->pfile = BufFileCreateTemp(false);
58 : 4 : gfbb->nFileBlocks = 0;
59 : :
60 : : /* Initialize free page management. */
61 : 4 : gfbb->nFreeBlocks = 0;
62 : 4 : gfbb->freeBlocksLen = 32;
63 : 4 : gfbb->freeBlocks = palloc_array(long, gfbb->freeBlocksLen);
64 : :
65 : : /*
66 : : * Current memory context will be used for all in-memory data structures
67 : : * of buffers which are persistent during buffering build.
68 : : */
69 : 4 : gfbb->context = CurrentMemoryContext;
70 : :
71 : : /*
72 : : * nodeBuffersTab hash is association between index blocks and it's
73 : : * buffers.
74 : : */
75 : 4 : hashCtl.keysize = sizeof(BlockNumber);
76 : 4 : hashCtl.entrysize = sizeof(GISTNodeBuffer);
77 : 4 : hashCtl.hcxt = CurrentMemoryContext;
78 : 4 : gfbb->nodeBuffersTab = hash_create("gistbuildbuffers",
79 : : 1024,
80 : : &hashCtl,
81 : : HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
82 : :
83 : 4 : gfbb->bufferEmptyingQueue = NIL;
84 : :
85 : : /*
86 : : * Per-level node buffers lists for final buffers emptying process. Node
87 : : * buffers are inserted here when they are created.
88 : : */
89 : 4 : gfbb->buffersOnLevelsLen = 1;
90 : 4 : gfbb->buffersOnLevels = palloc_array(List *, gfbb->buffersOnLevelsLen);
91 : 4 : gfbb->buffersOnLevels[0] = NIL;
92 : :
93 : : /*
94 : : * Block numbers of node buffers which last pages are currently loaded
95 : : * into main memory.
96 : : */
97 : 4 : gfbb->loadedBuffersLen = 32;
98 : 4 : gfbb->loadedBuffers = palloc_array(GISTNodeBuffer *, gfbb->loadedBuffersLen);
99 : 4 : gfbb->loadedBuffersCount = 0;
100 : :
101 : 4 : gfbb->rootlevel = maxLevel;
102 : :
103 : 4 : return gfbb;
104 : : }
105 : :
106 : : /*
107 : : * Returns a node buffer for given block. The buffer is created if it
108 : : * doesn't exist yet.
109 : : */
110 : : GISTNodeBuffer *
111 : 22904 : gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate,
112 : : BlockNumber nodeBlocknum, int level)
113 : : {
114 : : GISTNodeBuffer *nodeBuffer;
115 : : bool found;
116 : :
117 : : /* Find node buffer in hash table */
118 : 22904 : nodeBuffer = (GISTNodeBuffer *) hash_search(gfbb->nodeBuffersTab,
119 : : &nodeBlocknum,
120 : : HASH_ENTER,
121 : : &found);
122 [ + + ]: 22904 : if (!found)
123 : : {
124 : : /*
125 : : * Node buffer wasn't found. Initialize the new buffer as empty.
126 : : */
127 : 12 : MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);
128 : :
129 : : /* nodeBuffer->nodeBlocknum is the hash key and was filled in already */
130 : 12 : nodeBuffer->blocksCount = 0;
131 : 12 : nodeBuffer->pageBlocknum = InvalidBlockNumber;
132 : 12 : nodeBuffer->pageBuffer = NULL;
133 : 12 : nodeBuffer->queuedForEmptying = false;
134 : 12 : nodeBuffer->isTemp = false;
135 : 12 : nodeBuffer->level = level;
136 : :
137 : : /*
138 : : * Add this buffer to the list of buffers on this level. Enlarge
139 : : * buffersOnLevels array if needed.
140 : : */
141 [ + + ]: 12 : if (level >= gfbb->buffersOnLevelsLen)
142 : : {
143 : : int i;
144 : :
145 : 4 : gfbb->buffersOnLevels = repalloc_array(gfbb->buffersOnLevels, List *, level + 1);
146 : :
147 : : /* initialize the enlarged portion */
148 [ + + ]: 8 : for (i = gfbb->buffersOnLevelsLen; i <= level; i++)
149 : 4 : gfbb->buffersOnLevels[i] = NIL;
150 : 4 : gfbb->buffersOnLevelsLen = level + 1;
151 : : }
152 : :
153 : : /*
154 : : * Prepend the new buffer to the list of buffers on this level. It's
155 : : * not arbitrary that the new buffer is put to the beginning of the
156 : : * list: in the final emptying phase we loop through all buffers at
157 : : * each level, and flush them. If a page is split during the emptying,
158 : : * it's more efficient to flush the new split pages first, before
159 : : * moving on to pre-existing pages on the level. The buffers just
160 : : * created during the page split are likely still in cache, so
161 : : * flushing them immediately is more efficient than putting them to
162 : : * the end of the queue.
163 : : */
164 : 24 : gfbb->buffersOnLevels[level] = lcons(nodeBuffer,
165 : 12 : gfbb->buffersOnLevels[level]);
166 : :
167 : 12 : MemoryContextSwitchTo(oldcxt);
168 : : }
169 : :
170 : 22904 : return nodeBuffer;
171 : : }
172 : :
173 : : /*
174 : : * Allocate memory for a buffer page.
175 : : */
176 : : static GISTNodeBufferPage *
177 : 32 : gistAllocateNewPageBuffer(GISTBuildBuffers *gfbb)
178 : : {
179 : : GISTNodeBufferPage *pageBuffer;
180 : :
181 : 32 : pageBuffer = (GISTNodeBufferPage *) MemoryContextAllocZero(gfbb->context,
182 : : BLCKSZ);
183 : 32 : pageBuffer->prev = InvalidBlockNumber;
184 : :
185 : : /* Set page free space */
186 : 32 : PAGE_FREE_SPACE(pageBuffer) = BLCKSZ - BUFFER_PAGE_DATA_OFFSET;
187 : 32 : return pageBuffer;
188 : : }
189 : :
190 : : /*
191 : : * Add specified buffer into loadedBuffers array.
192 : : */
193 : : static void
194 : 32 : gistAddLoadedBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer)
195 : : {
196 : : /* Never add a temporary buffer to the array */
197 [ - + ]: 32 : if (nodeBuffer->isTemp)
198 : 0 : return;
199 : :
200 : : /* Enlarge the array if needed */
201 [ - + ]: 32 : if (gfbb->loadedBuffersCount >= gfbb->loadedBuffersLen)
202 : : {
203 : 0 : gfbb->loadedBuffersLen *= 2;
204 : 0 : gfbb->loadedBuffers = repalloc_array(gfbb->loadedBuffers,
205 : : GISTNodeBuffer *, gfbb->loadedBuffersLen);
206 : : }
207 : :
208 : 32 : gfbb->loadedBuffers[gfbb->loadedBuffersCount] = nodeBuffer;
209 : 32 : gfbb->loadedBuffersCount++;
210 : : }
211 : :
212 : : /*
213 : : * Load last page of node buffer into main memory.
214 : : */
215 : : static void
216 : 12 : gistLoadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer)
217 : : {
218 : : /* Check if we really should load something */
219 [ + - + - ]: 12 : if (!nodeBuffer->pageBuffer && nodeBuffer->blocksCount > 0)
220 : : {
221 : : /* Allocate memory for page */
222 : 12 : nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb);
223 : :
224 : : /* Read block from temporary file */
225 : 12 : ReadTempFileBlock(gfbb->pfile, nodeBuffer->pageBlocknum,
226 : 12 : nodeBuffer->pageBuffer);
227 : :
228 : : /* Mark file block as free */
229 : 12 : gistBuffersReleaseBlock(gfbb, nodeBuffer->pageBlocknum);
230 : :
231 : : /* Mark node buffer as loaded */
232 : 12 : gistAddLoadedBuffer(gfbb, nodeBuffer);
233 : 12 : nodeBuffer->pageBlocknum = InvalidBlockNumber;
234 : : }
235 : 12 : }
236 : :
237 : : /*
238 : : * Write last page of node buffer to the disk.
239 : : */
240 : : static void
241 : 28 : gistUnloadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer)
242 : : {
243 : : /* Check if we have something to write */
244 [ + + ]: 28 : if (nodeBuffer->pageBuffer)
245 : : {
246 : : BlockNumber blkno;
247 : :
248 : : /* Get free file block */
249 : 12 : blkno = gistBuffersGetFreeBlock(gfbb);
250 : :
251 : : /* Write block to the temporary file */
252 : 12 : WriteTempFileBlock(gfbb->pfile, blkno, nodeBuffer->pageBuffer);
253 : :
254 : : /* Free memory of that page */
255 : 12 : pfree(nodeBuffer->pageBuffer);
256 : 12 : nodeBuffer->pageBuffer = NULL;
257 : :
258 : : /* Save block number */
259 : 12 : nodeBuffer->pageBlocknum = blkno;
260 : : }
261 : 28 : }
262 : :
263 : : /*
264 : : * Write last pages of all node buffers to the disk.
265 : : */
266 : : void
267 : 12 : gistUnloadNodeBuffers(GISTBuildBuffers *gfbb)
268 : : {
269 : : int i;
270 : :
271 : : /* Unload all the buffers that have a page loaded in memory. */
272 [ + + ]: 40 : for (i = 0; i < gfbb->loadedBuffersCount; i++)
273 : 28 : gistUnloadNodeBuffer(gfbb, gfbb->loadedBuffers[i]);
274 : :
275 : : /* Now there are no node buffers with loaded last page */
276 : 12 : gfbb->loadedBuffersCount = 0;
277 : 12 : }
278 : :
279 : : /*
280 : : * Add index tuple to buffer page.
281 : : */
282 : : static void
283 : 42716 : gistPlaceItupToPage(GISTNodeBufferPage *pageBuffer, IndexTuple itup)
284 : : {
285 : 42716 : Size itupsz = IndexTupleSize(itup);
286 : : char *ptr;
287 : :
288 : : /* There should be enough of space. */
289 : : Assert(PAGE_FREE_SPACE(pageBuffer) >= MAXALIGN(itupsz));
290 : :
291 : : /* Reduce free space value of page to reserve a spot for the tuple. */
292 : 42716 : PAGE_FREE_SPACE(pageBuffer) -= MAXALIGN(itupsz);
293 : :
294 : : /* Get pointer to the spot we reserved (ie. end of free space). */
295 : 42716 : ptr = (char *) pageBuffer + BUFFER_PAGE_DATA_OFFSET
296 : 42716 : + PAGE_FREE_SPACE(pageBuffer);
297 : :
298 : : /* Copy the index tuple there. */
299 : 42716 : memcpy(ptr, itup, itupsz);
300 : 42716 : }
301 : :
302 : : /*
303 : : * Get last item from buffer page and remove it from page.
304 : : */
305 : : static void
306 : 42716 : gistGetItupFromPage(GISTNodeBufferPage *pageBuffer, IndexTuple *itup)
307 : : {
308 : : IndexTuple ptr;
309 : : Size itupsz;
310 : :
311 : : Assert(!PAGE_IS_EMPTY(pageBuffer)); /* Page shouldn't be empty */
312 : :
313 : : /* Get pointer to last index tuple */
314 : 42716 : ptr = (IndexTuple) ((char *) pageBuffer
315 : : + BUFFER_PAGE_DATA_OFFSET
316 : 42716 : + PAGE_FREE_SPACE(pageBuffer));
317 : 42716 : itupsz = IndexTupleSize(ptr);
318 : :
319 : : /* Make a copy of the tuple */
320 : 42716 : *itup = (IndexTuple) palloc(itupsz);
321 : 42716 : memcpy(*itup, ptr, itupsz);
322 : :
323 : : /* Mark the space used by the tuple as free */
324 : 42716 : PAGE_FREE_SPACE(pageBuffer) += MAXALIGN(itupsz);
325 : 42716 : }
326 : :
327 : : /*
328 : : * Push an index tuple to node buffer.
329 : : */
330 : : void
331 : 42716 : gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer,
332 : : IndexTuple itup)
333 : : {
334 : : /*
335 : : * Most part of memory operations will be in buffering build persistent
336 : : * context. So, let's switch to it.
337 : : */
338 : 42716 : MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);
339 : :
340 : : /*
341 : : * If the buffer is currently empty, create the first page.
342 : : */
343 [ + + ]: 42716 : if (nodeBuffer->blocksCount == 0)
344 : : {
345 : 20 : nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb);
346 : 20 : nodeBuffer->blocksCount = 1;
347 : 20 : gistAddLoadedBuffer(gfbb, nodeBuffer);
348 : : }
349 : :
350 : : /* Load last page of node buffer if it wasn't in memory already */
351 [ - + ]: 42716 : if (!nodeBuffer->pageBuffer)
352 : 0 : gistLoadNodeBuffer(gfbb, nodeBuffer);
353 : :
354 : : /*
355 : : * Check if there is enough space on the last page for the tuple.
356 : : */
357 [ + + ]: 42716 : if (PAGE_NO_SPACE(nodeBuffer->pageBuffer, itup))
358 : : {
359 : : /*
360 : : * Nope. Swap previous block to disk and allocate a new one.
361 : : */
362 : : BlockNumber blkno;
363 : :
364 : : /* Write filled page to the disk */
365 : 204 : blkno = gistBuffersGetFreeBlock(gfbb);
366 : 204 : WriteTempFileBlock(gfbb->pfile, blkno, nodeBuffer->pageBuffer);
367 : :
368 : : /*
369 : : * Reset the in-memory page as empty, and link the previous block to
370 : : * the new page by storing its block number in the prev-link.
371 : : */
372 : 204 : PAGE_FREE_SPACE(nodeBuffer->pageBuffer) =
373 : : BLCKSZ - MAXALIGN(offsetof(GISTNodeBufferPage, tupledata));
374 : 204 : nodeBuffer->pageBuffer->prev = blkno;
375 : :
376 : : /* We've just added one more page */
377 : 204 : nodeBuffer->blocksCount++;
378 : : }
379 : :
380 : 42716 : gistPlaceItupToPage(nodeBuffer->pageBuffer, itup);
381 : :
382 : : /*
383 : : * If the buffer just overflowed, add it to the emptying queue.
384 : : */
385 [ - + - - ]: 42716 : if (BUFFER_HALF_FILLED(nodeBuffer, gfbb) && !nodeBuffer->queuedForEmptying)
386 : : {
387 : 0 : gfbb->bufferEmptyingQueue = lcons(nodeBuffer,
388 : : gfbb->bufferEmptyingQueue);
389 : 0 : nodeBuffer->queuedForEmptying = true;
390 : : }
391 : :
392 : : /* Restore memory context */
393 : 42716 : MemoryContextSwitchTo(oldcxt);
394 : 42716 : }
395 : :
396 : : /*
397 : : * Removes one index tuple from node buffer. Returns true if success and false
398 : : * if node buffer is empty.
399 : : */
400 : : bool
401 : 42736 : gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer,
402 : : IndexTuple *itup)
403 : : {
404 : : /*
405 : : * If node buffer is empty then return false.
406 : : */
407 [ + + ]: 42736 : if (nodeBuffer->blocksCount <= 0)
408 : 20 : return false;
409 : :
410 : : /* Load last page of node buffer if needed */
411 [ + + ]: 42716 : if (!nodeBuffer->pageBuffer)
412 : 12 : gistLoadNodeBuffer(gfbb, nodeBuffer);
413 : :
414 : : /*
415 : : * Get index tuple from last non-empty page.
416 : : */
417 : 42716 : gistGetItupFromPage(nodeBuffer->pageBuffer, itup);
418 : :
419 : : /*
420 : : * If we just removed the last tuple from the page, fetch previous page on
421 : : * this node buffer (if any).
422 : : */
423 [ + + ]: 42716 : if (PAGE_IS_EMPTY(nodeBuffer->pageBuffer))
424 : : {
425 : : BlockNumber prevblkno;
426 : :
427 : : /*
428 : : * blocksCount includes the page in pageBuffer, so decrease it now.
429 : : */
430 : 224 : nodeBuffer->blocksCount--;
431 : :
432 : : /*
433 : : * If there's more pages, fetch previous one.
434 : : */
435 : 224 : prevblkno = nodeBuffer->pageBuffer->prev;
436 [ + + ]: 224 : if (prevblkno != InvalidBlockNumber)
437 : : {
438 : : /* There is a previous page. Fetch it. */
439 : : Assert(nodeBuffer->blocksCount > 0);
440 : 204 : ReadTempFileBlock(gfbb->pfile, prevblkno, nodeBuffer->pageBuffer);
441 : :
442 : : /*
443 : : * Now that we've read the block in memory, we can release its
444 : : * on-disk block for reuse.
445 : : */
446 : 204 : gistBuffersReleaseBlock(gfbb, prevblkno);
447 : : }
448 : : else
449 : : {
450 : : /* No more pages. Free memory. */
451 : : Assert(nodeBuffer->blocksCount == 0);
452 : 20 : pfree(nodeBuffer->pageBuffer);
453 : 20 : nodeBuffer->pageBuffer = NULL;
454 : : }
455 : : }
456 : 42716 : return true;
457 : : }
458 : :
459 : : /*
460 : : * Select a currently unused block for writing to.
461 : : */
462 : : static long
463 : 216 : gistBuffersGetFreeBlock(GISTBuildBuffers *gfbb)
464 : : {
465 : : /*
466 : : * If there are multiple free blocks, we select the one appearing last in
467 : : * freeBlocks[]. If there are none, assign the next block at the end of
468 : : * the file (causing the file to be extended).
469 : : */
470 [ + + ]: 216 : if (gfbb->nFreeBlocks > 0)
471 : 100 : return gfbb->freeBlocks[--gfbb->nFreeBlocks];
472 : : else
473 : 116 : return gfbb->nFileBlocks++;
474 : : }
475 : :
476 : : /*
477 : : * Return a block# to the freelist.
478 : : */
479 : : static void
480 : 216 : gistBuffersReleaseBlock(GISTBuildBuffers *gfbb, long blocknum)
481 : : {
482 : : int ndx;
483 : :
484 : : /* Enlarge freeBlocks array if full. */
485 [ - + ]: 216 : if (gfbb->nFreeBlocks >= gfbb->freeBlocksLen)
486 : : {
487 : 0 : gfbb->freeBlocksLen *= 2;
488 : 0 : gfbb->freeBlocks = repalloc_array(gfbb->freeBlocks,
489 : : long, gfbb->freeBlocksLen);
490 : : }
491 : :
492 : : /* Add blocknum to array */
493 : 216 : ndx = gfbb->nFreeBlocks++;
494 : 216 : gfbb->freeBlocks[ndx] = blocknum;
495 : 216 : }
496 : :
497 : : /*
498 : : * Free buffering build data structure.
499 : : */
500 : : void
501 : 4 : gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
502 : : {
503 : : /* Close buffers file. */
504 : 4 : BufFileClose(gfbb->pfile);
505 : :
506 : : /* All other things will be freed on memory context release */
507 : 4 : }
508 : :
509 : : /*
510 : : * Data structure representing information about node buffer for index tuples
511 : : * relocation from split node buffer.
512 : : */
513 : : typedef struct
514 : : {
515 : : GISTENTRY entry[INDEX_MAX_KEYS];
516 : : bool isnull[INDEX_MAX_KEYS];
517 : : GISTPageSplitInfo *splitinfo;
518 : : GISTNodeBuffer *nodeBuffer;
519 : : } RelocationBufferInfo;
520 : :
521 : : /*
522 : : * At page split, distribute tuples from the buffer of the split page to
523 : : * new buffers for the created page halves. This also adjusts the downlinks
524 : : * in 'splitinfo' to include the tuples in the buffers.
525 : : */
526 : : void
527 : 512 : gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate,
528 : : Relation r, int level,
529 : : Buffer buffer, List *splitinfo)
530 : : {
531 : : RelocationBufferInfo *relocationBuffersInfos;
532 : : bool found;
533 : : GISTNodeBuffer *nodeBuffer;
534 : : BlockNumber blocknum;
535 : : IndexTuple itup;
536 : 512 : int splitPagesCount = 0;
537 : : GISTENTRY entry[INDEX_MAX_KEYS];
538 : : bool isnull[INDEX_MAX_KEYS];
539 : : GISTNodeBuffer oldBuf;
540 : : ListCell *lc;
541 : :
542 : : /* If the split page doesn't have buffers, we have nothing to do. */
543 [ + + + - : 512 : if (!LEVEL_HAS_BUFFERS(level, gfbb))
- + ]
544 : 504 : return;
545 : :
546 : : /*
547 : : * Get the node buffer of the split page.
548 : : */
549 : 8 : blocknum = BufferGetBlockNumber(buffer);
550 : 8 : nodeBuffer = hash_search(gfbb->nodeBuffersTab, &blocknum,
551 : : HASH_FIND, &found);
552 [ - + ]: 8 : if (!found)
553 : : {
554 : : /* The page has no buffer, so we have nothing to do. */
555 : 0 : return;
556 : : }
557 : :
558 : : /*
559 : : * Make a copy of the old buffer, as we're going reuse it as the buffer
560 : : * for the new left page, which is on the same block as the old page.
561 : : * That's not true for the root page, but that's fine because we never
562 : : * have a buffer on the root page anyway. The original algorithm as
563 : : * described by Arge et al did, but it's of no use, as you might as well
564 : : * read the tuples straight from the heap instead of the root buffer.
565 : : */
566 : : Assert(blocknum != GIST_ROOT_BLKNO);
567 : 8 : memcpy(&oldBuf, nodeBuffer, sizeof(GISTNodeBuffer));
568 : 8 : oldBuf.isTemp = true;
569 : :
570 : : /* Reset the old buffer, used for the new left page from now on */
571 : 8 : nodeBuffer->blocksCount = 0;
572 : 8 : nodeBuffer->pageBuffer = NULL;
573 : 8 : nodeBuffer->pageBlocknum = InvalidBlockNumber;
574 : :
575 : : /*
576 : : * Allocate memory for information about relocation buffers.
577 : : */
578 : 8 : splitPagesCount = list_length(splitinfo);
579 : 8 : relocationBuffersInfos = palloc_array(RelocationBufferInfo, splitPagesCount);
580 : :
581 : : /*
582 : : * Fill relocation buffers information for node buffers of pages produced
583 : : * by split.
584 : : */
585 [ + - + + : 24 : foreach(lc, splitinfo)
+ + ]
586 : : {
587 : 16 : GISTPageSplitInfo *si = (GISTPageSplitInfo *) lfirst(lc);
588 : : GISTNodeBuffer *newNodeBuffer;
589 : 16 : int i = foreach_current_index(lc);
590 : :
591 : : /* Decompress parent index tuple of node buffer page. */
592 : 16 : gistDeCompressAtt(giststate, r,
593 : : si->downlink, NULL, (OffsetNumber) 0,
594 : 16 : relocationBuffersInfos[i].entry,
595 : 16 : relocationBuffersInfos[i].isnull);
596 : :
597 : : /*
598 : : * Create a node buffer for the page. The leftmost half is on the same
599 : : * block as the old page before split, so for the leftmost half this
600 : : * will return the original buffer. The tuples on the original buffer
601 : : * were relinked to the temporary buffer, so the original one is now
602 : : * empty.
603 : : */
604 : 16 : newNodeBuffer = gistGetNodeBuffer(gfbb, giststate, BufferGetBlockNumber(si->buf), level);
605 : :
606 : 16 : relocationBuffersInfos[i].nodeBuffer = newNodeBuffer;
607 : 16 : relocationBuffersInfos[i].splitinfo = si;
608 : : }
609 : :
610 : : /*
611 : : * Loop through all index tuples in the buffer of the page being split,
612 : : * moving them to buffers for the new pages. We try to move each tuple to
613 : : * the page that will result in the lowest penalty for the leading column
614 : : * or, in the case of a tie, the lowest penalty for the earliest column
615 : : * that is not tied.
616 : : *
617 : : * The page searching logic is very similar to gistchoose().
618 : : */
619 [ + + ]: 19836 : while (gistPopItupFromNodeBuffer(gfbb, &oldBuf, &itup))
620 : : {
621 : : float best_penalty[INDEX_MAX_KEYS];
622 : : int i,
623 : : which;
624 : : IndexTuple newtup;
625 : : RelocationBufferInfo *targetBufferInfo;
626 : :
627 : 19828 : gistDeCompressAtt(giststate, r,
628 : : itup, NULL, (OffsetNumber) 0, entry, isnull);
629 : :
630 : : /* default to using first page (shouldn't matter) */
631 : 19828 : which = 0;
632 : :
633 : : /*
634 : : * best_penalty[j] is the best penalty we have seen so far for column
635 : : * j, or -1 when we haven't yet examined column j. Array entries to
636 : : * the right of the first -1 are undefined.
637 : : */
638 : 19828 : best_penalty[0] = -1;
639 : :
640 : : /*
641 : : * Loop over possible target pages, looking for one to move this tuple
642 : : * to.
643 : : */
644 [ + + ]: 59476 : for (i = 0; i < splitPagesCount; i++)
645 : : {
646 : 39652 : RelocationBufferInfo *splitPageInfo = &relocationBuffersInfos[i];
647 : : bool zero_penalty;
648 : : int j;
649 : :
650 : 39652 : zero_penalty = true;
651 : :
652 : : /* Loop over index attributes. */
653 [ + + ]: 73720 : for (j = 0; j < IndexRelationGetNumberOfKeyAttributes(r); j++)
654 : : {
655 : : float usize;
656 : :
657 : : /* Compute penalty for this column. */
658 : 39652 : usize = gistpenalty(giststate, j,
659 : : &splitPageInfo->entry[j],
660 : 39652 : splitPageInfo->isnull[j],
661 : 39652 : &entry[j], isnull[j]);
662 [ + + ]: 39652 : if (usize > 0)
663 : 39648 : zero_penalty = false;
664 : :
665 [ + + + + ]: 39652 : if (best_penalty[j] < 0 || usize < best_penalty[j])
666 : : {
667 : : /*
668 : : * New best penalty for column. Tentatively select this
669 : : * page as the target, and record the best penalty. Then
670 : : * reset the next column's penalty to "unknown" (and
671 : : * indirectly, the same for all the ones to its right).
672 : : * This will force us to adopt this page's penalty values
673 : : * as the best for all the remaining columns during
674 : : * subsequent loop iterations.
675 : : */
676 : 34068 : which = i;
677 : 34068 : best_penalty[j] = usize;
678 : :
679 [ - + ]: 34068 : if (j < IndexRelationGetNumberOfKeyAttributes(r) - 1)
680 : 0 : best_penalty[j + 1] = -1;
681 : : }
682 [ + - ]: 5584 : else if (best_penalty[j] == usize)
683 : : {
684 : : /*
685 : : * The current page is exactly as good for this column as
686 : : * the best page seen so far. The next iteration of this
687 : : * loop will compare the next column.
688 : : */
689 : : }
690 : : else
691 : : {
692 : : /*
693 : : * The current page is worse for this column than the best
694 : : * page seen so far. Skip the remaining columns and move
695 : : * on to the next page, if any.
696 : : */
697 : 5584 : zero_penalty = false; /* so outer loop won't exit */
698 : 5584 : break;
699 : : }
700 : : }
701 : :
702 : : /*
703 : : * If we find a page with zero penalty for all columns, there's no
704 : : * need to examine remaining pages; just break out of the loop and
705 : : * return it.
706 : : */
707 [ + + ]: 39652 : if (zero_penalty)
708 : 4 : break;
709 : : }
710 : :
711 : : /* OK, "which" is the page index to push the tuple to */
712 : 19828 : targetBufferInfo = &relocationBuffersInfos[which];
713 : :
714 : : /* Push item to selected node buffer */
715 : 19828 : gistPushItupToNodeBuffer(gfbb, targetBufferInfo->nodeBuffer, itup);
716 : :
717 : : /* Adjust the downlink for this page, if needed. */
718 : 19828 : newtup = gistgetadjusted(r, targetBufferInfo->splitinfo->downlink,
719 : : itup, giststate);
720 [ + + ]: 19828 : if (newtup)
721 : : {
722 : 19824 : gistDeCompressAtt(giststate, r,
723 : : newtup, NULL, (OffsetNumber) 0,
724 : 19824 : targetBufferInfo->entry,
725 : 19824 : targetBufferInfo->isnull);
726 : :
727 : 19824 : targetBufferInfo->splitinfo->downlink = newtup;
728 : : }
729 : : }
730 : :
731 : 8 : pfree(relocationBuffersInfos);
732 : : }
733 : :
734 : :
735 : : /*
736 : : * Wrappers around BufFile operations. The main difference is that these
737 : : * wrappers report errors with ereport(), so that the callers don't need
738 : : * to check the return code.
739 : : */
740 : :
741 : : static void
742 : 216 : ReadTempFileBlock(BufFile *file, long blknum, void *ptr)
743 : : {
744 [ - + ]: 216 : if (BufFileSeekBlock(file, blknum) != 0)
745 [ # # ]: 0 : elog(ERROR, "could not seek to block %ld in temporary file", blknum);
746 : 216 : BufFileReadExact(file, ptr, BLCKSZ);
747 : 216 : }
748 : :
749 : : static void
750 : 216 : WriteTempFileBlock(BufFile *file, long blknum, const void *ptr)
751 : : {
752 [ - + ]: 216 : if (BufFileSeekBlock(file, blknum) != 0)
753 [ # # ]: 0 : elog(ERROR, "could not seek to block %ld in temporary file", blknum);
754 : 216 : BufFileWrite(file, ptr, BLCKSZ);
755 : 216 : }
|
