Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitf35bd9b

Browse files
committed
Teach TID store to skip bitmap for small numbers of offsets
The header portion of BlocktableEntry has enough padding space foran array of 3 offsets (1 on 32-bit platforms). Use this space insteadof having a sparse bitmap array. This will take up a constant amountof space no matter what the offsets are.Reviewed (in an earlier version) by Masahiko SawadaDiscussion:https://postgr.es/m/CANWCAZYw+_KAaUNruhJfE=h6WgtBKeDG32St8vBJBEY82bGVRQ@mail.gmail.comDiscussion:https://postgr.es/m/CAD21AoBci3Hujzijubomo1tdwH3XtQ9F89cTNQ4bsQijOmqnEw@mail.gmail.com
1 parentdd1f6b0 commitf35bd9b

File tree

3 files changed

+130
-37
lines changed

3 files changed

+130
-37
lines changed

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

Lines 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
#defineWORDS_PER_PAGE(n) ((n) / BITS_PER_BITMAPWORD + 1)
3636

37+
/* number of offsets we can store in the header of a BlocktableEntry */
38+
#defineNUM_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
typedefstructBlocktableEntry
4245
{
4346
uint16nwords;
47+
48+
/*
49+
* We can store a small number of offsets here to avoid wasting space with
50+
* a sparse bitmap.
51+
*/
52+
OffsetNumberfull_offsets[NUM_FULL_OFFSETS];
53+
4454
bitmapwordwords[FLEXIBLE_ARRAY_MEMBER];
4555
}BlocktableEntry;
4656
#defineMaxBlocktableEntrySize \
@@ -331,33 +341,53 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets,
331341
for (inti=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 (inti=0;i<num_offsets;i++)
341349
{
342-
OffsetNumberoff=offsets[idx];
350+
OffsetNumberoff=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+
OffsetNumberoff=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 (inti=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-
bitmapwordw=page->words[wordnum];
517-
intoff=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 (inti=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+
bitmapwordw=page->words[wordnum];
571+
intoff=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

Lines 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

Lines 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)
[8]ページ先頭
©2009-2025 Movatter.jp