[postgis-devel] KNN and 9.5

Tue Jan 5 21:11:12 PST 2016

Steve,

Nevermind. I was able to recreate your error with my test data.  I had to reduce the table set so my patience wasn't exhausted.

I'll ticket this one and see if I can trigger the same error with the built-in geometry types so I can complain upstream.  So final test data and test to trigger:

CREATE OR REPLACE FUNCTION zz_2nn_angle(geometry) RETURNS float AS $$

-- Here are my wonderful points to KNN search:
WITH index_query AS (

	SELECT edge.geom AS geom
	FROM (SELECT * FROM knn_recheck_geom) AS edge
-- This is my query point
	ORDER BY $1
		<->
	edge.geom LIMIT 2
	),
templine AS (
	SELECT ST_MakeLine(geom) AS geom FROM index_query
),
angle1 AS (
	SELECT ST_Azimuth(ST_StartPoint(geom), $1) angle FROM templine
),
angle2 AS (
	SELECT ST_Azimuth(ST_EndPoint(geom), $1) angle FROM templine
)
SELECT a1.angle - a2.angle FROM angle1 a1, angle2 a2

$$ LANGUAGE SQL;

CREATE OR REPLACE FUNCTION zz_1nn_d(geometry) RETURNS float AS $$

-- Here are my wonderful points to KNN search:
WITH index_query AS (

	SELECT edge.geom AS geom
	FROM (SELECT * FROM knn_recheck_geom WHERE gid = 881) AS edge
-- This is my query point
	ORDER BY $1
		<->
	edge.geom LIMIT 1
	)
SELECT ST_Distance($1,geom) FROM index_query

$$ LANGUAGE SQL;

CREATE TABLE knn_recheck_geom(gid serial primary key, geom geometry);
INSERT INTO knn_recheck_geom(gid,geom)
SELECT ROW_NUMBER() OVER(ORDER BY x,y) AS gid, ST_Point(x*0.777,y*0.887) As geom
FROM generate_series(-100,1000, 9) AS x CROSS JOIN generate_series(-300,1000,9) As y;

--- 
DROP TABLE IF EXISTS test_angle_subset CASCADE;
CREATE TABLE test_angle_subset AS
WITH returnline AS (
	SELECT gid, geom,
		zz_1nn_d(geom) AS distance,
		abs(degrees(zz_2nn_angle(geom))) AS angle FROM
		(SELECT * FROM knn_recheck_geom) subset
)
SELECT * FROM returnline;

Yields error:

ERROR:  index returned tuples in wrong order
CONTEXT:  SQL function "zz_2nn_angle" statement 1
********** Error **********

Though I can't trigger the error with the 1nn function

e.g this works fine:

SELECT zz_1nn_d(geom)
FROM knn_recheck_geom;

Retuns 17835 rows in 300 ms.

But this:

SELECT zz_2nn_angle(geom)
FROM knn_recheck_geom;

--- triggers same error
ERROR:  index returned tuples in wrong order
CONTEXT:  SQL function "zz_2nn_angle" statement 1

You are a cruel bastard Steve.  You make me proud,

Regina

-----Original Message-----
From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On Behalf Of Paragon Corporation
Sent: Tuesday, January 05, 2016 11:56 PM
To: 'PostGIS Development Discussion' <postgis-devel at lists.osgeo.org>
Subject: Re: [postgis-devel] KNN and 9.5

Steve,

I tested with my junk dataset and I can't trigger the issue.

Are you able to with this?

CREATE TABLE knn_recheck_geom(gid serial primary key, geom geometry); INSERT INTO knn_recheck_geom(gid,geom) SELECT ROW_NUMBER() OVER(ORDER BY x,y) AS gid, ST_Point(x*0.777,y*0.887) As geom FROM generate_series(-100,1000, 1) AS x CROSS JOIN generate_series(-300,1000,1) As y;

