sorting by distance?

[Andreas Petersson]

hi!
im using hibernate-spatial with postgis.
first of all, i wanted to hear what your approach is to this problem,
second, i need suggestions for this strange stacktrace im getting.
i wanted to do a simple search - sort by distance, using an index. it
turned out its harder than i thought.
typically i use the Criteria API from hibernate.
looking through the javadoc, i did not find a Subclass/usages of
org.hibernate.criterion.Order, so i thought i need to roll my own.
a very simple implementation is the following: (omitting the constructor)

public class DistanceOrder extends Order {
    public String toSqlString(Criteria criteria, CriteriaQuery
criteriaQuery) throws HibernateException {
        return "distance_sphere(" + propertyName + ", GeomFromText('" +
p.toText() + "', " + p.getSRID() + ")) asc";
}


suprisingly, this did work, but the query took ages.. obviously its not
using the index.
since im interested in the nearest 5-10 results, i decided to do the
following: create a bounding box (this is using the index) and double
its size until i match the desired number of results.
then apply the sorting my distance afterwards.  - is filter the right
approach here?

this will create  bunch of queries but for the most common cases,
queries in dense cities, i will get results quickly. plus i can  create
very flexible Criteria queries.
a downside is i have to supply a factory for fresh identical queries to
execute new queries.

the class looks like this:

public class DistanceOrder extends Order {
    private final Point p;
    private final String propertyName;
    private final long needNearest;
    private final transient Provider<Criteria> freshCriteria;

    public DistanceOrder(final String propertyName, Point point, long
needNearest, Provider<Criteria> freshCriteria) {
        super(propertyName, true);
        this.p = point;
        this.propertyName = propertyName;
        this.needNearest = needNearest;
        this.freshCriteria = freshCriteria;
    }

    int boxSize = 1;

    @Override
    public String toSqlString(Criteria criteria, CriteriaQuery
criteriaQuery) throws HibernateException {
        if (freshCriteria == null) {
            throw new ImplementationException("did not expect to be
serialized..");
        }
        int lastCount = 0;
        while (lastCount < needNearest) { //recurse here
            boxSize *= 2;
            final Criteria newCriteria = freshCriteria.get();
            addBoxTocriteria(newCriteria);
            lastCount = (Integer)
newCriteria.setProjection(Projections.rowCount()).uniqueResult();
        }
        addBoxTocriteria(criteria); //the real stuff
        return "distance_sphere(" + propertyName + ", GeomFromText('" +
p.toText() + "', " + p.getSRID() + ")) asc";
    }

    private void addBoxTocriteria(Criteria newCriteria) {
        final Envelope envelope = new Envelope(p.getCoordinates()[0]);
        envelope.expandBy(boxSize);
        newCriteria.add(SpatialRestrictions.filter(propertyName,
envelope, p.getSRID()));
    }
}

the matching boudning box was found - containing 988 elements.
then the final query - restricting by last known bounding box+sorting is
being issued and here comes my problem: i get
org.postgresql.util.PSQLException: Der Spaltenindex 1 ist ausserhalb des
gültigen Bereichs. Anzahl Spalten: 0.
means: index out of range.
log4jdbc tells me that the index number 1 was set to the polygon. but no
columns were bound to the preparedStatement.

stackrace below:
do you have any idea why this is happening?
may this be an incompatibility to hibernate 3.3?

