Thread: 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@tao11.riddles.org.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@tao11.riddles.org.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@svana.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@svana.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 triesto split>> the data again based on the positions of the box centers. But>> there's a problem here with floating-pointrounding; it's possible>> for the average of N floating-point values to be strictly greater>> (or less) thanall 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 predictableresults. Martijn> ISTM the simplest solution here is detect that everythingMartijn> has been put in one node (left or right) and inthat caseMartijn> just split the list straight down the middle (since clearlyMartijn> it doesn't matter on which side theyappear.). 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@sigaev.ru
WWW: http://www.sigaev.ru/
Attachment
Teodor Sigaev <teodor@sigaev.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@sigaev.ru
WWW: http://www.sigaev.ru/
>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes: > Teodor Sigaev <teodor@sigaev.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, notTom> spread it even further. And what confidence do youhave thatTom> 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@sigaev.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
fromAndrew, allTeodor> boxes are placed to one page because of floating-pointTeodor> 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 oneTeodor> half of all boxes on one page and another half
tothe anotherTeodor> page as it does if all boxes are equal. But FPeq() seemed toTeodor> me a simpler solution and FP*
comparisonsare widely used inTeodor> 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@tao11.riddles.org.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@sigaev.ru
WWW: http://www.sigaev.ru/
Attachment
Teodor Sigaev <teodor@sigaev.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@sigaev.ru
WWW: http://www.sigaev.ru/
Attachment
Teodor Sigaev <teodor@sigaev.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
onein 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@sigaev.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@gmx.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