Re: Fillfactor for GIN indexes

Hi all,

Please find attached a simple patch adding fillfactor as storage parameter
for GIN indexes. The default value is the same as the one currently aka 100
to have the pages completely packed when a GIN index is created.

Note that to have this feature correctly working, the fix I sent yesterday
to set up isBuild for the entry insertion is needed (patch attached as well
here to facilitate the review):
http://www.postgresql.org/message-id/CAB7nPqSc4VQ9mHKqm_YvAfcTEhO-iUY8SKbXYdnMGnAi1XnPaw@mail.gmail.com

Here are the results of some tests with a simple pg_trgm index on the
English translation of "Les Miserables":
CREATE EXTENSION pg_trgm;
CREATE TABLE les_miserables (num serial, line text);
COPY les_miserables (line) FROM '/to/path/pg135.txt';
CREATE INDEX les_miserables_100 ON les_miserables USING gin (line
gin_trgm_ops);
CREATE INDEX les_miserables_40 ON les_miserables USING gin (line
gin_trgm_ops) with (fillfactor = 40);
CREATE INDEX les_miserables_20 ON les_miserables USING gin (line
gin_trgm_ops) with (fillfactor = 20);
CREATE INDEX les_miserables_80 ON les_miserables USING gin (line
gin_trgm_ops) with (fillfactor = 80);
CREATE INDEX les_miserables_10 ON les_miserables USING gin (line
gin_trgm_ops) with (fillfactor = 10);
SELECT relname, pg_size_pretty(pg_relation_size(oid)), reloptions FROM
pg_class where relname like 'les_miserables_%';
relname | pg_size_pretty | reloptions
------------------------+----------------+-----------------
les_miserables_100 | 8256 kB | null
les_miserables_20 | 14 MB | {fillfactor=20}
les_miserables_40 | 11 MB | {fillfactor=40}
les_miserables_80 | 8712 kB | {fillfactor=80}
les_miserables_num_seq | 8192 bytes | null
(5 rows)

I am adding that to the commit fest of December.
Regards,
--
Michael

On Fri, Nov 21, 2014 at 2:12 PM, Michael Paquier
<michael(dot)paquier(at)gmail(dot)com> wrote:
> I am adding that to the commit fest of December.
Here are updated patches. Alvaro notified me about an inconsistent comment.
--
Michael

Le jeudi 27 novembre 2014 23:33:11 Michael Paquier a écrit :
> On Fri, Nov 21, 2014 at 2:12 PM, Michael Paquier
>
> <michael(dot)paquier(at)gmail(dot)com> wrote:
> > I am adding that to the commit fest of December.
>
> Here are updated patches. Alvaro notified me about an inconsistent
> comment.

what are the benefits of this patch ? (maybe you had some test case or a
benchmark ?)
--
Cédric Villemain +33 (0)6 20 30 22 52
http://2ndQuadrant.fr/
PostgreSQL: Support 24x7 - Développement, Expertise et Formation

Hi!

On Fri, Nov 21, 2014 at 8:12 AM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
wrote:

> Please find attached a simple patch adding fillfactor as storage parameter
> for GIN indexes. The default value is the same as the one currently aka 100
> to have the pages completely packed when a GIN index is created.
>

That's not true. Let us discuss it a little bit.
In btree access method index is created by sorting index tuples. Once they
are sorted it can write a tree with any fullness of the pages. With
completely filled pages you will get flood of index page splits on table
updates or inserts. In order to avoid that the default fillfactor is 90.
Besides index creation, btree access method tries to follow given
fillfactor in the case of inserting ordered data. When rightmost page
splits then fillfactor percent of data goes to the left page.
Btree page life cycle is between being freshly branched by split (50%
filled) and being full packed (100% filled) and then splitted. Thus we can
roughly estimate average fullness of btree page to be 75%. This
"equilibrium" state can be achieved by huge amount of inserts over btree
index.

Fillfactor was spreaded to other access methods. For instance, GiST. In
GiST, tree is always constructed by page splits. So, freshly created GiST
is already in its "equilibrium" state. Even more GiST doesn't splits page
by halves. Split ration depends on opclass. So, "equilibrium" fullness of
particular GiST index is even less than 75%. What does fillfactor do with
GiST? It makes GiST pages split on fillfactor fullness on index build. So,
GiST is even less fulled. But why? You anyway don't get flood of split on
fresh GiST index because it's in "equilibrium" state. That's why I would
rather delete fillfactor from GiST until we have some algorithm to
construct GiST without page splits.

What is going on with GIN? GIN is, basically, two-level nested btree. So,
fillfactor should be applicable here. But GIN is not constructed like
btree...
GIN accumulates maintenance_work_mem of data and then inserts it into the
tree. So fresh GIN is the result of insertion of maintenance_work_mem
buckets. And each bucket is sorted. On small index (or large
maintenance_work_mem) it would be the only one bucket. GIN has two levels
of btree: entry tree and posting tree. Currently entry tree has on special
logic to control fullness during index build. So, with only one bucket
entry tree will be 50% filled. With many buckets entry tree will be at
"equilibrium" state. In some specific cases (about two buckets) entry tree
can be almost fully packed. Insertion into posting tree is always ordered
during index build because posting tree is a tree of TIDs. When posting
tree page splits it leaves left page fully packed during index build and
75% packed during insertion (because it expects some sequential inserts).

Idea of GIN building algorithm is that entry tree is expected to be
relatively small and fit to cache. Insertions into posting trees are
orders. Thus this algorithm should be IO efficient and have low overhead.
However, with large entry trees this algorithm can perform much worse.

My summary is following:
1) In order to have fully correct support of fillfactor in GIN we need to
rewrite GIN build algorithm.
2) Without rewriting GIN build algorithm, not much can be done with entry
tree. However, you can implement some heuristics.
3) You definitely need to touch code that selects ratio of split in
dataPlaceToPageLeaf (starting with if (!btree->isBuild)).
3) GIN data pages are always compressed excepts pg_upgraded indexes from
pre-9.4. Take care about it in following code.
if (GinPageIsCompressed(page))
freespace = GinDataLeafPageGetFreeSpace(page);
+ else if (btree->isBuild)
+ freespace = BLCKSZ * (100 - fillfactor) / 100;

------
With best regards,
Alexander Korotkov.

On Fri, Nov 28, 2014 at 4:27 AM, Alexander Korotkov
<aekorotkov(at)gmail(dot)com> wrote:
> On Fri, Nov 21, 2014 at 8:12 AM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
> wrote:
>> Please find attached a simple patch adding fillfactor as storage parameter
>> for GIN indexes. The default value is the same as the one currently aka 100
>> to have the pages completely packed when a GIN index is created.
>
>
> That's not true. Let us discuss it a little bit.
> In btree access method index is created by sorting index tuples. Once they
> are sorted it can write a tree with any fullness of the pages. With
> completely filled pages you will get flood of index page splits on table
> updates or inserts. In order to avoid that the default fillfactor is 90.
> Besides index creation, btree access method tries to follow given fillfactor
> in the case of inserting ordered data. When rightmost page splits then
> fillfactor percent of data goes to the left page.
> Btree page life cycle is between being freshly branched by split (50%
> filled) and being full packed (100% filled) and then splitted. Thus we can
> roughly estimate average fullness of btree page to be 75%. This
> "equilibrium" state can be achieved by huge amount of inserts over btree
> index.
>
> Fillfactor was spreaded to other access methods. For instance, GiST. In
> GiST, tree is always constructed by page splits. So, freshly created GiST is
> already in its "equilibrium" state. Even more GiST doesn't splits page by
> halves. Split ration depends on opclass. So, "equilibrium" fullness of
> particular GiST index is even less than 75%. What does fillfactor do with
> GiST? It makes GiST pages split on fillfactor fullness on index build. So,
> GiST is even less fulled. But why? You anyway don't get flood of split on
> fresh GiST index because it's in "equilibrium" state. That's why I would
> rather delete fillfactor from GiST until we have some algorithm to construct
> GiST without page splits.
>
> What is going on with GIN? GIN is, basically, two-level nested btree. So,
> fillfactor should be applicable here. But GIN is not constructed like
> btree...
> GIN accumulates maintenance_work_mem of data and then inserts it into the
> tree. So fresh GIN is the result of insertion of maintenance_work_mem
> buckets. And each bucket is sorted. On small index (or large
> maintenance_work_mem) it would be the only one bucket. GIN has two levels of
> btree: entry tree and posting tree. Currently entry tree has on special
> logic to control fullness during index build. So, with only one bucket entry
> tree will be 50% filled. With many buckets entry tree will be at
> "equilibrium" state. In some specific cases (about two buckets) entry tree
> can be almost fully packed. Insertion into posting tree is always ordered
> during index build because posting tree is a tree of TIDs. When posting tree
> page splits it leaves left page fully packed during index build and 75%
> packed during insertion (because it expects some sequential inserts).
>
> Idea of GIN building algorithm is that entry tree is expected to be
> relatively small and fit to cache. Insertions into posting trees are orders.
> Thus this algorithm should be IO efficient and have low overhead. However,
> with large entry trees this algorithm can perform much worse.
>
> My summary is following:
> 1) In order to have fully correct support of fillfactor in GIN we need to
> rewrite GIN build algorithm.
> 2) Without rewriting GIN build algorithm, not much can be done with entry
> tree. However, you can implement some heuristics.
> 3) You definitely need to touch code that selects ratio of split in
> dataPlaceToPageLeaf (starting with if (!btree->isBuild)).
> 3) GIN data pages are always compressed excepts pg_upgraded indexes from
> pre-9.4. Take care about it in following code.
> if (GinPageIsCompressed(page))
> freespace = GinDataLeafPageGetFreeSpace(page);
> + else if (btree->isBuild)
> + freespace = BLCKSZ * (100 - fillfactor) / 100;

