Thread: Fix picksplit with nan values

Alexander Korotkov <aekorotkov@gmail.com> writes:
> PostGIS spotted that picksplit algorithm freezes in infinite loop when
> dealing with nan values. I discovered same bug is present in core
> opclasses. Attached patch fixes this issue interpreting nan as value
> greater than infinity like btree comparison function does.

Hm.  Good point, but it seems like some of these hunks are only taking
care of a subset of the possible combinations of input NaNs.  If you're
certain the other combinations are impossible, there should be code
comments explaining why.

BTW, as a stylistic matter, I think it sucks to write     !float8_cmp_internal(x,y)
when what you mean is     float8_cmp_internal(x,y) == 0
The "!" syntax should pretty much only be used for boolean tests IMO.

I do recognize that there's a tradition of writing "!ptr" rather than
"ptr == NULL", which I think is all right in most contexts, mainly
because returning a null pointer has an element of boolean yes-or-no-ness
to it.  When you're doing arithmetic comparisons, though, it's just
confusing.

I wrote another rant about this years ago in the context of complaining
about "!strcmp" tests; there was probably more detail in that, if you
care to look in the archives.
        regards, tom lane

>>>>> "Alexander" == Alexander Korotkov <aekorotkov@gmail.com> writes:
Alexander> 2) NaN coordinates should be processed in GiST index scanAlexander> like in sequential scan.

postgres=# select * from pts order by a <-> '(0,0)' limit 10;   a     
----------(1,1)(7,nan)(9,nan)(11,nan)(4,nan)(nan,6)(2,1)(1,2)(2,2)(3,1)
(10 rows)

postgres=# set enable_indexscan=false;
SET

postgres=# select * from pts order by a <-> '(0,0)' limit 10;  a   
-------(1,1)(2,1)(1,2)(2,2)(3,1)(1,3)(3,2)(2,3)(4,1)(1,4)
(10 rows)

this data set was created by:
insert into pts select point(i,j)   from (select generate_series(1,100)::float8 union all select 'nan') s1(i),
(selectgenerate_series(1,100)::float8 union all select 'nan') s2(j)  order by random();
 

-- 
Andrew (irc:RhodiumToad)

Alexander Korotkov <aekorotkov@gmail.com> writes:
>> Thanks, Andrew! Good spot.
>> I didn't examine order by operators for work with NaNs.
>> I think this time problem is in GiST itself rather than in opclass. I'm
>> going to fix it in a separate patch.

> Attached patch fixes knn GiST behaviour with NaN. It makes RB-tree
> comparison function in GiST work like float8 btree opclass comparison
> function.

Hmm ... does that really work, or even do anything?  I'd have thought
that if either input is a NAN, the initial test
    if (sa->distances[i] != sb->distances[i])

would return false so we'd not enter the rest of it.
        regards, tom lane

Alexander Korotkov <aekorotkov@gmail.com> writes:
> I wrote attached patch by following principles:
> 1) NaN coordinates shouldn't crash or hang GiST.
> 2) NaN coordinates should be processed in GiST index scan like in
> sequential scan.
> 3) NaN coordinates shouldn't lead to significant slowdown.

I looked at this patch for awhile.  It seems like there's still an awful
lot of places in gistproc.c that are not worrying about NANs, and it's not
clear to me that they don't need to.  For instance, despite the changes in
adjustBox(), it'll still be possible to have boxes with NAN boundaries if
all the contained values are all-NAN boxes.  It doesn't seem like
gist_box_penalty will behave very sanely for that; it'll return a NAN
penalty which seems unhelpful.  The static box_penalty function doesn't
work sanely for NANs either, and if it can return NAN then you also have
to worry about NAN deltas in common_entry_cmp.  And isn't it still
possible for the Assert in gist_box_picksplit to fire?

> That could be illustrated on following test-case:

> create table test1 as (select point(random(), random()) as p from
> generate_series(1,1000000));
> create index test1_idx on test1 using gist(p);
> create table temp as (select * from test1);
> insert into temp (select point('nan'::float8, 'nan'::float8) from
> generate_series(1,1000));
> insert into temp (select point('nan'::float8, random()) from
> generate_series(1,1000));
> insert into temp (select point(random(), 'nan'::float8) from
> generate_series(1,1000));
> create table test2 as (select * from temp order by random());
> create index test2_idx on test2 using gist(p);
> drop table temp;

I think this test case is unlikely to generate any all-NAN index entry
boxes, because almost certainly the initial entries will be non-NANs, and
you've got it set up to keep incoming NANs from adjusting the boundaries
of an existing box.  You'd get better code coverage if you started by
inserting some NANs into an empty index.

Also, as a stylistic matter, I thought your previous solution of
copying float8_cmp_internal was a better idea than manually inlining it
(sans comments!) in multiple places as this version does.
        regards, tom lane

Where are we on this?

---------------------------------------------------------------------------

On Fri, Nov  8, 2013 at 01:38:28PM -0500, Tom Lane wrote:
> Alexander Korotkov <aekorotkov@gmail.com> writes:
> > I wrote attached patch by following principles:
> > 1) NaN coordinates shouldn't crash or hang GiST.
> > 2) NaN coordinates should be processed in GiST index scan like in
> > sequential scan.
> > 3) NaN coordinates shouldn't lead to significant slowdown.
> 
> I looked at this patch for awhile.  It seems like there's still an awful
> lot of places in gistproc.c that are not worrying about NANs, and it's not
> clear to me that they don't need to.  For instance, despite the changes in
> adjustBox(), it'll still be possible to have boxes with NAN boundaries if
> all the contained values are all-NAN boxes.  It doesn't seem like
> gist_box_penalty will behave very sanely for that; it'll return a NAN
> penalty which seems unhelpful.  The static box_penalty function doesn't
> work sanely for NANs either, and if it can return NAN then you also have
> to worry about NAN deltas in common_entry_cmp.  And isn't it still
> possible for the Assert in gist_box_picksplit to fire?
> 
> > That could be illustrated on following test-case:
> 
> > create table test1 as (select point(random(), random()) as p from
> > generate_series(1,1000000));
> > create index test1_idx on test1 using gist(p);
> > create table temp as (select * from test1);
> > insert into temp (select point('nan'::float8, 'nan'::float8) from
> > generate_series(1,1000));
> > insert into temp (select point('nan'::float8, random()) from
> > generate_series(1,1000));
> > insert into temp (select point(random(), 'nan'::float8) from
> > generate_series(1,1000));
> > create table test2 as (select * from temp order by random());
> > create index test2_idx on test2 using gist(p);
> > drop table temp;
> 
> I think this test case is unlikely to generate any all-NAN index entry
> boxes, because almost certainly the initial entries will be non-NANs, and
> you've got it set up to keep incoming NANs from adjusting the boundaries
> of an existing box.  You'd get better code coverage if you started by
> inserting some NANs into an empty index.
> 
> Also, as a stylistic matter, I thought your previous solution of
> copying float8_cmp_internal was a better idea than manually inlining it
> (sans comments!) in multiple places as this version does.
> 
>             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

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +