Compressed TOAST Slicing

classic Classic list List threaded Threaded
60 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Compressed TOAST Slicing

Paul Ramsey
Currently, PG_DETOAST_DATUM_SLICE when run on a compressed TOAST entry will first decompress the whole object, then extract the relevant slice. 

When the desired slice is at or near the front of the object, this is obviously non-optimal. 

The attached patch adds in a code path to do a partial decompression of the TOAST entry, when the requested slice is at the start of the object.

For an example of the improvement possible, this trivial example:

    create table slicingtest (
      id serial primary key,
      a text
    );

    insert into slicingtest (a) select repeat('xyz123', 10000) as a from generate_series(1,10000);
    \timing
    select sum(length(substr(a, 0, 20))) from slicingtest;

On master, in the current state on my wee laptop, I get

    Time: 1426.737 ms (00:01.427)

With the patch, on my wee laptop, I get

    Time: 46.886 ms

As usual, doing less work is faster.

Interesting note to motivate a follow-on patch: the substr() function does attempt to slice, but the left() function does not. So, if this patch is accepted, next patch will be to left() to add slicing behaviour.

If nobody lights me on fire, I'll submit to commitfest shortly.

P.

compressed-datum-slicing-20190101a.patch (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Stephen Frost
Greetings,

* Paul Ramsey ([hidden email]) wrote:
> The attached patch adds in a code path to do a partial decompression of the
> TOAST entry, when the requested slice is at the start of the object.

Neat!

> As usual, doing less work is faster.

Definitely.

> Interesting note to motivate a follow-on patch: the substr() function does
> attempt to slice, but the left() function does not. So, if this patch is
> accepted, next patch will be to left() to add slicing behaviour.

Makes sense to me.

There two things that I wonder about in the patch- if it would be of any
use to try and allocate on a need basis instead of just allocating the
whole chunk up to the toast size, and secondly, why we wouldn't consider
handling a non-zero offset.  A non-zero offset would, of course, still
require decompressing from the start and then just throwing away what we
skip over, but we're going to be doing that anyway, aren't we?  Why not
stop when we get to the end, at least, and save ourselves the trouble of
decompressing the rest and then throwing it away.

> If nobody lights me on fire, I'll submit to commitfest shortly.

Sounds like a good idea to me.

Thanks!

Stephen

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey


On Thu, Nov 1, 2018 at 2:29 PM Stephen Frost <[hidden email]> wrote:
Greetings,

* Paul Ramsey ([hidden email]) wrote:
> The attached patch adds in a code path to do a partial decompression of the
> TOAST entry, when the requested slice is at the start of the object.

There two things that I wonder about in the patch- if it would be of any
use to try and allocate on a need basis instead of just allocating the
whole chunk up to the toast size,

I'm not sure what I was thinking when I rejected allocating the slice size in favour of the whole uncompressed size... I cannot see why that wouldn't work.
 
and secondly, why we wouldn't consider
handling a non-zero offset.  A non-zero offset would, of course, still
require decompressing from the start and then just throwing away what we
skip over, but we're going to be doing that anyway, aren't we?  Why not
stop when we get to the end, at least, and save ourselves the trouble of
decompressing the rest and then throwing it away.

I was worried about changing the pg_lz code too much because it scared me, but debugging some stuff made me read it more closely so I fear it less now, and doing interior slices seems not unreasonable, so I will give it a try.
 
P

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Tom Lane-2
Paul Ramsey <[hidden email]> writes:
> On Thu, Nov 1, 2018 at 2:29 PM Stephen Frost <[hidden email]> wrote:
>> and secondly, why we wouldn't consider
>> handling a non-zero offset.  A non-zero offset would, of course, still
>> require decompressing from the start and then just throwing away what we
>> skip over, but we're going to be doing that anyway, aren't we?  Why not
>> stop when we get to the end, at least, and save ourselves the trouble of
>> decompressing the rest and then throwing it away.

> I was worried about changing the pg_lz code too much because it scared me,
> but debugging some stuff made me read it more closely so I fear it less
> now, and doing interior slices seems not unreasonable, so I will give it a
> try.

I think Stephen was just envisioning decompressing from offset 0 up to
the end of what's needed, and then discarding any data before the start
of what's needed; at least, that's what'd occurred to me.  It sounds like
you were thinking about hacking pg_lz to not write the leading data
anywhere.  While that'd likely be a win for cases where there was leading
data to discard, I'm worried about adding any cycles to the inner loops
of the decompressor.  We don't want to pessimize every other use of pg_lz
to buy a little bit for these cases.

                        regards, tom lane

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey


On Thu, Nov 1, 2018 at 4:02 PM Tom Lane <[hidden email]> wrote:
Paul Ramsey <[hidden email]> writes:
> On Thu, Nov 1, 2018 at 2:29 PM Stephen Frost <[hidden email]> wrote:
>> and secondly, why we wouldn't consider
>> handling a non-zero offset.  A non-zero offset would, of course, still
>> require decompressing from the start and then just throwing away what we
>> skip over, but we're going to be doing that anyway, aren't we?  Why not
>> stop when we get to the end, at least, and save ourselves the trouble of
>> decompressing the rest and then throwing it away.

> I was worried about changing the pg_lz code too much because it scared me,
> but debugging some stuff made me read it more closely so I fear it less
> now, and doing interior slices seems not unreasonable, so I will give it a
> try.

I think Stephen was just envisioning decompressing from offset 0 up to
the end of what's needed, and then discarding any data before the start
of what's needed; at least, that's what'd occurred to me. 

Understood, that makes lots of sense and is a very small change, it turns out :)
Allocating just what is needed also makes things faster yet, which is nice, and no big surprise.
Some light testing seems to show no obvious regression in speed of decompression for the usual "decompress it all" case.

