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

Commit6292cde

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 parentfe50481 commit6292cde

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,ie.
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
{
@@ -130,33 +140,40 @@ decode_varbyte(unsigned char **ptr)
130140
unsignedchar*p=*ptr;
131141
uint64c;
132142

143+
/* 1st byte */
133144
c=*(p++);
134145
val=c&0x7F;
135146
if (c&0x80)
136147
{
148+
/* 2nd byte */
137149
c=*(p++);
138150
val |= (c&0x7F) <<7;
139151
if (c&0x80)
140152
{
153+
/* 3rd byte */
141154
c=*(p++);
142155
val |= (c&0x7F) <<14;
143156
if (c&0x80)
144157
{
158+
/* 4th byte */
145159
c=*(p++);
146160
val |= (c&0x7F) <<21;
147161
if (c&0x80)
148162
{
163+
/* 5th byte */
149164
c=*(p++);
150165
val |= (c&0x7F) <<28;
151166
if (c&0x80)
152167
{
168+
/* 6th byte */
153169
c=*(p++);
154170
val |= (c&0x7F) <<35;
155171
if (c&0x80)
156172
{
157-
/*last byte,no continuation bit */
173+
/*7th byte,should not have continuation bit */
158174
c=*(p++);
159175
val |=c <<42;
176+
Assert((c&0x80)==0);
160177
}
161178
}
162179
}
@@ -212,15 +229,15 @@ ginCompressPostingList(const ItemPointer ipd, int nipd, int maxsize,
212229

213230
Assert(val>prev);
214231

215-
if (endptr-ptr >=6)
232+
if (endptr-ptr >=MaxBytesPerInteger)
216233
encode_varbyte(delta,&ptr);
217234
else
218235
{
219236
/*
220-
* There are less than6 bytes left. Have to check if the next
237+
* There are less than7 bytes left. Have to check if the next
221238
* item fits in that space before writing it out.
222239
*/
223-
unsignedcharbuf[6];
240+
unsignedcharbuf[MaxBytesPerInteger];
224241
unsignedchar*p=buf;
225242

226243
encode_varbyte(delta,&p);

0 commit comments

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