Thread: GiST KNN Crasher

I'm implementing the recheck functionality for PostGIS so we can
support it when 9.5 comes out, and came across this fun little
crasher.

This works:

select id, name from geonames order by geom <->
'SRID=4326;POINT(-75.6163 39.746)'::geometry limit 10;

This crashes (just reversing the argument order to the <-> operator):

select id, name from geonames order by 'SRID=4326;POINT(-75.6163
39.746)'::geometry <-> geom limit 10;

The stack trace on crash looks like this:

* thread #1: tid = 0x8d2bb, 0x0000000100455247
postgres`create_indexscan_plan(root=0x00007fbf8d005c80,
best_path=0x00007fbf8b823600, tlist=0x00007fbf8d0088d0,
scan_clauses=0x0000000000000000, indexonly='\0') + 1063 at
createplan.c:1354, queue = 'com.apple.main-thread', stop reason =
EXC_BAD_ACCESS (code=1, address=0x24)
 * frame #0: 0x0000000100455247
postgres`create_indexscan_plan(root=0x00007fbf8d005c80,
best_path=0x00007fbf8b823600, tlist=0x00007fbf8d0088d0,
scan_clauses=0x0000000000000000, indexonly='\0') + 1063 at
createplan.c:1354
   frame #1: 0x00000001004518c9
postgres`create_scan_plan(root=0x00007fbf8d005c80,
best_path=0x00007fbf8b823600) + 377 at createplan.c:360
   frame #2: 0x000000010044e749
postgres`create_plan_recurse(root=0x00007fbf8d005c80,
best_path=0x00007fbf8b823600) + 73 at createplan.c:248
   frame #3: 0x000000010044e691
postgres`create_plan(root=0x00007fbf8d005c80,
best_path=0x00007fbf8b823600) + 113 at createplan.c:209
   frame #4: 0x0000000100460770
postgres`grouping_planner(root=0x00007fbf8d005c80,
tuple_fraction=0.0000048008487900660838) + 4560 at planner.c:1736
   frame #5: 0x000000010045e1dd
postgres`subquery_planner(glob=0x00007fbf8b823950,
parse=0x00007fbf8b823060, parent_root=0x0000000000000000,
hasRecursion='\0', tuple_fraction=0, subroot=0x00007fff5faf7028) +
2461 at planner.c:619
   frame #6: 0x000000010045d4a2
postgres`standard_planner(parse=0x00007fbf8b823060, cursorOptions=0,
boundParams=0x0000000000000000) + 450 at planner.c:229
   frame #7: 0x000000010045d2d1
postgres`planner(parse=0x00007fbf8b823060, cursorOptions=0,
boundParams=0x0000000000000000) + 81 at planner.c:157
   frame #8: 0x000000010054ab6c
postgres`pg_plan_query(querytree=0x00007fbf8b823060, cursorOptions=0,
boundParams=0x0000000000000000) + 140 at postgres.c:809
   frame #9: 0x000000010054ac43
postgres`pg_plan_queries(querytrees=0x00007fbf8d006230,
cursorOptions=0, boundParams=0x0000000000000000) + 115 at
postgres.c:868
   frame #10: 0x000000010054d920
postgres`exec_simple_query(query_string=0x00007fbf8b821a38) + 800 at
postgres.c:1033
   frame #11: 0x000000010054cda2 postgres`PostgresMain(argc=1,
argv=0x00007fbf8b8066d0, dbname=0x00007fbf8b806538,
username=0x00007fbf8b806518) + 2546 at postgres.c:4025
   frame #12: 0x00000001004b17fe
postgres`BackendRun(port=0x00007fbf8b4079d0) + 686 at
postmaster.c:4162
   frame #13: 0x00000001004b0d90
postgres`BackendStartup(port=0x00007fbf8b4079d0) + 384 at
postmaster.c:3838
   frame #14: 0x00000001004ad497 postgres`ServerLoop + 663 at postmaster.c:1594
   frame #15: 0x00000001004aab9c postgres`PostmasterMain(argc=3,
argv=0x00007fbf8b407760) + 5644 at postmaster.c:1241
   frame #16: 0x00000001003e649d postgres`main(argc=3,
argv=0x00007fbf8b407760) + 749 at main.c:221
   frame #17: 0x00007fff8ca915fd libdyld.dylib`start + 1

And my SQL declarations look like this:

#if POSTGIS_PGSQL_VERSION >= 95

-- Availability: 2.2.0
CREATE OR REPLACE FUNCTION geography_knn_distance(geography, geography) RETURNS float8 AS
'MODULE_PATHNAME','geography_distance'LANGUAGE 'c' IMMUTABLE STRICT COST 100;
 

-- Availability: 2.2.0
CREATE OPERATOR <-> ( LEFTARG = geography, RIGHTARG = geography, PROCEDURE = geography_knn_distance, COMMUTATOR =
'<->'
);

-- Availability: 2.2.0
CREATE OR REPLACE FUNCTION geography_gist_distance(internal, geography, int4)
RETURNS float8
AS 'MODULE_PATHNAME' ,'gserialized_gist_distance'
LANGUAGE 'c';

#endif

-- Availability: 1.5.0
CREATE OPERATOR CLASS gist_geography_ops
DEFAULT FOR TYPE geography USING GIST AS
STORAGE gidx,
OPERATOR        3        && ,
-- OPERATOR        6        ~= ,
-- OPERATOR        7        ~ ,
-- OPERATOR        8        @ ,
#if POSTGIS_PGSQL_VERSION >= 95
-- Availability: 2.2.0
OPERATOR        13       <-> FOR ORDER BY pg_catalog.float_ops,
FUNCTION        8        geography_gist_distance (internal, geography, int4),
#endif
FUNCTION        1        geography_gist_consistent (internal, geography, int4),
FUNCTION        2        geography_gist_union (bytea, internal),
FUNCTION        3        geography_gist_compress (internal),
FUNCTION        4        geography_gist_decompress (internal),
FUNCTION        5        geography_gist_penalty (internal, internal, internal),
FUNCTION        6        geography_gist_picksplit (internal, internal),
FUNCTION        7        geography_gist_same (box2d, box2d, internal);

Paul Ramsey <pramsey@cleverelephant.ca> writes:
> I'm implementing the recheck functionality for PostGIS so we can
> support it when 9.5 comes out, and came across this fun little
> crasher.

Hmm, works in 9.3 and 9.4, so it's been broken recently.
Will look, thanks!
        regards, tom lane

On 05/21/2015 11:28 PM, Tom Lane wrote:
> Paul Ramsey <pramsey@cleverelephant.ca> writes:
>> I'm implementing the recheck functionality for PostGIS so we can
>> support it when 9.5 comes out, and came across this fun little
>> crasher.
>
> Hmm, works in 9.3 and 9.4, so it's been broken recently.

It was clearly broken by knn-with-recheck patch (35fcb1b3), which added 
the code where the segfault happened.

The find_ec_member_for_expr() call in create_indexscan_plan() fails to 
find the equivalence member for the path key. 
match_clause_to_ordering_op() found the match by commuting the operator, 
but code in create_indexscan_plan() doesn't take that into account.

I think that trying to find the equivalence member in 
create_index_scan() is too fragile. I'm not too familiar with the 
equivalence class stuff though, so I'm not sure what the correct 
solution is. Could we store the datatype in the IndexPath to begin with, 
to avoid having to deduce it in create_indexscan_plan()? Or could we 
just use exprType() on the expression in create_indexscan_plan() and not 
bother finding the equivalence member? The comments in EquivalenceMember 
suggest that that won't work in particular with anyarray_ops, but to be 
honest this goes beyond my planner skills..

- Heikki

Heikki Linnakangas <hlinnaka@iki.fi> writes:
> The find_ec_member_for_expr() call in create_indexscan_plan() fails to 
> find the equivalence member for the path key. 
> match_clause_to_ordering_op() found the match by commuting the operator, 
> but code in create_indexscan_plan() doesn't take that into account.

Right.

> I think that trying to find the equivalence member in 
> create_index_scan() is too fragile.

I agree; will contemplate how to do this better.
        regards, tom lane

I wrote:
> Heikki Linnakangas <hlinnaka@iki.fi> writes:
>> I think that trying to find the equivalence member in 
>> create_index_scan() is too fragile.

> I agree; will contemplate how to do this better.

I think probably what we ought to do here is just use exprType() of the
ORDER BY expression.  There are opclasses for which that would not work,
because the operators are declared to accept anyarray or some other
pseudotype; but I'm not aware of any current or contemplated indexorderby
support that would hit such cases.  It doesn't seem worth going out of
our way for full generality when there are a lot of other restrictions
on the indexorderby mechanism anyway.
        regards, tom lane

Paul Ramsey <pramsey@cleverelephant.ca> writes:
> I'm implementing the recheck functionality for PostGIS so we can
> support it when 9.5 comes out, and came across this fun little
> crasher.

Should be fixed as of git tip.  Thanks for the report!
        regards, tom lane