Обсуждение: REINDEX : new parameter to preserve current average leaf density asnew implicit FILLFACTOR

Background :   For some workloads involving high volume of INSERT/UPDATE/DELETE,  It is sometimes beneficial
to schedule regular REINDEX of high-activity indexes,   so as to improve performance,  or restore performance levels
backto what it was earlier,   by removing dead keys etc.      This can result in the average page density of these
indexesfluctuating up and down in a saw-tooth fashion,  REINDEX causing large increase in density (large drop in total
numberof pages) and the workload gradually  decreasing density back to some "steady-state". 

Suggestion : it would be useful if REINDEX could ,   when some new parameter is set , first determine current average
leafpage density in the index to be rebuilt,    (e.g. the value of pgstatindex().avg_leaf_density from the  
pgstattupleextension ),  and then adopt this density as the temporary override FILLFACTOR while rebuilding index
pages, as to to minimize change in density. 

This would avoid the saw-tooth effect on number of pages,   and also reduce the number of index page-splits which occur
duringthe period immediately following a REINDEX done with default FILLFACTOR of 90%.   In effect,  it lessens the need
forthe physical reorganization aspect of REINDEX and focusses more on the function of removing dead  keys. 

An admin do this for themselves by monitoring index page density and setting the FILLFACTOR to the current density
beforeeach REINDEX (and may find that this doesn't change much if the workload is truly steady-state),   but I wonder
ifthis community would agree that it would provide a useful automation of the process. 

Cheers,  John Lumby

John Lumby <johnlumby@hotmail.com> writes:
> Suggestion : it would be useful if REINDEX could ,   when some new parameter is set , first determine current average
leafpage density in the index to be rebuilt,    (e.g. the value of pgstatindex().avg_leaf_density from the  
pgstattupleextension ),  and then adopt this density as the temporary override FILLFACTOR while rebuilding index
pages, as to to minimize change in density. 

Um ... why bother reindexing at all, then?

> This would avoid the saw-tooth effect on number of pages,   and also reduce the number of index page-splits which
occurduring the period immediately following a REINDEX done with default FILLFACTOR of 90%.   In effect,  it lessens
theneed for the physical reorganization aspect of REINDEX and focusses more on the function of removing dead  keys. 

I think you've confused REINDEX with VACUUM.  It seems like a pretty poor
substitute for that --- it's much more expensive and has worse locking
requirements.

            regards, tom lane

On Tue, Jun 25, 2019 at 2:56 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > This would avoid the saw-tooth effect on number of pages,   and also reduce the number of index page-splits which
occurduring the period immediately following a REINDEX done with default FILLFACTOR of 90%.   In effect,  it lessens
theneed for the physical reorganization aspect of REINDEX and focusses more on the function of removing dead  keys. 
>
> I think you've confused REINDEX with VACUUM.  It seems like a pretty poor
> substitute for that --- it's much more expensive and has worse locking
> requirements.

There is a very recent research paper that discusses the idea of
varying fillfactor with a view to ameliorating page splits:

https://btw.informatik.uni-rostock.de/download/tagungsband/B2-2.pdf

I found the paper to be fairly convincing. The general idea is to make
page splits occur at a steady rate following a REINDEX, rather than
having "waves" of page splits. This is quite different to changing
leaf fillfactor based on the observed leaf density, though. You can
already do that by looking at pgstattuple's pgstatindex() function,
which reports a avg_leaf_density for the index. Though I agree that
that's not likely to help matters. Apart from anything else, the
steady state of an index is embodied by more than just its
avg_leaf_density. Especially following the v12 enhancements to B-Tree
indexes.

--
Peter Geoghegan

On Tue, Jun 25, 2019 at 2:45 PM John Lumby <johnlumby@hotmail.com> wrote:
> Background :   For some workloads involving high volume of INSERT/UPDATE/DELETE,  It is sometimes beneficial
> to schedule regular REINDEX of high-activity indexes,   so as to improve performance,  or restore performance levels
backto what it was earlier,   by removing dead keys etc.      This can result in the average page density of these
indexesfluctuating up and down in a saw-tooth fashion,  REINDEX causing large increase in density (large drop in total
numberof pages) and the workload gradually  decreasing density back to some "steady-state". 

I suspect that you might find that the enhancements to B-Tree indexes
that went into Postgres 12 would help with this workload, especially
if you notice that this happens with indexes that have a lot of
duplicates. For the full background, you might take a look at my pgCon
talk:

https://youtu.be/p5RaATILoiE

Fair warning: this is a very technical talk.

Does it seem at all possible that you were affected by either the
issue with duplicates, or the issue that is addressed by the "split
after new tuple" optimization? They're both causes of index bloat that
VACUUM cannot usually prevent.

--
Peter Geoghegan

Thanks Tom and Peter for those thoughts.

>
> I think you've confused REINDEX with VACUUM.  It seems like a pretty poor
> substitute for that --- it's much more expensive and has worse locking
> requirements.
>

I think the answer is mainly "I wish it were so" ,   but in practice,   even with a reasonably aggressive autovacuum
configurationrunning,  eventually the number of pages and number of dead keys builds up too much.    The assumption
(whichis the case in our particular workload) is that,  eventually,  unavailable-service maintenance operation must be
done, and REINDEX does (today,  pg-11.x) play a useful role because it addresses various aspects.   And then,  given we
findit useful to REINDEX,   we would prefer to avoid the sawtooth / "wave of misery" syndrome. 

>
> There is a very recent research paper that discusses the idea of
> varying fillfactor with a view to ameliorating page splits:
>

Thanks,  I am chewing my way through that.  As you say,  it does address exactly the issues I raised.
Do you happen to know if their source-code is available somewhere?
( I did see their db is MS SQL Server but it still might provide some portable ideas. )

>
> I suspect that you might find that the enhancements to B-Tree indexes
> that went into Postgres 12 would help with this workload, especially
> if you notice that this happens with indexes that have a lot of duplicates
>

I had not noticed that,   thanks for pointing it out.  Yes ,  in my workload most of the indexes in question are
non-uniqueand some have very low key card.    I will try out the pg-12 beta when I get a chance. 

>
> For the full background, you might take a look at my pgCon talk:
> https://youtu.be/p5RaATILoiE
>

Is there a pdf or text version?

>
> Does it seem at all possible that you were affected by either the issue with duplicates,
>

definitely

>
> or the issue that is addressed by the "split after new tuple" optimization?
>

don't know,    yet more research needed.    is there a module or contrib which would tell me?

Thanks again      John Lumby





From: Peter Geoghegan <pg@bowt.ie>

Sent: June 25, 2019 6:12 PM

To: John Lumby

Cc: pgsql general

Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR

 


On Tue, Jun 25, 2019 at 2:45 PM John Lumby <johnlumby@hotmail.com> wrote:

> Background :   For some workloads involving high volume of INSERT/UPDATE/DELETE,  It is sometimes beneficial

> to schedule regular REINDEX of high-activity indexes,   so as to improve performance,  or restore performance levels
backto what it was earlier,   by removing dead keys etc.      This can result in the average page density of these
indexesfluctuating up 
 and down in a saw-tooth fashion,  REINDEX causing large increase in density (large drop in total number of pages) and
theworkload gradually  decreasing density back to some "steady-state". 



I suspect that you might find that the enhancements to B-Tree indexes

that went into Postgres 12 would help with this workload, especially

if you notice that this happens with indexes that have a lot of

duplicates. For the full background, you might take a look at my pgCon

talk:



https://youtu.be/p5RaATILoiE



Fair warning: this is a very technical talk.



Does it seem at all possible that you were affected by either the

issue with duplicates, or the issue that is addressed by the "split

after new tuple" optimization? They're both causes of index bloat that

VACUUM cannot usually prevent.



--

Peter Geoghegan

On Wed, Jun 26, 2019 at 8:05 AM John Lumby <johnlumby@hotmail.com> wrote:
> > There is a very recent research paper that discusses the idea of
> > varying fillfactor with a view to ameliorating page splits:
> >
>
> Thanks,  I am chewing my way through that.  As you say,  it does address exactly the issues I raised.
> Do you happen to know if their source-code is available somewhere?
> ( I did see their db is MS SQL Server but it still might provide some portable ideas. )

It's just a research paper. It might never be implemented in any system.

The point of the paper is to make page splits occur at a steady rate
after REINDEX'ing -- not to eliminate or even reduce page splits.

> > I suspect that you might find that the enhancements to B-Tree indexes
> > that went into Postgres 12 would help with this workload, especially
> > if you notice that this happens with indexes that have a lot of duplicates
> >
>
> I had not noticed that,   thanks for pointing it out.  Yes ,  in my workload most of the indexes in question are
non-uniqueand some have very low key card.    I will try out the pg-12 beta when I get a chance.
 

It's easy to show problems with very low cardinality indexes in the
old code. You'll definitely notice a difference there.

> Is there a pdf or text version?

Just the talk slides:
https://www.pgcon.org/2019/schedule/attachments/518_nbtree-arch-pgcon.pdf

-- 
Peter Geoghegan

> From: Peter Geoghegan <pg@bowt.ie>
> Sent: June 26, 2019 12:09 PM
> Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR
>
> > >
> > > I suspect that you might find that the enhancements to B-Tree indexes
> > > that went into Postgres 12 would help with this workload, especially
> > > if you notice that this happens with indexes that have a lot of duplicates
> > >
>
> >
> > I had not noticed that,   thanks for pointing it out.  Yes ,  in my workload most of the indexes in question
> >  are non-unique and some have very low key card.    I will try out the pg-12 beta when I get a chance.
> >
>
>
> It's easy to show problems with very low cardinality indexes in the
> old code. You'll definitely notice a difference there.
>

I've run a comparison of pg-12beta2 with an older release, pg-9.4.6,       running the same intensive-delete-insert
workloadas mentioned before in this thread,    and would appreciate if you could comment on the results,  especially as
towhether they are roughly in line with your expectation. 
I also have one question about a new-in-pg-11 config parm.

Briefly,   the workload involves a repetition of a loop in which ,  on one single table which has 8 indexes,  2 unique
and6 non-unique, 
about 4300 records are deleted,  and for each of those records,   a corresponding record is inserted in which one or
moreof the non-unique key values are modified to values which are not present in the relevant index at that point.  In
otherwords, across all the indexes ,  4300 key-tids are deleted and then 4300 new key-tids are inserted.     At the end
ofeach loop there is zero net change in counts of records and keys but possibly some increase in numbers of pages,
whichis what the test is interested in as well as overall throughput rate. 

For this test,   I did not modify the index default fill factors which therefore remained at 90%,   in order to make a
stabat evaluating not setting explicit fillfactor.   In each case the indexes were either freshly loaded or else
reindexedto have the same starting density.       Here are counts and sizes after 768 iterations 



| tbpages |  tbtuples    |            ixname            | isuniq | livetuples | deadtuples | avg_leaf_density | ixpages


+---------+--------------+------------------------------+--------+------------+------------+------------------+---------

pg-9.4.6
---------------------

|   32160 | 2.55548e+06  | metadata_value_boolean       | f      |    2932852 |          0 |            46.39 |   13535
|   32160 | 2.55548e+06  | metadata_value_field_id      | f      |    2932852 |          0 |            48.58 |   12916
|   32160 | 2.55548e+06  | metadata_value_floatnumber   | f      |    2932852 |          0 |            45.97 |   13658
|   32160 | 2.55548e+06  | metadata_value_longnumber    | f      |    2932852 |          0 |            48.26 |   13009
|   32160 | 2.55548e+06  | metadata_value_owner_field_u | t      |    2932852 |          0 |            58.69 |   14990
|   32160 | 2.55548e+06  | metadata_value_owner_id      | f      |    2932852 |          0 |            53.06 |   11817
|   32160 | 2.55548e+06  | metadata_value_pkey          | t      |    2932852 |          0 |            57.83 |   10842
|   32160 | 2.55548e+06  | metadata_value_timestamp     | f      |    2932852 |          0 |            45.96 |   13663

pg-12beta2
---------------------

|   41814 | 2.519268e+06 | metadata_value_boolean       | f      |    2519268 |       6766 |            63.17 |   10768
|   41814 | 2.519268e+06 | metadata_value_field_id      | f      |    2519268 |       6766 |             68.7 |   12031
|   41814 | 2.519268e+06 | metadata_value_floatnumber   | f      |    2519268 |       6766 |            61.48 |   11225
|   41814 | 2.519268e+06 | metadata_value_longnumber    | f      |    2519268 |       6766 |            58.34 |   12397
|   41814 | 2.519268e+06 | metadata_value_owner_field_u | t      |    2519268 |       6766 |            61.69 |   14780
|   41814 | 2.519268e+06 | metadata_value_owner_id      | f      |    2519268 |       6766 |            48.86 |   12947
|   41814 | 2.519268e+06 | metadata_value_pkey          | t      |    2519268 |       6766 |            59.71 |   11076
|   41814 | 2.519268e+06 | metadata_value_timestamp     | f      |    2519268 |       6766 |            57.81 |   12295

Overall,  pg-12beta2 yielded a 6.7% reduction in sizes (total pages) of indexes,   which was most noticable with the 6
non-uniqueones. 
In fact the primary-key index was larger with pg-12.           Would you have expected better than 6.7%?       Although
awelcome improvement,  I think it is not enough to justify stopping use of setting a lower explicit FILLFACTOR.
Whichthen brings me back to  thinking there is a case for the subject of this thread,  an automatic way to preserve
density.

Secondary points:

I did not expect to see the number of table pages grow so much larger for pg-12 than for pg-9.4.      The number of
tablepages was almost identical at the start of each run.   However this was not the focus of the test.   

Also,  although not shown in those tables,  pg-12 was around 4.5 times faster in completing those 768 iterations,    an
enormousimprovement. 

And one question :
I notice that in some pg-11 release,   a new config parameter appeared  :
      vacuum_cleanup_index_scale_factor
specifies the fraction of the total number of heap tuples counted in the previous statistics collection that can be
insertedwithout incurring an index scan at the VACUUM cleanup stage.  

I have not researched this at all and nor did I set it to anything for my pg-12beta2 run,      but it sounds as though
maybeit could be relevant to this kind of workload  -   Is that so? 

Cheers    John Lumby

On Mon, Jul 8, 2019 at 9:23 AM John Lumby <johnlumby@hotmail.com> wrote:
> Overall,  pg-12beta2 yielded a 6.7% reduction in sizes (total pages) of indexes,   which was most noticable with the
6non-unique ones.
 
> In fact the primary-key index was larger with pg-12.

The avg_leaf_density was actually higher for the primary key index, so
it looks like it really came out slightly ahead on v12. Perhaps you
didn't take deleted_pages into account -- there must be free space
that is reusable by the index that has yet to be reused. It would
probably make sense to subtract that across the board.

> Would you have expected better than 6.7%?

I don't think that a test case that runs VACUUM when there are only
4300 deletions and 4300 insertions is particularly realistic, in
general. You might see a larger difference if there was more churn
between each VACUUM run.

> Although a welcome improvement,  I think it is not enough to justify stopping use of setting a lower explicit
FILLFACTOR.    Which then brings me back to  thinking there is a case for the subject of this thread,  an automatic way
topreserve density.
 

I don't think that such an option would make much sense. The "waves of
misery" paper is about smoothing out the frequency of page splits
following bulk loading and a CREATE INDEX. It is not about making
splits occur less often. It's well understood that a certain amount of
free space is the overhead of B-Tree indexes, albeit an overhead that
can be avoided in certain specific instances.

> And one question :
> I notice that in some pg-11 release,   a new config parameter appeared  :
>       vacuum_cleanup_index_scale_factor

> I have not researched this at all and nor did I set it to anything for my pg-12beta2 run,      but it sounds as
thoughmaybe it could be relevant to this kind of workload  -   Is that so?
 

You seem to be worried about keeping indexes as small as possible.
vacuum_cleanup_index_scale_factor won't help with that.

-- 
Peter Geoghegan

Thanks Peter

> From: Peter Geoghegan <pg@bowt.ie>
> Sent: July 8, 2019 1:39 PM
> Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR
>
> Perhaps you didn't take deleted_pages into account -- there must be
> free space that is reusable by the index that has yet to be reused.
> It would probably make sense to subtract that across the board.
>

Correct,  I did not,   but will do so for the next runs.

>
> I don't think that a test case that runs VACUUM when there are only
> 4300 deletions and 4300 insertions is particularly realistic, in
> general. You might see a larger difference if there was more churn
> between each VACUUM run.
>

Actually the test workload does not run any explicit VACUUM command,
it relies on autovacuum with these settings
(same settings for 9.4 and 12beta2)

 autovacuum                      | on      |
 autovacuum_analyze_scale_factor | 0.4     |
 autovacuum_analyze_threshold    | 50000   |
 autovacuum_max_workers          | 6       |
 autovacuum_naptime              | 20      | s
 autovacuum_vacuum_cost_delay    | 0       | ms
 autovacuum_vacuum_cost_limit    | 9999    |
 autovacuum_vacuum_scale_factor  | 0       |
 autovacuum_vacuum_threshold     | 2000    |
 autovacuum_work_mem             | 1048576 | kB


To correspond to your " more churn between each VACUUM"
Would you then suggest increasing
autovacuum_vacuum_cost_delay and/or  autovacuum_vacuum_scale_factor?

Cheers,  John Lumby

On Mon, Jul 8, 2019 at 12:10 PM John Lumby <johnlumby@hotmail.com> wrote:
> Actually the test workload does not run any explicit VACUUM command,
> it relies on autovacuum with these settings
> (same settings for 9.4 and 12beta2)

> To correspond to your " more churn between each VACUUM"
> Would you then suggest increasing
> autovacuum_vacuum_cost_delay and/or  autovacuum_vacuum_scale_factor?

Well, you're still running autovacuum very aggressively here. It'll
easily keep up when run on a relatively small table such as this.

BTW, you should definitely run the latest point release of 9.4 -- not
9.4.6. You're missing years of bug fixes by sticking to such an old
point release, including some rather nasty ones -- 9.4.23 is the
current 9.4 point release. Actually, 9.4 is going to lose support this
year, as the oldest stable version that's currently supported by the
community.

-- 
Peter Geoghegan

On Mon, Jul 8, 2019 at 12:19 PM Peter Geoghegan <pg@bowt.ie> wrote:
> Well, you're still running autovacuum very aggressively here. It'll
> easily keep up when run on a relatively small table such as this.

Also, an exactly equal number of insertions and deletions is rather
likely to result in bloated indexes in a way that probably isn't
representative of many workloads. Even if the number of insertions was
only slightly greater than the number of deletions, then the overall
pattern would be one of continual growth, which is generally
considered much more interesting.

For far far more information on the topic than you want, see the paper
"B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than
Merge-at-Half":

https://www.sciencedirect.com/science/article/pii/002200009390020W

The salient point made by the paper is that good space utilization
rests on the assumption that there are fewer deletes than inserts,
though maybe only slightly fewer:

"The tendency of the utilization to remain near 69% can be explained
by the following arguments: If there are even just a few more inserts
than deletes, the B-tree will grow at the net insert rate (the rate of
inserts minus the rate of deletes)."

If the volume of data never grows past a certain point, then it's
unlikely that the space utilization is very important. This may even
be premature optimization.
-- 
Peter Geoghegan

> From: Peter Geoghegan <pg@bowt.ie>
> Sent: July 8, 2019 1:39 PM
> Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR
>
> On Mon, Jul 8, 2019 at 9:23 AM John Lumby <johnlumby@hotmail.com> wrote:
>
> > Although a welcome improvement,  I think it is not enough to justify stopping use of setting
> > a lower explicit FILLFACTOR.   Which then brings me back to  thinking there is a case
> > for the subject of this thread,  an automatic way to preserve density.
>
> I don't think that such an option would make much sense. The "waves of
> misery" paper is about smoothing out the frequency of page splits
> following bulk loading and a CREATE INDEX. It is not about making
> splits occur less often. It's well understood that a certain amount of
> free space is the overhead of B-Tree indexes, albeit an overhead that
> can be avoided in certain specific instances.
>
Yes,   I see that.     But surely "making splits occur less often" is a desirable
objective in itself, is it not?     And I believe that a parameter to preserve the "steady-state"
density in high-traffic indexes would help achieve that goal,   wouldn't you agree?

Cheers,  John Lumby

On Tue, Jul 9, 2019 at 10:31 AM John Lumby <johnlumby@hotmail.com> wrote:
> Yes,   I see that.     But surely "making splits occur less often" is a desirable
> objective in itself, is it not?     And I believe that a parameter to preserve the "steady-state"
> density in high-traffic indexes would help achieve that goal,   wouldn't you agree?

Anything that reliably reduces page splits without hurting space
utilization is well worthwhile. I can't see how what you describe
could have that effect, though. If you expect the leaf density to be
the same after a REINDEX, then why bother at all? There is no reason
to think that that will be more effective than simple vacuuming.

-- 
Peter Geoghegan

> From: Peter Geoghegan <pg@bowt.ie>
> Sent: July 9, 2019 1:47 PM
> Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR
>
> On Tue, Jul 9, 2019 at 10:31 AM John Lumby <johnlumby@hotmail.com> wrote:
> > Yes,   I see that.     But surely "making splits occur less often" is a desirable
> > objective in itself, is it not?     And I believe that a parameter to preserve the "steady-state"
> > density in high-traffic indexes would help achieve that goal,   wouldn't you agree?
>
> Anything that reliably reduces page splits without hurting space
> utilization is well worthwhile. I can't see how what you describe
> could have that effect, though. If you expect the leaf density to be
> the same after a REINDEX, then why bother at all? There is no reason
> to think that that will be more effective than simple vacuuming.
>
Ah,  I did not explain the idea welll enough.
The scenario (simplified) is this:
Time 0      FILLFACTORs all set to default 90%
            because we do not yet know what the steady-state density
            will turn out to be.
       {   workload runs for a few weeks  }
Time N      gather table and index stats,   discover growth and learn density.
            growth is more than autovacuum could control so
       {   ALTER INDEX ??? SET (fillfactor = AUTO); }
       {   REINDEX,   desiring to preserve current density whatever this is }
       {   workload runs for a few more weeks  }
Time 2*N    gather table and index stats,   discover little or no growth since time N.
            we have achieved steady-state in total number of pages.

Would this not work?

Cheers,   John

And the point of the REINDEX at that point (below) is to remove dead tuple keys-tids
and  reorganize those split pages back into physical order without losing the freespace.

> From: Peter Geoghegan <pg@bowt.ie>
> Sent: July 9, 2019 1:47 PM
> Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR
>
> On Tue, Jul 9, 2019 at 10:31 AM John Lumby <johnlumby@hotmail.com> wrote:
> > Yes,   I see that.     But surely "making splits occur less often" is a desirable
> > objective in itself, is it not?     And I believe that a parameter to preserve the "steady-state"
> > density in high-traffic indexes would help achieve that goal,   wouldn't you agree?
>
> Anything that reliably reduces page splits without hurting space
> utilization is well worthwhile. I can't see how what you describe
> could have that effect, though. If you expect the leaf density to be
> the same after a REINDEX, then why bother at all? There is no reason
> to think that that will be more effective than simple vacuuming.
>
Ah,  I did not explain the idea welll enough.
The scenario (simplified) is this:
Time 0      FILLFACTORs all set to default 90%
            because we do not yet know what the steady-state density
            will turn out to be.
       {   workload runs for a few weeks  }
Time N      gather table and index stats,   discover growth and learn density.
            growth is more than autovacuum could control so
       {   ALTER INDEX ??? SET (fillfactor = AUTO); }
       {   REINDEX,   desiring to preserve current density whatever this is }
       {   workload runs for a few more weeks  }
Time 2*N    gather table and index stats,   discover little or no growth since time N.
            we have achieved steady-state in total number of pages.

Would this not work?

Cheers,   John

On Tue, Jul 9, 2019 at 11:27 AM John Lumby <johnlumby@hotmail.com> wrote:
> And the point of the REINDEX at that point (below) is to remove dead tuple keys-tids
> and  reorganize those split pages back into physical order without losing the freespace.

VACUUM already removes the tuples, accounting for all overhead.

You are right that it would be possible for us to "defragment" the
pages, so that they'd be in sequential order on disk from the point of
view of a whole index scan -- this is what the "leaf_fragmentation"
statistic from pgstatindex() reports on. We could in principle come up
with a way of moving pages around, which would have some modest
benefit for certain types of queries (it wouldn't improve the
heap/index correlation, though, which is far more important). That
would either necessitate that the command acquire a disruptive lock on
the index (i.e. no writes, just like regular REINDEX), or that we
drastically rearchitect the B-Tree code to make it support this.
Neither of which seem particularly appealing.

I believe that this is a lot more important in systems that generally
use clustered indexes, such as MS SQL Server. This kind of
"fragmentation" isn't usually much of a problem when using Postgres.

-- 
Peter Geoghegan

On Tue, Jul 9, 2019 at 12:29 PM John Lumby <johnlumby@hotmail.com> wrote:
> I was not thinking of a new command,  just an extension of the existing REINDEX
> which would apply a fillfactor equal to current average page density,
> by adding a preliminary step to sample that first.

That would be a very different thing to REINDEX no matter how you
spelt it, though. REINDEX creates a new index, from scratch, whereas
you're talking about restructuring what's already there.

> > I believe that this is a lot more important in systems that generally
> > use clustered indexes, such as MS SQL Server. This kind of
> > "fragmentation" isn't usually much of a problem when using Postgres.
> >
> We have found that, for an index which has both experienced large number of page splits
> and whose table has a large number of dead tuples (despite autovacuum),
> REINDEX with FILLFACTOR set to current page_density does produce a performance improvement,
> and also does reduce future growth in number of pages.    I don't have numbers to
> hand,  and in fact not sure if any catalog view or pgstattuple tells me about the proportion
> of dead key-tids in the index itself (do you know of any source?) as opposed to the table,
> but based on that recollection,  yes,   REINDEX can reduce fragmentation.

This could help the old "getting tired" behavior with many duplicates,
by making the free space available in earlier leaf pages (those
further to the left) that are full of duplicates -- the original
average space utilization may reflect a very uneven distribution of
free space overall. Or, it could be that range scan performance
benefitted from reduced fragmentation, because your workload happened
to be bottlenecked on large range scans. Though that seems unlikely.

I believe that the effect that you identified is real, but at a
minimum it's not clear why a REINDEX with a fillfactor to match the
original leaf space utilization helped. It would be fairly difficult
to figure it out for sure. If it was a problem with
duplicates/"getting tired", then I'd expect the new v12 code will help
a lot.

> However we did not run a VACUUM command first.     Maybe if we had run VACUUM instead of
> the REINDEX commands,   we might have obtained the same degree of improvement,  I don't know.
> I think this was Tom's point earlier on in this thread.

It was. Tom's intuition about that matches my own, though I
acknowledge that the old behavior with duplicates muddies the waters.

> Correct me if I'm wrong but I believe whether an index is "clustered" or not is not relevant for
> this discussion because the clustering in that context is referring to ordering of the
> table pages,  not the index pages.

Right.

> I believe it is quite possible to have a perfectly
> "clustered" table whose clustering index is itself badly disorganized.

Technically the two things are separate metrics, so that is
theoretically possible, but it doesn't seem all that likely. It could
happen with lots of non-HOT updates, where all new index tuples relate
to the same logical row as some existing index tuple, causing many
page splits despite there being no real change in the logical contents
of the index. Even then, the table will itself lose much of its
original order, so the index will become "unclustered" as it becomes
fragmented.

-- 
Peter Geoghegan

> From: Peter Geoghegan <pg@bowt.ie>
> Sent: July 9, 2019 5:15 PM
> Subject: Re: REINDEX : new parameter to preserve current average leaf density as new implicit FILLFACTOR
>
> On Tue, Jul 9, 2019 at 12:29 PM John Lumby <johnlumby@hotmail.com> wrote:
> > I was not thinking of a new command,  just an extension of the existing REINDEX
> > which would apply a fillfactor equal to current average page density,
> > by adding a preliminary step to sample that first.
>
> That would be a very different thing to REINDEX no matter how you
> spelt it, though. REINDEX creates a new index, from scratch, whereas
> you're talking about restructuring what's already there.

No,  no,   I really am talking about an extension to the *existing* REINDEX,
and yes,  yes,  my extended REINDEX *would* still; create a new index from scratch.
The *only* difference is that,  instead of taking the FILLFACTOR it uses from
whatever is set in the index attributes,  it would take it from first calculating
current average page density.  and then build a new index with that fillfactor.

>
> Or, it could be that range scan performance benefitted from reduced fragmentation,
>

Yes,  I think so.

Cheers,  John

On Tue, Jul 9, 2019 at 3:18 PM John Lumby <johnlumby@hotmail.com> wrote:
> > Or, it could be that range scan performance benefitted from reduced fragmentation,
> >
>
> Yes,  I think so.

ISTM that the simplest explanation here is that index fragmentation
(and even index size) is a red herring, and the real issue is that
you're suffering from problems similar to those that are described in
these old threads:

https://www.postgresql.org/message-id/flat/20160524173914.GA11880%40telsasoft.com
https://www.postgresql.org/message-id/flat/520D6610.8040907%40emulex.com

There have been numerous reports from users with problems involving
low cardinality indexes that gradually became less correlated with the
underlying table over time. At least a couple of these users found
that a periodic REINDEX temporarily fixed the problem -- see the first
thread for an example. Postgres 12 maintains the heap/table sort order
among duplicates by treating heap TID as a tiebreaker column, which
may make REINDEXing totally unnecessary for you. It's harder to model
this issue because the problem with heap TID order will only be seen
when there is at least a moderate amount of churn.

-- 
Peter Geoghegan

On Tue, Jul 9, 2019 at 9:04 PM Peter Geoghegan <pg@bowt.ie> wrote:
> ISTM that the simplest explanation here is that index fragmentation
> (and even index size) is a red herring, and the real issue is that
> you're suffering from problems similar to those that are described in
> these old threads:
>
> https://www.postgresql.org/message-id/flat/20160524173914.GA11880%40telsasoft.com
> https://www.postgresql.org/message-id/flat/520D6610.8040907%40emulex.com

I can imagine why you found you needed to reduce fillfactor to get
much of any benefit from a REINDEX. Page splits are inherently
expensive, for one thing. Also, in this specific scenario a succession
of page splits might hasten the index returning to having little
correlation with the underlying table within each large group of
duplicates. Splits on fillfactor 90 pages would make new space
available for future insertions on earlier duplicate pages, mixing old
and new rows together before long.

-- 
Peter Geoghegan