MIME-Version: 1.0
From: Dilshod Urazov <urazofficial@gmail.com>
Date: Mon, 19 Feb 2024 08:50:18 +0300
Message-ID: <CAHc0=ph-7ma=1x-mOc7B1jHkoU_8+is-1zY_ejFz-t-OWiXJUQ@mail.gmail.com>
Subject: Proposal: Adjacent B-Tree index
To: pgsql-hackers@postgresql.org
Content-Type: multipart/alternative; boundary="000000000000dcac2b0611b5ab7d"
Archived-At: <https://www.postgresql.org/message-id/CAHc0%3Dph-7ma%3D1x-mOc7B1jHkoU_8%2Bis-1zY_ejFz-t-OWiXJUQ%40mail.gmail.com>
Precedence: bulk

--000000000000dcac2b0611b5ab7d
Content-Type: text/plain; charset="UTF-8"

- Motivation

A regular B-tree index provides efficient mapping of key values to tuples
within a table. However, if you have two tables connected in some way, a
regular B-tree index may not be efficient enough. In this case, you would
need to create an index for each table. The purpose will become clearer if
we consider a simple example which is the main use-case as I see it.

- Example

We need to store a graph. So we create a table for nodes

CREATE TABLE Nodes (
  id SERIAL PRIMARY KEY,
  label VARCHAR(255)
);

and a table for edges

CREATE TABLE Edges (
  label VARCHAR(255),
  source INTEGER REFERENCES Nodes(id),
  target INTEGER REFERENCES Nodes(id)
);

In order to efficiently traverse a graph we would have an index for
Nodes.id which created automatically in this case and an index for
Edges.source.

- Tweaked B-Tree

We could optimize cases like the former by modifying PostgreSQL btree index
to allow it to index 2 tables simultaneously.

Semantically it would be UNIQUE index for attribute x of table A and an
index for attribute y in table B. In the non-deduplicated case  index tuple
pointing to a tuple in A should be marked by a flag. In the deduplicated
case first TID in an array can be interpreted as a link to A.
During the vacuum of A an index tuple pointing to a dead tuple in A should
be cleaned as well as all index tuples for the same key. We can reach this
by clearing all index tuples after the dead one until we come to index
tuple marked by a flag with different key. Or we can enforce deduplication
in such index.

In the example with a graph such index would provide PRIMARY KEY for Nodes
and the index for Edges.Source. The query

SELECT * FROM Nodes WHERE id = X;

will use this index and take into account only a TID in Nodes (so this
would be marked index tuple or first TID in a posting list).  The query

SELECT * FROM Edges WHERE source = X;

conversely will ignore links to Nodes.

-- Syntax

I believe that
CREATE TABLE Nodes (
  id SERIAL PRIMARY KEY ADJACENT,
  label VARCHAR(255)
);
CREATE TABLE Edges (
  label VARCHAR(255),
  source INTEGER REFERENCES ADJACENT Nodes(id),
  target INTEGER REFERENCES Nodes(id)
);

would suffice for this new semantics.
--
Dilshod Urazov

--000000000000dcac2b0611b5ab7d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>- Motivation<br><br>A regular B-tree index provides e=
fficient mapping of key values to tuples within a table. However, if you ha=
ve two tables connected in some way, a regular B-tree index may not be effi=
cient enough. In this case, you would need to create an index for each tabl=
e. The=C2=A0purpose=C2=A0will=C2=A0become=C2=A0clearer=C2=A0if we consider=
=C2=A0a simple=C2=A0example which is the main use-case as I see it.</div><d=
iv><br>- Example</div><div><br>We need to store a graph. So we create a tab=
le for nodes</div><div><br>CREATE TABLE Nodes (<br>=C2=A0 id SERIAL PRIMARY=
 KEY,<br>=C2=A0 label VARCHAR(255)<br>);</div><div><br>and a table for edge=
s</div><div><br>CREATE TABLE Edges ( =C2=A0<br>=C2=A0 label VARCHAR(255),<b=
r>=C2=A0 source INTEGER REFERENCES Nodes(id),<br>=C2=A0 target INTEGER REFE=
RENCES Nodes(id)<br>);</div><div><br>In order to efficiently traverse a gra=
ph we would have an index for Nodes.id which created automatically in this =
case and an index for Edges.source.</div><div><br>- Tweaked B-Tree</div><di=
v><br>We could optimize cases like the former by modifying PostgreSQL btree=
 index to allow it to index 2 tables simultaneously.</div><div><br>Semantic=
ally it would be UNIQUE index for attribute x of table A and an index for a=
ttribute y in table B. In the non-deduplicated case =C2=A0index tuple point=
ing to a tuple in A should be marked by a flag. In the deduplicated case fi=
rst TID in an array can be interpreted as a link to A.<br>During the vacuum=
 of A an index tuple pointing to a dead tuple in A should be cleaned as wel=
l as all index tuples for the same key. We can reach this by clearing all i=
ndex tuples after the dead one until we come to index tuple marked by a fla=
g with different key. Or we can enforce deduplication in such index.</div><=
div><br>In the example with a graph such index would provide PRIMARY KEY fo=
r Nodes and the index for Edges.Source. The query</div><div><br>SELECT * FR=
OM Nodes WHERE id =3D X;</div><div><br>will use this index and take into ac=
count only a TID in Nodes (so this would be marked index tuple or first TID=
 in a posting list).=C2=A0 The query</div><div><br>SELECT * FROM Edges WHER=
E source =3D X;</div><div><br>conversely will ignore links to Nodes.</div><=
div><br>-- Syntax</div><div><br>I believe that<br>CREATE TABLE Nodes (<br>=
=C2=A0 id SERIAL PRIMARY KEY ADJACENT,<br>=C2=A0 label VARCHAR(255)<br>);<b=
r>CREATE TABLE Edges ( =C2=A0<br>=C2=A0 label VARCHAR(255),<br>=C2=A0 sourc=
e INTEGER REFERENCES ADJACENT Nodes(id),<br>=C2=A0 target INTEGER REFERENCE=
S Nodes(id)<br>);</div><div><br>would suffice for this new semantics.<font =
color=3D"#888888"><br></font></div><font color=3D"#888888"><span class=3D"g=
mail_signature_prefix">--</span><br><div dir=3D"ltr" class=3D"gmail_signatu=
re"><div dir=3D"ltr">Dilshod Urazov</div></div></font></div>

--000000000000dcac2b0611b5ab7d--