P
 

compressed-datum-slicing-20190102a.patch (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey
As threatened, I have also added a patch to left() to also use sliced access.

compressed-datum-slicing-20190102a.patch (7K) Download Attachment
compressed-datum-slicing-left-20190102a.patch (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

rafia.sabih
On Fri, Nov 2, 2018 at 11:55 PM Paul Ramsey <[hidden email]> wrote:
>
> As threatened, I have also added a patch to left() to also use sliced access.

Hi Paul,

The idea looks good and believing your performance evaluation it seems
like a practical one too.

I had a look at this patch and here are my initial comments,
1.
- if (dp != destend || sp != srcend)
+ if (!is_slice && (dp != destend || sp != srcend))
  return -1;

A comment explaining how this check differs for is_slice case would be helpful.
2.
- int len = VARSIZE_ANY_EXHDR(str);
- int n = PG_GETARG_INT32(1);
- int rlen;
+ int n = PG_GETARG_INT32(1);

Looks like PG indentation is not followed here for n.

--
Regards,
Rafia Sabih
EnterpriseDB: http://www.enterprisedb.com/

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey
On Sun, Dec 2, 2018 at 7:03 AM Rafia Sabih <[hidden email]> wrote:
>
> The idea looks good and believing your performance evaluation it seems
> like a practical one too.

Thank you kindly for the review!

> A comment explaining how this check differs for is_slice case would be helpful.
> Looks like PG indentation is not followed here for n.

I have attached updated patches that add the comment and adhere to the Pg variable declaration indentation styles,
ATB!
P

--
Paul Ramsey


compressed-datum-slicing-left-20190103a.patch (1K) Download Attachment
compressed-datum-slicing-20190103a.patch (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Andres Freund
Hi Stephen,


On 2018-12-06 12:54:18 -0800, Paul Ramsey wrote:

> On Sun, Dec 2, 2018 at 7:03 AM Rafia Sabih <[hidden email]>
> wrote:
> >
> > The idea looks good and believing your performance evaluation it seems
> > like a practical one too.
>
> Thank you kindly for the review!
>
> > A comment explaining how this check differs for is_slice case would be
> helpful.
> > Looks like PG indentation is not followed here for n.
>
> I have attached updated patches that add the comment and adhere to the Pg
> variable declaration indentation styles,
> ATB!
> P

You were mentioning committing this at the Brussels meeting... :)

Greetings,

Andres Freund

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Simon Riggs
In reply to this post by Paul Ramsey
On Thu, 6 Dec 2018 at 20:54, Paul Ramsey <[hidden email]> wrote:
On Sun, Dec 2, 2018 at 7:03 AM Rafia Sabih <[hidden email]> wrote:
>
> The idea looks good and believing your performance evaluation it seems
> like a practical one too.

Thank you kindly for the review!

Sounds good.

Could we get an similarly optimized implementation of -> operator for JSONB as well?

Are there any other potential uses? Best to fix em all up at once and then move on to other things. Thanks.

--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey
On Sat, Feb 16, 2019 at 7:25 AM Simon Riggs <[hidden email]> wrote:

> Could we get an similarly optimized implementation of -> operator for JSONB as well?
> Are there any other potential uses? Best to fix em all up at once and then move on to other things. Thanks.

Oddly enough, I couldn't find many/any things that were sensitive to
left-end decompression. The only exception is "LIKE this%" which
clearly would be helped, but unfortunately wouldn't be a quick
drop-in, but a rather major reorganization of the regex handling.

I had a look at "->" and I couldn't see how a slice could be used to
make it faster? We don't a priori know how big a slice would give us
what we want. This again makes Stephen's case for an iterator, but of
course all the iterator benefits only come when the actual function at
the top (in this case the json parser) are also updated to be
iterative.

Committing this little change doesn't preclude an iterator, or even
make doing one more complicated... :)

P.

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Юрий Соколов
Some time ago I posted PoC patch with alternative TOAST compression scheme: instead of "compress-then-chunk" I suggested "chunk-then-compress". It decrease compression level, but allows efficient arbitrary slicing.

ср, 20 февр. 2019 г., 2:09 Paul Ramsey [hidden email]:
On Sat, Feb 16, 2019 at 7:25 AM Simon Riggs <[hidden email]> wrote:

> Could we get an similarly optimized implementation of -> operator for JSONB as well?
> Are there any other potential uses? Best to fix em all up at once and then move on to other things. Thanks.

Oddly enough, I couldn't find many/any things that were sensitive to
left-end decompression. The only exception is "LIKE this%" which
clearly would be helped, but unfortunately wouldn't be a quick
drop-in, but a rather major reorganization of the regex handling.

I had a look at "->" and I couldn't see how a slice could be used to
make it faster? We don't a priori know how big a slice would give us
what we want. This again makes Stephen's case for an iterator, but of
course all the iterator benefits only come when the actual function at
the top (in this case the json parser) are also updated to be
iterative.

Committing this little change doesn't preclude an iterator, or even
make doing one more complicated... :)

