From: Tom Lane <tgl@sss.pgh.pa.us>
To: Paul A Jungwirth <pj@illuminatedcomputing.com>
cc: pgsql-docs@lists.postgresql.org
Subject: Re: Correct docs about GiST leaf page structure
In-reply-to: 
 <CA+renyXv6+tVi2yeQNXRwRkAm=wg89k=orjU8nMRKqWf1q6mtg@mail.gmail.com>
References: 
 <CA+renyWs5Np+FLSYfL+eu20S4U671A3fQGb-+7e22HLrD1NbYw@mail.gmail.com>
 <1855968.1774812758@sss.pgh.pa.us>
 <CA+renyXv6+tVi2yeQNXRwRkAm=wg89k=orjU8nMRKqWf1q6mtg@mail.gmail.com>
Comments: In-reply-to Paul A Jungwirth <pj@illuminatedcomputing.com>
	message dated "Sun, 29 Mar 2026 18:35:19 -0700"
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <2581630.1774908264.0@sss.pgh.pa.us>
Content-Transfer-Encoding: 8bit
Date: Mon, 30 Mar 2026 18:06:01 -0400
Message-ID: <2581763.1774908361@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/2581763.1774908361%40sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="UTF-8"
Content-ID: <2581630.1774908264.1@sss.pgh.pa.us>
Content-Transfer-Encoding: 8bit

Paul A Jungwirth <pj@illuminatedcomputing.com> writes:
> On Sun, Mar 29, 2026 at 12:32 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Actually I think it's more complicated than that.  A GiST opclass
>> can choose whether to compress leaf-key entries, and if it does it
>> can use a different representation than it does on internal pages.
>> You can see that in action in compress/decompress functions that
>> pay attention to the GISTENTRY.leafkey flag, which many do.

> I think your changes are great. I agree about not needing two commits.
> My only hesitation is removing the line about STORAGE. In btree_gist
> we do declare the storage of many opclasses. But I'm not sure why. Is
> it necessary? Does an opclass gain some advantage from it? Does core
> use that information somehow? Especially if leaf keys might or might
> not be the same type as internal keys, I'm not sure what value
> declaring STORAGE can provide. (It must be for core's sake, not the
> opclass's, right?)

Excellent questions, and thanks for holding my feet to the fire about
that ;-).  Reading more closely, the STORAGE option does indeed do
something: it determines the declared data type of the index's column,
as stored in pg_attribute.  And that's important because GiST uses
that datatype while forming or deforming index tuples.  So it has to
be accurate --- but only to the extent of having the right
typlen/typbyval/typalign properties, because that's as much as
index_form_tuple() and related functions really care about.  They
don't look into the contents of the entries, except for the length
word if it's typlen -1.

My claim that the leaf key representation can be different from upper
levels is still accurate, but both representations have to match the
typlen/typbyval/typalign properties of whatever type is mentioned
in STORAGE.  (I was misled by the fact that the GiST code has
different "leafTupdesc" and "nonLeafTupdesc" tuple descriptors.
But leafTupdesc is just the standard rd_att descriptor made from
the index's pg_attribute entries, and nonLeafTupdesc differs from
it only in having removed any INCLUDE attributes.)

So here's a v3 that accounts for that.  I also decided that we were
going in quite the wrong direction by cramming more info into the
summary paragraph early in gist.sgml.  The general plan there is to
offer about a one-sentence description of each opclass method, and
then go into more detail as necessary in the per-method text below.
So I moved all this info down into the compress method's section.
This seems to me to read noticeably better.

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff;
	name*0="v3-0001-Correct-GiST-documentation-about-compressed-value.p";
	name*1="atch"; charset="us-ascii"
Content-ID: <2581630.1774908264.2@sss.pgh.pa.us>
Content-Description: 
 v3-0001-Correct-GiST-documentation-about-compressed-value.patch
Content-Transfer-Encoding: quoted-printable

diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml
index 5c0a0c48bab..bedbc84d7b0 100644
--- a/doc/src/sgml/gist.sgml
+++ b/doc/src/sgml/gist.sgml
@@ -273,13 +273,9 @@ CREATE INDEX ON my_table USING GIST (my_inet_column i=
net_ops);
    index will depend on the <function>penalty</function> and <function>pi=
cksplit</function>
    methods.
    Two optional methods are <function>compress</function> and
-   <function>decompress</function>, which allow an index to have internal=
 tree data of
-   a different type than the data it indexes. The leaves are to be of the
-   indexed data type, while the other tree nodes can be of any C struct (=
but
-   you still have to follow <productname>PostgreSQL</productname> data ty=
pe rules here,
-   see about <literal>varlena</literal> for variable sized data). If the =
tree's
-   internal data type exists at the SQL level, the <literal>STORAGE</lite=
ral> option
-   of the <command>CREATE OPERATOR CLASS</command> command can be used.
+   <function>decompress</function>, which allow an index to store keys th=
at
+   are of a different type than the data it indexes, or are a compressed
+   representation of that type.
    The optional eighth method is <function>distance</function>, which is =
needed
    if the operator class wishes to support ordered scans (nearest-neighbo=
r
    searches). The optional ninth method <function>fetch</function> is nee=
ded if the
@@ -484,6 +480,24 @@ my_union(PG_FUNCTION_ARGS)
        in the index without modification.
       </para>
 =

+      <para>
+       Use the <literal>STORAGE</literal> option of the <command>CREATE
+       OPERATOR CLASS</command> command to define the data type that is
+       stored in the index, if it is different from the data type being
+       indexed.  Be aware however that the <literal>STORAGE</literal> dat=
a
+       type is only used to define the physical properties of the index
+       entries (their <replaceable>typlen</replaceable>,
+       <replaceable>typbyval</replaceable>,
+       and <replaceable>typalign</replaceable> attributes).  What is
+       actually in the index datums is under the control of the
+       <function>compress</function> and <function>decompress</function>
+       methods, so long as the stored datums fit those properties.  It is
+       allowed for <function>compress</function> to produce different
+       representations for leaf keys than for keys on higher-level index
+       pages, so long as both representations fit
+       the <literal>STORAGE</literal> data type.
+      </para>
+
       <para>
         The <acronym>SQL</acronym> declaration of the function must look =
like this:
 =

diff --git a/src/backend/access/gist/README b/src/backend/access/gist/READ=
ME
index 76e0e11f228..75445b07455 100644
--- a/src/backend/access/gist/README
+++ b/src/backend/access/gist/README
@@ -10,9 +10,13 @@ GiST stands for Generalized Search Tree. It was introdu=
ced in the seminal paper
 Jeffrey F. Naughton, Avi Pfeffer:
 =

     http://www.sai.msu.su/~megera/postgres/gist/papers/gist.ps
+
+Concurrency support was described in "Concurrency and Recovery in General=
ized
+Search Trees", 1997, Marcel Kornacker, C. Mohan, Joseph M. Hellerstein:
+
     https://dsf.berkeley.edu/papers/sigmod97-gist.pdf
 =

-and implemented by J. Hellerstein and P. Aoki in an early version of
+GiST was implemented by J. Hellerstein and P. Aoki in an early version of
 PostgreSQL (more details are available from The GiST Indexing Project
 at Berkeley at http://gist.cs.berkeley.edu/). As a "university"
 project it had a limited number of features and was in rare use.
@@ -55,6 +59,9 @@ The original algorithms were modified in several ways:
   it is now a single-pass algorithm.
 * Since the papers were theoretical, some details were omitted and we
   had to find out ourself how to solve some specific problems.
+* The 1997 paper above (but not the 1995 one) states that leaf pages shou=
ld
+  store the original key.  While that can be done in PostgreSQL, it is
+  also possible to use a compressed representation in leaf pages.
 =

 Because of the above reasons, we have revised the interaction of GiST
 core and PostgreSQL WAL system. Moreover, we encountered (and solved)

------- =_aaaaaaaaaa0--