Crash in gist insertion on pathological box data

A user on IRC reported a crash (backend segfault) in GiST insertion
(in 8.3.5 but I can reproduce this in today's HEAD) that turns out
to be due to misbehaviour of gist_box_picksplit.

The nature of the problem is this: if gist_box_picksplit doesn't find
a good disposition on the first try, then it tries to split the data
again based on the positions of the box centers. But there's a problem
here with floating-point rounding; it's possible for the average of N
floating-point values to be strictly greater (or less) than all of the
values individually, and the function then returns with, for example,
all the entries assigned to the left node, and nothing in the right
node. This causes gistSplit to try and split the left node again, with
predictable results.

Here is a test case:

file of floating-point values here (999 lines):
http://www.rhodiumtoad.org.uk/junk/badfloats.txt

create table floats3(x float8, y float8);
\copy floats3 from 'badfloats.txt'
create table boxes1 (b box);
create index boxes1_idx on boxes1 using gist (b);
insert into boxes1 select box(point(x,x),point(y,y)) as b from floats3;
[crash]

I'm not sure what the best fix is. I would think that it would make
sense for gistUserPickSplit to error out if the user's split function
returned an empty left or right node, since that would seem to
guarantee this problem. Certainly gist_box_picksplit also needs some
sort of fix to try and split sensibly in the presence of data of this
type.

--
Andrew (irc:RhodiumToad)

On Thu, Mar 26, 2009 at 5:39 PM, Andrew Gierth
<andrew(at)tao11(dot)riddles(dot)org(dot)uk> wrote:
> A user on IRC reported a crash (backend segfault) in GiST insertion
> (in 8.3.5 but I can reproduce this in today's HEAD) that turns out
> to be due to misbehaviour of gist_box_picksplit.
>

Andrew, thank you for the test case and report.

p.s. The user Andrew mentioned above is me and if you have a question
to me I am ready to answer it.

--
Regards,
Sergey Konoplev
--
PostgreSQL articles in english & russian
http://gray-hemp.blogspot.com/search/label/postgresql/

On Thu, Mar 26, 2009 at 5:39 PM, Andrew Gierth
<andrew(at)tao11(dot)riddles(dot)org(dot)uk> wrote:
> A user on IRC reported a crash (backend segfault) in GiST insertion
> (in 8.3.5 but I can reproduce this in today's HEAD) that turns out
> to be due to misbehaviour of gist_box_picksplit.
>
> The nature of the problem is this: if gist_box_picksplit doesn't find
> a good disposition on the first try, then it tries to split the data
> again based on the positions of the box centers. But there's a problem
> here with floating-point rounding; it's possible for the average of N
> floating-point values to be strictly greater (or less) than all of the
> values individually, and the function then returns with, for example,
> all the entries assigned to the left node, and nothing in the right
> node. This causes gistSplit to try and split the left node again, with
> predictable results.
>

I probably have a workaround. As I understand the problem it touches
gist indexes with one box type field only. After googling picksplit
and reading some info I supposed that If another (distinctive) field
would be appended to the index (after the box field) then another
(old) picksplit functionality would be started instead of new (buggy)
one. Andrew approved my assumption on IRC. So I found all the indexes
(gist) with one box field and recreated them with extra column (bigint
PK field). Well on this moment our DB has been working for a 22 hour
without crashes and errors.

Of course not being pg-hacker I can't guaranty that my assumption is
absolutely correct and I welcome your criticism.

--
Regards,
Sergey Konoplev
--
PostgreSQL articles in english & russian
http://gray-hemp.blogspot.com/search/label/postgresql/

On Thu, Mar 26, 2009 at 02:39:05PM +0000, Andrew Gierth wrote:
> A user on IRC reported a crash (backend segfault) in GiST insertion
> (in 8.3.5 but I can reproduce this in today's HEAD) that turns out
> to be due to misbehaviour of gist_box_picksplit.
>
> The nature of the problem is this: if gist_box_picksplit doesn't find
> a good disposition on the first try, then it tries to split the data
> again based on the positions of the box centers. But there's a problem
> here with floating-point rounding; it's possible for the average of N
> floating-point values to be strictly greater (or less) than all of the
> values individually, and the function then returns with, for example,
> all the entries assigned to the left node, and nothing in the right
> node. This causes gistSplit to try and split the left node again, with
> predictable results.

ISTM the simplest solution here is detect that everything has been put
in one node (left or right) and in that case just split the list
straight down the middle (since clearly it doesn't matter on which side
they appear.).

Or switch algorithms, but that's more than just a bugfix.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Please line up in a tree and maintain the heap invariant while
> boarding. Thank you for flying nlogn airlines.

>>>>> "Martijn" == Martijn van Oosterhout <kleptog(at)svana(dot)org> writes:

>> The nature of the problem is this: if gist_box_picksplit doesn't
>> find a good disposition on the first try, then it tries to split
>> the data again based on the positions of the box centers. But
>> there's a problem here with floating-point rounding; it's possible
>> for the average of N floating-point values to be strictly greater
>> (or less) than all of the values individually, and the function
>> then returns with, for example, all the entries assigned to the
>> left node, and nothing in the right node. This causes gistSplit to
>> try and split the left node again, with predictable results.

Martijn> ISTM the simplest solution here is detect that everything
Martijn> has been put in one node (left or right) and in that case
Martijn> just split the list straight down the middle (since clearly
Martijn> it doesn't matter on which side they appear.).

It's not quite so simple; we know that not all the values are equal,
since that's checked for earlier in the code (if they're all actually
equal they just get split down the middle). In this specific case the
values could actually be quite different, since we're only looking
at the centers; and with, say, a large number of very different size
boxes all centered on the same point, it would be preferable to split
them so that at least one node has a smaller union.

I'm interested to see what Oleg's solution (see other thread) is.

--
Andrew.

> The nature of the problem is this: if gist_box_picksplit doesn't find
> a good disposition on the first try, then it tries to split the data
> again based on the positions of the box centers. But there's a problem
> here with floating-point rounding; it's possible for the average of N

Look at the patch, it fixes the problem by comparing for equality by FPeq()
macros which is used everywhere in geometry calculation.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
> Look at the patch, it fixes the problem by comparing for equality by FPeq()
> macros which is used everywhere in geometry calculation.

Ick. FPeq() is a crock; I'd like to see us get rid of it, not spread it
even further. And what confidence do you have that this change
eliminates all forms of the problem, anyway?

regards, tom lane

> even further. And what confidence do you have that this change
> eliminates all forms of the problem, anyway?

Yes, I think. Because that part of code ( if (IS_BADRATIO) {...} ) is a corner
case itself. In example from Andrew, all boxes are placed to one page because of
floating-point rounding.

We could check IS_BADRATIO again and if it's just put one half of all boxes on
one page and another half to the another page as it does if all boxes are equal.
But FPeq() seemed to me a simpler solution and FP* comparisons are widely used
in geometry.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

>>>>> "Tom" == Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
>> Look at the patch, it fixes the problem by comparing for equality
>> by FPeq() macros which is used everywhere in geometry calculation.

Tom> Ick. FPeq() is a crock; I'd like to see us get rid of it, not
Tom> spread it even further. And what confidence do you have that
Tom> this change eliminates all forms of the problem, anyway?

Here is a test case that crashes even with the patch:

create table floats3(x float8, y float8);
-- same badfloats.txt data as before
\copy floats3 from 'badfloats.txt'
update floats3 set x = x * pow(2::float8,33), y = y * pow(2::float8,33);
create table boxes1 (b box);
create index boxes1_idx on boxes1 using gist (b);
insert into boxes1 select box(point(x,x),point(y,y)) as b from floats3;
[crash]

--
Andrew (irc:RhodiumToad)

>>>>> "Teodor" == Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:

>> even further. And what confidence do you have that this change
>> eliminates all forms of the problem, anyway?

Teodor> Yes, I think. Because that part of code ( if (IS_BADRATIO)
Teodor> {...} ) is a corner case itself. In example from Andrew, all
Teodor> boxes are placed to one page because of floating-point
Teodor> rounding.

Yes, it's a corner case, but it arose in real-world data (the test
data set is contrived, but that's simply because it was the easiest
way to demonstrate the bug without access to the real data, which
had a much larger variation in box sizes).

Teodor> We could check IS_BADRATIO again and if it's just put one
Teodor> half of all boxes on one page and another half to the another
Teodor> page as it does if all boxes are equal. But FPeq() seemed to
Teodor> me a simpler solution and FP* comparisons are widely used in
Teodor> geometry.

I think that not only does there need to be another IS_BADRATIO check,
but also there needs to be some sort of backstop in gistSplit or
gistUserPicksplit to either recover or (as a last resort) error out
cleanly rather than crash the entire db in cases that would result in
infinite recursion.

--
Andrew (irc:RhodiumToad)

Andrew Gierth <andrew(at)tao11(dot)riddles(dot)org(dot)uk> writes:
> I think that not only does there need to be another IS_BADRATIO check,
> but also there needs to be some sort of backstop in gistSplit or
> gistUserPicksplit to either recover or (as a last resort) error out
> cleanly rather than crash the entire db in cases that would result in
> infinite recursion.

+1. This is not just a problem in one picksplit method, it's a generic
hazard for all of them. The core code should be defending against a
pathological split.

regards, tom lane

> Here is a test case that crashes even with the patch:
I was too optimistic :(

Attached patch contains:
- changes in R-tree picksplit methods. Now it checks bad ratio and if so then
use simple split: one half of entries to one page, and another part - to
another page.
- protection from buggy picksplit method: GiST will emit an error if picksplit
of first column has that bug. For second and next column it could be a desired
behaviour, because picksplit may take in attention result of picksplit of
previous column.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
>> Here is a test case that crashes even with the patch:

> I was too optimistic :(

> Attached patch contains:
> - changes in R-tree picksplit methods. Now it checks bad ratio and if so then
> use simple split: one half of entries to one page, and another part - to
> another page.
> - protection from buggy picksplit method: GiST will emit an error if picksplit
> of first column has that bug. For second and next column it could be a desired
> behaviour, because picksplit may take in attention result of picksplit of
> previous column.

I don't like throwing an error there; I wish there were a way for the
generic code to apply the fallbackSplit code instead. I see that
in this particular formulation it's dependent on the datatype ---
can we get around that, by having it invoke the union method?

regards, tom lane

> I don't like throwing an error there; I wish there were a way for the
> generic code to apply the fallbackSplit code instead. I see that
> in this particular formulation it's dependent on the datatype ---
> can we get around that, by having it invoke the union method?

Done. rtree.patch.gz contains patch for gistproc.c, genericsplit.patch.gz adds
simple genericPickSplit to gistsplit.c to workaround bug of user-defined picksplit.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
>> I don't like throwing an error there; I wish there were a way for the
>> generic code to apply the fallbackSplit code instead. I see that
>> in this particular formulation it's dependent on the datatype ---
>> can we get around that, by having it invoke the union method?

> Done. rtree.patch.gz contains patch for gistproc.c, genericsplit.patch.gz adds
> simple genericPickSplit to gistsplit.c to workaround bug of user-defined picksplit.

This looks good to me. I tested it to the extent of verifying that
either patch individually would prevent the originally-reported failure.

The only question I have is whether we want this nag message or not:

! ereport(LOG,
! (errcode(ERRCODE_INTERNAL_ERROR),
! errmsg("Picksplit method for %d column of index \"%s\" failed",
! attno+1, RelationGetRelationName(r)),
! errhint("Index is not optimal, to optimize it contact developer or try to use the column as a second one in create index command")));

I'd be inclined to keep it but reduce it to level DEBUG1 or so.

regards, tom lane

> This looks good to me. I tested it to the extent of verifying that
> either patch individually would prevent the originally-reported failure.
> I'd be inclined to keep it but reduce it to level DEBUG1 or so.

Committed in HEAD, 8.3 and 8.2. Previous versions need to be patched too but
codebase is different, so I'll patch them a bit later.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On Monday 06 April 2009 04:29:02 Tom Lane wrote:
> The only question I have is whether we want this nag message or not:
>
> ! ereport(LOG,
> ! (errcode(ERRCODE_INTERNAL_ERROR),
> ! errmsg("Picksplit method for %d column of index \"%s\"
> failed", ! attno+1, RelationGetRelationName(r)),
> ! errhint("Index is not optimal, to optimize it contact
> developer or try to use the column as a second one in create index
> command")));
>
> I'd be inclined to keep it but reduce it to level DEBUG1 or so.

If it is supposed to be DEBUG1, would you mind if I convert it to an elog so
it doesn't appear in the translation roster?

Not sure how many responses you will get if you hide the message like that.
Probably almost anyone would not turn on DEBUG1 unless asked by a developer in
the first place.

Peter Eisentraut <peter_e(at)gmx(dot)net> writes:
> On Monday 06 April 2009 04:29:02 Tom Lane wrote:
>> The only question I have is whether we want this nag message or not:

> If it is supposed to be DEBUG1, would you mind if I convert it to an elog so
> it doesn't appear in the translation roster?

Okay with me. You could use errmsg_internal but we have no equivalent
of errhint_internal, so I suppose it's got to be smashed to a single
message anyway if you don't want to translate it.

regards, tom lane