P.

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Simon Riggs
In reply to this post by Paul Ramsey
On Tue, 19 Feb 2019 at 23:09, Paul Ramsey <[hidden email]> wrote:
On Sat, Feb 16, 2019 at 7:25 AM Simon Riggs <[hidden email]> wrote:

> Could we get an similarly optimized implementation of -> operator for JSONB as well?
> Are there any other potential uses? Best to fix em all up at once and then move on to other things. Thanks.

Oddly enough, I couldn't find many/any things that were sensitive to
left-end decompression. The only exception is "LIKE this%" which
clearly would be helped, but unfortunately wouldn't be a quick
drop-in, but a rather major reorganization of the regex handling.

I had a look at "->" and I couldn't see how a slice could be used to
make it faster? We don't a priori know how big a slice would give us
what we want. This again makes Stephen's case for an iterator, but of
course all the iterator benefits only come when the actual function at
the top (in this case the json parser) are also updated to be
iterative.

Committing this little change doesn't preclude an iterator, or even
make doing one more complicated... :)

Sure, but we have the choice between something that benefits just a few cases or one that benefits more widely.

If we all only work on the narrow use cases that are right in front of us at the present moment then we would not have come this far. I'm sure many GIS applications also store JSONB data, so you would be helping the performance of the whole app, even if there isn't much JSON in PostGIS.

--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Andres Freund
On 2019-02-20 08:39:38 +0000, Simon Riggs wrote:

> On Tue, 19 Feb 2019 at 23:09, Paul Ramsey <[hidden email]> wrote:
>
> > On Sat, Feb 16, 2019 at 7:25 AM Simon Riggs <[hidden email]> wrote:
> >
> > > Could we get an similarly optimized implementation of -> operator for
> > JSONB as well?
> > > Are there any other potential uses? Best to fix em all up at once and
> > then move on to other things. Thanks.
> >
> > Oddly enough, I couldn't find many/any things that were sensitive to
> > left-end decompression. The only exception is "LIKE this%" which
> > clearly would be helped, but unfortunately wouldn't be a quick
> > drop-in, but a rather major reorganization of the regex handling.
> >
> > I had a look at "->" and I couldn't see how a slice could be used to
> > make it faster? We don't a priori know how big a slice would give us
> > what we want. This again makes Stephen's case for an iterator, but of
> > course all the iterator benefits only come when the actual function at
> > the top (in this case the json parser) are also updated to be
> > iterative.
> >
> > Committing this little change doesn't preclude an iterator, or even
> > make doing one more complicated... :)
> >
>
> Sure, but we have the choice between something that benefits just a few
> cases or one that benefits more widely.
>
> If we all only work on the narrow use cases that are right in front of us
> at the present moment then we would not have come this far. I'm sure many
> GIS applications also store JSONB data, so you would be helping the
> performance of the whole app, even if there isn't much JSON in PostGIS.

-1, I think this is blowing up the complexity of a already useful patch,
even though there's no increase in complexity due to the patch proposed
here.  I totally get wanting incremental decompression for jsonb, but I
don't see why Paul should be held hostage for that.

Greetings,

Andres Freund

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Robert Haas
On Wed, Feb 20, 2019 at 11:27 AM Andres Freund <[hidden email]> wrote:
> -1, I think this is blowing up the complexity of a already useful patch,
> even though there's no increase in complexity due to the patch proposed
> here.  I totally get wanting incremental decompression for jsonb, but I
> don't see why Paul should be held hostage for that.

I concur.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Simon Riggs
In reply to this post by Andres Freund
On Wed, 20 Feb 2019 at 16:27, Andres Freund <[hidden email]> wrote:

> Sure, but we have the choice between something that benefits just a few
> cases or one that benefits more widely.
>
> If we all only work on the narrow use cases that are right in front of us
> at the present moment then we would not have come this far. I'm sure many
> GIS applications also store JSONB data, so you would be helping the
> performance of the whole app, even if there isn't much JSON in PostGIS.

-1, I think this is blowing up the complexity of a already useful patch,
even though there's no increase in complexity due to the patch proposed
here.  I totally get wanting incremental decompression for jsonb, but I
don't see why Paul should be held hostage for that.

Not sure I agree with your emotive language. Review comments != holding hostages.

If we add one set of code now and need to add another different one later, we will have 2 sets of code that do similar things.

I'm surprised to hear you think that is a good thing.

--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey

On Feb 20, 2019, at 10:37 AM, Simon Riggs <[hidden email]> wrote:

-1, I think this is blowing up the complexity of a already useful patch,
even though there's no increase in complexity due to the patch proposed
here.  I totally get wanting incremental decompression for jsonb, but I
don't see why Paul should be held hostage for that.

Not sure I agree with your emotive language. Review comments != holding hostages.

If we add one set of code now and need to add another different one later, we will have 2 sets of code that do similar things.

So, current state is, asked for a datum slice, we can now decompress just the parts we need to get that slice. This allows us to speed up anything that knows in advance how big a slice they are going to want. At this moment all I’ve found is left() and substr() for the start-at-front case.

What this does not support: any function that probably wants less-than-everything, but doesn’t know how big a slice to look for. Stephen thinks I should put an iterator on decompression, which would be an interesting piece of work. Having looked at the json code a little doing partial searches would require a lot of re-work that is above my paygrade, but if there was an iterator in place, at least that next stop would then be open. 

Note that adding an iterator isn’t adding two ways to do the same thing, since the iterator would slot nicely underneath the existing slicing API, and just iterate to the requested slice size. So this is easily just “another step” along the train line to providing streaming access to compressed and TOASTed data.

I’d hate for the simple slice ability to get stuck behind the other work, since it’s both (a) useful and (b) exists. If you are concerned the iterator will never get done, I can only offer my word that, since it seems important to multiple people on this list, I will do it. (Just not, maybe, very well :)

P.
Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Daniel Verite
In reply to this post by Paul Ramsey
        Paul Ramsey wrote:

> Oddly enough, I couldn't find many/any things that were sensitive to
> left-end decompression. The only exception is "LIKE this%" which
> clearly would be helped, but unfortunately wouldn't be a quick
> drop-in, but a rather major reorganization of the regex handling.

What about starts_with(string, prefix)?

text_starts_with(arg1,arg2) in varlena.c does a full decompression
of  arg1 when it could limit itself to the length of the smaller arg2:

Datum
text_starts_with(PG_FUNCTION_ARGS)
....
  len1 = toast_raw_datum_size(arg1);
  len2 = toast_raw_datum_size(arg2);
  if (len2 > len1)
      result = false;
  else
  {
      text *targ1 = DatumGetTextPP(arg1);
      text *targ2 = DatumGetTextPP(arg2);

      result = (memcmp(VARDATA_ANY(targ1), VARDATA_ANY(targ2),
               VARSIZE_ANY_EXHDR(targ2)) == 0);
...



Best regards,
--
Daniel Vérité
PostgreSQL-powered mailer: http://www.manitou-mail.org
Twitter: @DanielVerite

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Robert Haas
In reply to this post by Paul Ramsey
On Wed, Feb 20, 2019 at 1:45 PM Paul Ramsey <[hidden email]> wrote:
> What this does not support: any function that probably wants less-than-everything, but doesn’t know how big a slice to look for. Stephen thinks I should put an iterator on decompression, which would be an interesting piece of work. Having looked at the json code a little doing partial searches would require a lot of re-work that is above my paygrade, but if there was an iterator in place, at least that next stop would then be open.
>
> Note that adding an iterator isn’t adding two ways to do the same thing, since the iterator would slot nicely underneath the existing slicing API, and just iterate to the requested slice size. So this is easily just “another step” along the train line to providing streaming access to compressed and TOASTed data.

Yeah.  Plus, I'm not sure the iterator thing is even the right design
for the JSONB case.  It might be better to think, for that case, about
whether there's someway to operate directly on the compressed data.
If you could somehow jigger the format and the chunking so that you
could jump directly to the right chunk and decompress from there,
rather than having to walk over all of the earlier chunks to figure
out where the data you want is, you could probably obtain a large
performance benefit.  But figuring out how to design such a scheme
seems pretty far afield from the topic at hand.

I'd actually be inclined not to add an iterator until we have a real
user for it, for exactly the reason that we don't know that it is the
right thing.  But there is certain value in decompressing partially,
to a known byte position, as your patch does, no matter what we decide
to do about that stuff.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Reply | Threaded
Open this post in threaded view
|

Re: Compressed TOAST Slicing

Paul Ramsey
In reply to this post by Daniel Verite
On Wed, Feb 20, 2019 at 10:50 AM Daniel Verite <[hidden email]> wrote:

>
>         Paul Ramsey wrote:
>
> > Oddly enough, I couldn't find many/any things that were sensitive to
> > left-end decompression. The only exception is "LIKE this%" which
> > clearly would be helped, but unfortunately wouldn't be a quick
> > drop-in, but a rather major reorganization of the regex handling.
>
> What about starts_with(string, prefix)?
>
> text_starts_with(arg1,arg2) in varlena.c does a full decompression
> of  arg1 when it could limit itself to the length of the smaller arg2:

Nice catch, I didn't find that one as it's not user visible, seems to
be only called in spgist (!!)
./backend/access/spgist/spgtextproc.c:
DatumGetBool(DirectFunctionCall2(text_starts_with

Thanks, I'll add that.

P

123