This is a very interesting explanation; thanks for writing it up!

It does leave me wondering why anyone would want fillfactor for GIN at
all, even if they were willing to rewrite the build algorithm.

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

On Wed, Dec 3, 2014 at 2:37 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Fri, Nov 28, 2014 at 4:27 AM, Alexander Korotkov
> <aekorotkov(at)gmail(dot)com> wrote:
>> On Fri, Nov 21, 2014 at 8:12 AM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
>> wrote:
>>> Please find attached a simple patch adding fillfactor as storage parameter
>>> for GIN indexes. The default value is the same as the one currently aka 100
>>> to have the pages completely packed when a GIN index is created.
>>
>>
>> That's not true. Let us discuss it a little bit.
>> [blah discussion]
That's quite a nice explanation. Thanks!

>> My summary is following:
>> 1) In order to have fully correct support of fillfactor in GIN we need to
>> rewrite GIN build algorithm.
>> 2) Without rewriting GIN build algorithm, not much can be done with entry
>> tree. However, you can implement some heuristics.
TBH, I am not really planning to rewrite the whole code.

>> 3) You definitely need to touch code that selects ratio of split in
>> dataPlaceToPageLeaf (starting with if (!btree->isBuild)).
OK I see, so for a split we need to have a calculation based on the
fillfactor, with 75% by default.

>> 4) GIN data pages are always compressed excepts pg_upgraded indexes from
>> pre-9.4. Take care about it in following code.
>> if (GinPageIsCompressed(page))
>> freespace = GinDataLeafPageGetFreeSpace(page);
>> + else if (btree->isBuild)
>> + freespace = BLCKSZ * (100 - fillfactor) / 100;
Hm. Simply reversing both conditions is fine, no?

> This is a very interesting explanation; thanks for writing it up!
> It does leave me wondering why anyone would want fillfactor for GIN at
> all, even if they were willing to rewrite the build algorithm.
Based on the explanation of Alexander, the current GIN code fills in a
page at 75% for a split, and was doing even 50/50 pre-9.4 if I recall
correctly. IMO a higher fillfactor makes sense for a GIN index that
gets less random updates, no?

I am attaching an updated patch, with the default fillfactor value at
75%, and with the page split code using the fillfactor rate.
Thoughts?
--
Michael

On Wed, Jan 7, 2015 at 4:11 PM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
wrote:

> On Wed, Dec 3, 2014 at 2:37 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> > On Fri, Nov 28, 2014 at 4:27 AM, Alexander Korotkov
> > <aekorotkov(at)gmail(dot)com> wrote:
> >> On Fri, Nov 21, 2014 at 8:12 AM, Michael Paquier <
> michael(dot)paquier(at)gmail(dot)com>
> >> wrote:
> >>> Please find attached a simple patch adding fillfactor as storage
> parameter
> >>> for GIN indexes. The default value is the same as the one currently
> aka 100
> >>> to have the pages completely packed when a GIN index is created.
> >>
> >>
> >> That's not true. Let us discuss it a little bit.
> >> [blah discussion]
> That's quite a nice explanation. Thanks!
>
> >> My summary is following:
> >> 1) In order to have fully correct support of fillfactor in GIN we need
> to
> >> rewrite GIN build algorithm.
> >> 2) Without rewriting GIN build algorithm, not much can be done with
> entry
> >> tree. However, you can implement some heuristics.
> TBH, I am not really planning to rewrite the whole code.
>
> >> 3) You definitely need to touch code that selects ratio of split in
> >> dataPlaceToPageLeaf (starting with if (!btree->isBuild)).
> OK I see, so for a split we need to have a calculation based on the
> fillfactor, with 75% by default.
>
> >> 4) GIN data pages are always compressed excepts pg_upgraded indexes from
> >> pre-9.4. Take care about it in following code.
> >> if (GinPageIsCompressed(page))
> >> freespace = GinDataLeafPageGetFreeSpace(page);
> >> + else if (btree->isBuild)
> >> + freespace = BLCKSZ * (100 - fillfactor) / 100;
> Hm. Simply reversing both conditions is fine, no?
>
> > This is a very interesting explanation; thanks for writing it up!
> > It does leave me wondering why anyone would want fillfactor for GIN at
> > all, even if they were willing to rewrite the build algorithm.
> Based on the explanation of Alexander, the current GIN code fills in a
> page at 75% for a split, and was doing even 50/50 pre-9.4 if I recall
> correctly. IMO a higher fillfactor makes sense for a GIN index that
> gets less random updates, no?
>
> I am attaching an updated patch, with the default fillfactor value at
> 75%, and with the page split code using the fillfactor rate.
> Thoughts?

Rewritten version of patch is attached. I made following changes:

1) I removed fillfactor handling from entry tree. Because in this case
fillfactor parameter would be only upper bound for actual page fullness.
It's very like GiST approach to fillfactor. But I would rather remove
fillfactor from GiST than spread such approach to other AMs.
2) Fillfactor handling for posting trees is fixed.
3) Default fillfactor for GIN is reverted to 90. I didn't mean that default
fillfactor should be 75%. I mean that equilibrium state of tree would be
about 75% fullness. But that doesn't mean that we don't want indexes to be
better packed just after creation. Anyway I didn't see reason why default
fillfactor for GIN btree should differs from default fillfactor of regular
btree.

------
With best regards,
Alexander Korotkov.

On Thu, Jan 8, 2015 at 12:31 AM, Alexander Korotkov <aekorotkov(at)gmail(dot)com>
wrote:
>
> Rewritten version of patch is attached. I made following changes:
>
> 1) I removed fillfactor handling from entry tree. Because in this case
> fillfactor parameter would be only upper bound for actual page fullness.
> It's very like GiST approach to fillfactor. But I would rather remove
> fillfactor from GiST than spread such approach to other AMs.
> 2) Fillfactor handling for posting trees is fixed.
> 3) Default fillfactor for GIN is reverted to 90. I didn't mean that
> default fillfactor should be 75%. I mean that equilibrium state of tree
> would be about 75% fullness. But that doesn't mean that we don't want
> indexes to be better packed just after creation. Anyway I didn't see reason
> why default fillfactor for GIN btree should differs from default fillfactor
> of regular btree.
>

Just forgot simple case that I used to test the patch.

create table test as (select array[1,2,3] v from
generate_series(1,1000000));
create index test_idx20 on test using gin(v) with (fillfactor=20);
create index test_idx30 on test using gin(v) with (fillfactor=30);
create index test_idx40 on test using gin(v) with (fillfactor=40);
create index test_idx50 on test using gin(v) with (fillfactor=50);
create index test_idx60 on test using gin(v) with (fillfactor=60);
create index test_idx70 on test using gin(v) with (fillfactor=70);
create index test_idx80 on test using gin(v) with (fillfactor=80);
create index test_idx90 on test using gin(v) with (fillfactor=90);
create index test_idx100 on test using gin(v) with (fillfactor=100);

List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+-------------+-------+--------+-------+---------+-------------
public | test_idx20 | index | smagen | test | 16 MB |
public | test_idx30 | index | smagen | test | 11 MB |
public | test_idx40 | index | smagen | test | 8152 kB |
public | test_idx50 | index | smagen | test | 6520 kB |
public | test_idx60 | index | smagen | test | 5176 kB |
public | test_idx70 | index | smagen | test | 4480 kB |
public | test_idx80 | index | smagen | test | 3928 kB |
public | test_idx90 | index | smagen | test | 3520 kB |
public | test_idx100 | index | smagen | test | 3184 kB |
(9 rows)