 INFO 09:44:40,102 - net.sf.log4jdbc.Slf4jSpyLogDelegator:325 - select
count(*) as y0_ from public.b_hotel this_ where (this_.coordinate &&
SRID=4326;POLYGON((-32 -32,-32 32,32 32,32 -32,-32 -32)) ) {executed in
62 msec}
ERROR 09:44:51,415 - net.sf.log4jdbc.Slf4jSpyLogDelegator:102 - 5.
PreparedStatement.setObject(1, SRID=4326;POLYGON((-32 -32,-32 32,32
32,32 -32,-32 -32)))
org.postgresql.util.PSQLException: Der Spaltenindex 1 ist ausserhalb des
gültigen Bereichs. Anzahl Spalten: 0.
    at
org.postgresql.core.v3.SimpleParameterList.bind(SimpleParameterList.java:57)
    at
org.postgresql.core.v3.SimpleParameterList.setStringParameter(SimpleParameterList.java:121)
    at
org.postgresql.jdbc2.AbstractJdbc2Statement.bindString(AbstractJdbc2Statement.java:2114)
    at
org.postgresql.jdbc2.AbstractJdbc2Statement.setString(AbstractJdbc2Statement.java:1238)
    at
org.postgresql.jdbc2.AbstractJdbc2Statement.setPGobject(AbstractJdbc2Statement.java:1540)
    at
org.postgresql.jdbc2.AbstractJdbc2Statement.setObject(AbstractJdbc2Statement.java:1730)
    at
net.sf.log4jdbc.PreparedStatementSpy.setObject(PreparedStatementSpy.java:944)
    at
com.mchange.v2.c3p0.impl.NewProxyPreparedStatement.setObject(NewProxyPreparedStatement.java:365)
    at
org.hibernatespatial.AbstractDBGeometryType.nullSafeSet(AbstractDBGeometryType.java:154)
    at
org.hibernatespatial.GeometryUserType.nullSafeSet(GeometryUserType.java:184)
    at org.hibernate.type.CustomType.nullSafeSet(CustomType.java:179)
    at
org.hibernate.loader.Loader.bindPositionalParameters(Loader.java:1728)
    at org.hibernate.loader.Loader.bindParameterValues(Loader.java:1699)
    at org.hibernate.loader.Loader.prepareQueryStatement(Loader.java:1589)
    at org.hibernate.loader.Loader.doQuery(Loader.java:696)
    at
org.hibernate.loader.Loader.doQueryAndInitializeNonLazyCollections(Loader.java:259)
    at org.hibernate.loader.Loader.doList(Loader.java:2228)
    at org.hibernate.loader.Loader.listIgnoreQueryCache(Loader.java:2125)
    at org.hibernate.loader.Loader.list(Loader.java:2120)
    at
org.hibernate.loader.criteria.CriteriaLoader.list(CriteriaLoader.java:118)
    at org.hibernate.impl.SessionImpl.list(SessionImpl.java:1596)
    at org.hibernate.impl.CriteriaImpl.list(CriteriaImpl.java:306)
    at org.hibernate.impl.CriteriaImpl.uniqueResult(CriteriaImpl.java:328)
    at quan.data.dao.booking.hotel.HotelDao.getNearest(HotelDao.java:28)

_______________________________________________
hibernatespatial-users mailing list
[hidden email]
http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users

[Davis Ford]

Andreas -- it seems that if you are trying to sort by distance, then
it follows that you want to fetch all the items that have a spatial
column.  If this is true, why not just do a fetch all, and sort them
in Java.  This is a lot easier, and potentially faster than trying to
do this in the database.

Assuming you are using JTS as your java geometry object model, you can
also pull in the Geotools referencing components to transform to a
cartesian coordinate system with units in meters, and easily calculate
distances on the collection.

Just a suggestion -- I'd be curious what solution you finally settle on.

Regards,
Davis

On Tue, Feb 24, 2009 at 4:00 AM, Andreas Petersson <[hidden email]> wrote:

> hi!
> im using hibernate-spatial with postgis.
> first of all, i wanted to hear what your approach is to this problem,
> second, i need suggestions for this strange stacktrace im getting.
> i wanted to do a simple search - sort by distance, using an index. it
> turned out its harder than i thought.
> typically i use the Criteria API from hibernate.
> looking through the javadoc, i did not find a Subclass/usages of
> org.hibernate.criterion.Order, so i thought i need to roll my own.
> a very simple implementation is the following: (omitting the constructor)
>
> public class DistanceOrder extends Order {
>    public String toSqlString(Criteria criteria, CriteriaQuery
> criteriaQuery) throws HibernateException {
>        return "distance_sphere(" + propertyName + ", GeomFromText('" +
> p.toText() + "', " + p.getSRID() + ")) asc";
> }
>
>
> suprisingly, this did work, but the query took ages.. obviously its not
> using the index.
> since im interested in the nearest 5-10 results, i decided to do the
> following: create a bounding box (this is using the index) and double
> its size until i match the desired number of results.
> then apply the sorting my distance afterwards.  - is filter the right
> approach here?
>
> this will create  bunch of queries but for the most common cases,
> queries in dense cities, i will get results quickly. plus i can  create
> very flexible Criteria queries.
> a downside is i have to supply a factory for fresh identical queries to
> execute new queries.
>
> the class looks like this:
>
> public class DistanceOrder extends Order {
>    private final Point p;
>    private final String propertyName;
>    private final long needNearest;
>    private final transient Provider<Criteria> freshCriteria;
>
>    public DistanceOrder(final String propertyName, Point point, long
> needNearest, Provider<Criteria> freshCriteria) {
>        super(propertyName, true);
>        this.p = point;
>        this.propertyName = propertyName;
>        this.needNearest = needNearest;
>        this.freshCriteria = freshCriteria;
>    }
>
>    int boxSize = 1;
>
>    @Override
>    public String toSqlString(Criteria criteria, CriteriaQuery
> criteriaQuery) throws HibernateException {
>        if (freshCriteria == null) {
>            throw new ImplementationException("did not expect to be
> serialized..");
>        }
>        int lastCount = 0;
>        while (lastCount < needNearest) { //recurse here
>            boxSize *= 2;
>            final Criteria newCriteria = freshCriteria.get();
>            addBoxTocriteria(newCriteria);
>            lastCount = (Integer)
> newCriteria.setProjection(Projections.rowCount()).uniqueResult();
>        }
>        addBoxTocriteria(criteria); //the real stuff
>        return "distance_sphere(" + propertyName + ", GeomFromText('" +
> p.toText() + "', " + p.getSRID() + ")) asc";
>    }
>
>    private void addBoxTocriteria(Criteria newCriteria) {
>        final Envelope envelope = new Envelope(p.getCoordinates()[0]);
>        envelope.expandBy(boxSize);
>        newCriteria.add(SpatialRestrictions.filter(propertyName,
> envelope, p.getSRID()));
>    }
> }
>
> the matching boudning box was found - containing 988 elements.
> then the final query - restricting by last known bounding box+sorting is
> being issued and here comes my problem: i get
> org.postgresql.util.PSQLException: Der Spaltenindex 1 ist ausserhalb des
> gültigen Bereichs. Anzahl Spalten: 0.
> means: index out of range.
> log4jdbc tells me that the index number 1 was set to the polygon. but no
> columns were bound to the preparedStatement.
>
> stackrace below:
> do you have any idea why this is happening?
> may this be an incompatibility to hibernate 3.3?
>
>  INFO 09:44:40,102 - net.sf.log4jdbc.Slf4jSpyLogDelegator:325 - select
> count(*) as y0_ from public.b_hotel this_ where (this_.coordinate &&
> SRID=4326;POLYGON((-32 -32,-32 32,32 32,32 -32,-32 -32)) ) {executed in
> 62 msec}
> ERROR 09:44:51,415 - net.sf.log4jdbc.Slf4jSpyLogDelegator:102 - 5.
> PreparedStatement.setObject(1, SRID=4326;POLYGON((-32 -32,-32 32,32
> 32,32 -32,-32 -32)))
> org.postgresql.util.PSQLException: Der Spaltenindex 1 ist ausserhalb des
> gültigen Bereichs. Anzahl Spalten: 0.
>    at
> org.postgresql.core.v3.SimpleParameterList.bind(SimpleParameterList.java:57)
>    at
> org.postgresql.core.v3.SimpleParameterList.setStringParameter(SimpleParameterList.java:121)
>    at
> org.postgresql.jdbc2.AbstractJdbc2Statement.bindString(AbstractJdbc2Statement.java:2114)
>    at
> org.postgresql.jdbc2.AbstractJdbc2Statement.setString(AbstractJdbc2Statement.java:1238)
>    at
> org.postgresql.jdbc2.AbstractJdbc2Statement.setPGobject(AbstractJdbc2Statement.java:1540)
>    at
> org.postgresql.jdbc2.AbstractJdbc2Statement.setObject(AbstractJdbc2Statement.java:1730)
>    at
> net.sf.log4jdbc.PreparedStatementSpy.setObject(PreparedStatementSpy.java:944)
>    at
> com.mchange.v2.c3p0.impl.NewProxyPreparedStatement.setObject(NewProxyPreparedStatement.java:365)
>    at
> org.hibernatespatial.AbstractDBGeometryType.nullSafeSet(AbstractDBGeometryType.java:154)
>    at
> org.hibernatespatial.GeometryUserType.nullSafeSet(GeometryUserType.java:184)
>    at org.hibernate.type.CustomType.nullSafeSet(CustomType.java:179)
>    at
> org.hibernate.loader.Loader.bindPositionalParameters(Loader.java:1728)
>    at org.hibernate.loader.Loader.bindParameterValues(Loader.java:1699)
>    at org.hibernate.loader.Loader.prepareQueryStatement(Loader.java:1589)
>    at org.hibernate.loader.Loader.doQuery(Loader.java:696)
>    at
> org.hibernate.loader.Loader.doQueryAndInitializeNonLazyCollections(Loader.java:259)
>    at org.hibernate.loader.Loader.doList(Loader.java:2228)
>    at org.hibernate.loader.Loader.listIgnoreQueryCache(Loader.java:2125)
>    at org.hibernate.loader.Loader.list(Loader.java:2120)
>    at
> org.hibernate.loader.criteria.CriteriaLoader.list(CriteriaLoader.java:118)
>    at org.hibernate.impl.SessionImpl.list(SessionImpl.java:1596)
>    at org.hibernate.impl.CriteriaImpl.list(CriteriaImpl.java:306)
>    at org.hibernate.impl.CriteriaImpl.uniqueResult(CriteriaImpl.java:328)
>    at quan.data.dao.booking.hotel.HotelDao.getNearest(HotelDao.java:28)
>
> _______________________________________________
> hibernatespatial-users mailing list
> [hidden email]
> http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users
>

--
Zeno Consulting, Inc.
home: http://www.zenoconsulting.biz
blog: http://zenoconsulting.wikidot.com
p: 248.894.4922
f: 313.884.2977
_______________________________________________
hibernatespatial-users mailing list
[hidden email]
http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users

[Andreas Petersson]

hi!
i thought about that, too, sorting the whole stuff inside java. they are
1000 elements now, but in very dense areas, those might as well be 20k.
furthermore, the objects are quite heavyweight (hotel entity), they have
numerous lazy loaded collections attached and have fields like
"description" which might become 4k bytes by itself.
so i want to avoid the memory + cpu overhead of loading all entities with
hibernate.
in the common case i do need the nearest 5 entities - one page -  matching
the search restrictions. when using pagination and navigate to page 20, i
will need  to extend the bounding box further  to include 100 elements and
sort the entities in a bigger bounding box.

i think idea of iterative widening using SpatialRestrictions.filter is a
quite flexible solution, as i can apply the surround search to any
hibernate criteria query. if i figure out how to clone a hibernate criteria
the provider<Criteria> might become obsolete.
according to the hibernate irc, cloning of Criteria should be possible but
it is an open issue since 2005. :(

http://opensource.atlassian.com/projects/hibernate/browse/HHH-1046
mybe some of you vote for this issue.

as well as the additional needNearest attribute, this can be calculated
from maxResults and firstResult

i worry a bit that in regions with distorted lat/long proportions - like
the north pole envelope.expandBy(boxSize) will get a very slim trapezoid
area, even if i widen by a lot i will not have the "true" nearest point
inside the bounding box.  so maybe i should construct a geometry that is a
physical circle using Point.buffer() around my query coordinate and use
SpatialRestrictions.within for filtering, will i get accurate results this
way?

but - my main problem still remains that the combination of bounding box +
sort produces an
error.

regards,
andreas

On Tue, 24 Feb 2009 10:20:55 -0500, Davis Ford
<[hidden email]> wrote:

> Andreas -- it seems that if you are trying to sort by distance, then
> it follows that you want to fetch all the items that have a spatial
> column.  If this is true, why not just do a fetch all, and sort them
> in Java.  This is a lot easier, and potentially faster than trying to
> do this in the database.
>
> Assuming you are using JTS as your java geometry object model, you can
> also pull in the Geotools referencing components to transform to a
> cartesian coordinate system with units in meters, and easily calculate
> distances on the collection.
>
> Just a suggestion -- I'd be curious what solution you finally settle on.
>
> Regards,
> Davis
>

_______________________________________________
hibernatespatial-users mailing list
[hidden email]
http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users

[Davis Ford]

On Tue, Feb 24, 2009 at 11:54 AM, Andreas Petersson
<[hidden email]> wrote:
> hi!
> i thought about that, too, sorting the whole stuff inside java. they are
> 1000 elements now, but in very dense areas, those might as well be 20k.
> furthermore, the objects are quite heavyweight (hotel entity), they have
> numerous lazy loaded collections attached and have fields like
> "description" which might become 4k bytes by itself.
> so i want to avoid the memory + cpu overhead of loading all entities with
> hibernate.

If you lazy load everything else, loading 20K + geometries should be
no problem.  I still think its an easier solution.


> in the common case i do need the nearest 5 entities - one page -  matching
> the search restrictions. when using pagination and navigate to page 20, i
> will need  to extend the bounding box further  to include 100 elements and
> sort the entities in a bigger bounding box.

Instead of distance-to you could instead filter it first on something
like contains / within / intersects with -- then you have a smaller
subset loaded...finish the distance calculations in java.

>
> i think idea of iterative widening using SpatialRestrictions.filter is a
> quite flexible solution, as i can apply the surround search to any
> hibernate criteria query. if i figure out how to clone a hibernate criteria
> the provider<Criteria> might become obsolete.
> according to the hibernate irc, cloning of Criteria should be possible but
> it is an open issue since 2005. :(
>
> http://opensource.atlassian.com/projects/hibernate/browse/HHH-1046
> mybe some of you vote for this issue.
>
> as well as the additional needNearest attribute, this can be calculated
> from maxResults and firstResult
>
> i worry a bit that in regions with distorted lat/long proportions - like
> the north pole envelope.expandBy(boxSize) will get a very slim trapezoid
> area, even if i widen by a lot i will not have the "true" nearest point
> inside the bounding box.  so maybe i should construct a geometry that is a
> physical circle using Point.buffer() around my query coordinate and use
> SpatialRestrictions.within for filtering, will i get accurate results this
> way?

How many hotels are in the north pole?  :)

You won't get accurate results, unless you do a math transform.  I
just worked on this myself.  Point.buffer( ) is *not* going to give
you what you expect from JTS if your coordinate reference system is
geographic (i.e. WGS84).  This is why you need to grab the referencing
module from Geotools, and do a MathTransform to a cartesian coordinate
system; then you can calculate a buffer accurately.

>
> but - my main problem still remains that the combination of bounding box +
> sort produces an
> error.
>
> regards,
> andreas
>
> On Tue, 24 Feb 2009 10:20:55 -0500, Davis Ford
> <[hidden email]> wrote:
>> Andreas -- it seems that if you are trying to sort by distance, then
>> it follows that you want to fetch all the items that have a spatial
>> column.  If this is true, why not just do a fetch all, and sort them
>> in Java.  This is a lot easier, and potentially faster than trying to
>> do this in the database.
>>
>> Assuming you are using JTS as your java geometry object model, you can
>> also pull in the Geotools referencing components to transform to a
>> cartesian coordinate system with units in meters, and easily calculate
>> distances on the collection.
>>
>> Just a suggestion -- I'd be curious what solution you finally settle on.
>>
>> Regards,
>> Davis
>>
>
> _______________________________________________
> hibernatespatial-users mailing list
> [hidden email]
> http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users
>

--
Zeno Consulting, Inc.
home: http://www.zenoconsulting.biz
blog: http://zenoconsulting.wikidot.com
p: 248.894.4922
f: 313.884.2977
_______________________________________________
hibernatespatial-users mailing list
[hidden email]
http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users

[Andreas Petersson]

i solved the problem - sort of . it seems it is not possible to modify
an existing criteria with new restrictions,
because at the time  toSqlString in the order class is called, a large
portion of the sql is already rendered by hibernate.
the temorary solution is to calcuate the bounding box beforehand and
assigning the restriction for it manually to the main query.
looks a bit ugly in java code right now, but works. i think it may be
possible to clean it up a little.

> but - my main problem still remains that the combination of bounding box +
> sort produces an
> error.
>  

_______________________________________________
hibernatespatial-users mailing list
[hidden email]
http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users

[Andreas Petersson]

this is my current solution: looks quite good, in the general case, but
i have not tested it fully.
its a bit hacky, and relies on distance_sphere as sorting method..


public class DistanceOrder extends Order {
    private final Point p;
    private final String propertyName;
    private final transient Provider<Criteria> freshCriteria;
    private final Geometry paramToBeModified;

    public DistanceOrder(final String propertyName, Point point,
Criteria origCriteria, Provider<Criteria> freshCriteria) {
        super(null, false);
        this.p = point;
        this.propertyName = propertyName;
        this.freshCriteria = freshCriteria;
        paramToBeModified = p.buffer(1);          //just dummy to get
consistent number of vertexes
        paramToBeModified.setSRID(p.getSRID());
        origCriteria.add(SpatialRestrictions.filter("coordinate",
paramToBeModified));

    }

//    double boxSize = 1;

    @Override
    public String toSqlString(Criteria criteria, CriteriaQuery
criteriaQuery) throws HibernateException {
        final Geometry targetCoords = calcBoxSize(p);
        //hack in values of coordinates to bind this new value to
preparedstatement
        for (int i = 0; i < paramToBeModified.getCoordinates().length;
i++) {
            Coordinate coordinate = paramToBeModified.getCoordinates()[i];
            coordinate.setCoordinate(targetCoords.getCoordinates()[i]);
        }
        paramToBeModified.geometryChanged();
        String col = criteriaQuery.getColumn(criteria, propertyName);
        return "distance_sphere(" + col + ", GeomFromText('" +
p.toText() + "', " + p.getSRID() + ")) asc";
    }

    private Geometry calcBoxSize(Point p) {
        int lastCount = 0;
        double boxSize = 1;
        Geometry value = null;
        final Criteria criteria = freshCriteria.get();
        int searchFor = 1;
        if (criteria instanceof CriteriaImpl) {
            final CriteriaImpl impl = (CriteriaImpl) criteria;
            final Integer max = impl.getMaxResults();
            Integer first = impl.getFirstResult();
            if (max == null) {
                return p.buffer(Double.MIN_VALUE); //no max -> no
restriction.
            }
            if (first == null) {   //no firstResult = start with first
element.
                first = 0;
            }
            searchFor = max + first;
        }
        int hardCap = (Integer)
criteria.setProjection(Projections.rowCount()).uniqueResult();
        if (hardCap <= searchFor) {
            return p.buffer(Double.MIN_VALUE);   //more desired results
than possible results->no restriction
        }
        while (lastCount <= searchFor) { //recurse here
            boxSize *= 2;
            final Criteria newCriteria = freshCriteria.get();
            value = p.buffer(boxSize);
            value.setSRID(p.getSRID());
            newCriteria.add(SpatialRestrictions.filter("coordinate",
value));
            lastCount = (Integer)
newCriteria.setProjection(Projections.rowCount()).uniqueResult();
        }
        return value;
    }
_______________________________________________
hibernatespatial-users mailing list
[hidden email]
http://www.hibernatespatial.org/cgi-bin/mailman/listinfo/hibernatespatial-users