Thread: pgsql: Compress GIN posting lists, for smaller index size.

pgsql: Compress GIN posting lists, for smaller index size.

From
Heikki Linnakangas
Date:
Compress GIN posting lists, for smaller index size.

GIN posting lists are now encoded using varbyte-encoding, which allows them
to fit in much smaller space than the straight ItemPointer array format used
before. The new encoding is used for both the lists stored in-line in entry
tree items, and in posting tree leaf pages.

To maintain backwards-compatibility and keep pg_upgrade working, the code
can still read old-style pages and tuples. Posting tree leaf pages in the
new format are flagged with GIN_COMPRESSED flag, to distinguish old and new
format pages. Likewise, entry tree tuples in the new format have a
GIN_ITUP_COMPRESSED flag set in a bit that was previously unused.

This patch bumps GIN_CURRENT_VERSION from 1 to 2. New indexes created with
version 9.4 will therefore have version number 2 in the metapage, while old
pg_upgraded indexes will have version 1. The code treats them the same, but
it might be come handy in the future, if we want to drop support for the
uncompressed format.

Alexander Korotkov and me. Reviewed by Tomas Vondra and Amit Langote.

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/36a35c550ac114caa423bcbe339d3515db0cd957

Modified Files
--------------
contrib/pgstattuple/expected/pgstattuple.out |    2 +-
src/backend/access/gin/README                |  123 ++-
src/backend/access/gin/ginbtree.c            |   73 +-
src/backend/access/gin/gindatapage.c         | 1450 ++++++++++++++++++++------
src/backend/access/gin/ginentrypage.c        |  134 ++-
src/backend/access/gin/ginfast.c             |    2 +-
src/backend/access/gin/ginget.c              |  117 ++-
src/backend/access/gin/gininsert.c           |   67 +-
src/backend/access/gin/ginpostinglist.c      |  386 ++++++-
src/backend/access/gin/ginvacuum.c           |  232 +++--
src/backend/access/gin/ginxlog.c             |  184 ++--
src/backend/access/rmgrdesc/gindesc.c        |   45 +-
src/include/access/gin_private.h             |  212 +++-
13 files changed, 2309 insertions(+), 718 deletions(-)


Re: pgsql: Compress GIN posting lists, for smaller index size.

From
Fujii Masao
Date:
On Thu, Jan 23, 2014 at 2:28 AM, Heikki Linnakangas
<heikki.linnakangas@iki.fi> wrote:
> Compress GIN posting lists, for smaller index size.
>
> GIN posting lists are now encoded using varbyte-encoding, which allows them
> to fit in much smaller space than the straight ItemPointer array format used
> before. The new encoding is used for both the lists stored in-line in entry
> tree items, and in posting tree leaf pages.
>
> To maintain backwards-compatibility and keep pg_upgrade working, the code
> can still read old-style pages and tuples. Posting tree leaf pages in the
> new format are flagged with GIN_COMPRESSED flag, to distinguish old and new
> format pages. Likewise, entry tree tuples in the new format have a
> GIN_ITUP_COMPRESSED flag set in a bit that was previously unused.
>
> This patch bumps GIN_CURRENT_VERSION from 1 to 2. New indexes created with
> version 9.4 will therefore have version number 2 in the metapage, while old
> pg_upgraded indexes will have version 1. The code treats them the same, but
> it might be come handy in the future, if we want to drop support for the
> uncompressed format.

I failed to compile HEAD because, ISTM, of this patch.

ginvacuum.c:34: error: redefinition of typedef 'GinVacuumState'
../../../../src/include/access/gin_private.h:715: error: previous
declaration of 'GinVacuumState' was here
make[4]: *** [ginvacuum.o] Error 1
make[3]: *** [gin-recursive] Error 2
make[2]: *** [access-recursive] Error 2
make[2]: *** Waiting for unfinished jobs....

$ uname -a
Darwin test.local 11.4.2 Darwin Kernel Version 11.4.2: Thu Aug 23
16:25:48 PDT 2012; root:xnu-1699.32.7~1/RELEASE_X86_64 x86_64

Regards,

--
Fujii Masao


Re: pgsql: Compress GIN posting lists, for smaller index size.

From
Heikki Linnakangas
Date:
On 01/22/2014 07:44 PM, Fujii Masao wrote:
> ginvacuum.c:34: error: redefinition of typedef 'GinVacuumState'
> ../../../../src/include/access/gin_private.h:715: error: previous
> declaration of 'GinVacuumState' was here
> make[4]: *** [ginvacuum.o] Error 1
> make[3]: *** [gin-recursive] Error 2
> make[2]: *** [access-recursive] Error 2
> make[2]: *** Waiting for unfinished jobs....

Hmm, my compiler (gcc 4.8) was happy with that, but that seems to be in
the minority. Fixed, thanks!

- Heikki


Re: pgsql: Compress GIN posting lists, for smaller index size.

From
Tom Lane
Date:
Fujii Masao <masao.fujii@gmail.com> writes:
> On Thu, Jan 23, 2014 at 2:28 AM, Heikki Linnakangas
> <heikki.linnakangas@iki.fi> wrote:
>> Compress GIN posting lists, for smaller index size.

> I failed to compile HEAD because, ISTM, of this patch.

It looks like some but not all buildfarm members are seeing the same
error.  Perhaps a platform- or build-option-specific issue?

            regards, tom lane


Re: pgsql: Compress GIN posting lists, for smaller index size.

From
Heikki Linnakangas
Date:
On 01/22/2014 07:58 PM, Tom Lane wrote:
> Fujii Masao <masao.fujii@gmail.com> writes:
>> On Thu, Jan 23, 2014 at 2:28 AM, Heikki Linnakangas
>> <heikki.linnakangas@iki.fi> wrote:
>>> Compress GIN posting lists, for smaller index size.
>
>> I failed to compile HEAD because, ISTM, of this patch.
>
> It looks like some but not all buildfarm members are seeing the same
> error.  Perhaps a platform- or build-option-specific issue?

clang says I was using a C11 feature:

ginvacuum.c:34:3: warning: redefinition of typedef 'GinVacuumState' is a C11
       feature [-Wtypedef-redefinition]
} GinVacuumState;
   ^
../../../../src/include/access/gin_private.h:715:31: note: previous
definition
       is here
typedef struct GinVacuumState GinVacuumState;
                               ^

Anyway, fixed now..

- Heikki


Re: pgsql: Compress GIN posting lists, for smaller index size.

From
Andres Freund
Date:
Hi,
On 2014-01-22 17:28:48 +0000, Heikki Linnakangas wrote:
> Compress GIN posting lists, for smaller index size.
>
> GIN posting lists are now encoded using varbyte-encoding, which allows them
> to fit in much smaller space than the straight ItemPointer array format used
> before. The new encoding is used for both the lists stored in-line in entry
> tree items, and in posting tree leaf pages.
>
> To maintain backwards-compatibility and keep pg_upgrade working, the code
> can still read old-style pages and tuples. Posting tree leaf pages in the
> new format are flagged with GIN_COMPRESSED flag, to distinguish old and new
> format pages. Likewise, entry tree tuples in the new format have a
> GIN_ITUP_COMPRESSED flag set in a bit that was previously unused.

A new version of clang complains:

/home/andres/src/postgresql/src/backend/access/gin/ginvacuum.c:512:34: warning: signed shift result (0x80000000) sets
thesign bit of the 
      shift expression's type ('int') and becomes negative [-Wshift-sign-overflow]
                                uncompressed = (ItemPointer) GinGetPosting(itup);
                                                             ^~~~~~~~~~~~~~~~~~~
/home/andres/src/postgresql/src/include/access/gin_private.h:226:59: note: expanded from macro 'GinGetPosting'
#define GinGetPosting(itup)                     ((Pointer) ((char*)(itup) + GinGetPostingOffset(itup)))
                                                                            ^~~~~~~~~~~~~~~~~~~~~~~~~
/home/andres/src/postgresql/src/include/access/gin_private.h:224:85: note: expanded from macro 'GinGetPostingOffset'
#define GinGetPostingOffset(itup)       (GinItemPointerGetBlockNumber(&(itup)->t_tid) & (~GIN_ITUP_COMPRESSED))
                                                                                          ^~~~~~~~~~~~~~~~~~~
/home/andres/src/postgresql/src/include/access/gin_private.h:223:33: note: expanded from macro 'GIN_ITUP_COMPRESSED'
#define GIN_ITUP_COMPRESSED             (1 << 31)

As far as I understand the code it should rather be
#define GIN_ITUP_COMPRESSED             (1U << 31)

Is that right?

Greetings,

Andres Freund

--
 Andres Freund                       http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services


Re: pgsql: Compress GIN posting lists, for smaller index size.

From
Heikki Linnakangas
Date:
On 09/02/2014 02:11 PM, Andres Freund wrote:
> Hi,
> On 2014-01-22 17:28:48 +0000, Heikki Linnakangas wrote:
>> Compress GIN posting lists, for smaller index size.
>>
>> GIN posting lists are now encoded using varbyte-encoding, which allows them
>> to fit in much smaller space than the straight ItemPointer array format used
>> before. The new encoding is used for both the lists stored in-line in entry
>> tree items, and in posting tree leaf pages.
>>
>> To maintain backwards-compatibility and keep pg_upgrade working, the code
>> can still read old-style pages and tuples. Posting tree leaf pages in the
>> new format are flagged with GIN_COMPRESSED flag, to distinguish old and new
>> format pages. Likewise, entry tree tuples in the new format have a
>> GIN_ITUP_COMPRESSED flag set in a bit that was previously unused.
>
> A new version of clang complains:
>
> /home/andres/src/postgresql/src/backend/access/gin/ginvacuum.c:512:34: warning: signed shift result (0x80000000) sets
thesign bit of the 
>        shift expression's type ('int') and becomes negative [-Wshift-sign-overflow]
>                                  uncompressed = (ItemPointer) GinGetPosting(itup);
>                                                               ^~~~~~~~~~~~~~~~~~~
> /home/andres/src/postgresql/src/include/access/gin_private.h:226:59: note: expanded from macro 'GinGetPosting'
> #define GinGetPosting(itup)                     ((Pointer) ((char*)(itup) + GinGetPostingOffset(itup)))
>                                                                              ^~~~~~~~~~~~~~~~~~~~~~~~~
> /home/andres/src/postgresql/src/include/access/gin_private.h:224:85: note: expanded from macro 'GinGetPostingOffset'
> #define GinGetPostingOffset(itup)       (GinItemPointerGetBlockNumber(&(itup)->t_tid) & (~GIN_ITUP_COMPRESSED))
>                                                                                            ^~~~~~~~~~~~~~~~~~~
> /home/andres/src/postgresql/src/include/access/gin_private.h:223:33: note: expanded from macro 'GIN_ITUP_COMPRESSED'
> #define GIN_ITUP_COMPRESSED             (1 << 31)
>
> As far as I understand the code it should rather be
> #define GIN_ITUP_COMPRESSED             (1U << 31)
>
> Is that right?

Yep. Fixed, thanks.

- Heikki