gistchoose vs. bloat
Hackers,
While experimenting with gistchoose I achieve interesting results about
relation of gistchoose behaviour and gist index bloat.
I've created following testcase for reproducing gist index bloating:
1) Create test table with 1000000 points from geonames
# create table geotest (id serial, point point);
# insert into geotest (point) (select * from geonames order by random()
limit 1000000);
2) Create gist index and statistics table. Insert initial statistics (rows
count, index size) into table.
# create index geotest_idx on geotest using gist (point) with (buffering =
off);
# create table geotest_stats (id serial, count bigint, size bigint);
# insert into geotest_stats (count, size) values ((select count(*) from
geotest), pg_relation_size('geotest_idx'));
3) Delete 10% of geotest and vacuum it.
delete from geotest where id in (select id from geotest order by random()
limit 100000);
vacuum geotest;
4) Insert new 100000 points fromg eonames.
insert into geotest (point) (select * from geonames order by random() limit
100000);
5) Insert current statistics (rows count, index size) into table.
insert into geotest_stats (count, size) values ((select count(*) from
geotest), pg_relation_size('geotest_idx'));
6) Repeat 3-5 steps 50 times.
I get following results with current gistchoose implementation:
test=# select * from geotest1_stats;
id | count | size
----+---------+-----------
1 | 1000000 | 75767808
2 | 1000000 | 76046336
3 | 1000000 | 76840960
4 | 1000000 | 77799424
5 | 1000000 | 78766080
6 | 1000000 | 79757312
7 | 1000000 | 80494592
8 | 1000000 | 81125376
9 | 1000000 | 81985536
10 | 1000000 | 82804736
11 | 1000000 | 83378176
12 | 1000000 | 84115456
13 | 1000000 | 84819968
14 | 1000000 | 85598208
15 | 1000000 | 86302720
16 | 1000000 | 87023616
17 | 1000000 | 87703552
18 | 1000000 | 88342528
19 | 1000000 | 88915968
20 | 1000000 | 89513984
21 | 1000000 | 90152960
22 | 1000000 | 90742784
23 | 1000000 | 91324416
24 | 1000000 | 91742208
25 | 1000000 | 92258304
26 | 1000000 | 92758016
27 | 1000000 | 93241344
28 | 1000000 | 93683712
29 | 1000000 | 93970432
30 | 1000000 | 94396416
31 | 1000000 | 94740480
32 | 1000000 | 95068160
33 | 1000000 | 95444992
34 | 1000000 | 95780864
35 | 1000000 | 96313344
36 | 1000000 | 96731136
37 | 1000000 | 96968704
38 | 1000000 | 97222656
39 | 1000000 | 97509376
40 | 1000000 | 97779712
41 | 1000000 | 98074624
42 | 1000000 | 98344960
43 | 1000000 | 98639872
44 | 1000000 | 99000320
45 | 1000000 | 99229696
46 | 1000000 | 99459072
47 | 1000000 | 99672064
48 | 1000000 | 99901440
49 | 1000000 | 100114432
50 | 1000000 | 100261888
51 | 1000000 | 100458496
(51 rows)
Index grow about from 75 MB to 100 MB.
Current implementation of gistchoose select first index tuple which have
minimal penalty. It is possible for several tuples to have same minimal
penalty. I've created simple patch which selects random from them. I then
I've following results for same testcase.
test=# select * from geotest_stats;
id | count | size
----+---------+----------
1 | 1000000 | 74694656
2 | 1000000 | 74743808
3 | 1000000 | 74891264
4 | 1000000 | 75120640
5 | 1000000 | 75374592
6 | 1000000 | 75612160
7 | 1000000 | 75833344
8 | 1000000 | 76144640
9 | 1000000 | 76333056
10 | 1000000 | 76595200
11 | 1000000 | 76718080
12 | 1000000 | 76939264
13 | 1000000 | 77070336
14 | 1000000 | 77332480
15 | 1000000 | 77520896
16 | 1000000 | 77750272
17 | 1000000 | 77996032
18 | 1000000 | 78127104
19 | 1000000 | 78307328
20 | 1000000 | 78512128
21 | 1000000 | 78610432
22 | 1000000 | 78774272
23 | 1000000 | 78929920
24 | 1000000 | 79060992
25 | 1000000 | 79216640
26 | 1000000 | 79331328
27 | 1000000 | 79454208
28 | 1000000 | 79593472
29 | 1000000 | 79708160
30 | 1000000 | 79822848
31 | 1000000 | 79921152
32 | 1000000 | 80035840
33 | 1000000 | 80076800
34 | 1000000 | 80175104
35 | 1000000 | 80207872
36 | 1000000 | 80322560
37 | 1000000 | 80363520
38 | 1000000 | 80445440
39 | 1000000 | 80494592
40 | 1000000 | 80576512
41 | 1000000 | 80666624
42 | 1000000 | 80764928
43 | 1000000 | 80805888
44 | 1000000 | 80912384
45 | 1000000 | 80994304
46 | 1000000 | 81027072
47 | 1000000 | 81100800
48 | 1000000 | 81174528
49 | 1000000 | 81297408
50 | 1000000 | 81371136
51 | 1000000 | 81420288
(51 rows)
Now index grow about from 75 MB to 81 MB. It is almost 4 times less index
bloat!
I've following explanation of that. If index tuples are overlapping then
possibility of insertion into last tuple is much lower than possibility of
insertion to the first tuple. Thereby, freed space underlying to last
tuples of inner page is not likely to be reused. Selecting random tuple
increase that chances.
Obviously, it makes insertion more expensive. I need some more benchmarks
to measure it. Probably, we would need a user-visible option for cheaper
insert or less bloat.
------
With best regards,
Alexander Korotkov.
Attachments:
gist_choose_bloat-0.1.patchapplication/octet-stream; name=gist_choose_bloat-0.1.patchDownload+18-21
On Mon, 2012-06-18 at 15:12 +0400, Alexander Korotkov wrote:
Hackers,
While experimenting with gistchoose I achieve interesting results
about relation of gistchoose behaviour and gist index bloat.
...
Current implementation of gistchoose select first index tuple which
have minimal penalty. It is possible for several tuples to have same
minimal penalty. I've created simple patch which selects random from
them. I then I've following results for same testcase.
I took a look at this patch. The surrounding code is pretty messy (not
necessarily because of your patch). A few comments would go a long way.
The 'which_grow' array is initialized as it goes, first using pointer
notations ("*which_grows = -1.0") and then using subscript notation. As
far as I can tell, the first r->rd_att->natts of the array (the only
elements that matter) need to be written the first time through anyway.
Why not just replace "which_grow[j] < 0" with "i == FirstOffsetNumber"
and add a comment that we're initializing the penalties with the first
index tuple?
The 'sum_grow' didn't make any sense, thank you for getting rid of that.
Also, we should document that the earlier attributes always take
precedence, which is why we break out of the inner loop as soon as we
encounter an attribute with a higher penalty.
Please add a comment indicating why you are randomly choosing among the
equal penalties.
I think that there might be a problem with the logic, as well. Let's say
you have two attributes and there are two index tuples, it1 and it2;
with penalties [10,10] and [10,100] respectively. The second time
through the outer loop, with i = 2, you might (P=0.5) assign 2 to the
'which' variable in the first iteration of the inner loop, before it
realizes that it2 actually has a higher penalty. I think you need to
finish out the inner loop and have a flag that indicates that all
attributes are equal before you do the probabilistic replacement.
Also, I think you should use random() rather than rand().
Regards,
Jeff Davis
On Mon, Aug 20, 2012 at 7:13 AM, Jeff Davis <pgsql@j-davis.com> wrote:
I took a look at this patch. The surrounding code is pretty messy (not
necessarily because of your patch). A few comments would go a long way.The 'which_grow' array is initialized as it goes, first using pointer
notations ("*which_grows = -1.0") and then using subscript notation. As
far as I can tell, the first r->rd_att->natts of the array (the only
elements that matter) need to be written the first time through anyway.
Why not just replace "which_grow[j] < 0" with "i == FirstOffsetNumber"
and add a comment that we're initializing the penalties with the first
index tuple?The 'sum_grow' didn't make any sense, thank you for getting rid of that.
Also, we should document that the earlier attributes always take
precedence, which is why we break out of the inner loop as soon as we
encounter an attribute with a higher penalty.Please add a comment indicating why you are randomly choosing among the
equal penalties.I think that there might be a problem with the logic, as well. Let's say
you have two attributes and there are two index tuples, it1 and it2;
with penalties [10,10] and [10,100] respectively. The second time
through the outer loop, with i = 2, you might (P=0.5) assign 2 to the
'which' variable in the first iteration of the inner loop, before it
realizes that it2 actually has a higher penalty. I think you need to
finish out the inner loop and have a flag that indicates that all
attributes are equal before you do the probabilistic replacement.
Current gistchoose code has a bug. I've started separate thread about it.
http://archives.postgresql.org/pgsql-hackers/2012-08/msg00544.php
Also, it obviously needs more comments.
Current state of patch is more proof of concept than something ready. I'm
going to change it in following ways:
1) We don't know how expensive user penalty function is. So, I'm going to
change randomization algorithm so that it doesn't increase number of
penalty calls in average.
2) Since, randomization could produce additional IO, there are probably no
optimal solution for all the cases. We could introduce user-visible option
which enables or disables randomization. However, default value of this
option is another question.
Also, I think you should use random() rather than rand().
Thanks, will fix.
------
With best regards,
Alexander Korotkov.
On Mon, Aug 20, 2012 at 9:13 PM, Alexander Korotkov <aekorotkov@gmail.com>wrote:
Current gistchoose code has a bug. I've started separate thread about it.
http://archives.postgresql.org/pgsql-hackers/2012-08/msg00544.php
Also, it obviously needs more comments.Current state of patch is more proof of concept than something ready. I'm
going to change it in following ways:
1) We don't know how expensive user penalty function is. So, I'm going to
change randomization algorithm so that it doesn't increase number of
penalty calls in average.
2) Since, randomization could produce additional IO, there are probably no
optimal solution for all the cases. We could introduce user-visible option
which enables or disables randomization. However, default value of this
option is another question.Also, I think you should use random() rather than rand().
Thanks, will fix.
New version of patch is attached. Parameter "randomization" was introduced.
It controls whether to randomize choose. Choose algorithm was rewritten.
------
With best regards,
Alexander Korotkov.
Attachments:
gist_choose_bloat-0.2.patchapplication/octet-stream; name=gist_choose_bloat-0.2.patchDownload+100-51
On Tue, 2012-09-04 at 19:21 +0400, Alexander Korotkov wrote:
New version of patch is attached. Parameter "randomization" was
introduced. It controls whether to randomize choose. Choose algorithm
was rewritten.
Do you expect it to be bad in any reasonable situations? I'm inclined to
just make it always randomize if it's better. I think it would be hard
for a user to guess when it's better and when not.
Maybe it's useful to turn randomization off for testing purposes, e.g.
to ensure determinism?
Regards,
Jeff Davis
On Tue, Sep 11, 2012 at 10:35 AM, Jeff Davis <pgsql@j-davis.com> wrote:
On Tue, 2012-09-04 at 19:21 +0400, Alexander Korotkov wrote:
New version of patch is attached. Parameter "randomization" was
introduced. It controls whether to randomize choose. Choose algorithm
was rewritten.Do you expect it to be bad in any reasonable situations? I'm inclined to
just make it always randomize if it's better. I think it would be hard
for a user to guess when it's better and when not.
Randomization should increase IO when index doesn't entirely fit to cache.
Without randomization only fraction of the tree would be used for actual
insertions. While with randomization whole tree would be potentially used
for insertions.
Maybe it's useful to turn randomization off for testing purposes, e.g.
to ensure determinism?
Yes, that's another good point. For example, randomization impede
reproducing of bugs.
------
With best regards,
Alexander Korotkov.
On Tue, 2012-09-04 at 19:21 +0400, Alexander Korotkov wrote:
New version of patch is attached. Parameter "randomization" was
introduced. It controls whether to randomize choose. Choose algorithm
was rewritten.
Review comments:
1. Comment above while loop in gistRelocateBuildBuffersOnSplit needs to
be updated.
2. Typo in two places: "if randomization id required".
3. In gistRelocateBuildBuffersOnSplit, shouldn't that be:
splitPageInfo = &relocationBuffersInfos[bufferIndex];
not:
splitPageInfo = &relocationBuffersInfos[i];
4. It looks like the randomization is happening while trying to compare
the penalties. I think it may be more readable to separate those two
steps; e.g.
/* create a mapping whether randomization is on or not */
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
offsets[i - FirstOffsetNumber] = i;
if (randomization)
/* randomize offsets array */
for (i = 0; i < maxoff; i++)
{
offset = offsets[i];
...
}
That's just an idea; if you think it's more readable as-is (or if I am
misunderstanding) then let me know.
Regards,
Jeff Davis
On Mon, Oct 1, 2012 at 5:15 AM, Jeff Davis <pgsql@j-davis.com> wrote:
On Tue, 2012-09-04 at 19:21 +0400, Alexander Korotkov wrote:
New version of patch is attached. Parameter "randomization" was
introduced. It controls whether to randomize choose. Choose algorithm
was rewritten.Review comments:
1. Comment above while loop in gistRelocateBuildBuffersOnSplit needs to
be updated.
Actually, I didn't realize what exact comment you expect. Check if added
commend meets you expectations.
2. Typo in two places: "if randomization id required".
3. In gistRelocateBuildBuffersOnSplit, shouldn't that be:
splitPageInfo = &relocationBuffersInfos[bufferIndex];
not:
splitPageInfo = &relocationBuffersInfos[i];
Fixed.
4. It looks like the randomization is happening while trying to compare
the penalties. I think it may be more readable to separate those two
steps; e.g./* create a mapping whether randomization is on or not */
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
offsets[i - FirstOffsetNumber] = i;if (randomization)
/* randomize offsets array */for (i = 0; i < maxoff; i++)
{
offset = offsets[i];
...
}That's just an idea; if you think it's more readable as-is (or if I am
misunderstanding) then let me know.
Actually, current implementation comes from idea of creating possible less
overhead when randomization is off. I'll try to measure overhead in worst
case. If it is low enough then you proposal looks reasonable to me.
------
With best regards,
Alexander Korotkov.
Attachments:
gist_choose_bloat-0.3.patchapplication/octet-stream; name=gist_choose_bloat-0.3.patchDownload+108-55
Alexander Korotkov escribió:
4. It looks like the randomization is happening while trying to compare
the penalties. I think it may be more readable to separate those two
steps; e.g./* create a mapping whether randomization is on or not */
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
offsets[i - FirstOffsetNumber] = i;if (randomization)
/* randomize offsets array */for (i = 0; i < maxoff; i++)
{
offset = offsets[i];
...
}That's just an idea; if you think it's more readable as-is (or if I am
misunderstanding) then let me know.Actually, current implementation comes from idea of creating possible less
overhead when randomization is off. I'll try to measure overhead in worst
case. If it is low enough then you proposal looks reasonable to me.
Were you able to do these measurements? If not, I'll defer to your and
Jeff's judgement on what's the best next step here.
Jeff, do you think we need more review of this patch?
--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
On Thu, 2012-10-18 at 15:09 -0300, Alvaro Herrera wrote:
Jeff, do you think we need more review of this patch?
In the patch, it refers to rd_options without checking for NULL first,
which needs to be fixed.
There's actually still one place where it says "id" rather than "is".
Just a nitpick.
Regarding my point 4 from the previous email, I mildly disagree with the
style, but I don't see a correctness problem there.
If the first two items are fixed, then the patch is fine with me.
Regards,
Jeff Davis
On Sun, Oct 21, 2012 at 11:03 AM, Jeff Davis <pgsql@j-davis.com> wrote:
On Thu, 2012-10-18 at 15:09 -0300, Alvaro Herrera wrote:
Jeff, do you think we need more review of this patch?
In the patch, it refers to rd_options without checking for NULL first,
which needs to be fixed.There's actually still one place where it says "id" rather than "is".
Just a nitpick.Regarding my point 4 from the previous email, I mildly disagree with the
style, but I don't see a correctness problem there.If the first two items are fixed, then the patch is fine with me.
First two items are fixed in attached version of the patch.
------
With best regards,
Alexander Korotkov.
Attachments:
gist_choose_bloat-0.4.patchapplication/octet-stream; name=gist_choose_bloat-0.4.patchDownload+112-55
Hi,
On 2012-11-02 12:54:33 +0400, Alexander Korotkov wrote:
On Sun, Oct 21, 2012 at 11:03 AM, Jeff Davis <pgsql@j-davis.com> wrote:
On Thu, 2012-10-18 at 15:09 -0300, Alvaro Herrera wrote:
Jeff, do you think we need more review of this patch?
In the patch, it refers to rd_options without checking for NULL first,
which needs to be fixed.There's actually still one place where it says "id" rather than "is".
Just a nitpick.Regarding my point 4 from the previous email, I mildly disagree with the
style, but I don't see a correctness problem there.If the first two items are fixed, then the patch is fine with me.
First two items are fixed in attached version of the patch.
So the patch is ready for committer now?
I notice there's no documentation about the new reloption at all?
Greetings,
Andres Freund
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Hi!
On Sat, Dec 8, 2012 at 7:05 PM, Andres Freund <andres@2ndquadrant.com>wrote:
I notice there's no documentation about the new reloption at all?
Thanks for notice! I've added small description to docs in the attached
patch.
------
With best regards,
Alexander Korotkov.
Attachments:
gist_choose_bloat-0.5.patchapplication/octet-stream; name=gist_choose_bloat-0.5.patchDownload+129-57
On Fri, 2012-12-14 at 01:03 +0400, Alexander Korotkov wrote:
Hi!
On Sat, Dec 8, 2012 at 7:05 PM, Andres Freund <andres@2ndquadrant.com>
wrote:
I notice there's no documentation about the new reloption at
all?Thanks for notice! I've added small description to docs in the
attached patch.
Here is an edited version of the documentation note. Please review to
see if you like my version.
Also, I fixed a compiler warning.
My tests showed a significant reduction in the size of a gist index with
many of the same penalty values. The run times showed mixed results,
however, and I didn't dig in much further because you've already done
significant testing.
Marking this one ready again.
Regards,
Jeff Davis
Attachments:
On Fri, Dec 14, 2012 at 12:46 PM, Jeff Davis <pgsql@j-davis.com> wrote:
Thanks for notice! I've added small description to docs in the
attached patch.Here is an edited version of the documentation note. Please review to
see if you like my version.
Edited version looks good for me.
Also, I fixed a compiler warning.
Thanks!
------
With best regards,
Alexander Korotkov.
One question: does the randomization ever help when building a new
index? In the original test case, you repeatedly delete and insert
tuples, and I can see how the index can get bloated in that case. But I
don't see how bloat would occur when building the index from scratch.
BTW, I don't much like the option name "randomization". It's not clear
what's been randomized. I'd prefer something like
"distribute_on_equal_penalty", although that's really long. Better ideas?
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On Fri, 2012-12-14 at 18:36 +0200, Heikki Linnakangas wrote:
One question: does the randomization ever help when building a new
index? In the original test case, you repeatedly delete and insert
tuples, and I can see how the index can get bloated in that case. But I
don't see how bloat would occur when building the index from scratch.
When building an index on a bunch of identical int4range values (in my
test, [1,10) ), the resulting index was about 17% smaller.
If the current algorithm always chooses to insert on the left-most page,
then it seems like there would be a half-filled right page for every
split that occurs. Is that reasoning correct?
However, I'm having some second thoughts about the run time for index
builds. Maybe we should have a few more tests to determine if this
should really be the default or just an option?
BTW, I don't much like the option name "randomization". It's not clear
what's been randomized. I'd prefer something like
"distribute_on_equal_penalty", although that's really long. Better ideas?
I agree that "randomization" is vague, but I can't think of anything
better.
Regards,
Jeff Davis
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Jeff Davis <pgsql@j-davis.com> writes:
On Fri, 2012-12-14 at 18:36 +0200, Heikki Linnakangas wrote:
BTW, I don't much like the option name "randomization". It's not clear
what's been randomized. I'd prefer something like
"distribute_on_equal_penalty", although that's really long. Better ideas?
I agree that "randomization" is vague, but I can't think of anything
better.
I looked at this patch. ISTM we should not have the option at all but
just do it always. I cannot believe that always-go-left is ever a
preferable strategy in the long run; the resulting imbalance in the
index will surely kill any possible benefit. Even if there are some
cases where it miraculously fails to lose, how many users are going to
realize that applies to their case and make use of the option?
regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On Mon, 2013-01-21 at 00:48 -0500, Tom Lane wrote:
I looked at this patch. ISTM we should not have the option at all but
just do it always. I cannot believe that always-go-left is ever a
preferable strategy in the long run; the resulting imbalance in the
index will surely kill any possible benefit. Even if there are some
cases where it miraculously fails to lose, how many users are going to
realize that applies to their case and make use of the option?
Sounds good to me.
If I remember correctly, there was also an argument that it may be
useful for repeatable test results. That's a little questionable for
performance (except in those cases where few penalties are identical
anyway), but could plausibly be useful for a crash report or something.
Regards,
Jeff Davis
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Jeff Davis <pgsql@j-davis.com> writes:
On Mon, 2013-01-21 at 00:48 -0500, Tom Lane wrote:
I looked at this patch. ISTM we should not have the option at all but
just do it always. I cannot believe that always-go-left is ever a
preferable strategy in the long run; the resulting imbalance in the
index will surely kill any possible benefit. Even if there are some
cases where it miraculously fails to lose, how many users are going to
realize that applies to their case and make use of the option?
Sounds good to me.
If I remember correctly, there was also an argument that it may be
useful for repeatable test results. That's a little questionable for
performance (except in those cases where few penalties are identical
anyway), but could plausibly be useful for a crash report or something.
Meh. There's already a random decision, in the equivalent place and for
a comparable reason, in btree (cf _bt_findinsertloc). Nobody's ever
complained about that being indeterminate, so I'm unconvinced that
there's a market for it with gist.
regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers