Thread: drop/truncate table sucks for large values of shared buffers

Amit Kapila <amit.kapila16@gmail.com> writes:
> I have looked into it and found that the main reason for such
> a behaviour is that for those operations it traverses whole
> shared_buffers and it seems to me that we don't need that
> especially for not-so-big tables.  We can optimize that path
> by looking into buff mapping table for the pages that exist in
> shared_buffers for the case when table size is less than some
> threshold (say 25%) of shared buffers.

I don't like this too much because it will fail badly if the caller
is wrong about the maximum possible page number for the table, which
seems not exactly far-fetched.  (For instance, remember those kernel bugs
we've seen that cause lseek to lie about the EOF position?)  It also
offers no hope of a fix for the other operations that scan the whole
buffer pool, such as DROP TABLESPACE and DROP DATABASE.

In the past we've speculated about fixing the performance of these things
by complicating the buffer lookup mechanism enough so that it could do
"find any page for this table/tablespace/database" efficiently.
Nobody's had ideas that seemed sane performance-wise though.
        regards, tom lane

On 2015-06-27 10:10:04 -0400, Tom Lane wrote:
> In the past we've speculated about fixing the performance of these things
> by complicating the buffer lookup mechanism enough so that it could do
> "find any page for this table/tablespace/database" efficiently.
> Nobody's had ideas that seemed sane performance-wise though.

I've started to play around with doing that a year or three back. My
approach was to use a linux style radix tree for the buffer mapping
table.  Besides lack of time what made it hard to be efficient was the
size of our buffer tags requiring rather deep trees.

I think I was considering playing around with a two-level tree (so we
could cache a pointer in Relation or such), but the memory management
requirements for that made my head hurt too much. The other alternative
is to work on having a much simpler buffer tag

If you have a buffer mapping that allows orderly traversal it becomes a)
much easier to do efficient readahead, as it's possible to read uncached
areas b) allows to write combine neighbouring pages when writing out
from a backend.

On Sat, Jun 27, 2015 at 11:38 AM, Andres Freund <andres@anarazel.de> wrote:
> On 2015-06-27 10:10:04 -0400, Tom Lane wrote:
>> In the past we've speculated about fixing the performance of these things
>> by complicating the buffer lookup mechanism enough so that it could do
>> "find any page for this table/tablespace/database" efficiently.
>> Nobody's had ideas that seemed sane performance-wise though.
>
> I've started to play around with doing that a year or three back. My
> approach was to use a linux style radix tree for the buffer mapping
> table.  Besides lack of time what made it hard to be efficient was the
> size of our buffer tags requiring rather deep trees.
>
> I think I was considering playing around with a two-level tree (so we
> could cache a pointer in Relation or such), but the memory management
> requirements for that made my head hurt too much. The other alternative
> is to work on having a much simpler buffer tag

Wouldn't even a two-level tree have the same problem you complained
about vis-a-vis chash?  In that case, you were of the opinion that
even ONE extra level of indirection was enough to pinch.  (I'm still
hoping there is a way to fix that, but even so.)

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

On 06/27/2015 10:10 AM, Tom Lane wrote:
> It also
> offers no hope of a fix for the other operations that scan the whole
> buffer pool, such as DROP TABLESPACE and DROP DATABASE.
>

Improving DROP TABLE / TRUNCATE would still be a significant advance. 
These cases cause far more real world pain than the ones you mention, in 
my experience.

cheers

andrew

On 2015-06-28 09:11:29 -0400, Robert Haas wrote:
> On Sat, Jun 27, 2015 at 11:38 AM, Andres Freund <andres@anarazel.de> wrote:
> > I've started to play around with doing that a year or three back. My
> > approach was to use a linux style radix tree for the buffer mapping
> > table.  Besides lack of time what made it hard to be efficient was the
> > size of our buffer tags requiring rather deep trees.
> >
> > I think I was considering playing around with a two-level tree (so we
> > could cache a pointer in Relation or such), but the memory management
> > requirements for that made my head hurt too much. The other alternative
> > is to work on having a much simpler buffer tag
> 
> Wouldn't even a two-level tree have the same problem you complained
> about vis-a-vis chash?

I was hoping to avoid the upper tree (mapping relfilenodes to the block
tree) in the majority of the cases by caching that mapping in struct
Relation or so.

But generally, yes, a tree will have more indirections. But they're
often of a different quality than with a hash table. There's a high
amount of spatial locality when looking up blocks: You're much more
likely to lookup a block close to one recently looked up than just a
randomly different one. Hashtables don't have a way to benefit from that
- tree structures sometimes do.

