/src/postgres/src/backend/access/gist/gistbuildbuffers.c
Line | Count | Source |
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 | | gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel) |
45 | 0 | { |
46 | 0 | GISTBuildBuffers *gfbb; |
47 | 0 | HASHCTL hashCtl; |
48 | |
|
49 | 0 | gfbb = palloc_object(GISTBuildBuffers); |
50 | 0 | gfbb->pagesPerBuffer = pagesPerBuffer; |
51 | 0 | gfbb->levelStep = levelStep; |
52 | | |
53 | | /* |
54 | | * Create a temporary file to hold buffer pages that are swapped out of |
55 | | * memory. |
56 | | */ |
57 | 0 | gfbb->pfile = BufFileCreateTemp(false); |
58 | 0 | gfbb->nFileBlocks = 0; |
59 | | |
60 | | /* Initialize free page management. */ |
61 | 0 | gfbb->nFreeBlocks = 0; |
62 | 0 | gfbb->freeBlocksLen = 32; |
63 | 0 | 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 | 0 | gfbb->context = CurrentMemoryContext; |
70 | | |
71 | | /* |
72 | | * nodeBuffersTab hash is association between index blocks and it's |
73 | | * buffers. |
74 | | */ |
75 | 0 | hashCtl.keysize = sizeof(BlockNumber); |
76 | 0 | hashCtl.entrysize = sizeof(GISTNodeBuffer); |
77 | 0 | hashCtl.hcxt = CurrentMemoryContext; |
78 | 0 | gfbb->nodeBuffersTab = hash_create("gistbuildbuffers", |
79 | 0 | 1024, |
80 | 0 | &hashCtl, |
81 | 0 | HASH_ELEM | HASH_BLOBS | HASH_CONTEXT); |
82 | |
|
83 | 0 | 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 | 0 | gfbb->buffersOnLevelsLen = 1; |
90 | 0 | gfbb->buffersOnLevels = palloc_array(List *, gfbb->buffersOnLevelsLen); |
91 | 0 | gfbb->buffersOnLevels[0] = NIL; |
92 | | |
93 | | /* |
94 | | * Block numbers of node buffers which last pages are currently loaded |
95 | | * into main memory. |
96 | | */ |
97 | 0 | gfbb->loadedBuffersLen = 32; |
98 | 0 | gfbb->loadedBuffers = palloc_array(GISTNodeBuffer *, gfbb->loadedBuffersLen); |
99 | 0 | gfbb->loadedBuffersCount = 0; |
100 | |
|
101 | 0 | gfbb->rootlevel = maxLevel; |
102 | |
|
103 | 0 | return gfbb; |
104 | 0 | } |
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 | | gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, |
112 | | BlockNumber nodeBlocknum, int level) |
113 | 0 | { |
114 | 0 | GISTNodeBuffer *nodeBuffer; |
115 | 0 | bool found; |
116 | | |
117 | | /* Find node buffer in hash table */ |
118 | 0 | nodeBuffer = (GISTNodeBuffer *) hash_search(gfbb->nodeBuffersTab, |
119 | 0 | &nodeBlocknum, |
120 | 0 | HASH_ENTER, |
121 | 0 | &found); |
122 | 0 | if (!found) |
123 | 0 | { |
124 | | /* |
125 | | * Node buffer wasn't found. Initialize the new buffer as empty. |
126 | | */ |
127 | 0 | MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context); |
128 | | |
129 | | /* nodeBuffer->nodeBlocknum is the hash key and was filled in already */ |
130 | 0 | nodeBuffer->blocksCount = 0; |
131 | 0 | nodeBuffer->pageBlocknum = InvalidBlockNumber; |
132 | 0 | nodeBuffer->pageBuffer = NULL; |
133 | 0 | nodeBuffer->queuedForEmptying = false; |
134 | 0 | nodeBuffer->isTemp = false; |
135 | 0 | 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 | 0 | if (level >= gfbb->buffersOnLevelsLen) |
142 | 0 | { |
143 | 0 | int i; |
144 | |
|
145 | 0 | gfbb->buffersOnLevels = repalloc_array(gfbb->buffersOnLevels, List *, level + 1); |
146 | | |
147 | | /* initialize the enlarged portion */ |
148 | 0 | for (i = gfbb->buffersOnLevelsLen; i <= level; i++) |
149 | 0 | gfbb->buffersOnLevels[i] = NIL; |
150 | 0 | gfbb->buffersOnLevelsLen = level + 1; |
151 | 0 | } |
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 | 0 | gfbb->buffersOnLevels[level] = lcons(nodeBuffer, |
165 | 0 | gfbb->buffersOnLevels[level]); |
166 | |
|
167 | 0 | MemoryContextSwitchTo(oldcxt); |
168 | 0 | } |
169 | |
|
170 | 0 | return nodeBuffer; |
171 | 0 | } |
172 | | |
173 | | /* |
174 | | * Allocate memory for a buffer page. |
175 | | */ |
176 | | static GISTNodeBufferPage * |
177 | | gistAllocateNewPageBuffer(GISTBuildBuffers *gfbb) |
178 | 0 | { |
179 | 0 | GISTNodeBufferPage *pageBuffer; |
180 | |
|
181 | 0 | pageBuffer = (GISTNodeBufferPage *) MemoryContextAllocZero(gfbb->context, |
182 | 0 | BLCKSZ); |
183 | 0 | pageBuffer->prev = InvalidBlockNumber; |
184 | | |
185 | | /* Set page free space */ |
186 | 0 | PAGE_FREE_SPACE(pageBuffer) = BLCKSZ - BUFFER_PAGE_DATA_OFFSET; |
187 | 0 | return pageBuffer; |
188 | 0 | } |
189 | | |
190 | | /* |
191 | | * Add specified buffer into loadedBuffers array. |
192 | | */ |
193 | | static void |
194 | | gistAddLoadedBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer) |
195 | 0 | { |
196 | | /* Never add a temporary buffer to the array */ |
197 | 0 | if (nodeBuffer->isTemp) |
198 | 0 | return; |
199 | | |
200 | | /* Enlarge the array if needed */ |
201 | 0 | if (gfbb->loadedBuffersCount >= gfbb->loadedBuffersLen) |
202 | 0 | { |
203 | 0 | gfbb->loadedBuffersLen *= 2; |
204 | 0 | gfbb->loadedBuffers = repalloc_array(gfbb->loadedBuffers, |
205 | 0 | GISTNodeBuffer *, gfbb->loadedBuffersLen); |
206 | 0 | } |
207 | |
|
208 | 0 | gfbb->loadedBuffers[gfbb->loadedBuffersCount] = nodeBuffer; |
209 | 0 | gfbb->loadedBuffersCount++; |
210 | 0 | } |
211 | | |
212 | | /* |
213 | | * Load last page of node buffer into main memory. |
214 | | */ |
215 | | static void |
216 | | gistLoadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer) |
217 | 0 | { |
218 | | /* Check if we really should load something */ |
219 | 0 | if (!nodeBuffer->pageBuffer && nodeBuffer->blocksCount > 0) |
220 | 0 | { |
221 | | /* Allocate memory for page */ |
222 | 0 | nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb); |
223 | | |
224 | | /* Read block from temporary file */ |
225 | 0 | ReadTempFileBlock(gfbb->pfile, nodeBuffer->pageBlocknum, |
226 | 0 | nodeBuffer->pageBuffer); |
227 | | |
228 | | /* Mark file block as free */ |
229 | 0 | gistBuffersReleaseBlock(gfbb, nodeBuffer->pageBlocknum); |
230 | | |
231 | | /* Mark node buffer as loaded */ |
232 | 0 | gistAddLoadedBuffer(gfbb, nodeBuffer); |
233 | 0 | nodeBuffer->pageBlocknum = InvalidBlockNumber; |
234 | 0 | } |
235 | 0 | } |
236 | | |
237 | | /* |
238 | | * Write last page of node buffer to the disk. |
239 | | */ |
240 | | static void |
241 | | gistUnloadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer) |
242 | 0 | { |
243 | | /* Check if we have something to write */ |
244 | 0 | if (nodeBuffer->pageBuffer) |
245 | 0 | { |
246 | 0 | BlockNumber blkno; |
247 | | |
248 | | /* Get free file block */ |
249 | 0 | blkno = gistBuffersGetFreeBlock(gfbb); |
250 | | |
251 | | /* Write block to the temporary file */ |
252 | 0 | WriteTempFileBlock(gfbb->pfile, blkno, nodeBuffer->pageBuffer); |
253 | | |
254 | | /* Free memory of that page */ |
255 | 0 | pfree(nodeBuffer->pageBuffer); |
256 | 0 | nodeBuffer->pageBuffer = NULL; |
257 | | |
258 | | /* Save block number */ |
259 | 0 | nodeBuffer->pageBlocknum = blkno; |
260 | 0 | } |
261 | 0 | } |
262 | | |
263 | | /* |
264 | | * Write last pages of all node buffers to the disk. |
265 | | */ |
266 | | void |
267 | | gistUnloadNodeBuffers(GISTBuildBuffers *gfbb) |
268 | 0 | { |
269 | 0 | int i; |
270 | | |
271 | | /* Unload all the buffers that have a page loaded in memory. */ |
272 | 0 | for (i = 0; i < gfbb->loadedBuffersCount; i++) |
273 | 0 | gistUnloadNodeBuffer(gfbb, gfbb->loadedBuffers[i]); |
274 | | |
275 | | /* Now there are no node buffers with loaded last page */ |
276 | 0 | gfbb->loadedBuffersCount = 0; |
277 | 0 | } |
278 | | |
279 | | /* |
280 | | * Add index tuple to buffer page. |
281 | | */ |
282 | | static void |
283 | | gistPlaceItupToPage(GISTNodeBufferPage *pageBuffer, IndexTuple itup) |
284 | 0 | { |
285 | 0 | Size itupsz = IndexTupleSize(itup); |
286 | 0 | char *ptr; |
287 | | |
288 | | /* There should be enough of space. */ |
289 | 0 | Assert(PAGE_FREE_SPACE(pageBuffer) >= MAXALIGN(itupsz)); |
290 | | |
291 | | /* Reduce free space value of page to reserve a spot for the tuple. */ |
292 | 0 | PAGE_FREE_SPACE(pageBuffer) -= MAXALIGN(itupsz); |
293 | | |
294 | | /* Get pointer to the spot we reserved (ie. end of free space). */ |
295 | 0 | ptr = (char *) pageBuffer + BUFFER_PAGE_DATA_OFFSET |
296 | 0 | + PAGE_FREE_SPACE(pageBuffer); |
297 | | |
298 | | /* Copy the index tuple there. */ |
299 | 0 | memcpy(ptr, itup, itupsz); |
300 | 0 | } |
301 | | |
302 | | /* |
303 | | * Get last item from buffer page and remove it from page. |
304 | | */ |
305 | | static void |
306 | | gistGetItupFromPage(GISTNodeBufferPage *pageBuffer, IndexTuple *itup) |
307 | 0 | { |
308 | 0 | IndexTuple ptr; |
309 | 0 | Size itupsz; |
310 | |
|
311 | 0 | Assert(!PAGE_IS_EMPTY(pageBuffer)); /* Page shouldn't be empty */ |
312 | | |
313 | | /* Get pointer to last index tuple */ |
314 | 0 | ptr = (IndexTuple) ((char *) pageBuffer |
315 | 0 | + BUFFER_PAGE_DATA_OFFSET |
316 | 0 | + PAGE_FREE_SPACE(pageBuffer)); |
317 | 0 | itupsz = IndexTupleSize(ptr); |
318 | | |
319 | | /* Make a copy of the tuple */ |
320 | 0 | *itup = (IndexTuple) palloc(itupsz); |
321 | 0 | memcpy(*itup, ptr, itupsz); |
322 | | |
323 | | /* Mark the space used by the tuple as free */ |
324 | 0 | PAGE_FREE_SPACE(pageBuffer) += MAXALIGN(itupsz); |
325 | 0 | } |
326 | | |
327 | | /* |
328 | | * Push an index tuple to node buffer. |
329 | | */ |
330 | | void |
331 | | gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, |
332 | | IndexTuple itup) |
333 | 0 | { |
334 | | /* |
335 | | * Most part of memory operations will be in buffering build persistent |
336 | | * context. So, let's switch to it. |
337 | | */ |
338 | 0 | MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context); |
339 | | |
340 | | /* |
341 | | * If the buffer is currently empty, create the first page. |
342 | | */ |
343 | 0 | if (nodeBuffer->blocksCount == 0) |
344 | 0 | { |
345 | 0 | nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb); |
346 | 0 | nodeBuffer->blocksCount = 1; |
347 | 0 | gistAddLoadedBuffer(gfbb, nodeBuffer); |
348 | 0 | } |
349 | | |
350 | | /* Load last page of node buffer if it wasn't in memory already */ |
351 | 0 | 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 | 0 | if (PAGE_NO_SPACE(nodeBuffer->pageBuffer, itup)) |
358 | 0 | { |
359 | | /* |
360 | | * Nope. Swap previous block to disk and allocate a new one. |
361 | | */ |
362 | 0 | BlockNumber blkno; |
363 | | |
364 | | /* Write filled page to the disk */ |
365 | 0 | blkno = gistBuffersGetFreeBlock(gfbb); |
366 | 0 | 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 | 0 | PAGE_FREE_SPACE(nodeBuffer->pageBuffer) = |
373 | 0 | BLCKSZ - MAXALIGN(offsetof(GISTNodeBufferPage, tupledata)); |
374 | 0 | nodeBuffer->pageBuffer->prev = blkno; |
375 | | |
376 | | /* We've just added one more page */ |
377 | 0 | nodeBuffer->blocksCount++; |
378 | 0 | } |
379 | |
|
380 | 0 | gistPlaceItupToPage(nodeBuffer->pageBuffer, itup); |
381 | | |
382 | | /* |
383 | | * If the buffer just overflowed, add it to the emptying queue. |
384 | | */ |
385 | 0 | if (BUFFER_HALF_FILLED(nodeBuffer, gfbb) && !nodeBuffer->queuedForEmptying) |
386 | 0 | { |
387 | 0 | gfbb->bufferEmptyingQueue = lcons(nodeBuffer, |
388 | 0 | gfbb->bufferEmptyingQueue); |
389 | 0 | nodeBuffer->queuedForEmptying = true; |
390 | 0 | } |
391 | | |
392 | | /* Restore memory context */ |
393 | 0 | MemoryContextSwitchTo(oldcxt); |
394 | 0 | } |
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 | | gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, |
402 | | IndexTuple *itup) |
403 | 0 | { |
404 | | /* |
405 | | * If node buffer is empty then return false. |
406 | | */ |
407 | 0 | if (nodeBuffer->blocksCount <= 0) |
408 | 0 | return false; |
409 | | |
410 | | /* Load last page of node buffer if needed */ |
411 | 0 | if (!nodeBuffer->pageBuffer) |
412 | 0 | gistLoadNodeBuffer(gfbb, nodeBuffer); |
413 | | |
414 | | /* |
415 | | * Get index tuple from last non-empty page. |
416 | | */ |
417 | 0 | 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 | 0 | if (PAGE_IS_EMPTY(nodeBuffer->pageBuffer)) |
424 | 0 | { |
425 | 0 | BlockNumber prevblkno; |
426 | | |
427 | | /* |
428 | | * blocksCount includes the page in pageBuffer, so decrease it now. |
429 | | */ |
430 | 0 | nodeBuffer->blocksCount--; |
431 | | |
432 | | /* |
433 | | * If there's more pages, fetch previous one. |
434 | | */ |
435 | 0 | prevblkno = nodeBuffer->pageBuffer->prev; |
436 | 0 | if (prevblkno != InvalidBlockNumber) |
437 | 0 | { |
438 | | /* There is a previous page. Fetch it. */ |
439 | 0 | Assert(nodeBuffer->blocksCount > 0); |
440 | 0 | 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 | 0 | gistBuffersReleaseBlock(gfbb, prevblkno); |
447 | 0 | } |
448 | 0 | else |
449 | 0 | { |
450 | | /* No more pages. Free memory. */ |
451 | 0 | Assert(nodeBuffer->blocksCount == 0); |
452 | 0 | pfree(nodeBuffer->pageBuffer); |
453 | 0 | nodeBuffer->pageBuffer = NULL; |
454 | 0 | } |
455 | 0 | } |
456 | 0 | return true; |
457 | 0 | } |
458 | | |
459 | | /* |
460 | | * Select a currently unused block for writing to. |
461 | | */ |
462 | | static long |
463 | | gistBuffersGetFreeBlock(GISTBuildBuffers *gfbb) |
464 | 0 | { |
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 | 0 | if (gfbb->nFreeBlocks > 0) |
471 | 0 | return gfbb->freeBlocks[--gfbb->nFreeBlocks]; |
472 | 0 | else |
473 | 0 | return gfbb->nFileBlocks++; |
474 | 0 | } |
475 | | |
476 | | /* |
477 | | * Return a block# to the freelist. |
478 | | */ |
479 | | static void |
480 | | gistBuffersReleaseBlock(GISTBuildBuffers *gfbb, long blocknum) |
481 | 0 | { |
482 | 0 | int ndx; |
483 | | |
484 | | /* Enlarge freeBlocks array if full. */ |
485 | 0 | if (gfbb->nFreeBlocks >= gfbb->freeBlocksLen) |
486 | 0 | { |
487 | 0 | gfbb->freeBlocksLen *= 2; |
488 | 0 | gfbb->freeBlocks = repalloc_array(gfbb->freeBlocks, |
489 | 0 | long, gfbb->freeBlocksLen); |
490 | 0 | } |
491 | | |
492 | | /* Add blocknum to array */ |
493 | 0 | ndx = gfbb->nFreeBlocks++; |
494 | 0 | gfbb->freeBlocks[ndx] = blocknum; |
495 | 0 | } |
496 | | |
497 | | /* |
498 | | * Free buffering build data structure. |
499 | | */ |
500 | | void |
501 | | gistFreeBuildBuffers(GISTBuildBuffers *gfbb) |
502 | 0 | { |
503 | | /* Close buffers file. */ |
504 | 0 | BufFileClose(gfbb->pfile); |
505 | | |
506 | | /* All other things will be freed on memory context release */ |
507 | 0 | } |
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 | | gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, |
528 | | Relation r, int level, |
529 | | Buffer buffer, List *splitinfo) |
530 | 0 | { |
531 | 0 | RelocationBufferInfo *relocationBuffersInfos; |
532 | 0 | bool found; |
533 | 0 | GISTNodeBuffer *nodeBuffer; |
534 | 0 | BlockNumber blocknum; |
535 | 0 | IndexTuple itup; |
536 | 0 | int splitPagesCount = 0; |
537 | 0 | GISTENTRY entry[INDEX_MAX_KEYS]; |
538 | 0 | bool isnull[INDEX_MAX_KEYS]; |
539 | 0 | GISTNodeBuffer oldBuf; |
540 | 0 | ListCell *lc; |
541 | | |
542 | | /* If the split page doesn't have buffers, we have nothing to do. */ |
543 | 0 | if (!LEVEL_HAS_BUFFERS(level, gfbb)) |
544 | 0 | return; |
545 | | |
546 | | /* |
547 | | * Get the node buffer of the split page. |
548 | | */ |
549 | 0 | blocknum = BufferGetBlockNumber(buffer); |
550 | 0 | nodeBuffer = hash_search(gfbb->nodeBuffersTab, &blocknum, |
551 | 0 | HASH_FIND, &found); |
552 | 0 | if (!found) |
553 | 0 | { |
554 | | /* The page has no buffer, so we have nothing to do. */ |
555 | 0 | return; |
556 | 0 | } |
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 | 0 | Assert(blocknum != GIST_ROOT_BLKNO); |
567 | 0 | memcpy(&oldBuf, nodeBuffer, sizeof(GISTNodeBuffer)); |
568 | 0 | oldBuf.isTemp = true; |
569 | | |
570 | | /* Reset the old buffer, used for the new left page from now on */ |
571 | 0 | nodeBuffer->blocksCount = 0; |
572 | 0 | nodeBuffer->pageBuffer = NULL; |
573 | 0 | nodeBuffer->pageBlocknum = InvalidBlockNumber; |
574 | | |
575 | | /* |
576 | | * Allocate memory for information about relocation buffers. |
577 | | */ |
578 | 0 | splitPagesCount = list_length(splitinfo); |
579 | 0 | relocationBuffersInfos = palloc_array(RelocationBufferInfo, splitPagesCount); |
580 | | |
581 | | /* |
582 | | * Fill relocation buffers information for node buffers of pages produced |
583 | | * by split. |
584 | | */ |
585 | 0 | foreach(lc, splitinfo) |
586 | 0 | { |
587 | 0 | GISTPageSplitInfo *si = (GISTPageSplitInfo *) lfirst(lc); |
588 | 0 | GISTNodeBuffer *newNodeBuffer; |
589 | 0 | int i = foreach_current_index(lc); |
590 | | |
591 | | /* Decompress parent index tuple of node buffer page. */ |
592 | 0 | gistDeCompressAtt(giststate, r, |
593 | 0 | si->downlink, NULL, (OffsetNumber) 0, |
594 | 0 | relocationBuffersInfos[i].entry, |
595 | 0 | 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 | 0 | newNodeBuffer = gistGetNodeBuffer(gfbb, giststate, BufferGetBlockNumber(si->buf), level); |
605 | |
|
606 | 0 | relocationBuffersInfos[i].nodeBuffer = newNodeBuffer; |
607 | 0 | relocationBuffersInfos[i].splitinfo = si; |
608 | 0 | } |
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 | 0 | while (gistPopItupFromNodeBuffer(gfbb, &oldBuf, &itup)) |
620 | 0 | { |
621 | 0 | float best_penalty[INDEX_MAX_KEYS]; |
622 | 0 | int i, |
623 | 0 | which; |
624 | 0 | IndexTuple newtup; |
625 | 0 | RelocationBufferInfo *targetBufferInfo; |
626 | |
|
627 | 0 | gistDeCompressAtt(giststate, r, |
628 | 0 | itup, NULL, (OffsetNumber) 0, entry, isnull); |
629 | | |
630 | | /* default to using first page (shouldn't matter) */ |
631 | 0 | 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 | 0 | best_penalty[0] = -1; |
639 | | |
640 | | /* |
641 | | * Loop over possible target pages, looking for one to move this tuple |
642 | | * to. |
643 | | */ |
644 | 0 | for (i = 0; i < splitPagesCount; i++) |
645 | 0 | { |
646 | 0 | RelocationBufferInfo *splitPageInfo = &relocationBuffersInfos[i]; |
647 | 0 | bool zero_penalty; |
648 | 0 | int j; |
649 | |
|
650 | 0 | zero_penalty = true; |
651 | | |
652 | | /* Loop over index attributes. */ |
653 | 0 | for (j = 0; j < IndexRelationGetNumberOfKeyAttributes(r); j++) |
654 | 0 | { |
655 | 0 | float usize; |
656 | | |
657 | | /* Compute penalty for this column. */ |
658 | 0 | usize = gistpenalty(giststate, j, |
659 | 0 | &splitPageInfo->entry[j], |
660 | 0 | splitPageInfo->isnull[j], |
661 | 0 | &entry[j], isnull[j]); |
662 | 0 | if (usize > 0) |
663 | 0 | zero_penalty = false; |
664 | |
|
665 | 0 | if (best_penalty[j] < 0 || usize < best_penalty[j]) |
666 | 0 | { |
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 | 0 | which = i; |
677 | 0 | best_penalty[j] = usize; |
678 | |
|
679 | 0 | if (j < IndexRelationGetNumberOfKeyAttributes(r) - 1) |
680 | 0 | best_penalty[j + 1] = -1; |
681 | 0 | } |
682 | 0 | else if (best_penalty[j] == usize) |
683 | 0 | { |
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 | 0 | } |
690 | 0 | else |
691 | 0 | { |
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 | 0 | zero_penalty = false; /* so outer loop won't exit */ |
698 | 0 | break; |
699 | 0 | } |
700 | 0 | } |
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 | 0 | if (zero_penalty) |
708 | 0 | break; |
709 | 0 | } |
710 | | |
711 | | /* OK, "which" is the page index to push the tuple to */ |
712 | 0 | targetBufferInfo = &relocationBuffersInfos[which]; |
713 | | |
714 | | /* Push item to selected node buffer */ |
715 | 0 | gistPushItupToNodeBuffer(gfbb, targetBufferInfo->nodeBuffer, itup); |
716 | | |
717 | | /* Adjust the downlink for this page, if needed. */ |
718 | 0 | newtup = gistgetadjusted(r, targetBufferInfo->splitinfo->downlink, |
719 | 0 | itup, giststate); |
720 | 0 | if (newtup) |
721 | 0 | { |
722 | 0 | gistDeCompressAtt(giststate, r, |
723 | 0 | newtup, NULL, (OffsetNumber) 0, |
724 | 0 | targetBufferInfo->entry, |
725 | 0 | targetBufferInfo->isnull); |
726 | |
|
727 | 0 | targetBufferInfo->splitinfo->downlink = newtup; |
728 | 0 | } |
729 | 0 | } |
730 | |
|
731 | 0 | pfree(relocationBuffersInfos); |
732 | 0 | } |
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 | | ReadTempFileBlock(BufFile *file, long blknum, void *ptr) |
743 | 0 | { |
744 | 0 | if (BufFileSeekBlock(file, blknum) != 0) |
745 | 0 | elog(ERROR, "could not seek to block %ld in temporary file", blknum); |
746 | 0 | BufFileReadExact(file, ptr, BLCKSZ); |
747 | 0 | } |
748 | | |
749 | | static void |
750 | | WriteTempFileBlock(BufFile *file, long blknum, const void *ptr) |
751 | 0 | { |
752 | 0 | if (BufFileSeekBlock(file, blknum) != 0) |
753 | 0 | elog(ERROR, "could not seek to block %ld in temporary file", blknum); |
754 | 0 | BufFileWrite(file, ptr, BLCKSZ); |
755 | 0 | } |