------
With best regards,
Alexander Korotkov.

On Thu, Jan 8, 2015 at 6:31 AM, Alexander Korotkov <aekorotkov(at)gmail(dot)com> wrote:
> On Wed, Jan 7, 2015 at 4:11 PM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
>> I am attaching an updated patch, with the default fillfactor value at
>> 75%, and with the page split code using the fillfactor rate.
>> Thoughts?
> Rewritten version of patch is attached. I made following changes:

Thanks! With this patch (and my previous version as well) GIN indexes
with default fillfactor have a size higher than 9.4 indexes, 9.4
behavior being consistent only with fillfactor=100 and not the default
of 90. Are we fine with that?
--
Michael

On Thu, Jan 8, 2015 at 2:03 PM, Michael Paquier
<michael(dot)paquier(at)gmail(dot)com> wrote:
> On Thu, Jan 8, 2015 at 6:31 AM, Alexander Korotkov <aekorotkov(at)gmail(dot)com> wrote:
>> On Wed, Jan 7, 2015 at 4:11 PM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
>>> I am attaching an updated patch, with the default fillfactor value at
>>> 75%, and with the page split code using the fillfactor rate.
>>> Thoughts?
>> Rewritten version of patch is attached. I made following changes:
>
> Thanks! With this patch (and my previous version as well) GIN indexes
> with default fillfactor have a size higher than 9.4 indexes, 9.4
> behavior being consistent only with fillfactor=100 and not the default
> of 90. Are we fine with that?
IMO, this patch has value to control random updates on GIN indexes,
but we should have a default fillfactor of 100 to have index size
consistent with 9.4. Thoughts?
--
Michael

On Thu, Jan 15, 2015 at 10:19 AM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com
> wrote:

> On Thu, Jan 8, 2015 at 2:03 PM, Michael Paquier
> <michael(dot)paquier(at)gmail(dot)com> wrote:
> > On Thu, Jan 8, 2015 at 6:31 AM, Alexander Korotkov <aekorotkov(at)gmail(dot)com>
> wrote:
> >> On Wed, Jan 7, 2015 at 4:11 PM, Michael Paquier <
> michael(dot)paquier(at)gmail(dot)com>
> >>> I am attaching an updated patch, with the default fillfactor value at
> >>> 75%, and with the page split code using the fillfactor rate.
> >>> Thoughts?
> >> Rewritten version of patch is attached. I made following changes:
> >
> > Thanks! With this patch (and my previous version as well) GIN indexes
> > with default fillfactor have a size higher than 9.4 indexes, 9.4
> > behavior being consistent only with fillfactor=100 and not the default
> > of 90. Are we fine with that?
> IMO, this patch has value to control random updates on GIN indexes,
> but we should have a default fillfactor of 100 to have index size
> consistent with 9.4. Thoughts?
>

I'm not sure. On the one hand it's unclear why fillfactor should be
different from 9.4.
On the other hand it's unclear why it should be different from btree.
I propose marking this "ready for committer". So, committer can make a
final decision.

------
With best regards,
Alexander Korotkov.

Alexander Korotkov wrote:
> I'm not sure. On the one hand it's unclear why fillfactor should be
> different from 9.4.
> On the other hand it's unclear why it should be different from btree.
> I propose marking this "ready for committer". So, committer can make a final
> decision.
OK let's do so then. My preference is to fully pack the index at
build. GIN compression has been one of the headlines of 9.4.
--
Michael

On Thu, Jan 15, 2015 at 7:06 AM, Michael Paquier
<michael(dot)paquier(at)gmail(dot)com> wrote:
> Alexander Korotkov wrote:
>> I'm not sure. On the one hand it's unclear why fillfactor should be
>> different from 9.4.
>> On the other hand it's unclear why it should be different from btree.
>> I propose marking this "ready for committer". So, committer can make a final
>> decision.
> OK let's do so then. My preference is to fully pack the index at
> build. GIN compression has been one of the headlines of 9.4.

I'm struggling to understand why we shouldn't just reject this patch.
On November 27th, Cedric said:

"what are the benefits of this patch ? (maybe you had some test case
or a benchmark ?)"

Nobody replied. On January 15th, you (Michael) hypothesized that
"this patch has value to control random updates on GIN indexes" but
there seem to be absolutely no test results showing that any such
value exists.

There's only value in adding a fillfactor parameter to GIN indexes if
it improves performance. There are no benchmarks showing it does.
So, why are we still talking about this?

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

On Sat, Jan 17, 2015 at 2:40 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> There's only value in adding a fillfactor parameter to GIN indexes if
> it improves performance. There are no benchmarks showing it does.
> So, why are we still talking about this?
Indeed. There is no such benchmark as of now, and I am not sure I'll
get the time to work more on that soon, so let's reject the patch for
now. And sorry for the useless noise.
--
Michael

On Fri, Jan 16, 2015 at 8:40 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Thu, Jan 15, 2015 at 7:06 AM, Michael Paquier
> <michael(dot)paquier(at)gmail(dot)com> wrote:
> > Alexander Korotkov wrote:
> >> I'm not sure. On the one hand it's unclear why fillfactor should be
> >> different from 9.4.
> >> On the other hand it's unclear why it should be different from btree.
> >> I propose marking this "ready for committer". So, committer can make a
> final
> >> decision.
> > OK let's do so then. My preference is to fully pack the index at
> > build. GIN compression has been one of the headlines of 9.4.
>
> I'm struggling to understand why we shouldn't just reject this patch.
> On November 27th, Cedric said:
>
> "what are the benefits of this patch ? (maybe you had some test case
> or a benchmark ?)"
>
> Nobody replied. On January 15th, you (Michael) hypothesized that
> "this patch has value to control random updates on GIN indexes" but
> there seem to be absolutely no test results showing that any such
> value exists.
>
> There's only value in adding a fillfactor parameter to GIN indexes if
> it improves performance. There are no benchmarks showing it does.
> So, why are we still talking about this?

I already wrote quite detailed explanation of subject. Let mel try to
explain in shortly. GIN is two level nested btree. Thus, GIN would have
absolutely same benefits from fillfactor as btree. Lack of tests showing it
is, for sure, fault.

However, GIN posting trees are ordered by ItemPointer and this makes some
specific. If you have freshly created table and do inserts/updates they
would use the end of heap. Thus, inserts would go to the end of GIN posting
tree and fillfactor wouldn't affect anything. Fillfactor would give
benefits on HOT or heap space re-usage.

In the following example you can see that index size was increased greatly
while updating every 20th row. It's because every update causes page split
in index.

# create table test with (fillfactor=90) as (select id, array[1,2,3] v from
generate_series(1,1000000) id);
# create index test_idx100 on test using gin(v) with (fillfactor=100,
fastupdate=off);
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼─────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx100 │ index │ smagen │ test │ *3184 kB* │

# update test set v = array[1,2] where id%20 = 0;
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼─────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx100 │ index │ smagen │ test │ *5264 kB* │
(1 row)

But if we create index with fillfactor=90, index size would remain the
same: no page splits.

# create table test with (fillfactor=90) as (select id, array[1,2,3] v from
generate_series(1,1000000) id);
# create index test_idx90 on test using gin(v) with (fillfactor=90,
fastupdate=off);
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx90 │ index │ smagen │ test │ *3520 kB* │

# update test set v = array[1,2] where id%20 = 0;
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx90 │ index │ smagen │ test │ *3520 kB* │
(1 row)

Similar situation would be if we use fastupdate. But fastupdate takes some
space for pending lists which is independent from fillfactor.

# create table test with (fillfactor=90) as (select id, array[1,2,3] v from
generate_series(1,1000000) id);
# create index test_idx100 on test using gin(v) with (fillfactor=100,
fastupdate=on);
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼─────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx100 │ index │ smagen │ test │ *3184 kB* │

# update test set v = array[1,2] where id%20 = 0;
# vacuum test;
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼─────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx100 │ index │ smagen │ test │ *7256 kB* │

# create table test with (fillfactor=90) as (select id, array[1,2,3] v from
generate_series(1,1000000) id);
# create index test_idx100 on test using gin(v) with (fillfactor=90,
fastupdate=on);
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼─────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx100 │ index │ smagen │ test │ *3520 kB* │

# update test set v = array[1,2] where id%20 = 0;
# vacuum test;
# \di+
List of relations
Schema │ Name │ Type │ Owner │ Table │ Size │ Description
────────┼─────────────┼───────┼────────┼───────┼─────────┼─────────────
public │ test_idx100 │ index │ smagen │ test │ *5512 kB* │

BTW, previous version of patch contained some bugs. Revised version is
attached.

------
With best regards,
Alexander Korotkov.