CREATE INDEX idx_knn_recheck_geom on knn_recheck_geom using gist(geom);

CREATE OR REPLACE FUNCTION zz_2nn_angle(geometry) RETURNS float AS $$

-- Here are my wonderful points to KNN search:
WITH index_query AS (

	SELECT edge.geom AS geom
	FROM (SELECT * FROM knn_recheck_geom) AS edge
-- This is my query point
	ORDER BY $1
		<->
	edge.geom LIMIT 2
	),
templine AS (
	SELECT ST_MakeLine(geom) AS geom FROM index_query ),
angle1 AS (
	SELECT ST_Azimuth(ST_StartPoint(geom), $1) angle FROM templine ),
angle2 AS (
	SELECT ST_Azimuth(ST_EndPoint(geom), $1) angle FROM templine
)
SELECT a1.angle - a2.angle FROM angle1 a1, angle2 a2

$$ LANGUAGE SQL;

vacuum analyze knn_recheck_geom;

Then I ran with this query:

SELECT zz_2nn_angle(ST_Point(10,2));  --returns 2.56969144546978 in 11ms

This is testing on PostGIS 2.2.1, PostgreSQL 9.5.0rc1 under windows 7 64-bit

I'm gonna try next on a real dataset.  Maybe I don't have enough test data or distribution is too predictable.

Does the above test crash for you?

Thanks,
Regina

From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On Behalf Of Stephen Mather
Sent: Tuesday, January 05, 2016 10:31 PM
To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
Subject: Re: [postgis-devel] KNN and 9.5

Hi Regina,

The dataset is from Natural Earth: http://www.naturalearthdata.com/http//www.naturalearthdata.com/download/10m/physical/ne_10m_geography_regions_polys.zip

I imported that dataset and transformed to 3857 just to get it in planar coordinates. I affectionately called it regions_polys_subset.

https://gist.github.com/smathermather/320273309124bf8b80a7

But honestly, as long as you throw the knn in a function, any point dataset will do it, I think.

Hope this helps (and helps in time!)!
Cheers,
Best,
Steve

On Sun, Jan 3, 2016 at 9:24 PM, Paragon Corporation <lr at pcorp.us> wrote:
Steve,

Well that sucks.  Can I borrow your dataset to test with?

Thanks,
Regina

From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On Behalf Of Stephen Mather
Sent: Sunday, January 03, 2016 10:41 AM
To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
Subject: Re: [postgis-devel] KNN and 9.5

Hi Regina,

On a lark, I also tested with 2.3.0dev r14538 (9.5rc1)

"POSTGIS="2.3.0dev r14538" GEOS="3.5.0-CAPI-1.9.0 r4084" SFCGAL="1.2.2" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.1, released 2013/08/26" LIBXML="2.9.1" LIBJSON="0.11.99" RASTER"

Same result.

Cheers,
Best,
Steve

On Sun, Jan 3, 2016 at 9:34 AM, Stephen Mather <stephen at smathermather.com> wrote:
2.2.0 and RC1. Should I be trying 2.2 branch?

SELECT version();

"PostgreSQL 9.5rc1 on x86_64-pc-linux-gnu, compiled by gcc (Debian 4.7.2-5) 4.7.2, 64-bit"

SELECT postgis_full_version();

"POSTGIS="2.2.0 r14208" GEOS="3.5.0-CAPI-1.9.0 r4084" SFCGAL="1.2.2" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.1, released 2013/08/26" LIBXML="2.9.1" LIBJSON="0.11.99" RASTER"

On Sun, Jan 3, 2016 at 2:18 AM, Paragon Corporation <lr at pcorp.us> wrote:
Steve,

Haven't had a chance to look thru what you have here and test it out myself. 

The issue I flagged in the ticket was fixed in PostgreSQL 9.5 code base upstream:

http://www.postgresql.org/message-id/55630D9D.3090508@iki.fi

