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

Commit6b7819a

Browse files
committed
Fix overflow check and comment in GIN posting list encoding.
The comment did not match what the code actually did for integers withthe 43rd bit set. You get an integer like that, if you have a postinglist with two adjacent TIDs that are more than 2^31 blocks apart.According to the comment, we would store that in 6 bytes, with nocontinuation bit on the 6th byte, but in reality, the code encodes itusing 7 bytes, with a continuation bit on the 6th byte as normal.The decoding routine also handled these 7-byte integers correctly, exceptfor an overflow check that assumed that one integer needs at most 6 bytes.Fix the overflow check, and fix the comment to match what the codeactually does. Also fix the comment that claimed that there are 17 unusedbits in the 64-bit representation of an item pointer. In reality, thereare 64-32-11=21.Fitting any item pointer into max 6 bytes was an important property whenthis was written, because in the old pre-9.4 format, item pointers werestored as plain arrays, with 6 bytes for every item pointer. The maximumof 6 bytes per integer in the new format guaranteed that we could convertany page from the old format to the new format after upgrade, so that thenew format was never larger than the old format. But we hardly need toworry about that anymore, and running into that problem during upgrade,where an item pointer is expanded from 6 to 7 bytes such that the datadoesn't fit on a page anymore, is implausible in practice anyway.Backpatch to all supported versions.This also includes a little test module to test these large distancesbetween item pointers, without requiring a 16 TB table. It is notbackpatched, I'm including it more for the benefit of future developmentof new posting list formats.Discussion:https://www.postgresql.org/message-id/33bfc20a-5c86-f50c-f5a5-58e9925d05ff%40iki.fiReviewed-by: Masahiko Sawada, Alexander Korotkov
1 parent8cc6016 commit6b7819a

File tree

1 file changed

+26
-9
lines changed

1 file changed

+26
-9
lines changed

‎src/backend/access/gin/ginpostinglist.c

Lines changed: 26 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -23,25 +23,32 @@
2323
/*
2424
* For encoding purposes, item pointers are represented as 64-bit unsigned
2525
* integers. The lowest 11 bits represent the offset number, and the next
26-
* lowest 32 bits are the block number. That leaves17 bits unused, i.e.
26+
* lowest 32 bits are the block number. That leaves21 bits unused, i.e.
2727
* only 43 low bits are used.
2828
*
29+
* 11 bits is enough for the offset number, because MaxHeapTuplesPerPage <
30+
* 2^11 on all supported block sizes. We are frugal with the bits, because
31+
* smaller integers use fewer bytes in the varbyte encoding, saving disk
32+
* space. (If we get a new table AM in the future that wants to use the full
33+
* range of possible offset numbers, we'll need to change this.)
34+
*
2935
* These 43-bit integers are encoded using varbyte encoding. In each byte,
3036
* the 7 low bits contain data, while the highest bit is a continuation bit.
3137
* When the continuation bit is set, the next byte is part of the same
32-
* integer, otherwise this is the last byte of this integer. 43 bits fit
33-
* conveniently in at most 6 bytes when varbyte encoded (the 6th byte does
34-
* not need a continuation bit, because we know the max size to be 43 bits):
38+
* integer, otherwise this is the last byte of this integer. 43 bits need
39+
* at most 7 bytes in this encoding:
3540
*
3641
* 0XXXXXXX
3742
* 1XXXXXXX 0XXXXYYY
3843
* 1XXXXXXX 1XXXXYYY 0YYYYYYY
3944
* 1XXXXXXX 1XXXXYYY 1YYYYYYY 0YYYYYYY
4045
* 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 0YYYYYYY
41-
* 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY YYYYYYYY
46+
* 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY 0YYYYYYY
47+
* 1XXXXXXX 1XXXXYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY 1YYYYYYY 0uuuuuuY
4248
*
4349
* X = bits used for offset number
4450
* Y = bits used for block number
51+
* u = unused bit
4552
*
4653
* The bytes are in stored in little-endian order.
4754
*
@@ -73,6 +80,9 @@
7380
*/
7481
#defineMaxHeapTuplesPerPageBits11
7582

83+
/* Max. number of bytes needed to encode the largest supported integer. */
84+
#defineMaxBytesPerInteger7
85+
7686
staticinlineuint64
7787
itemptr_to_uint64(constItemPointeriptr)
7888
{
@@ -126,33 +136,40 @@ decode_varbyte(unsigned char **ptr)
126136
unsignedchar*p=*ptr;
127137
uint64c;
128138

139+
/* 1st byte */
129140
c=*(p++);
130141
val=c&0x7F;
131142
if (c&0x80)
132143
{
144+
/* 2nd byte */
133145
c=*(p++);
134146
val |= (c&0x7F) <<7;
135147
if (c&0x80)
136148
{
149+
/* 3rd byte */
137150
c=*(p++);
138151
val |= (c&0x7F) <<14;
139152
if (c&0x80)
140153
{
154+
/* 4th byte */
141155
c=*(p++);
142156
val |= (c&0x7F) <<21;
143157
if (c&0x80)
144158
{
159+
/* 5th byte */
145160
c=*(p++);
146161
val |= (c&0x7F) <<28;
147162
if (c&0x80)
148163
{
164+
/* 6th byte */
149165
c=*(p++);
150166
val |= (c&0x7F) <<35;
151167
if (c&0x80)
152168
{
153-
/*last byte,no continuation bit */
169+
/*7th byte,should not have continuation bit */
154170
c=*(p++);
155171
val |=c <<42;
172+
Assert((c&0x80)==0);
156173
}
157174
}
158175
}
@@ -208,15 +225,15 @@ ginCompressPostingList(const ItemPointer ipd, int nipd, int maxsize,
208225

209226
Assert(val>prev);
210227

211-
if (endptr-ptr >=6)
228+
if (endptr-ptr >=MaxBytesPerInteger)
212229
encode_varbyte(delta,&ptr);
213230
else
214231
{
215232
/*
216-
* There are less than6 bytes left. Have to check if the next
233+
* There are less than7 bytes left. Have to check if the next
217234
* item fits in that space before writing it out.
218235
*/
219-
unsignedcharbuf[6];
236+
unsignedcharbuf[MaxBytesPerInteger];
220237
unsignedchar*p=buf;
221238

222239
encode_varbyte(delta,&p);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp