Message-ID: <55E4723D.8060101@2ndquadrant.com>
Date: Mon, 31 Aug 2015 17:26:53 +0200
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: pgsql-hackers@postgresql.org
Subject: Re: [PROPOSAL] Effective storage of duplicates in B-tree
 index.
References: <55E4051B.7020209@postgrespro.ru>
In-Reply-To: <55E4051B.7020209@postgrespro.ru>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

Hi,

On 08/31/2015 09:41 AM, Anastasia Lubennikova wrote:
> 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.

In general, index size is often a serious issue - cases where indexes 
need more space than tables are not quite uncommon in my experience. So 
I think the efforts to lower space requirements for indexes are good.

But if we introduce posting lists into btree indexes, how different are 
they from GIN? It seems to me that if I create a GIN index (using 
btree_gin), I do get mostly the same thing you propose, no?

Sure, there are differences - GIN indexes don't handle UNIQUE indexes, 
but the compression can only be effective when there are duplicate rows. 
So either the index is not UNIQUE (so the b-tree feature is not needed), 
or there are many updates.

Which brings me to the other benefit of btree indexes - they are 
designed for high concurrency. How much is this going to be affected by 
introducing the posting lists?

kind regards

--
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers