Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit f35bd9b

Browse filesBrowse files
j-naylorj-naylor
committed
Teach TID store to skip bitmap for small numbers of offsets
The header portion of BlocktableEntry has enough padding space for an array of 3 offsets (1 on 32-bit platforms). Use this space instead of having a sparse bitmap array. This will take up a constant amount of space no matter what the offsets are. Reviewed (in an earlier version) by Masahiko Sawada Discussion: https://postgr.es/m/CANWCAZYw+_KAaUNruhJfE=h6WgtBKeDG32St8vBJBEY82bGVRQ@mail.gmail.com Discussion: https://postgr.es/m/CAD21AoBci3Hujzijubomo1tdwH3XtQ9F89cTNQ4bsQijOmqnEw@mail.gmail.com
1 parent dd1f6b0 commit f35bd9b
Copy full SHA for f35bd9b

File tree

Expand file treeCollapse file tree

3 files changed

+130
-37
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+130
-37
lines changed

‎src/backend/access/common/tidstore.c

Copy file name to clipboardExpand all lines: src/backend/access/common/tidstore.c
+92-37Lines changed: 92 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -34,13 +34,23 @@
3434
/* number of active words for a page: */
3535
#define WORDS_PER_PAGE(n) ((n) / BITS_PER_BITMAPWORD + 1)
3636

37+
/* number of offsets we can store in the header of a BlocktableEntry */
38+
#define NUM_FULL_OFFSETS ((sizeof(bitmapword) - sizeof(uint16)) / sizeof(OffsetNumber))
39+
3740
/*
3841
* This is named similarly to PagetableEntry in tidbitmap.c
3942
* because the two have a similar function.
4043
*/
4144
typedef struct BlocktableEntry
4245
{
4346
uint16 nwords;
47+
48+
/*
49+
* We can store a small number of offsets here to avoid wasting space with
50+
* a sparse bitmap.
51+
*/
52+
OffsetNumber full_offsets[NUM_FULL_OFFSETS];
53+
4454
bitmapword words[FLEXIBLE_ARRAY_MEMBER];
4555
} BlocktableEntry;
4656
#define MaxBlocktableEntrySize \
@@ -331,33 +341,53 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
331341
for (int i = 1; i < num_offsets; i++)
332342
Assert(offsets[i] > offsets[i - 1]);
333343

334-
for (wordnum = 0, next_word_threshold = BITS_PER_BITMAPWORD;
335-
wordnum <= WORDNUM(offsets[num_offsets - 1]);
336-
wordnum++, next_word_threshold += BITS_PER_BITMAPWORD)
337-
{
338-
word = 0;
344+
memset(page, 0, offsetof(BlocktableEntry, words));
339345

340-
while (idx < num_offsets)
346+
if (num_offsets <= NUM_FULL_OFFSETS)
347+
{
348+
for (int i = 0; i < num_offsets; i++)
341349
{
342-
OffsetNumber off = offsets[idx];
350+
OffsetNumber off = offsets[i];
343351

344352
/* safety check to ensure we don't overrun bit array bounds */
345353
if (!OffsetNumberIsValid(off))
346354
elog(ERROR, "tuple offset out of range: %u", off);
347355

348-
if (off >= next_word_threshold)
349-
break;
350-
351-
word |= ((bitmapword) 1 << BITNUM(off));
352-
idx++;
356+
page->full_offsets[i] = off;
353357
}
354358

355-
/* write out offset bitmap for this wordnum */
356-
page->words[wordnum] = word;
359+
page->nwords = 0;
357360
}
361+
else
362+
{
363+
for (wordnum = 0, next_word_threshold = BITS_PER_BITMAPWORD;
364+
wordnum <= WORDNUM(offsets[num_offsets - 1]);
365+
wordnum++, next_word_threshold += BITS_PER_BITMAPWORD)
366+
{
367+
word = 0;
368+
369+
while (idx < num_offsets)
370+
{
371+
OffsetNumber off = offsets[idx];
372+
373+
/* safety check to ensure we don't overrun bit array bounds */
374+
if (!OffsetNumberIsValid(off))
375+
elog(ERROR, "tuple offset out of range: %u", off);
376+
377+
if (off >= next_word_threshold)
378+
break;
379+
380+
word |= ((bitmapword) 1 << BITNUM(off));
381+
idx++;
382+
}
383+
384+
/* write out offset bitmap for this wordnum */
385+
page->words[wordnum] = word;
386+
}
358387

359-
page->nwords = wordnum;
360-
Assert(page->nwords == WORDS_PER_PAGE(offsets[num_offsets - 1]));
388+
page->nwords = wordnum;
389+
Assert(page->nwords == WORDS_PER_PAGE(offsets[num_offsets - 1]));
390+
}
361391

362392
if (TidStoreIsShared(ts))
363393
shared_ts_set(ts->tree.shared, blkno, page);
@@ -384,14 +414,27 @@ TidStoreIsMember(TidStore *ts, ItemPointer tid)
384414
if (page == NULL)
385415
return false;
386416

387-
wordnum = WORDNUM(off);
388-
bitnum = BITNUM(off);
389-
390-
/* no bitmap for the off */
391-
if (wordnum >= page->nwords)
417+
if (page->nwords == 0)
418+
{
419+
/* we have offsets in the header */
420+
for (int i = 0; i < NUM_FULL_OFFSETS; i++)
421+
{
422+
if (page->full_offsets[i] == off)
423+
return true;
424+
}
392425
return false;
426+
}
427+
else
428+
{
429+
wordnum = WORDNUM(off);
430+
bitnum = BITNUM(off);
431+
432+
/* no bitmap for the off */
433+
if (wordnum >= page->nwords)
434+
return false;
393435

394-
return (page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0;
436+
return (page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0;
437+
}
395438
}
396439

397440
/*
@@ -511,25 +554,37 @@ tidstore_iter_extract_tids(TidStoreIter *iter, BlockNumber blkno,
511554
result->num_offsets = 0;
512555
result->blkno = blkno;
513556

514-
for (wordnum = 0; wordnum < page->nwords; wordnum++)
557+
if (page->nwords == 0)
515558
{
516-
bitmapword w = page->words[wordnum];
517-
int off = wordnum * BITS_PER_BITMAPWORD;
518-
519-
/* Make sure there is enough space to add offsets */
520-
if ((result->num_offsets + BITS_PER_BITMAPWORD) > result->max_offset)
559+
/* we have offsets in the header */
560+
for (int i = 0; i < NUM_FULL_OFFSETS; i++)
521561
{
522-
result->max_offset *= 2;
523-
result->offsets = repalloc(result->offsets,
524-
sizeof(OffsetNumber) * result->max_offset);
562+
if (page->full_offsets[i] != InvalidOffsetNumber)
563+
result->offsets[result->num_offsets++] = page->full_offsets[i];
525564
}
526-
527-
while (w != 0)
565+
}
566+
else
567+
{
568+
for (wordnum = 0; wordnum < page->nwords; wordnum++)
528569
{
529-
if (w & 1)
530-
result->offsets[result->num_offsets++] = (OffsetNumber) off;
531-
off++;
532-
w >>= 1;
570+
bitmapword w = page->words[wordnum];
571+
int off = wordnum * BITS_PER_BITMAPWORD;
572+
573+
/* Make sure there is enough space to add offsets */
574+
if ((result->num_offsets + BITS_PER_BITMAPWORD) > result->max_offset)
575+
{
576+
result->max_offset *= 2;
577+
result->offsets = repalloc(result->offsets,
578+
sizeof(OffsetNumber) * result->max_offset);
579+
}
580+
581+
while (w != 0)
582+
{
583+
if (w & 1)
584+
result->offsets[result->num_offsets++] = (OffsetNumber) off;
585+
off++;
586+
w >>= 1;
587+
}
533588
}
534589
}
535590
}

