Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Subject: Re: R-tree and start/end queries
Date: Wed, 21 Sep 2005 15:29:34 -0400
Message-ID: <F18A6F7CF1661F46920F2CF713122FED46CCAC@mail.aveo.aveopharma.com>
Thread-Topic: [SQL] R-tree and start/end queries
Thread-Index: AcW+4iJNjyY9irNnQ6KhazrwLN0DmwAAD0Sw
From: "Dmitri Bichko" <dbichko@aveopharma.com>
To: "Chris Mungall" <cjm@fruitfly.org>,
	"Sean Davis" <sdavis2@mail.nih.gov>
Cc: <pgsql-sql@postgresql.org>, "Hilmar Lapp" <hlapp@gnf.org>

How does the performance of the R-tree searches compare to the Bio::GFF
binning approach?

I've been wondering for a while how well the postgres builtins would do
for this application.

Dmitri

> -----Original Message-----
> From: pgsql-sql-owner@postgresql.org=20
> [mailto:pgsql-sql-owner@postgresql.org] On Behalf Of Chris Mungall
> Sent: Wednesday, September 21, 2005 3:14 PM
> To: Sean Davis
> Cc: pgsql-sql@postgresql.org; Hilmar Lapp
> Subject: Re: [SQL] R-tree and start/end queries
>=20
>=20
>=20
> On Wed, 21 Sep 2005, Sean Davis wrote:
>=20
> > I have a table like:
> >
> > Create table gf (
> >     pk    serial,
> >     start int,
> >     end   int,
> >     gf    varchar
> > );
> >
> > I want to do queries along the lines of:
> >
> > "find all gf that overlap with (10000,20000)" or
> > "find all gf that overlap with each other"
> >
> > And others.  I have read over the documentation, but I still remain=20=

> > unclear about how to implement R-tree indexing in this=20
> situation.  Any=20
> > suggestions?
>=20
> Hi Sean
>=20
> I'm guessing that this is for some kind of genome database, yep?
>=20
> You may want to look at the chado database which has a=20
> growing library of functions for this sort of thing;=20
> www.gmod.org/schema
>=20
> Here is the code for doing range interval functions; our=20
> featureloc is equivalent to your "gf" (though we separate the=20
> entity from the entity being located). Our fmin and fmax may=20
> be equivalent to your start and end above (unless you=20
> indicate directionality with start>end in which case the=20
> intersection functions get a bit trickier). Our feature_id is=20
> probably equivalent to your gf column.
>=20
> We use the builtin pg types "point" and "box" and make an=20
> RTREE index over
> this:
>=20
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> --
> -- functions operating on featureloc ranges
> --
>=20
> -- create a point
> CREATE OR REPLACE FUNCTION create_point (int, int) RETURNS=20
> point AS  'SELECT point ($1, $2)' LANGUAGE 'sql';
>=20
> -- create a range box
> -- (make this immutable so we can index it)
> CREATE OR REPLACE FUNCTION boxrange (int, int) RETURNS box AS=20
>  'SELECT box (create_point(0, $1),=20
> create_point($2,500000000))' LANGUAGE 'sql' IMMUTABLE;
>=20
> -- create a query box
> CREATE OR REPLACE FUNCTION boxquery (int, int) RETURNS box AS=20
>  'SELECT box (create_point($1, $2), create_point($1, $2))'=20
> LANGUAGE 'sql' IMMUTABLE;
>=20
> --functional index that depends on the above functions
> CREATE INDEX binloc_boxrange ON featureloc USING RTREE=20
> (boxrange(fmin, fmax));
>=20
>=20
> CREATE OR REPLACE FUNCTION featureloc_slice(int, int) RETURNS=20
> setof featureloc AS
>   'SELECT * from featureloc where boxquery($1, $2) @=20
> boxrange(fmin,fmax)' LANGUAGE 'sql';
>=20
> CREATE OR REPLACE FUNCTION featureloc_slice(varchar, int, int)
>   RETURNS setof featureloc AS
>   'SELECT featureloc.*
>    FROM featureloc
>    INNER JOIN feature AS srcf ON (srcf.feature_id =3D=20
> featureloc.srcfeature_id)
>    WHERE boxquery($2, $3) @ boxrange(fmin,fmax)
>    AND srcf.name =3D $1 '
> LANGUAGE 'sql';
>=20
> CREATE OR REPLACE FUNCTION featureloc_slice(int, int, int)
>   RETURNS setof featureloc AS
>   'SELECT *
>    FROM featureloc
>    WHERE boxquery($2, $3) @ boxrange(fmin,fmax)
>    AND srcfeature_id =3D $1 '
> LANGUAGE 'sql';
>=20
> -- can we not just do these as views?
> CREATE OR REPLACE FUNCTION feature_overlaps(int)
>  RETURNS setof feature AS
>  'SELECT feature.*
>   FROM feature
>    INNER JOIN featureloc AS x ON (x.feature_id=3Dfeature.feature_id)
>    INNER JOIN featureloc AS y ON (y.feature_id=3D$1)
>   WHERE
>    x.srcfeature_id =3D y.srcfeature_id            AND
>    ( x.fmax >=3D y.fmin AND x.fmin <=3D y.fmax ) '
> LANGUAGE 'sql';
>=20
> CREATE OR REPLACE FUNCTION feature_disjoint_from(int)
>  RETURNS setof feature AS
>  'SELECT feature.*
>   FROM feature
>    INNER JOIN featureloc AS x ON (x.feature_id=3Dfeature.feature_id)
>    INNER JOIN featureloc AS y ON (y.feature_id=3D$1)
>   WHERE
>    x.srcfeature_id =3D y.srcfeature_id            AND
>    ( x.fmax < y.fmin OR x.fmin > y.fmax ) '
> LANGUAGE 'sql';
>=20
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>=20
> Cheers
> Chris
>=20
> > Thanks,
> > Sean
> >
> >
> > ---------------------------(end of=20
> > broadcast)---------------------------
> > TIP 1: if posting/reading through Usenet, please send an appropriate
> >        subscribe-nomail command to majordomo@postgresql.org=20
> so that your
> >        message can get through to the mailing list cleanly
> >
>=20
>=20
>=20
> ---------------------------(end of=20
> broadcast)---------------------------
> TIP 6: explain analyze is your friend
>=20
The information transmitted is intended only for the person or entity to =
which it is addressed and may contain confidential and/or privileged mate=
rial. Any review, retransmission, dissemination or other use of, or takin=
g of any action in reliance upon, this information by persons or entities=
 other than the intended recipient is prohibited. If you received this in=
 error, please contact the sender and delete the material from any comput=
er