Date: Mon, 15 Apr 2019 19:32:54 +0200
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Ashwin Agrawal <aagrawal@pivotal.io>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, Tom Lane <tgl@sss.pgh.pa.us>,
	Mark Kirkwood <mark.kirkwood@catalyst.net.nz>,
	PostgreSQL mailing lists <pgsql-hackers@postgresql.org>
Subject: Re: Zedstore - compressed in-core columnar storage
Message-ID: <20190415173254.nlnk2xqhgt7c5pta@development>
References: 
 <CALfoeiuF-m5jg51mJUPm5GN8u396o5sA2AF5N97vTRAEDYac7w@mail.gmail.com>
 <fc2d4f99-1ca6-854f-7025-ec3db94f6e04@catalyst.net.nz>
 <f301066e-08e1-a4b6-e058-0c1f24a1cc92@catalyst.net.nz>
 <6A2B85A8-1ABD-4F85-981E-C94172D662FD@pivotal.io>
 <11257.1554994460@sss.pgh.pa.us>
 <d4bfe7b0-0836-06b1-6b03-f5874b5a2b00@iki.fi>
 <20190414163947.owdw4gyjui36rakf@development>
 <CALfoeiuc_FFXO00qZgEVsahw4_R5OKNWbc4+VWMxUfWm=iSeMg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: 
 <CALfoeiuc_FFXO00qZgEVsahw4_R5OKNWbc4+VWMxUfWm=iSeMg@mail.gmail.com>
User-Agent: NeoMutt/20180716-1444-295967
Precedence: bulk

On Mon, Apr 15, 2019 at 09:29:37AM -0700, Ashwin Agrawal wrote:
>   On Sun, Apr 14, 2019 at 9:40 AM Tomas Vondra
>   <tomas.vondra@2ndquadrant.com> wrote:
>
>     On Thu, Apr 11, 2019 at 06:20:47PM +0300, Heikki Linnakangas wrote:
>     >On 11/04/2019 17:54, Tom Lane wrote:
>     >>Ashwin Agrawal <aagrawal@pivotal.io> writes:
>     >>>Thank you for trying it out. Yes, noticed for certain patterns
>     pg_lzcompress() actually requires much larger output buffers. Like for
>     one 86 len source it required 2296 len output buffer. Current zedstore
>     code doesn’t handle this case and errors out. LZ4 for same patterns
>     works fine, would highly recommend using LZ4 only, as anyways speed is
>     very fast as well with it.
>     >>
>     >>You realize of course that *every* compression method has some inputs
>     that
>     >>it makes bigger.  If your code assumes that compression always
>     produces a
>     >>smaller string, that's a bug in your code, not the compression
>     algorithm.
>     >
>     >Of course. The code is not making that assumption, although clearly
>     >there is a bug there somewhere because it throws that error. It's
>     >early days..
>     >
>     >In practice it's easy to weasel out of that, by storing the data
>     >uncompressed, if compression would make it longer. Then you need an
>     >extra flag somewhere to indicate whether it's compressed or not. It
>     >doesn't break the theoretical limit because the actual stored length
>     >is then original length + 1 bit, but it's usually not hard to find a
>     >place for one extra bit.
>     >
>
>     Don't we already have that flag, though? I see ZSCompressedBtreeItem has
>     t_flags, and there's ZSBT_COMPRESSED, but maybe it's more complicated.
>
>   The flag ZSBT_COMPRESSED differentiates between container (compressed)
>   item and plain (uncompressed item). Current code is writtten such that
>   within container (compressed) item, all the data is compressed. If need
>   exists to store some part of uncompressed data inside container item, then
>   this additional flag would be required to indicate the same. Hence its
>   different than ZSBT_COMPRESSED. I am thinking one of the ways could be to
>   just not store this datum in container item if can't be compressed and
>   just store it as plain item with uncompressed data, this additional flag
>   won't be required. Will know more once write code for this.

I see. Perhaps it'd be better to call the flag ZSBT_CONTAINER, when it
means "this is a container". And then have another flag to track whether
the container is compressed or not. But as I suggested elsewhere in this
thread, I think it might be better to store some ID of the compression
algorithm used instead of a simple flag.

FWIW when I had to deal with incremental compression (adding data into
already compressed buffers), which is what seems to be happening here, I
found it very useful/efficient to allow partially compressed buffers and
only trigger recompressin when absolutely needed.

Applied to this case, the container would first store compressed chunk,
followed by raw (uncompressed) data. Say, like this:

ZSContainerData {

    // header etc.

    int nbytes;         /* total bytes in data */
    int ncompressed;    /* ncompressed <= nbytes, fully compressed when
                         * (ncompressed == nbytes) */

    char data[FLEXIBLE_ARRAY_MEMBER];
}

When adding a value to the buffer, it'd be simply appended to the data
array. When the container would grow too much (can't fit on the page or
something), recompression is triggered.


cheers

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