I don't think using a radix tree in itself will have significant
performance benefits over the hash table. But it allows for a bunch of
cool further optimizations like the aforementioned 'intelligent'
readahead, combining writes when flushing buffers, and - which made me
look into it originally - tagging inner nodes in the tree with
information about dirtyness to avoid scanning large amounts of nondirty
buffers.

> In that case, you were of the opinion that even ONE extra level of
> indirection was enough to pinch.  (I'm still hoping there is a way to
> fix that, but even so.)

Me too.


Andres

Amit Kapila <amit.kapila16@gmail.com> writes:
> On Sat, Jun 27, 2015 at 7:40 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I don't like this too much because it will fail badly if the caller
>> is wrong about the maximum possible page number for the table, which
>> seems not exactly far-fetched.  (For instance, remember those kernel bugs
>> we've seen that cause lseek to lie about the EOF position?)

> Considering we already have exclusive lock while doing this operation
> and nobody else can perform write on this file, won't closing and
> opening it again would avoid such problems.

On what grounds do you base that touching faith?  Quite aside from
outright bugs, having lock on a table has nothing to do with whether
low-level processes such as the checkpointer can touch it.
        regards, tom lane

Simon Riggs <simon@2ndQuadrant.com> writes:
> On 27 June 2015 at 15:10, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I don't like this too much because it will fail badly if the caller
>> is wrong about the maximum possible page number for the table, which
>> seems not exactly far-fetched.  (For instance, remember those kernel bugs
>> we've seen that cause lseek to lie about the EOF position?)

> If that is true, then our reliance on lseek elsewhere could also cause data
> loss, for example by failing to scan data during a seq scan.

The lseek point was a for-example, not the entire universe of possible
problem sources for this patch.  (Also, underestimating the EOF point in
a seqscan is normally not an issue since any rows in a just-added page
are by definition not visible to the scan's snapshot.  But I digress.)

> The consequences of failure of lseek in this case are nowhere near as dire,
> since by definition the data is being destroyed by the user.

I'm not sure what you consider "dire", but missing a dirty buffer
belonging to the to-be-destroyed table would result in the system being
permanently unable to checkpoint, because attempts to write out the buffer
to the no-longer-extant file would fail.  You could only get out of the
situation via a forced database crash (immediate shutdown), followed by
replaying all the WAL since the time of the problem.  In production
contexts that could be pretty dire.
        regards, tom lane

On Sun, Jun 28, 2015 at 12:17 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I'm not sure what you consider "dire", but missing a dirty buffer
> belonging to the to-be-destroyed table would result in the system being
> permanently unable to checkpoint, because attempts to write out the buffer
> to the no-longer-extant file would fail.  You could only get out of the
> situation via a forced database crash (immediate shutdown), followed by
> replaying all the WAL since the time of the problem.  In production
> contexts that could be pretty dire.

Hmm, that is kind of ugly.  Is the write actually going to fail,
though, or is it just going to create a sparse file?

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

On 06/27/2015 07:45 AM, Amit Kapila wrote:
> Sometime back on one of the PostgreSQL blog [1], there was
> discussion about the performance of drop/truncate table for
> large values of shared_buffers and it seems that as the value
> of shared_buffers increase the performance of drop/truncate
> table becomes worse.  I think those are not often used operations,
> so it never became priority to look into improving them if possible.
>
> I have looked into it and found that the main reason for such
> a behaviour is that for those operations it traverses whole
> shared_buffers and it seems to me that we don't need that
> especially for not-so-big tables.  We can optimize that path
> by looking into buff mapping table for the pages that exist in
> shared_buffers for the case when table size is less than some
> threshold (say 25%) of shared buffers.
>
> Attached patch implements the above idea and I found that
> performance doesn't dip much with patch even with large value
> of shared_buffers.  I have also attached script and sql file used
> to take performance data.

I'm marking this as "returned with feedback" in the commitfest. In 
addition to the issues raised so far, ISTM that the patch makes dropping 
a very large table with small shared_buffers slower 
(DropForkSpecificBuffers() is O(n) where n is the size of the relation, 
while the current method is O(shared_buffers))

I concur that we should explore using a radix tree or something else 
that would naturally allow you to find all buffers for relation/database 
X quickly.

- Heikki

On 2015-07-02 16:08:03 +0300, Heikki Linnakangas wrote:
> I'm marking this as "returned with feedback" in the commitfest. In addition
> to the issues raised so far, ISTM that the patch makes dropping a very large
> table with small shared_buffers slower (DropForkSpecificBuffers() is O(n)
> where n is the size of the relation, while the current method is
> O(shared_buffers))

I think upthread there was talk about only using the O(relsize) approach
if relsize << NBuffers. That's actually a pretty common scenario,
especially in testsuites.

> I concur that we should explore using a radix tree or something else that
> would naturally allow you to find all buffers for relation/database X
> quickly.

I unsurprisingly think that's the right way to go. But I'm not sure if
it's not worth to add another layer of bandaid till were there...

Greetings,

Andres Freund

On 07/02/2015 04:18 PM, Amit Kapila wrote:
> On Thu, Jul 2, 2015 at 6:38 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>>
>> On 06/27/2015 07:45 AM, Amit Kapila wrote:
>>>
>>> Sometime back on one of the PostgreSQL blog [1], there was
>>> discussion about the performance of drop/truncate table for
>>> large values of shared_buffers and it seems that as the value
>>> of shared_buffers increase the performance of drop/truncate
>>> table becomes worse.  I think those are not often used operations,
>>> so it never became priority to look into improving them if possible.
>>>
>>> I have looked into it and found that the main reason for such
>>> a behaviour is that for those operations it traverses whole
>>> shared_buffers and it seems to me that we don't need that
>>> especially for not-so-big tables.  We can optimize that path
>>> by looking into buff mapping table for the pages that exist in
>>> shared_buffers for the case when table size is less than some
>>> threshold (say 25%) of shared buffers.
>>>
>>> Attached patch implements the above idea and I found that
>>> performance doesn't dip much with patch even with large value
>>> of shared_buffers.  I have also attached script and sql file used
>>> to take performance data.
>>
>> I'm marking this as "returned with feedback" in the commitfest. In
> addition to the issues raised so far,
>
> Don't you think the approach discussed (delayed cleanup of buffers
> during checkpoint scan) is sufficient to fix the issues raised.

Dunno, but there is no patch for that.

- Heikki

On 07/02/2015 04:33 PM, Simon Riggs wrote:
> On 2 July 2015 at 14:08, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>
>> On 06/27/2015 07:45 AM, Amit Kapila wrote:
>>
>>> Sometime back on one of the PostgreSQL blog [1], there was
>>> discussion about the performance of drop/truncate table for
>>> large values of shared_buffers and it seems that as the value
>>> of shared_buffers increase the performance of drop/truncate
>>> table becomes worse.  I think those are not often used operations,
>>> so it never became priority to look into improving them if possible.
>>>
>>> I have looked into it and found that the main reason for such
>>> a behaviour is that for those operations it traverses whole
>>> shared_buffers and it seems to me that we don't need that
>>> especially for not-so-big tables.  We can optimize that path
>>> by looking into buff mapping table for the pages that exist in
>>> shared_buffers for the case when table size is less than some
>>> threshold (say 25%) of shared buffers.
>>>
>>> Attached patch implements the above idea and I found that
>>> performance doesn't dip much with patch even with large value
>>> of shared_buffers.  I have also attached script and sql file used
>>> to take performance data.
>>>
>>
>> I'm marking this as "returned with feedback" in the commitfest. In
>> addition to the issues raised so far, ISTM that the patch makes dropping a
>> very large table with small shared_buffers slower
>> (DropForkSpecificBuffers() is O(n) where n is the size of the relation,
>> while the current method is O(shared_buffers))
>
> There are no unresolved issues with the approach, nor is it true it is
> slower. If you think there are some, you should say what they are, not act
> high handedly to reject a patch without reason.

Oh, I missed the NBuffers / 4 threshold.

(The total_blocks calculation is prone to overflowing, btw, if you have 
a table close to 32 TB in size. But that's trivial to fix)

>> I concur that we should explore using a radix tree or something else that
>> would naturally allow you to find all buffers for relation/database X
>> quickly.
>
> I doubt that it can be managed efficiently while retaining optimal memory
> management. If it can its going to be very low priority (or should be).
>
> This approach works, so lets do it, now. If someone comes up with a better
> way later, great.

*shrug*. I don't think this is ready to be committed. I can't stop you 
from working on this, but as far as this commitfest is concerned, case 
closed.

- Heikki

Simon Riggs <simon@2ndQuadrant.com> writes:
> On 2 July 2015 at 14:08, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>> I'm marking this as "returned with feedback" in the commitfest.

> There are no unresolved issues with the approach, nor is it true it is
> slower. If you think there are some, you should say what they are, not act
> high handedly to reject a patch without reason.

Have you read the thread?  There were plenty of objections, as well as
a design for a better solution.  In addition, we should think about
more holistic solutions such as Andres' nearby proposal (which I doubt
will work as-is, but maybe somebody will think of how to fix it).
Committing a band-aid will just make it harder to pursue real fixes.
        regards, tom lane