Subject: Re: [WIP] Effective storage of duplicates in B-tree index.
To: Anastasia Lubennikova <a.lubennikova@postgrespro.ru>,
 David Steele <david@pgmasters.net>, pgsql-hackers@postgresql.org
References: <55E4051B.7020209@postgrespro.ru>
 <56AA2081.1080001@postgrespro.ru>
 <CAA-aLv68Ptrnk2HpHSg9wYR0c+D2AyTB+XrS671brxqQz3dH3w@mail.gmail.com>
 <56AA3E06.8040006@postgrespro.ru>
 <CAA-aLv5aQezrfh2iJD97R1sQ6nqMsR2QZ_YAzNfAOkkMgO8CFQ@mail.gmail.com>
 <56AB6D30.2040900@postgrespro.ru> <20160129184733.2ca9026a@fujitsu>
 <CAA-aLv7pmO41G78jfLsftsCvkXZw6dL8HZoCX9ute6nQxJv2tw@mail.gmail.com>
 <56AB9866.6050207@postgrespro.ru>
 <CAM3SWZQ3_PLQCH4w7uQ8q_f2t4HEseKTr2n0rQ5pxA18OeRTJw@mail.gmail.com>
 <56C5FCE1.1090509@postgrespro.ru> <56C5FF80.5050905@postgrespro.ru>
 <56E6B64E.6000101@pgmasters.net> <56E84834.2070003@postgrespro.ru>
 <56EC38A9.9030303@postgrespro.ru>
From: Alexandr Popov <a.popov@postgrespro.ru>
Message-ID: <56F2B686.9070602@postgrespro.ru>
Date: Wed, 23 Mar 2016 18:30:14 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.6.0
MIME-Version: 1.0
In-Reply-To: <56EC38A9.9030303@postgrespro.ru>
Content-Type: multipart/alternative;
 boundary="------------040404030907000904050607"
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

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


On 18.03.2016 20:19, Anastasia Lubennikova wrote:
> Please, find the new version of the patch attached. Now it has WAL 
> functionality.
>
> Detailed description of the feature you can find in README draft 
> https://goo.gl/50O8Q0
>
> This patch is pretty complicated, so I ask everyone, who interested in 
> this feature,
> to help with reviewing and testing it. I will be grateful for any 
> feedback.
> But please, don't complain about code style, it is still work in 
> progress.
>
> Next things I'm going to do:
> 1. More debugging and testing. I'm going to attach in next message 
> couple of sql scripts for testing.
> 2. Fix NULLs processing
> 3. Add a flag into pg_index, that allows to enable/disable compression 
> for each particular index.
> 4. Recheck locking considerations. I tried to write code as less 
> invasive as possible, but we need to make sure that algorithm is still 
> correct.
> 5. Change BTMaxItemSize
> 6. Bring back microvacuum functionality.
>


Hi, hackers.

It's my first review, so do not be strict to me.

I have tested this patch on the next table:
create table message
     (
         id        serial,
         usr_id        integer,
         text        text
     );
CREATE INDEX message_usr_id ON message (usr_id);
The table has 10000000 records.

I found the following:
The less unique keys the less size of the table.

Next 2 tablas demonstrates it.
New B-tree
Count of unique keys (usr_id), index“s size , time of creation
10000000    ;"214 MB"    ;"00:00:34.193441"
3333333      ;"214 MB"    ;"00:00:45.731173"
2000000      ;"129 MB"    ;"00:00:41.445876"
1000000      ;"129 MB"    ;"00:00:38.455616"
100000        ;"86 MB"      ;"00:00:40.887626"
10000          ;"79 MB"      ;"00:00:47.199774"

Old B-tree
Count of unique keys (usr_id), index“s size , time of creation
10000000    ;"214 MB"    ;"00:00:35.043677"
3333333      ;"286 MB"    ;"00:00:40.922845"
2000000      ;"300 MB"    ;"00:00:46.454846"
1000000      ;"278 MB"    ;"00:00:42.323525"
100000        ;"287 MB"    ;"00:00:47.438132"
10000          ;"280 MB"    ;"00:01:00.307873"

I inserted data  randomly and sequentially, it did not influence the 
index's size.
Time of select, insert and update random rows is not changed. It is 
great, but certainly it needs some more detailed study.

Alexander Popov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company


--------------040404030907000904050607
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: 8bit

<html>
  <head>
    <meta content="text/html; charset=windows-1252"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <br>
    <br>
    <div class="moz-cite-prefix">On 18.03.2016 20:19, Anastasia
      Lubennikova wrote:<br>
    </div>
    <blockquote cite="mid:56EC38A9.9030303@postgrespro.ru" type="cite">Please,
      find the new version of the patch attached. Now it has WAL
      functionality.
      <br>
      <br>
      Detailed description of the feature you can find in README draft
      <a class="moz-txt-link-freetext" href="https://goo.gl/50O8Q0">https://goo.gl/50O8Q0</a>
      <br>
      <br>
      This patch is pretty complicated, so I ask everyone, who
      interested in this feature,
      <br>
      to help with reviewing and testing it. I will be grateful for any
      feedback.
      <br>
      But please, don't complain about code style, it is still work in
      progress.
      <br>
      <br>
      Next things I'm going to do:
      <br>
      1. More debugging and testing. I'm going to attach in next message
      couple of sql scripts for testing.
      <br>
      2. Fix NULLs processing
      <br>
      3. Add a flag into pg_index, that allows to enable/disable
      compression for each particular index.
      <br>
      4. Recheck locking considerations. I tried to write code as less
      invasive as possible, but we need to make sure that algorithm is
      still correct.
      <br>
      5. Change BTMaxItemSize
      <br>
      6. Bring back microvacuum functionality.
      <br>
      <br>
    </blockquote>
    <br>
    <meta http-equiv="content-type" content="text/html;
      charset=windows-1252">
    <title></title>
    <meta name="generator" content="LibreOffice 5.1.1.2 (Linux)">
    <style type="text/css">
		@page { margin: 0.79in }
		pre.cjk { font-family: "Nimbus Mono L", monospace }
		p { margin-bottom: 0.1in; line-height: 120% }
		a:link { so-language: zxx }
	</style><br>
    Hi, hackers.<br>
    <br>
    It's my first review, so do not be strict to me.<br>
    <br>
    I have tested this patch on the next table:<br>
    create table message<br>
        (<br>
            id        serial,<br>
            usr_id        integer,<br>
            text        text<br>
        );<br>
    CREATE INDEX message_usr_id ON message (usr_id);<br>
    The table has 10000000 records.<br>
    <br>
    I found the following:<br>
    The less unique keys the less size of the table.<br>
    <br>
    Next 2 tablas demonstrates it. <br>
    New B-tree <br>
    Count of unique keys (usr_id), index“s size , time of creation<br>
    10000000    ;"214 MB"    ;"00:00:34.193441"<br>
    3333333      ;"214 MB"    ;"00:00:45.731173"<br>
    2000000      ;"129 MB"    ;"00:00:41.445876"<br>
    1000000      ;"129 MB"    ;"00:00:38.455616"<br>
    100000        ;"86 MB"      ;"00:00:40.887626"<br>
    10000          ;"79 MB"      ;"00:00:47.199774"<br>
    <br>
    Old B-tree <br>
    Count of unique keys (usr_id), index“s size , time of creation<br>
    10000000    ;"214 MB"    ;"00:00:35.043677"<br>
    3333333      ;"286 MB"    ;"00:00:40.922845"<br>
    2000000      ;"300 MB"    ;"00:00:46.454846"<br>
    1000000      ;"278 MB"    ;"00:00:42.323525"<br>
    100000        ;"287 MB"    ;"00:00:47.438132"<br>
    10000          ;"280 MB"    ;"00:01:00.307873"<br>
    <br>
    I inserted data  randomly and sequentially, it did not influence the
    index's size.<br>
    Time of select, insert and update random rows is not changed. It is
    great, but certainly it needs some more detailed study.<br>
     <br>
    Alexander Popov<br>
    Postgres Professional: <a class="moz-txt-link-freetext" href="http://www.postgrespro.com">http://www.postgrespro.com</a> <br>
    The Russian Postgres Company <br>
    <br>
    <br>
  </body>
</html>

--------------040404030907000904050607--