[PostGIS] #6026: Distance operator <-> returns "tuple order" error

[PostGIS]

#6026: Distance operator <-> returns "tuple order" error
----------------------------------------------+---------------------
 Reporter:  dirc                              |      Owner:  pramsey
     Type:  defect                            |     Status:  new
 Priority:  medium                            |  Milestone:
Component:  postgis                           |    Version:  3.5.x
 Keywords:  distance, operator, tuple, order  |
----------------------------------------------+---------------------
 Since Postgis v3.5 the distance operator sometimes returns:
 "ERROR:  index returned tuples in wrong order"

 In Postgis v3.4 we do not get this error.

 The issue can be reproduced with this small table of 5 rows contain a
 Polygon. The table index. We want to order the Polygons by distance to a
 given Point.
 For some Points it returns the above error.
 I have added two points, one that works and one with the error.

 Reproduce:

 {{{#!sql
 CREATE TABLE reproduce (
     id SERIAL PRIMARY KEY,
     geometry GEOMETRY(POLYGON, 28992)
 );
 INSERT INTO reproduce (geometry) VALUES
     (ST_GeomFromText('POLYGON ((133894.531 490000, 132700 490000, 132460
 490000, 131703.958 489011.71, 131695 489000, 132880 489000, 132880
 488416.725, 133206.605 488583.011, 134029.81 489022.36, 133917.695 490000,
 133894.531 490000))', 28992)),
     (ST_GeomFromText('POLYGON ((138000 492000, 141276.49 492000, 141050
 492550, 140967.11 492751.305, 139951.651 495217.42, 139490.072 495217.42,
 136358.892 495217.42, 135900 495217.42, 135301.1 495217.42, 135118.887
 495296.573, 135115.873 495264.338, 135106.301 495164.456, 135098.485
 495065.802, 135090.476 494967.014, 135085.764 494917.296, 135078.439
 494866.459, 135070.381 494817.483, 135060.353 494767.172, 135036.351
 494674.319, 135017.779 494615.505, 134991.438 494544.049, 134972.66
 494501.055, 134948.148 494446.666, 134922.544 494398.914, 134872.859
 494311.273, 134859.929 494292.444, 134843.402 494264.587, 134815.107
 494200.454, 134770.855 494120.756, 134728.422 494053.048, 134932.74
 493923.77, 133708.3 491825.92, 133917.695 490000, 134029.81 489022.36,
 138000 492000))', 28992)),
     (ST_GeomFromText('POLYGON ((131215.201 487105.005, 134029.81
 486992.15, 134029.81 489022.36, 133206.605 488583.011, 132880 488416.725,
 132198.685 488069.845, 131375.721 487651.916, 131199.012 487560.733,
 131198.76 487560.603, 131215.201 487105.005))', 28992)),
     (ST_GeomFromText('POLYGON ((134029.81 489022.36, 136889.1 488581.7,
 138000 492000, 134029.81 489022.36))', 28992)),
     (ST_GeomFromText('POLYGON ((133917.695 490000, 133708.3 491825.92,
 133541.312 491951.805, 133460 491840, 132820 491000, 132210 490190, 132460
 490000, 132700 490000, 133894.531 490000, 133917.695 490000))', 28992));

 --- create index
 CREATE INDEX idx_reproduce_geometry
 ON reproduce USING GIST(geometry);

 --- Query without error, that uses the index
 SET enable_seqscan = OFF; --- Disable the use of Quicksort algoritm, to
 ensure the index is used.
 explain analyse
 SELECT id
 FROM reproduce
 ORDER BY geometry <-> ST_SetSRID(ST_MakePoint(133000, 489000), 28992)
 LIMIT 4;

 --- Reproduce error
 SET enable_seqscan = OFF;
 explain analyse
 SELECT id
 FROM reproduce
 ORDER BY geometry <-> ST_SetSRID(ST_MakePoint(133718, 489222), 28992)
 LIMIT 4;
 }}}


 To be complete, here is the postgis we use in production:

 {{{
 SELECT version();
 SELECT postgis_full_version();
 POSTGIS="3.5.2 0" [EXTENSION] PGSQL="160" GEOS="3.13.0-CAPI-1.19.0"
 PROJ="9.0.1 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org
 USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db"
 (compiled against PROJ 9.0.1) LIBXML="2.10.4" LIBJSON="0.15"
 LIBPROTOBUF="1.4.1" WAGYU="0.5.0 (Internal)"
 }}}

 I reproduced it on different postgis version using postgis docker images:
 postgis/postgis:16-3.4 -> no errors
 postgis/postgis:16-3.5 -> gives error
 postgis/postgis:18-3.6 -> gives error

 {{{
 TAG=16-3.4
 PORT=${TAG//[^0-9]/}
 docker run --rm -d --name postgis-$TAG -e POSTGRES_PASSWORD=postgres -p
 $PORT:5432  postgis/postgis:$TAG

 psql -h localhost -p $PORT -U postgres -W postgres
 #pwd: postgres
 }}}
-- 
Ticket URL: <https://trac.osgeo.org/postgis/ticket/6026>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.