MIME-Version: 1.0
From: Paul A Jungwirth <pj@illuminatedcomputing.com>
Date: Fri, 16 Jan 2026 12:57:38 -0800
Message-ID: 
 <CA+renyWs5Np+FLSYfL+eu20S4U671A3fQGb-+7e22HLrD1NbYw@mail.gmail.com>
Subject: Correct docs about GiST leaf page structure
To: pgsql-docs@lists.postgresql.org
Content-Type: multipart/mixed; boundary="000000000000163f5f0648879872"
Archived-At: 
 <https://www.postgresql.org/message-id/CA%2BrenyWs5Np%2BFLSYfL%2Beu20S4U671A3fQGb-%2B7e22HLrD1NbYw%40mail.gmail.com>
Precedence: bulk

--000000000000163f5f0648879872
Content-Type: text/plain; charset="UTF-8"

Our docs for GiST indexes say the compress function is only used for
internal pages, not leaf pages, but actually it is used everywhere.
Here are two patches to clean things up.

You can see that we store compressed values with the pageinspect
extension. For instance, multiranges are compressed to ranges. Here
they are in leaf pages:

[v19devel:5432][314069] postgres=# create table mr (id int4multirange);
CREATE TABLE
[v19devel:5432][314069] postgres=# create index idx_mr on mr using gist (id);
CREATE INDEX
[v19devel:5432][314069] postgres=# insert into mr values ('{[1,2)}'),
('{[2,3)}');
INSERT 0 2
[v19devel:5432][314069] postgres=# select * from
gist_page_opaque_info(get_raw_page('idx_mr', 0));
    lsn     |    nsn     | rightlink  | flags
------------+------------+------------+--------
 0/01917320 | 0/00000000 | 4294967295 | {leaf}
(1 row)

[v19devel:5432][314069] postgres=# select * from
gist_page_items(get_raw_page('idx_mr', 0), 'idx_mr');
 itemoffset | ctid  | itemlen | dead |      keys
------------+-------+---------+------+----------------
          1 | (0,1) |      24 | f    | (id)=("[1,2)")
          2 | (0,2) |      24 | f    | (id)=("[2,3)")

Similarly, btree_gist stores gbtreekey entries in leaf pages:

[v19devel:5432][314069] postgres=# create table i (id int);
CREATE TABLE
[v19devel:5432][314069] postgres=# create index idx_i on i using gist (id);
CREATE INDEX
[v19devel:5432][314069] postgres=# insert into i values (1), (2), (3);
INSERT 0 3
[v19devel:5432][314069] postgres=# select * from
gist_page_items(get_raw_page('idx_i', 0), 'idx_i');
ERROR:  cannot display a value of type gbtreekey?
[v19devel:5432][314069] postgres=# select * from
gist_page_items_bytea(get_raw_page('idx_i', 0));
 itemoffset | ctid  | itemlen | dead |              key_data
------------+-------+---------+------+------------------------------------
          1 | (0,1) |      16 | f    | \x00000000010010000100000001000000
          2 | (0,2) |      16 | f    | \x00000000020010000200000002000000
          3 | (0,3) |      16 | f    | \x00000000030010000300000003000000

