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
