From: Anastasia Lubennikova <a.lubennikova@postgrespro.ru>
Subject: [PROPOSAL] Effective storage of duplicates in B-tree index.
To: pgsql-hackers@postgresql.org
Message-ID: <55E4051B.7020209@postgrespro.ru>
Date: Mon, 31 Aug 2015 10:41:15 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.2.0
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="------------080000000507050607080604"
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

This is a multi-part message in MIME format.
--------------080000000507050607080604
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit

Hi, hackers!
I'm going to begin work on effective storage of duplicate keys in B-tree 
index.
The main idea is to implement posting lists and posting trees for B-tree 
index pages as it's already done for GIN.

In a nutshell, effective storing of duplicates in GIN is organised as 
follows.
Index stores single index tuple for each unique key. That index tuple 
points to posting list which contains pointers to heap tuples (TIDs). If 
too many rows having the same key, multiple pages are allocated for the 
TIDs and these constitute so called posting tree.
You can find wonderful detailed descriptions in gin readme 
<https://github.com/postgres/postgres/blob/master/src/backend/access/gin/README> 
and articles <http://www.cybertec.at/gin-just-an-index-type/>.
It also makes possible to apply compression algorithm to posting 
list/tree and significantly decrease index size. Read more in 
presentation (part 1) 
<http://www.pgcon.org/2014/schedule/attachments/329_PGCon2014-GIN.pdf>.

Now new B-tree index tuple must be inserted for each table row that we 
index.
It can possibly cause page split. Because of MVCC even unique index 
could contain duplicates.
Storing duplicates in posting list/tree helps to avoid superfluous splits.

So it seems to be very useful improvement. Of course it requires a lot 
of changes in B-tree implementation, so I need approval from community.

1. Compatibility.
It's important to save compatibility with older index versions.
I'm going to change BTREE_VERSION to 3.
And use new (posting) features for v3, saving old implementation for v2.
Any objections?

2. There are several tricks to handle non-unique keys in B-tree.
More info in btree readme 
<https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README> 
(chapter - Differences to the Lehman & Yao algorithm).
In the new version they'll become useless. Am I right?

3. Microvacuum.
Killed items are marked LP_DEAD and could be deleted from separate page 
at time of insertion.
Now it's fine, because each item corresponds with separate TID. But 
posting list implementation requires another way. I've got two ideas:
First is to mark LP_DEAD only those tuples where all TIDs are not visible.
Second is to add LP_DEAD flag to each TID in posting list(tree). This 
way requires a bit more space, but allows to do microvacuum of posting 
list/tree.
Which one is better?

-- 
Anastasia Lubennikova
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company


--------------080000000507050607080604
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: 7bit

<html>
  <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    Hi, hackers!<br>
    I'm going to begin work on effective storage of duplicate keys in
    B-tree index.<br>
    The main idea is to implement posting lists and posting trees for
    B-tree index pages as it's already done for GIN.<br>
    <br>
    In a nutshell, effective storing of duplicates in GIN is organised
    as follows.<br>
    Index stores single index tuple for each unique key. That index
    tuple points to posting list which contains pointers to heap tuples
    (TIDs). If too many rows having the same key, multiple pages are
    allocated for the TIDs and these constitute so called posting tree.<br>
    You can find wonderful detailed descriptions in gin <a
href="https://github.com/postgres/postgres/blob/master/src/backend/access/gin/README">readme</a>
    and <a href="http://www.cybertec.at/gin-just-an-index-type/">articles</a>.<br>
    It also makes possible to apply compression algorithm to posting
    list/tree and significantly decrease index size. Read more in <a
href="http://www.pgcon.org/2014/schedule/attachments/329_PGCon2014-GIN.pdf">presentation


      (part 1)</a>.<br>
    <br>
    Now new B-tree index tuple must be inserted for each table row that
    we index. <br>
    It can possibly cause page split. Because of MVCC even unique index
    could contain duplicates.<br>
    Storing duplicates in posting list/tree helps to avoid superfluous
    splits.<br>
    <br>
    So it seems to be very useful improvement. Of course it requires a
    lot of changes in B-tree implementation, so I need approval from
    community.<br>
    <br>
    1. Compatibility.<br>
    It's important to save compatibility with older index versions.<br>
    I'm going to change BTREE_VERSION to 3.<br>
    And use new (posting) features for v3, saving old implementation for
    v2.<br>
    Any objections?<br>
    <br>
    2. There are several tricks to handle non-unique keys in B-tree.<br>
    More info in btree <a
href="https://github.com/postgres/postgres/blob/master/src/backend/access/nbtree/README">readme</a>
    (chapter - Differences to the Lehman &amp; Yao algorithm).<br>
    In the new version they'll become useless. Am I right?<br>
    <br>
    3. Microvacuum.<br>
    Killed items are marked LP_DEAD and could be deleted from separate
    page at time of insertion.<br>
    Now it's fine, because each item corresponds with separate TID. But
    posting list implementation requires another way. I've got two
    ideas:<br>
    First is to mark LP_DEAD only those tuples where all TIDs are not
    visible.<br>
    Second is to add LP_DEAD flag to each TID in posting list(tree).
    This way requires a bit more space, but allows to do microvacuum of
    posting list/tree.<br>
    Which one is better?<br>
    <pre class="moz-signature" cols="72">-- 
Anastasia Lubennikova
Postgres Professional: <a class="moz-txt-link-freetext" href="http://www.postgrespro.com">http://www.postgrespro.com</a>
The Russian Postgres Company</pre>
  </body>
</html>

--------------080000000507050607080604--