It's my understanding that you should never get that notice again.  So I'm a bit concerned you are.  It's possible you found another area where this issue arises and is not handled.

Are you running PostgreSQL 9.5RC1 and latest PostGIS 2.2 branch (or 2.2.0?).

Thanks,
Regina

From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On Behalf Of Stephen Mather
Sent: Sunday, January 03, 2016 1:56 AM
To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
Subject: [postgis-devel] KNN and 9.5

Hi All,

Short version:
Does Regina's comment on http://trac.osgeo.org/postgis/ticket/2703 regarding ERROR: index returned tuples in wrong order apply to any uses of indices in conjunction with KNN?

Long version:
Digging many of the 2.2 / 9.5 updates. Having fun on break playing with skeleton simplification and using KNN in the process. Yes. For those of you who know me, this is an obsession that won't die quietly.

https://smathermather.files.wordpress.com/2016/01/screen-shot-2016-01-03-at-1-19-26-am.png

I've got a function that does my KNN in the usual style, finds the nearest 2 points, and makes a line from them:

CREATE OR REPLACE FUNCTION zz_knn_wonderful_points (geometry) RETURNS geometry AS $$

-- Here are my wonderful points to KNN search:
WITH index_query AS (

            SELECT edge.geom AS geom
            FROM (SELECT * FROM regions_dpoints WHERE gid = 882) AS edge
-- This is my query point
            ORDER BY $1
                        <->
            edge.geom LIMIT 2
            )
SELECT ST_MakeLine(geom) FROM index_query

$$ LANGUAGE SQL;

The intent is to implement angle values as an importance criterion for simplifying the skeleton as described at minute 2:20 in Balint Miklos video on the scale axis transform: http://balintmiklos.com/scale-axis/The_Scale_Axis_Picture_Show.mp4

Actually, in the final function, I will likely directly calculate the angle and return that instead of the geometry, but I digress.

Regardless, when I use this function as is, it works great in drawing lines connecting the two nearest points to the vertex in the medial axis:

DROP TABLE IF EXISTS test CASCADE;
CREATE TABLE test AS
WITH returnline AS (
            SELECT oid, gid,
                        ST_Union(
                        ST_MakeLine( ST_StartPoint(zz_knn_wonderful_points(subset.geom)), subset.geom),
                        ST_MakeLine( ST_EndPoint(zz_knn_wonderful_points(subset.geom)), subset.geom)
                        )
                        AS geom FROM
                        (SELECT * FROM regions_points WHERE oid = 882) subset
)
SELECT * FROM returnline
;

However, as implemented, this will not work in the case of overlapping geometries, such as Natural Earth's label polygon dataset "ne_10m_geography_regions_polys":

https://smathermather.files.wordpress.com/2016/01/screen-shot-2016-01-03-at-1-33-01-am.png

And so I add a constraint using an integer ID:

CREATE OR REPLACE FUNCTION zz_knn(integer,geometry) RETURNS geometry AS $$

-- Here are my wonderful points to KNN search:
WITH index_query AS (

            SELECT edge.geom AS geom
            FROM (SELECT * FROM regions_dpoints WHERE gid = $1) AS edge
-- This is my query point
            ORDER BY $2
                        <->
            edge.geom LIMIT 2
            )
SELECT ST_MakeLine(geom) FROM index_query

$$ LANGUAGE SQL;

And now it takes much longer and fails with 

"
ERROR:  index returned tuples in wrong order
CONTEXT:  SQL function "zz_knn" statement 1
********** Error **********

ERROR: index returned tuples in wrong order SQL state: XX000
Context: SQL function "zz_knn" statement 1 "

Thanks!
Cheers,
Best,
Steve Mather

_______________________________________________
postgis-devel mailing list
postgis-devel at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/postgis-devel

_______________________________________________
postgis-devel mailing list
postgis-devel at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/postgis-devel

_______________________________________________
postgis-devel mailing list
postgis-devel at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/postgis-devel