On Sat, Jan 17, 2015 at 12:49 PM, Alexander Korotkov <aekorotkov(at)gmail(dot)com>
wrote:

> BTW, previous version of patch contained some bugs. Revised version is
> attached.
>

Ooops, it's here.

------
With best regards,
Alexander Korotkov.

On Sat, Jan 17, 2015 at 4:49 AM, Alexander Korotkov
<aekorotkov(at)gmail(dot)com> wrote:
> I already wrote quite detailed explanation of subject. Let mel try to
> explain in shortly. GIN is two level nested btree. Thus, GIN would have
> absolutely same benefits from fillfactor as btree. Lack of tests showing it
> is, for sure, fault.
>
> However, GIN posting trees are ordered by ItemPointer and this makes some
> specific. If you have freshly created table and do inserts/updates they
> would use the end of heap. Thus, inserts would go to the end of GIN posting
> tree and fillfactor wouldn't affect anything. Fillfactor would give benefits
> on HOT or heap space re-usage.

Ah, OK. Those tests clarify things considerably; I see the point now.

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

Le lundi 19 janvier 2015 08:24:08 Robert Haas a écrit :
> On Sat, Jan 17, 2015 at 4:49 AM, Alexander Korotkov
>
> <aekorotkov(at)gmail(dot)com> wrote:
> > I already wrote quite detailed explanation of subject. Let mel try
> > to
> > explain in shortly. GIN is two level nested btree. Thus, GIN would
> > have absolutely same benefits from fillfactor as btree. Lack of
> > tests showing it is, for sure, fault.
> >
> > However, GIN posting trees are ordered by ItemPointer and this makes
> > some specific. If you have freshly created table and do
> > inserts/updates they would use the end of heap. Thus, inserts would
> > go to the end of GIN posting tree and fillfactor wouldn't affect
> > anything. Fillfactor would give benefits on HOT or heap space
> > re-usage.
>
> Ah, OK. Those tests clarify things considerably; I see the point now.

So I do.

Alexander said:
1) In order to have fully correct support of fillfactor in GIN we need to
rewrite GIN build algorithm.
2) Without rewriting GIN build algorithm, not much can be done with entry
tree. However, you can implement some heuristics.

The patch is 2), for the posting tree only ?

Thanks!
--
Cédric Villemain +33 (0)6 20 30 22 52
http://2ndQuadrant.fr/
PostgreSQL: Support 24x7 - Développement, Expertise et Formation

On Mon, Jan 19, 2015 at 5:46 PM, Cédric Villemain <cedric(at)2ndquadrant(dot)com>
wrote:

> Le lundi 19 janvier 2015 08:24:08 Robert Haas a écrit :
>
> > On Sat, Jan 17, 2015 at 4:49 AM, Alexander Korotkov
>
> >
>
> > <aekorotkov(at)gmail(dot)com> wrote:
>
> > > I already wrote quite detailed explanation of subject. Let mel try
>
> > > to
>
> > > explain in shortly. GIN is two level nested btree. Thus, GIN would
>
> > > have absolutely same benefits from fillfactor as btree. Lack of
>
> > > tests showing it is, for sure, fault.
>
> > >
>
> > > However, GIN posting trees are ordered by ItemPointer and this makes
>
> > > some specific. If you have freshly created table and do
>
> > > inserts/updates they would use the end of heap. Thus, inserts would
>
> > > go to the end of GIN posting tree and fillfactor wouldn't affect
>
> > > anything. Fillfactor would give benefits on HOT or heap space
>
> > > re-usage.
>
> >
>
> > Ah, OK. Those tests clarify things considerably; I see the point now.
>
>
>
> So I do.
>
>
>
> Alexander said:
>
> 1) In order to have fully correct support of fillfactor in GIN we need to
> rewrite GIN build algorithm.
>
> 2) Without rewriting GIN build algorithm, not much can be done with entry
> tree. However, you can implement some heuristics.
>
>
>
> The patch is 2), for the posting tree only ?
>

Yes, it's just for posting tree.

------
With best regards,
Alexander Korotkov.

Le samedi 17 janvier 2015 08:23:44 Michael Paquier a écrit :
> On Sat, Jan 17, 2015 at 2:40 AM, Robert Haas
<robertmhaas(at)gmail(dot)com> wrote:
> > There's only value in adding a fillfactor parameter to GIN indexes
> > if
> > it improves performance. There are no benchmarks showing it does.
> > So, why are we still talking about this?
>
> Indeed. There is no such benchmark as of now, and I am not sure I'll
> get the time to work more on that soon, so let's reject the patch for
> now. And sorry for the useless noise.

Michael, I first didn't understood how GiN can benefits from the
patch...thus my question.
There were no noise for me, and I learn some more about GiN. So I thank
you for your work!

--
Cédric Villemain +33 (0)6 20 30 22 52
http://2ndQuadrant.fr/
PostgreSQL: Support 24x7 - Développement, Expertise et Formation

On Tue, Jan 20, 2015 at 12:06 AM, Cédric Villemain
<cedric(at)2ndquadrant(dot)com> wrote:
> Michael, I first didn't understood how GiN can benefits from the
> patch...thus my question.
>
> There were no noise for me, and I learn some more about GiN. So I thank you
> for your work!
Kicking back the ball, I haven't done as much work as I should have.
Alexander, I think that we should continue on this patch in the next
CF. Are you fine if an entry is added with you as author. I'll drop
myself as author (not that I cannot find the time, just that I am sort
of useless).
--
Michael

Hi,

I've been wondering whether this might improve behavior with one of my
workloads, suffering by GIN bloat - the same one I used to test GIN
fastscan, for example.

It's a batch process that loads a mailing list archive into a table with
a GIN index on message body, by doing something like this:

for file in files:
BEGIN;
for message in file:

SAVEPOINT s;
INSERT INTO messages VALUES (...)

if error:
ROLLBACK TO s;

COMMIT;

And there are multiple processes, each processing subset of mbox files.

There are ~1M messages and right after the load I see this:

List of relations
Schema | Name | Type | Owner | Table | Size
--------+------------------+-------+-------+----------+---------
public | message_body_idx | index | tomas | messages | 2247 MB
(1 row)

and after VACUUM FULL:

List of relations
Schema | Name | Type | Owner | Table | Size
--------+------------------+-------+-------+----------+---------
public | message_body_idx | index | tomas | messages | 403 MB
(1 row)

So the index is ~5x larger, which is probably expected due to the amount
of random inserts within a very short time (~15 minutes), executed in
parallel.

I hoped lowering the fillfactor will improve this, but fillfactor=75 had
pretty much no effect in this case. Is that expected for this kind of
workload? I see the previous discussion talked about random updates, not
inserts, so maybe that's the culprit?

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

On Tue, Feb 24, 2015 at 5:15 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> I hoped lowering the fillfactor will improve this, but fillfactor=75 had
> pretty much no effect in this case. Is that expected for this kind of
> workload? I see the previous discussion talked about random updates, not
> inserts, so maybe that's the culprit?
>

Yes. Since posting trees are ordered by item pointers, you can get benefit
of fillfactor only if you use some item pointers lower than item pointers
already in use. You can still get benefit in the insert case but you should
have already some free space in the heap (perhaps do some deletes and
vacuum).

Actually, this is narrowing benefit from GIN fillfactor. Probably, that
means that we should still have default value of 100. But I think GIN
fillfactor still might be useful.

------
With best regards,
Alexander Korotkov.

On 25.2.2015 10:20, Alexander Korotkov wrote:
> On Tue, Feb 24, 2015 at 5:15 PM, Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>> wrote:
>
>> I hoped lowering the fillfactor will improve this, but
>> fillfactor=75 had pretty much no effect in this case. Is that
>> expected for this kind of workload? I see the previous discussion
>> talked about random updates, not inserts, so maybe that's the
>> culprit?
>
>
> Yes. Since posting trees are ordered by item pointers, you can get
> benefit of fillfactor only if you use some item pointers lower than
> item pointers already in use. You can still get benefit in the insert
> case but you should have already some free space in the heap (perhaps
> do some deletes and vacuum).

OK, understood. Thanks for the explanation.

> Actually, this is narrowing benefit from GIN fillfactor. Probably,
> that means that we should still have default value of 100. But I
> think GIN fillfactor still might be useful.

I'm not sure about that. It's true that lowering fillfactor to 90 does
not help this particular workload, but it does not hurt it either. For
other common workloads (updating the values, not just inserting them),
lowering the fillfactor to 90 may easily be a big improvement.

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

In dataPlaceToPageLeaf-function:

> if (append)
> {
> /*
> * Even when appending, trying to append more items than will fit is
> * not completely free, because we will merge the new items and old
> * items into an array below. In the best case, every new item fits in
> * a single byte, and we can use all the free space on the old page as
> * well as the new page. For simplicity, ignore segment overhead etc.
> */
> maxitems = Min(maxitems, freespace + GinDataPageMaxDataSize);
> }

Hmm. So after splitting the page, there is freespace +
GinDataPageMaxDataSize bytes available on both pages together. freespace
has been adjusted with the fillfactor, but GinDataPageMaxDataSize is
not. So this overshoots, because when leafRepackItems actually
distributes the segments on the pages, it will fill both pages only up
to the fillfactor. This is an upper bound, so that's harmless, it only
leads to some unnecessary work in dealing with the item lists. But I
think that should be:

maxitems = Min(maxitems, freespace + leaf->maxdatasize);

> else
> {
> /*
> * Calculate a conservative estimate of how many new items we can fit
> * on the two pages after splitting.
> *
> * We can use any remaining free space on the old page to store full
> * segments, as well as the new page. Each full-sized segment can hold
> * at least MinTuplesPerSegment items
> */
> int nnewsegments;
>
> nnewsegments = freespace / GinPostingListSegmentMaxSize;
> nnewsegments += GinDataPageMaxDataSize / GinPostingListSegmentMaxSize;
> maxitems = Min(maxitems, nnewsegments * MinTuplesPerSegment);
> }

This branch makes the same mistake, but this is calculating a lower
bound. It's important that maxitems is not set to higher value than what
actually fits on the page, otherwise you can get an ERROR later in the
function, when it turns out that not all the items actually fit on the
page. The saving grace here is that this branch is never taken when
building a new index, because index build inserts all the TIDs in order,
but that seems pretty fragile. Should use leaf->maxdatasize instead of
GinDataPageMaxDataSize here too.

But that can lead to funny things, if fillfactor is small, and BLCKSZ is
small too. With the minimums, BLCKSZ=1024 and fillfactor=0.2, the above
formula will set nnewsegments to zero. That's not going to end up well.
The problem is that maxdatasize becomes smaller than
GinPostingListSegmentMaxSize, which is a problem. I think
GinGetMaxDataSize() needs to make sure that the returned value is always
>= GinPostingListSegmentMaxSize.

Now that we have a fillfactor, shouldn't we replace the 75% heuristic
later in that function, when inserting to the rightmost page rather than
building it from scratch? In B-tree, the fillfactor is applied to that
case too.

- Heikki

Hi!

On Wed, Jul 8, 2015 at 10:27 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:

> In dataPlaceToPageLeaf-function:
>
> if (append)
>> {
>> /*
>> * Even when appending, trying to append more items than
>> will fit is
>> * not completely free, because we will merge the new
>> items and old
>> * items into an array below. In the best case, every new
>> item fits in
>> * a single byte, and we can use all the free space on
>> the old page as
>> * well as the new page. For simplicity, ignore segment
>> overhead etc.
>> */
>> maxitems = Min(maxitems, freespace +
>> GinDataPageMaxDataSize);
>> }
>>
>
> Hmm. So after splitting the page, there is freespace +
> GinDataPageMaxDataSize bytes available on both pages together. freespace
> has been adjusted with the fillfactor, but GinDataPageMaxDataSize is not.
> So this overshoots, because when leafRepackItems actually distributes the
> segments on the pages, it will fill both pages only up to the fillfactor.
> This is an upper bound, so that's harmless, it only leads to some
> unnecessary work in dealing with the item lists. But I think that should be:
>
> maxitems = Min(maxitems, freespace + leaf->maxdatasize);
>

Good catch! Fixed.

>
> else
>> {
>> /*
>> * Calculate a conservative estimate of how many new
>> items we can fit
>> * on the two pages after splitting.
>> *
>> * We can use any remaining free space on the old page to
>> store full
>> * segments, as well as the new page. Each full-sized
>> segment can hold
>> * at least MinTuplesPerSegment items
>> */
>> int nnewsegments;
>>
>> nnewsegments = freespace / GinPostingListSegmentMaxSize;
>> nnewsegments += GinDataPageMaxDataSize /
>> GinPostingListSegmentMaxSize;
>> maxitems = Min(maxitems, nnewsegments *
>> MinTuplesPerSegment);
>> }
>>
>
> This branch makes the same mistake, but this is calculating a lower bound.
> It's important that maxitems is not set to higher value than what actually
> fits on the page, otherwise you can get an ERROR later in the function,
> when it turns out that not all the items actually fit on the page. The
> saving grace here is that this branch is never taken when building a new
> index, because index build inserts all the TIDs in order, but that seems
> pretty fragile. Should use leaf->maxdatasize instead of
> GinDataPageMaxDataSize here too.
>

Fixed.

> But that can lead to funny things, if fillfactor is small, and BLCKSZ is
> small too. With the minimums, BLCKSZ=1024 and fillfactor=0.2, the above
> formula will set nnewsegments to zero. That's not going to end up well. The
> problem is that maxdatasize becomes smaller than
> GinPostingListSegmentMaxSize, which is a problem. I think
> GinGetMaxDataSize() needs to make sure that the returned value is always >=
> GinPostingListSegmentMaxSize.
>

Fixed.

> Now that we have a fillfactor, shouldn't we replace the 75% heuristic
> later in that function, when inserting to the rightmost page rather than
> building it from scratch? In B-tree, the fillfactor is applied to that case
> too.

Sounds reasonable. Now it works like btree.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Thu, Jul 9, 2015 at 10:33 PM, Alexander Korotkov wrote:
> [...]

+ /* Caclculate max data size on page according to fillfactor */
s/Caclculate/Calculate

When creating a simple gin index, I am seeing that GinGetMaxDataSize gets
called with ginEntryInsert:
* frame #0: 0x000000010a49d72e
postgres`GinGetMaxDataSize(index=0x0000000114168378, isBuild='\x01') + 14
at gindatapage.c:436
frame #1: 0x000000010a49ecbe
postgres`createPostingTree(index=0x0000000114168378,
items=0x0000000114a9c038, nitems=35772, buildStats=0x00007fff55787350) +
302 at gindatapage.c:1754
frame #2: 0x000000010a493423
postgres`buildFreshLeafTuple(ginstate=0x00007fff55784d90, attnum=1,
key=2105441, category='\0', items=0x0000000114a9c038, nitem=35772,
buildStats=0x00007fff55787350) + 339 at gininsert.c:158
frame #3: 0x000000010a492f84
postgres`ginEntryInsert(ginstate=0x00007fff55784d90, attnum=1, key=2105441,
category='\0', items=0x0000000114a9c038, nitem=35772,
buildStats=0x00007fff55787350) + 916 at gininsert.c:228

And as far as I can see GinGetMaxDataSize uses isBuild:
+ int
+ GinGetMaxDataSize(Relation index, bool isBuild)
+ {
+ int fillfactor, result;
+
+ /* Grab option value which affects only index build */
+ if (!isBuild)
However isBuild is not set in this code path, see
http://www.postgresql.org/message-id/CAB7nPqSc4VQ9mHKqm_YvAfcTEhO-iUY8SKbXYdnMGnAi1XnPaw@mail.gmail.com
where I reported the problem. So this code is somewhat broken, no? I am
attaching to this email the patch in question that should be applied on top
of Alexander's latest version.

+ #define GIN_MIN_FILLFACTOR 20
+ #define GIN_DEFAULT_FILLFACTOR 90
I am still worrying about using a default fillfactor at 90, as we did a lot
of promotion about compression of GIN indexes in 9.4. Feel free to ignore
this comment if you think that 90 is a good default. The difference is
visibly in order of MBs even for large indexes still, this is changing the
default of 9.4 and 9.5.
Regards,
--
Michael

On Fri, Jul 10, 2015 at 4:54 AM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
wrote:

>
>
> On Thu, Jul 9, 2015 at 10:33 PM, Alexander Korotkov wrote:
> > [...]
>
> + /* Caclculate max data size on page according to fillfactor */
> s/Caclculate/Calculate
>
> When creating a simple gin index, I am seeing that GinGetMaxDataSize gets
> called with ginEntryInsert:
> * frame #0: 0x000000010a49d72e
> postgres`GinGetMaxDataSize(index=0x0000000114168378, isBuild='\x01') + 14
> at gindatapage.c:436
> frame #1: 0x000000010a49ecbe
> postgres`createPostingTree(index=0x0000000114168378,
> items=0x0000000114a9c038, nitems=35772, buildStats=0x00007fff55787350) +
> 302 at gindatapage.c:1754
> frame #2: 0x000000010a493423
> postgres`buildFreshLeafTuple(ginstate=0x00007fff55784d90, attnum=1,
> key=2105441, category='\0', items=0x0000000114a9c038, nitem=35772,
> buildStats=0x00007fff55787350) + 339 at gininsert.c:158
> frame #3: 0x000000010a492f84
> postgres`ginEntryInsert(ginstate=0x00007fff55784d90, attnum=1, key=2105441,
> category='\0', items=0x0000000114a9c038, nitem=35772,
> buildStats=0x00007fff55787350) + 916 at gininsert.c:228
>
> And as far as I can see GinGetMaxDataSize uses isBuild:
> + int
> + GinGetMaxDataSize(Relation index, bool isBuild)
> + {
> + int fillfactor, result;
> +
> + /* Grab option value which affects only index build */
> + if (!isBuild)
> However isBuild is not set in this code path, see
> http://www.postgresql.org/message-id/CAB7nPqSc4VQ9mHKqm_YvAfcTEhO-iUY8SKbXYdnMGnAi1XnPaw@mail.gmail.com
> where I reported the problem. So this code is somewhat broken, no? I am
> attaching to this email the patch in question that should be applied on top
> of Alexander's latest version.
>

I didn't get what is problem. Was this stacktrace during index build? If
so, GinGetMaxDataSize really should get isBuild='\x01'. It is set by
following line

maxdatasize = GinGetMaxDataSize(index, buildStats ? true: false);

> + #define GIN_MIN_FILLFACTOR 20
> + #define GIN_DEFAULT_FILLFACTOR 90
> I am still worrying about using a default fillfactor at 90, as we did a
> lot of promotion about compression of GIN indexes in 9.4. Feel free to
> ignore this comment if you think that 90 is a good default. The difference
> is visibly in order of MBs even for large indexes still, this is changing
> the default of 9.4 and 9.5.
>

On the other side, it's unclear why should we have fillfactor distinct from
btree..

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 07/10/2015 01:13 PM, Alexander Korotkov wrote:
> On Fri, Jul 10, 2015 at 4:54 AM, Michael Paquier <michael(dot)paquier(at)gmail(dot)com>
> wrote:
>> + #define GIN_MIN_FILLFACTOR 20
>> + #define GIN_DEFAULT_FILLFACTOR 90
>> I am still worrying about using a default fillfactor at 90, as we did a
>> lot of promotion about compression of GIN indexes in 9.4. Feel free to
>> ignore this comment if you think that 90 is a good default. The difference
>> is visibly in order of MBs even for large indexes still, this is changing
>> the default of 9.4 and 9.5.
>
> On the other side, it's unclear why should we have fillfactor distinct from
> btree..

Good question. One argument is because the items on a GIN posting page
are much smaller (2-3 bytes typically) than index tuples in a B-tree
page (32 bytes or more). By a rough calculation, in the 10% free space
you leave in an index page, which is about 800 bytes, you can insert at
most 25 or so tuples. In the same amount of free space in a GIN page,
you can fit hundreds items. The fillfactor is particularly useful to
avoid splitting a lot pages after creating a new index, when you do a
few random updates.

Another argument is that for the typical use cases of GIN, tuples are
not updated as often as with B-tree indexes.

A third argument is that before this patch, we always packed the index
as full as possible (i.e. fillfactor=100), and we want to avoid
"changing the default" so much.

I'm not sure any of those arguments are very strong, but my gut feeling
is that 90 might indeed be too small. Perhaps set the default to 95..

I'm curious why the minimum in the patch is 20, while the minimum for
b-tree is 10, though. I don't see any particularly good reason for that.

- Heikki

On Fri, Jul 10, 2015 at 7:13 PM, Alexander Korotkov <aekorotkov(at)gmail(dot)com>
wrote:

> On Fri, Jul 10, 2015 at 4:54 AM, Michael Paquier <
> michael(dot)paquier(at)gmail(dot)com> wrote:
>
>>
>>
>> On Thu, Jul 9, 2015 at 10:33 PM, Alexander Korotkov wrote:
>> > [...]
>>
>> + /* Caclculate max data size on page according to fillfactor */
>> s/Caclculate/Calculate
>>
>> When creating a simple gin index, I am seeing that GinGetMaxDataSize gets
>> called with ginEntryInsert:
>> * frame #0: 0x000000010a49d72e
>> postgres`GinGetMaxDataSize(index=0x0000000114168378, isBuild='\x01') + 14
>> at gindatapage.c:436
>> frame #1: 0x000000010a49ecbe
>> postgres`createPostingTree(index=0x0000000114168378,
>> items=0x0000000114a9c038, nitems=35772, buildStats=0x00007fff55787350) +
>> 302 at gindatapage.c:1754
>> frame #2: 0x000000010a493423
>> postgres`buildFreshLeafTuple(ginstate=0x00007fff55784d90, attnum=1,
>> key=2105441, category='\0', items=0x0000000114a9c038, nitem=35772,
>> buildStats=0x00007fff55787350) + 339 at gininsert.c:158
>> frame #3: 0x000000010a492f84
>> postgres`ginEntryInsert(ginstate=0x00007fff55784d90, attnum=1, key=2105441,
>> category='\0', items=0x0000000114a9c038, nitem=35772,
>> buildStats=0x00007fff55787350) + 916 at gininsert.c:228
>>
>> And as far as I can see GinGetMaxDataSize uses isBuild:
>> + int
>> + GinGetMaxDataSize(Relation index, bool isBuild)
>> + {
>> + int fillfactor, result;
>> +
>> + /* Grab option value which affects only index build */
>> + if (!isBuild)
>> However isBuild is not set in this code path, see
>> http://www.postgresql.org/message-id/CAB7nPqSc4VQ9mHKqm_YvAfcTEhO-iUY8SKbXYdnMGnAi1XnPaw@mail.gmail.com
>> where I reported the problem. So this code is somewhat broken, no? I am
>> attaching to this email the patch in question that should be applied on top
>> of Alexander's latest version.
>>
>
> I didn't get what is problem. Was this stacktrace during index build? If
> so, GinGetMaxDataSize really should get isBuild='\x01'. It is set by
> following line
>
> maxdatasize = GinGetMaxDataSize(index, buildStats ? true: false);
>

Yeah, I just find confusing that we actually rely on the fact that
buildStats is NULL or not here instead of passing directly the isBuild flag
of GinBtree for example. But that's a point of detail..
--
Michael

Has anyone done any performance testing of this?

The purpose of a fillfactor is to avoid the storm of page splits right
after building the index, when there are some random updates to the
table. It causes the index to bloat, as every full page is split to two
half-full pages, and also adds latency to all the updates that have to
split pages.

As the code stands, do we actually have such a problem with GIN? Let's
investigate. Let's create a little test table:

create table foo (id int4, t text);
insert into foo select g, 'foo' from generate_series(1, 1000000) g;

And some indexes on it:

-- B-tree index on id, 100%
create index btree_100 on foo (id) with (fillfactor=100);
-- B-tree index on id, 90% (which is the default)
create index btree_90 on foo (id) with (fillfactor=90);
-- GIN index on id. Id is different on each row, so this index has no
posting trees, just the entry tree.
create index gin_id on foo using gin (id) with (fastupdate=off);
-- GIN index on t. T is the same on each row, so this index consists of
a single posting tree.
create index gin_t on foo using gin (t) with (fastupdate=off);

Immediately after creation, the index sizes are:

postgres=# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+-----------+-------+--------+-------+---------+-------------
public | btree_100 | index | heikki | foo | 19 MB |
public | btree_90 | index | heikki | foo | 21 MB |
public | gin_id | index | heikki | foo | 53 MB |
public | gin_t | index | heikki | foo | 1072 kB |
(4 rows)

Now let's update 1% of the table, spread evenly across the table, and
see what happens to the index sizes:

postgres=# update foo set id = id where id % 100 = 0;
UPDATE 10000
postgres=# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+-----------+-------+--------+-------+---------+-------------
public | btree_100 | index | heikki | foo | 39 MB |
public | btree_90 | index | heikki | foo | 21 MB |
public | gin_id | index | heikki | foo | 53 MB |
public | gin_t | index | heikki | foo | 1080 kB |
(4 rows)

As you can see, btree_100 index doubled in size. That's the effect we're
trying to avoid with the fillfactor, and indeed in the btree_90 index it
was avoided. However, the GIN indexes are not bloated either. Why is that?

The entry tree (demonstrated by the gin_id index) is not packed tightly
when it's built. If anything, we could pack it more tightly to make it
smaller to begin with. For the use cases where GIN works best, though,
the entry tree should be fairly small compared to the posting lists, so
it shouldn't make a big difference. For the posting tree, I think that's
because the way the items are packed in the segments. Even though we
pack the segments as tightly as possible, there is always some free
space left over on a page that's not enough to add another segment to it
at index build, but can be used by the updates to add items to the
existing segments. So in practice you always end up with some free space
on the posting tree pages, even without a fillfactor, so the "effective
fillfactor" even today is not actually 100%.

Based on this, I think we should just drop this patch. It's not useful
in practice.

- Heikki

On Tue, Jul 21, 2015 at 12:40 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>
wrote:

> Has anyone done any performance testing of this?
>
> The purpose of a fillfactor is to avoid the storm of page splits right
> after building the index, when there are some random updates to the table.
> It causes the index to bloat, as every full page is split to two half-full
> pages, and also adds latency to all the updates that have to split pages.
>
> As the code stands, do we actually have such a problem with GIN? Let's
> investigate. Let's create a little test table:
>
> create table foo (id int4, t text);
> insert into foo select g, 'foo' from generate_series(1, 1000000) g;
>
> And some indexes on it:
>
> -- B-tree index on id, 100%
> create index btree_100 on foo (id) with (fillfactor=100);
> -- B-tree index on id, 90% (which is the default)
> create index btree_90 on foo (id) with (fillfactor=90);
> -- GIN index on id. Id is different on each row, so this index has no
> posting trees, just the entry tree.
> create index gin_id on foo using gin (id) with (fastupdate=off);
> -- GIN index on t. T is the same on each row, so this index consists of a
> single posting tree.
> create index gin_t on foo using gin (t) with (fastupdate=off);
>
> Immediately after creation, the index sizes are:
>
> postgres=# \di+
> List of relations
> Schema | Name | Type | Owner | Table | Size | Description
> --------+-----------+-------+--------+-------+---------+-------------
> public | btree_100 | index | heikki | foo | 19 MB |
> public | btree_90 | index | heikki | foo | 21 MB |
> public | gin_id | index | heikki | foo | 53 MB |
> public | gin_t | index | heikki | foo | 1072 kB |
> (4 rows)
>
>
> Now let's update 1% of the table, spread evenly across the table, and see
> what happens to the index sizes:
>
> postgres=# update foo set id = id where id % 100 = 0;
> UPDATE 10000
> postgres=# \di+
> List of relations
> Schema | Name | Type | Owner | Table | Size | Description
> --------+-----------+-------+--------+-------+---------+-------------
> public | btree_100 | index | heikki | foo | 39 MB |
> public | btree_90 | index | heikki | foo | 21 MB |
> public | gin_id | index | heikki | foo | 53 MB |
> public | gin_t | index | heikki | foo | 1080 kB |
> (4 rows)
>
> As you can see, btree_100 index doubled in size. That's the effect we're
> trying to avoid with the fillfactor, and indeed in the btree_90 index it
> was avoided. However, the GIN indexes are not bloated either. Why is that?
>
> The entry tree (demonstrated by the gin_id index) is not packed tightly
> when it's built. If anything, we could pack it more tightly to make it
> smaller to begin with. For the use cases where GIN works best, though, the
> entry tree should be fairly small compared to the posting lists, so it
> shouldn't make a big difference. For the posting tree, I think that's
> because the way the items are packed in the segments. Even though we pack
> the segments as tightly as possible, there is always some free space left
> over on a page that's not enough to add another segment to it at index
> build, but can be used by the updates to add items to the existing
> segments. So in practice you always end up with some free space on the
> posting tree pages, even without a fillfactor, so the "effective
> fillfactor" even today is not actually 100%.
>

There are two reasons of this behavior. You mentioned the first one:
"effective fillfactor" for posting lists is not 100%. But the second one is
structure of posting lists. In your example UPDATE allocates new tuple at
the end of heap. So, from the point of posting lists these updates are
appends. Situation is different when you reuse space in the heap. See an
example.

drop table foo;
create table foo (id integer, val int[]) with (fillfactor = 90);
insert into foo (select g, array[g%2]::int[] from
generate_series(1,1000000) g);
create index foo_val_idx_100 on foo using gin(val) with (fastupdate=off,
fillfactor=100);
create index foo_val_idx_90 on foo using gin(val) with (fastupdate=off,
fillfactor=90);

# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+-----------------+-------+--------+-------+---------+-------------
public | foo_val_idx_100 | index | smagen | foo | 1088 kB |
public | foo_val_idx_90 | index | smagen | foo | 1200 kB |
(2 rows)

update foo set val = array[(id+1)%2]::int[] where id % 50 = 0;

# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+-----------------+-------+--------+-------+---------+-------------
public | foo_val_idx_100 | index | smagen | foo | 1608 kB |
public | foo_val_idx_90 | index | smagen | foo | 1200 kB |
(2 rows)

Based on this, I think we should just drop this patch. It's not useful in
> practice.

I wouldn't say it's not useful at all. It's for sure not as useful as btree
fillfactor, but it still could be useful in some cases...
Probably, we could leave 100 as default fillfactor, but provide an option.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 07/21/2015 02:00 PM, Alexander Korotkov wrote:
> On Tue, Jul 21, 2015 at 12:40 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>
> wrote:
>
>> Has anyone done any performance testing of this?
>>
>> The purpose of a fillfactor is to avoid the storm of page splits right
>> after building the index, when there are some random updates to the table.
>> It causes the index to bloat, as every full page is split to two half-full
>> pages, and also adds latency to all the updates that have to split pages.
>>
>> As the code stands, do we actually have such a problem with GIN? Let's
>> investigate. Let's create a little test table:
>>
>> create table foo (id int4, t text);
>> insert into foo select g, 'foo' from generate_series(1, 1000000) g;
>>
>> And some indexes on it:
>>
>> -- B-tree index on id, 100%
>> create index btree_100 on foo (id) with (fillfactor=100);
>> -- B-tree index on id, 90% (which is the default)
>> create index btree_90 on foo (id) with (fillfactor=90);
>> -- GIN index on id. Id is different on each row, so this index has no
>> posting trees, just the entry tree.
>> create index gin_id on foo using gin (id) with (fastupdate=off);
>> -- GIN index on t. T is the same on each row, so this index consists of a
>> single posting tree.
>> create index gin_t on foo using gin (t) with (fastupdate=off);
>>
>> Immediately after creation, the index sizes are:
>>
>> postgres=# \di+
>> List of relations
>> Schema | Name | Type | Owner | Table | Size | Description
>> --------+-----------+-------+--------+-------+---------+-------------
>> public | btree_100 | index | heikki | foo | 19 MB |
>> public | btree_90 | index | heikki | foo | 21 MB |
>> public | gin_id | index | heikki | foo | 53 MB |
>> public | gin_t | index | heikki | foo | 1072 kB |
>> (4 rows)
>>
>>
>> Now let's update 1% of the table, spread evenly across the table, and see
>> what happens to the index sizes:
>>
>> postgres=# update foo set id = id where id % 100 = 0;
>> UPDATE 10000
>> postgres=# \di+
>> List of relations
>> Schema | Name | Type | Owner | Table | Size | Description
>> --------+-----------+-------+--------+-------+---------+-------------
>> public | btree_100 | index | heikki | foo | 39 MB |
>> public | btree_90 | index | heikki | foo | 21 MB |
>> public | gin_id | index | heikki | foo | 53 MB |
>> public | gin_t | index | heikki | foo | 1080 kB |
>> (4 rows)
>>
>> As you can see, btree_100 index doubled in size. That's the effect we're
>> trying to avoid with the fillfactor, and indeed in the btree_90 index it
>> was avoided. However, the GIN indexes are not bloated either. Why is that?
>>
>> The entry tree (demonstrated by the gin_id index) is not packed tightly
>> when it's built. If anything, we could pack it more tightly to make it
>> smaller to begin with. For the use cases where GIN works best, though, the
>> entry tree should be fairly small compared to the posting lists, so it
>> shouldn't make a big difference. For the posting tree, I think that's
>> because the way the items are packed in the segments. Even though we pack
>> the segments as tightly as possible, there is always some free space left
>> over on a page that's not enough to add another segment to it at index
>> build, but can be used by the updates to add items to the existing
>> segments. So in practice you always end up with some free space on the
>> posting tree pages, even without a fillfactor, so the "effective
>> fillfactor" even today is not actually 100%.
>>
>
> There are two reasons of this behavior. You mentioned the first one:
> "effective fillfactor" for posting lists is not 100%. But the second one is
> structure of posting lists. In your example UPDATE allocates new tuple at
> the end of heap. So, from the point of posting lists these updates are
> appends.

Ah, good point.

> Situation is different when you reuse space in the heap. See an
> example.
>
> drop table foo;
> create table foo (id integer, val int[]) with (fillfactor = 90);
> insert into foo (select g, array[g%2]::int[] from
> generate_series(1,1000000) g);
> create index foo_val_idx_100 on foo using gin(val) with (fastupdate=off,
> fillfactor=100);
> create index foo_val_idx_90 on foo using gin(val) with (fastupdate=off,
> fillfactor=90);
>
> # \di+
> List of relations
> Schema | Name | Type | Owner | Table | Size | Description
> --------+-----------------+-------+--------+-------+---------+-------------
> public | foo_val_idx_100 | index | smagen | foo | 1088 kB |
> public | foo_val_idx_90 | index | smagen | foo | 1200 kB |
> (2 rows)
>
> update foo set val = array[(id+1)%2]::int[] where id % 50 = 0;
>
> # \di+
> List of relations
> Schema | Name | Type | Owner | Table | Size | Description
> --------+-----------------+-------+--------+-------+---------+-------------
> public | foo_val_idx_100 | index | smagen | foo | 1608 kB |
> public | foo_val_idx_90 | index | smagen | foo | 1200 kB |
> (2 rows)

Hmm. That's slightly different from the test case I used, in that the
update is changing the indexed value, which means that the new value
goes to different posting tree than the old one. I'm not sure if that
makes any difference. You're also updating more rows, 1/50 vs. 1/100.

This case is closer to my earlier one:

postgres=# create table foo (id int4, i int4, t text) with (fillfactor=90);
CREATE TABLE
postgres=# insert into foo select g, 1 from generate_series(1, 1000000) g;
INSERT 0 1000000
postgres=# create index btree_foo_id on foo (id); -- to force non-HOT
updates
CREATE INDEX
postgres=# create index gin_i on foo using gin (i) with (fastupdate=off);
CREATE INDEX
postgres=# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+--------------+-------+--------+-------+---------+-------------
public | btree_foo_id | index | heikki | foo | 21 MB |
public | gin_i | index | heikki | foo | 1072 kB |
(2 rows)

postgres=# update foo set id=-id where id % 100 = 0;
UPDATE 10000
postgres=# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+--------------+-------+--------+-------+---------+-------------
public | btree_foo_id | index | heikki | foo | 22 MB |
public | gin_i | index | heikki | foo | 1080 kB |
(2 rows)

I'm not sure what's making the difference to your test case. Could be
simply that your case happens to leave less free space on each page,
because of the different data.

>> Based on this, I think we should just drop this patch. It's not useful in
>> practice.
>
> I wouldn't say it's not useful at all. It's for sure not as useful as btree
> fillfactor, but it still could be useful in some cases...
> Probably, we could leave 100 as default fillfactor, but provide an option.

Doesn't seem worth the trouble to me...

- Heikki

On Tue, Jul 21, 2015 at 2:49 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:

> Hmm. That's slightly different from the test case I used, in that the
> update is changing the indexed value, which means that the new value goes
> to different posting tree than the old one. I'm not sure if that makes any
> difference. You're also updating more rows, 1/50 vs. 1/100.
>
> This case is closer to my earlier one:
>
> postgres=# create table foo (id int4, i int4, t text) with (fillfactor=90);
> CREATE TABLE
> postgres=# insert into foo select g, 1 from generate_series(1, 1000000) g;
> INSERT 0 1000000
> postgres=# create index btree_foo_id on foo (id); -- to force non-HOT
> updates
> CREATE INDEX
> postgres=# create index gin_i on foo using gin (i) with (fastupdate=off);
> CREATE INDEX
> postgres=# \di+
> List of relations
> Schema | Name | Type | Owner | Table | Size | Description
> --------+--------------+-------+--------+-------+---------+-------------
> public | btree_foo_id | index | heikki | foo | 21 MB |
> public | gin_i | index | heikki | foo | 1072 kB |
> (2 rows)
>
> postgres=# update foo set id=-id where id % 100 = 0;
> UPDATE 10000
> postgres=# \di+
> List of relations
> Schema | Name | Type | Owner | Table | Size | Description
> --------+--------------+-------+--------+-------+---------+-------------
> public | btree_foo_id | index | heikki | foo | 22 MB |
> public | gin_i | index | heikki | foo | 1080 kB |
> (2 rows)
>
> I'm not sure what's making the difference to your test case. Could be
> simply that your case happens to leave less free space on each page,
> because of the different data.

Yeah, it's likely because of different data.

Based on this, I think we should just drop this patch. It's not useful in
>>> practice.
>>>
>>
>> I wouldn't say it's not useful at all. It's for sure not as useful as
>> btree
>> fillfactor, but it still could be useful in some cases...
>> Probably, we could leave 100 as default fillfactor, but provide an option.
>>
>
> Doesn't seem worth the trouble to me...

Probably, but currently we are in quite unlogical situation. We have
default fillfactor = 90 for GiST where it has no use cases at all and
effectively is just a waste of space. On the other had we're rejecting
fillfactor for GIN where it could have at least some use cases... Should we
don't have fillfactor for both GiST and GIN?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 07/21/2015 02:56 PM, Alexander Korotkov wrote:
> Probably, but currently we are in quite unlogical situation. We have
> default fillfactor = 90 for GiST where it has no use cases at all and
> effectively is just a waste of space.

Why is it useless for GiST?
- Heikki

On Tue, Jul 21, 2015 at 3:52 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:

> On 07/21/2015 02:56 PM, Alexander Korotkov wrote:
>
>> Probably, but currently we are in quite unlogical situation. We have
>> default fillfactor = 90 for GiST where it has no use cases at all and
>> effectively is just a waste of space.
>>
>
> Why is it useless for GiST?

It's because all of GiST pages are produced by page splits. So, just after
CREATE INDEX GiST pages aren't tightly packed in average. Actually, they
could be tightly packed by incredible coincidence, but for large indexes
it's quite safe assumption that they are not. With GiST we don't have storm
of page splits after index creation with fillfactor = 100. So, why should
we reserve additional space with fillfactor = 90?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 07/21/2015 04:14 PM, Alexander Korotkov wrote:
> On Tue, Jul 21, 2015 at 3:52 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:
>
>> On 07/21/2015 02:56 PM, Alexander Korotkov wrote:
>>
>>> Probably, but currently we are in quite unlogical situation. We have
>>> default fillfactor = 90 for GiST where it has no use cases at all and
>>> effectively is just a waste of space.
>>>
>>
>> Why is it useless for GiST?
>
>
> It's because all of GiST pages are produced by page splits. So, just after
> CREATE INDEX GiST pages aren't tightly packed in average. Actually, they
> could be tightly packed by incredible coincidence, but for large indexes
> it's quite safe assumption that they are not. With GiST we don't have storm
> of page splits after index creation with fillfactor = 100. So, why should
> we reserve additional space with fillfactor = 90?

Aha, I see. Yeah, that's pretty useless. Ideally, we would make the GiST
build algorithm smarter so that it would pack the pages more tightly. I
have no idea how to do that, however.

Anyway, the fact that fillfactor is useless for GiST is more of an
argument for removing it from GiST, than for adding it to GIN.

- Heikki

On Tue, Jul 21, 2015 at 7:20 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:

> On 07/21/2015 04:14 PM, Alexander Korotkov wrote:
>
>> On Tue, Jul 21, 2015 at 3:52 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>
>> wrote:
>>
>> On 07/21/2015 02:56 PM, Alexander Korotkov wrote:
>>>
>>> Probably, but currently we are in quite unlogical situation. We have
>>>> default fillfactor = 90 for GiST where it has no use cases at all and
>>>> effectively is just a waste of space.
>>>>
>>>>
>>> Why is it useless for GiST?
>>>
>>
>>
>> It's because all of GiST pages are produced by page splits. So, just after
>> CREATE INDEX GiST pages aren't tightly packed in average. Actually, they
>> could be tightly packed by incredible coincidence, but for large indexes
>> it's quite safe assumption that they are not. With GiST we don't have
>> storm
>> of page splits after index creation with fillfactor = 100. So, why should
>> we reserve additional space with fillfactor = 90?
>>
>
> Aha, I see. Yeah, that's pretty useless. Ideally, we would make the GiST
> build algorithm smarter so that it would pack the pages more tightly. I
> have no idea how to do that, however.
>
> Anyway, the fact that fillfactor is useless for GiST is more of an
> argument for removing it from GiST, than for adding it to GIN.

Yes it is. I've just think that fillfactor is more useful for GIN than for
GiST now. However, it's probably doesn't worth it for both of them.
One of our customers complains that freshly built GIN indexes get bloat
very fast. I've asked them a test case. Using that test case I would try to
see if fillfactor for GIN could help in practice. For now we can mark it as
"Returned with feedback" where feedback is "Real life use cases needed".
Removing fillfactor for GiST is now not easy. Once it's exposed for users,
removing it completely would break compatibility. I would propose to chage
default fillfactor for GiST from 90 to 100.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company