‎src/test/modules/test_tidstore/expected/test_tidstore.out

Copy file name to clipboardExpand all lines: src/test/modules/test_tidstore/expected/test_tidstore.out
+28Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,20 @@ SELECT do_set_block_offsets(blk, array_agg(off)::int2[])
3636
(VALUES (0), (1), (:maxblkno / 2), (:maxblkno - 1), (:maxblkno)) AS blocks(blk),
3737
(VALUES (1), (2), (:maxoffset / 2), (:maxoffset - 1), (:maxoffset)) AS offsets(off)
3838
GROUP BY blk;
39+
-- Test offsets embedded in the bitmap header.
40+
SELECT do_set_block_offsets(501, array[greatest((random() * :maxoffset)::int, 1)]::int2[]);
41+
do_set_block_offsets
42+
----------------------
43+
501
44+
(1 row)
45+
46+
SELECT do_set_block_offsets(502, array_agg(DISTINCT greatest((random() * :maxoffset)::int, 1))::int2[])
47+
FROM generate_series(1, 3);
48+
do_set_block_offsets
49+
----------------------
50+
502
51+
(1 row)
52+
3953
-- Add enough TIDs to cause the store to appear "full", compared
4054
-- to the allocated memory it started out with. This is easier
4155
-- with memory contexts in local memory.
@@ -73,6 +87,20 @@ SELECT test_create(true);
7387

7488
(1 row)
7589

90+
-- Test offsets embedded in the bitmap header.
91+
SELECT do_set_block_offsets(501, array[greatest((random() * :maxoffset)::int, 1)]::int2[]);
92+
do_set_block_offsets
93+
----------------------
94+
501
95+
(1 row)
96+
97+
SELECT do_set_block_offsets(502, array_agg(DISTINCT greatest((random() * :maxoffset)::int, 1))::int2[])
98+
FROM generate_series(1, 3);
99+
do_set_block_offsets
100+
----------------------
101+
502
102+
(1 row)
103+
76104
-- Random TIDs test. The offset numbers are randomized and must be
77105
-- unique and ordered.
78106
INSERT INTO hideblocks (blockno)

‎src/test/modules/test_tidstore/sql/test_tidstore.sql

Copy file name to clipboardExpand all lines: src/test/modules/test_tidstore/sql/test_tidstore.sql
+10Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,11 @@ SELECT do_set_block_offsets(blk, array_agg(off)::int2[])
2828
(VALUES (1), (2), (:maxoffset / 2), (:maxoffset - 1), (:maxoffset)) AS offsets(off)
2929
GROUP BY blk;
3030

31+
-- Test offsets embedded in the bitmap header.
32+
SELECT do_set_block_offsets(501, array[greatest((random() * :maxoffset)::int, 1)]::int2[]);
33+
SELECT do_set_block_offsets(502, array_agg(DISTINCT greatest((random() * :maxoffset)::int, 1))::int2[])
34+
FROM generate_series(1, 3);
35+
3136
-- Add enough TIDs to cause the store to appear "full", compared
3237
-- to the allocated memory it started out with. This is easier
3338
-- with memory contexts in local memory.
@@ -49,6 +54,11 @@ SELECT test_destroy();
4954
-- because unused static functions would raise warnings there.
5055
SELECT test_create(true);
5156

57+
-- Test offsets embedded in the bitmap header.
58+
SELECT do_set_block_offsets(501, array[greatest((random() * :maxoffset)::int, 1)]::int2[]);
59+
SELECT do_set_block_offsets(502, array_agg(DISTINCT greatest((random() * :maxoffset)::int, 1))::int2[])
60+
FROM generate_series(1, 3);
61+
5262
-- Random TIDs test. The offset numbers are randomized and must be
5363
-- unique and ordered.
5464
INSERT INTO hideblocks (blockno)

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.