I think this error goes back to the second GiST paper referenced in
access/gist/README, titled "Concurrency and Recovery in Generalized
Search Trees" (from 1997). On page 2 it says that internal pages store
the predicate and leaf pages store the key. (The original 1995 paper
doesn't differentiate like that though.) Since our README has a list
of ways that our implementation diverges from the research, I added a
note there as well.

I've also supplied a patch to clarify that there are two papers. The
old wording is a bit confusing:

> GiST stands for Generalized Search Tree. It was introduced in the seminal paper
> "Generalized Search Trees for Database Systems", 1995, Joseph M. Hellerstein,
> Jeffrey F. Naughton, Avi Pfeffer:
>
>     http://www.sai.msu.su/~megera/postgres/gist/papers/gist.ps
>     https://dsf.berkeley.edu/papers/sigmod97-gist.pdf

Clarifying the two papers helps me call out the leaf page difference
in the main patch.

Yours,

-- 
Paul              ~{:-)
pj@illuminatedcomputing.com

--000000000000163f5f0648879872
Content-Type: text/x-patch; charset="US-ASCII";
	name="v1-0002-Correct-GiST-documentation-about-compressed-value.patch"
Content-Disposition: attachment;
	filename="v1-0002-Correct-GiST-documentation-about-compressed-value.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mkhcruco1>
X-Attachment-Id: f_mkhcruco1

RnJvbSA0MmI4ZGYxZjY2OWZlZGM4MzI4NTI0MTczZjE3OTkzNzljODBiYWI0IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiAiUGF1bCBBLiBKdW5nd2lydGgiIDxwakBpbGx1bWluYXRlZGNv
bXB1dGluZy5jb20+CkRhdGU6IEZyaSwgMTYgSmFuIDIwMjYgMTI6MzE6MDYgLTA4MDAKU3ViamVj
dDogW1BBVENIIHYxIDIvMl0gQ29ycmVjdCBHaVNUIGRvY3VtZW50YXRpb24gYWJvdXQgY29tcHJl
c3NlZCB2YWx1ZXMgaW4KIGxlYWYgcGFnZXMKCk91ciBkb2NzIHN0YXRlZCB0aGF0IHRoZSBHaVNU
IGNvbXByZXNzIHN1cHBvcnQgZnVuY3Rpb24gaXMgb25seSB1c2VkIHRvIHN0b3JlCnZhbHVlcyBp
biBpbnRlcm5hbCBwYWdlcywgbm90IGxlYWYgcGFnZXMuIEJ1dCBhY3R1YWxseSB3ZSB1c2UgY29t
cHJlc3MgZm9yIGFsbApwYWdlcyAoaWYgc3VwcGxpZWQpLiBUaGlzIGVycm9yIG1heSBnbyBiYWNr
IHRvIHRoZSAxOTk3IHBhcGVyICJDb25jdXJyZW5jeSBhbmQKUmVjb3ZlcnkgaW4gR2VuZXJhbGl6
ZWQgU2VhcmNoIFRyZWVzIiwgd2hpY2ggc3RhdGVzIHRoYXQgaW50ZXJuYWwgcGFnZXMgc2hvdWxk
CmhvbGQgYSBwcmVkaWNhdGUgYW5kIGxlYWYgcGFnZXMgc2hvdWxkIGhvbGQgdGhlIGtleSBpdHNl
bGYgKHBhZ2UgMikuIEJ1dCB0aGUKb3JpZ2luYWwgcGFwZXIgZnJvbSAxOTk1IGhhcyB0aGUgcHJl
ZGljYXRlIGV2ZXJ5d2hlcmUuIEkgYWxzbyB1cGRhdGVkIHRoZSBSRUFETUUKdG8gY2FsbCBvdXQg
dGhpcyBkaWZmZXJlbmNlLgotLS0KIGRvYy9zcmMvc2dtbC9naXN0LnNnbWwgICAgICAgICB8IDUg
KystLS0KIHNyYy9iYWNrZW5kL2FjY2Vzcy9naXN0L1JFQURNRSB8IDMgKysrCiAyIGZpbGVzIGNo
YW5nZWQsIDUgaW5zZXJ0aW9ucygrKSwgMyBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9kb2Mv
c3JjL3NnbWwvZ2lzdC5zZ21sIGIvZG9jL3NyYy9zZ21sL2dpc3Quc2dtbAppbmRleCAxODcxZjc0
MjcyMS4uYzUyNzc1N2E3ZWYgMTAwNjQ0Ci0tLSBhL2RvYy9zcmMvc2dtbC9naXN0LnNnbWwKKysr
IGIvZG9jL3NyYy9zZ21sL2dpc3Quc2dtbApAQCAtMjczLDkgKzI3Myw4IEBAIENSRUFURSBJTkRF
WCBPTiBteV90YWJsZSBVU0lORyBHSVNUIChteV9pbmV0X2NvbHVtbiBpbmV0X29wcyk7CiAgICBp
bmRleCB3aWxsIGRlcGVuZCBvbiB0aGUgPGZ1bmN0aW9uPnBlbmFsdHk8L2Z1bmN0aW9uPiBhbmQg
PGZ1bmN0aW9uPnBpY2tzcGxpdDwvZnVuY3Rpb24+CiAgICBtZXRob2RzLgogICAgVHdvIG9wdGlv
bmFsIG1ldGhvZHMgYXJlIDxmdW5jdGlvbj5jb21wcmVzczwvZnVuY3Rpb24+IGFuZAotICAgPGZ1
bmN0aW9uPmRlY29tcHJlc3M8L2Z1bmN0aW9uPiwgd2hpY2ggYWxsb3cgYW4gaW5kZXggdG8gaGF2
ZSBpbnRlcm5hbCB0cmVlIGRhdGEgb2YKLSAgIGEgZGlmZmVyZW50IHR5cGUgdGhhbiB0aGUgZGF0
YSBpdCBpbmRleGVzLiBUaGUgbGVhdmVzIGFyZSB0byBiZSBvZiB0aGUKLSAgIGluZGV4ZWQgZGF0
YSB0eXBlLCB3aGlsZSB0aGUgb3RoZXIgdHJlZSBub2RlcyBjYW4gYmUgb2YgYW55IEMgc3RydWN0
IChidXQKKyAgIDxmdW5jdGlvbj5kZWNvbXByZXNzPC9mdW5jdGlvbj4sIHdoaWNoIGFsbG93IGFu
IGluZGV4IHRvIHN0b3JlIGtleXMgb2YKKyAgIGEgZGlmZmVyZW50IHR5cGUgdGhhbiB0aGUgZGF0
YSBpdCBpbmRleGVzLiBUaGUgaW5kZXggdHVwbGVzIGNhbiBiZSBvZiBhbnkgQyBzdHJ1Y3QgKGJ1
dAogICAgeW91IHN0aWxsIGhhdmUgdG8gZm9sbG93IDxwcm9kdWN0bmFtZT5Qb3N0Z3JlU1FMPC9w
cm9kdWN0bmFtZT4gZGF0YSB0eXBlIHJ1bGVzIGhlcmUsCiAgICBzZWUgYWJvdXQgPGxpdGVyYWw+
dmFybGVuYTwvbGl0ZXJhbD4gZm9yIHZhcmlhYmxlIHNpemVkIGRhdGEpLiBJZiB0aGUgdHJlZSdz
CiAgICBpbnRlcm5hbCBkYXRhIHR5cGUgZXhpc3RzIGF0IHRoZSBTUUwgbGV2ZWwsIHRoZSA8bGl0
ZXJhbD5TVE9SQUdFPC9saXRlcmFsPiBvcHRpb24KZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL2Fj
Y2Vzcy9naXN0L1JFQURNRSBiL3NyYy9iYWNrZW5kL2FjY2Vzcy9naXN0L1JFQURNRQppbmRleCA1
MmIxNDExOWZmNi4uYzhmYzc0OWRjZjIgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL2FjY2Vzcy9n
aXN0L1JFQURNRQorKysgYi9zcmMvYmFja2VuZC9hY2Nlc3MvZ2lzdC9SRUFETUUKQEAgLTU5LDYg
KzU5LDkgQEAgVGhlIG9yaWdpbmFsIGFsZ29yaXRobXMgd2VyZSBtb2RpZmllZCBpbiBzZXZlcmFs
IHdheXM6CiAgIGl0IGlzIG5vdyBhIHNpbmdsZS1wYXNzIGFsZ29yaXRobS4KICogU2luY2UgdGhl
IHBhcGVycyB3ZXJlIHRoZW9yZXRpY2FsLCBzb21lIGRldGFpbHMgd2VyZSBvbWl0dGVkIGFuZCB3
ZQogICBoYWQgdG8gZmluZCBvdXQgb3Vyc2VsZiBob3cgdG8gc29sdmUgc29tZSBzcGVjaWZpYyBw
cm9ibGVtcy4KKyogV2Ugc3RvcmUgdGhlIChwb3RlbnRpYWxseS1jb21wcmVzc2VkKSBwcmVkaWNh
dGUgYXQgYWxsIG5vZGUgbGV2ZWxzLiBUaGUKKyAgMTk5NyBwYXBlciBhYm92ZSAoYnV0IG5vdCB0
aGUgMTk5NSBvbmUpIHN0YXRlcyB0aGF0IGxlYWYgcGFnZXMgc2hvdWxkIHN0b3JlCisgIHRoZSBv
cmlnaW5hbCBrZXkuCiAKIEJlY2F1c2Ugb2YgdGhlIGFib3ZlIHJlYXNvbnMsIHdlIGhhdmUgcmV2
aXNlZCB0aGUgaW50ZXJhY3Rpb24gb2YgR2lTVAogY29yZSBhbmQgUG9zdGdyZVNRTCBXQUwgc3lz
dGVtLiBNb3Jlb3Zlciwgd2UgZW5jb3VudGVyZWQgKGFuZCBzb2x2ZWQpCi0tIAoyLjQ3LjMKCg==
--000000000000163f5f0648879872
Content-Type: text/x-patch; charset="US-ASCII";
	name="v1-0001-Clarify-GiST-README-references-to-the-original-re.patch"
Content-Disposition: attachment;
	filename="v1-0001-Clarify-GiST-README-references-to-the-original-re.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_mkhcruc90>
X-Attachment-Id: f_mkhcruc90

RnJvbSBhMGFiYWY1OTc4NzcxMzVlNzdkZTkyM2QxN2VlZDRiNDBmYWNlOGMzIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiAiUGF1bCBBLiBKdW5nd2lydGgiIDxwakBpbGx1bWluYXRlZGNv
bXB1dGluZy5jb20+CkRhdGU6IEZyaSwgMTYgSmFuIDIwMjYgMTI6Mzg6MTIgLTA4MDAKU3ViamVj
dDogW1BBVENIIHYxIDEvMl0gQ2xhcmlmeSBHaVNUIFJFQURNRSByZWZlcmVuY2VzIHRvIHRoZSBv
cmlnaW5hbAogcmVzZWFyY2ggcGFwZXJzCgpUaGUgUkVBRE1FIHRleHQgZ2l2ZXMgdGhlIG5hbWUg
b2YgdGhlIG9yaWdpbmFsIDE5OTUgcGFwZXIsIGZvbGxvd2VkIGJ5IHR3bwpidWxsZXQgcG9pbnRz
LCBvbmUgdG8gdGhlIDE5OTUgcGFwZXIgdGhlbiBhbm90aGVyIHRvIGEgMTk5NyBwYXBlci4gVGhp
cyBjb21taXQKYWRkcyB0aGUgMTk5NyBwYXBlciBkZXRhaWxzLgotLS0KIHNyYy9iYWNrZW5kL2Fj
Y2Vzcy9naXN0L1JFQURNRSB8IDYgKysrKystCiAxIGZpbGUgY2hhbmdlZCwgNSBpbnNlcnRpb25z
KCspLCAxIGRlbGV0aW9uKC0pCgpkaWZmIC0tZ2l0IGEvc3JjL2JhY2tlbmQvYWNjZXNzL2dpc3Qv
UkVBRE1FIGIvc3JjL2JhY2tlbmQvYWNjZXNzL2dpc3QvUkVBRE1FCmluZGV4IDc2ZTBlMTFmMjI4
Li41MmIxNDExOWZmNiAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvYWNjZXNzL2dpc3QvUkVBRE1F
CisrKyBiL3NyYy9iYWNrZW5kL2FjY2Vzcy9naXN0L1JFQURNRQpAQCAtMTAsOSArMTAsMTMgQEAg
R2lTVCBzdGFuZHMgZm9yIEdlbmVyYWxpemVkIFNlYXJjaCBUcmVlLiBJdCB3YXMgaW50cm9kdWNl
ZCBpbiB0aGUgc2VtaW5hbCBwYXBlcgogSmVmZnJleSBGLiBOYXVnaHRvbiwgQXZpIFBmZWZmZXI6
CiAKICAgICBodHRwOi8vd3d3LnNhaS5tc3Uuc3Uvfm1lZ2VyYS9wb3N0Z3Jlcy9naXN0L3BhcGVy
cy9naXN0LnBzCisKK0NvbmN1cnJlbmN5IHN1cHBvcnQgd2FzIGRlc2NyaWJlZCBpbiAiQ29uY3Vy
cmVuY3kgYW5kIFJlY292ZXJ5IGluIEdlbmVyYWxpemVkCitTZWFyY2ggVHJlZXMiLCAxOTk3LCBN
YXJjZWwgS29ybmFja2VyLCBDLiBNb2hhbiwgSm9zZXBoIE0uIEhlbGxlcnN0ZWluOgorCiAgICAg
aHR0cHM6Ly9kc2YuYmVya2VsZXkuZWR1L3BhcGVycy9zaWdtb2Q5Ny1naXN0LnBkZgogCi1hbmQg
aW1wbGVtZW50ZWQgYnkgSi4gSGVsbGVyc3RlaW4gYW5kIFAuIEFva2kgaW4gYW4gZWFybHkgdmVy
c2lvbiBvZgorR2lTVCB3YXMgaW1wbGVtZW50ZWQgYnkgSi4gSGVsbGVyc3RlaW4gYW5kIFAuIEFv
a2kgaW4gYW4gZWFybHkgdmVyc2lvbiBvZgogUG9zdGdyZVNRTCAobW9yZSBkZXRhaWxzIGFyZSBh
dmFpbGFibGUgZnJvbSBUaGUgR2lTVCBJbmRleGluZyBQcm9qZWN0CiBhdCBCZXJrZWxleSBhdCBo
dHRwOi8vZ2lzdC5jcy5iZXJrZWxleS5lZHUvKS4gQXMgYSAidW5pdmVyc2l0eSIKIHByb2plY3Qg
aXQgaGFkIGEgbGltaXRlZCBudW1iZXIgb2YgZmVhdHVyZXMgYW5kIHdhcyBpbiByYXJlIHVzZS4K
LS0gCjIuNDcuMwoK
--000000000000163f5f0648879872--