pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedR-tree and start/end queries
5+ messages / 5 participants
[nested] [flat]
* R-tree and start/end queries
@ 2005-09-21 17:52 Sean Davis <sdavis2@mail.nih.gov>
2005-09-21 18:38 ` Re: R-tree and start/end queries Bruno Wolff III <bruno@wolff.to>
2005-09-21 19:13 ` Re: R-tree and start/end queries Chris Mungall <cjm@fruitfly.org>
0 siblings, 2 replies; 5+ messages in thread
From: Sean Davis @ 2005-09-21 17:52 UTC (permalink / raw)
To: pgsql-sql
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 unclear
about how to implement R-tree indexing in this situation. Any suggestions?
Thanks,
Sean
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: R-tree and start/end queries
2005-09-21 17:52 R-tree and start/end queries Sean Davis <sdavis2@mail.nih.gov>
@ 2005-09-21 18:38 ` Bruno Wolff III <bruno@wolff.to>
2005-09-21 19:43 ` Re: R-tree and start/end queries Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 5+ messages in thread
From: Bruno Wolff III @ 2005-09-21 18:38 UTC (permalink / raw)
To: Sean Davis <sdavis2@mail.nih.gov>; +Cc: pgsql-sql
On Wed, Sep 21, 2005 at 13:52:40 -0400,
Sean Davis <sdavis2@mail.nih.gov> wrote:
> 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 unclear
> about how to implement R-tree indexing in this situation. Any suggestions?
There is a built in type for line segments that uses floating point. That
will probably be usable by you directly unless the integers can can large
enough that precision is a problem. There is an overlaps operator for the
geometric types that could be used to answer your sample questions.
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: R-tree and start/end queries
2005-09-21 17:52 R-tree and start/end queries Sean Davis <sdavis2@mail.nih.gov>
2005-09-21 18:38 ` Re: R-tree and start/end queries Bruno Wolff III <bruno@wolff.to>
@ 2005-09-21 19:43 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 5+ messages in thread
From: Tom Lane @ 2005-09-21 19:43 UTC (permalink / raw)
To: Bruno Wolff III <bruno@wolff.to>; +Cc: Sean Davis <sdavis2@mail.nih.gov>; pgsql-sql
Bruno Wolff III <bruno@wolff.to> writes:
> There is a built in type for line segments that uses floating point. That
> will probably be usable by you directly unless the integers can can large
> enough that precision is a problem. There is an overlaps operator for the
> geometric types that could be used to answer your sample questions.
However, there's no built-in rtree opclass for that datatype, so he'd
still be stuck with respect to getting indexing support for overlaps
queries.
I think the contrib/seg datatype might help, though the precision issue
is still a possible problem.
regards, tom lane
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: R-tree and start/end queries
2005-09-21 17:52 R-tree and start/end queries Sean Davis <sdavis2@mail.nih.gov>
@ 2005-09-21 19:13 ` Chris Mungall <cjm@fruitfly.org>
1 sibling, 0 replies; 5+ messages in thread
From: Chris Mungall @ 2005-09-21 19:13 UTC (permalink / raw)
To: Sean Davis <sdavis2@mail.nih.gov>; +Cc: pgsql-sql@postgresql.org, Hilmar Lapp <hlapp@gnf.org>
On Wed, 21 Sep 2005, Sean Davis wrote:
> 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 unclear
> about how to implement R-tree indexing in this situation. Any suggestions?
Hi Sean
I'm guessing that this is for some kind of genome database, yep?
You may want to look at the chado database which has a growing library of
functions for this sort of thing; www.gmod.org/schema
Here is the code for doing range interval functions; our featureloc is
equivalent to your "gf" (though we separate the entity from the entity
being located). Our fmin and fmax may be equivalent to your start and end
above (unless you indicate directionality with start>end in which case the
intersection functions get a bit trickier). Our feature_id is probably
equivalent to your gf column.
We use the builtin pg types "point" and "box" and make an RTREE index over
this:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- functions operating on featureloc ranges
--
-- create a point
CREATE OR REPLACE FUNCTION create_point (int, int) RETURNS point AS
'SELECT point ($1, $2)'
LANGUAGE 'sql';
-- create a range box
-- (make this immutable so we can index it)
CREATE OR REPLACE FUNCTION boxrange (int, int) RETURNS box AS
'SELECT box (create_point(0, $1), create_point($2,500000000))'
LANGUAGE 'sql' IMMUTABLE;
-- create a query box
CREATE OR REPLACE FUNCTION boxquery (int, int) RETURNS box AS
'SELECT box (create_point($1, $2), create_point($1, $2))'
LANGUAGE 'sql' IMMUTABLE;
--functional index that depends on the above functions
CREATE INDEX binloc_boxrange ON featureloc USING RTREE (boxrange(fmin, fmax));
CREATE OR REPLACE FUNCTION featureloc_slice(int, int) RETURNS setof featureloc AS
'SELECT * from featureloc where boxquery($1, $2) @ boxrange(fmin,fmax)'
LANGUAGE 'sql';
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 = featureloc.srcfeature_id)
WHERE boxquery($2, $3) @ boxrange(fmin,fmax)
AND srcf.name = $1 '
LANGUAGE 'sql';
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 = $1 '
LANGUAGE 'sql';
-- 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=feature.feature_id)
INNER JOIN featureloc AS y ON (y.feature_id=$1)
WHERE
x.srcfeature_id = y.srcfeature_id AND
( x.fmax >= y.fmin AND x.fmin <= y.fmax ) '
LANGUAGE 'sql';
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=feature.feature_id)
INNER JOIN featureloc AS y ON (y.feature_id=$1)
WHERE
x.srcfeature_id = y.srcfeature_id AND
( x.fmax < y.fmin OR x.fmin > y.fmax ) '
LANGUAGE 'sql';
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Cheers
Chris
> Thanks,
> Sean
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly
>
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: R-tree and start/end queries
@ 2005-09-21 19:29 Dmitri Bichko <dbichko@aveopharma.com>
0 siblings, 0 replies; 5+ messages in thread
From: Dmitri Bichko @ 2005-09-21 19:29 UTC (permalink / raw)
To: Chris Mungall <cjm@fruitfly.org>; Sean Davis <sdavis2@mail.nih.gov>; +Cc: pgsql-sql; 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
> [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
>
>
>
> On Wed, 21 Sep 2005, Sean Davis wrote:
>
> > 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
> > unclear about how to implement R-tree indexing in this
> situation. Any
> > suggestions?
>
> Hi Sean
>
> I'm guessing that this is for some kind of genome database, yep?
>
> You may want to look at the chado database which has a
> growing library of functions for this sort of thing;
> www.gmod.org/schema
>
> Here is the code for doing range interval functions; our
> featureloc is equivalent to your "gf" (though we separate the
> entity from the entity being located). Our fmin and fmax may
> be equivalent to your start and end above (unless you
> indicate directionality with start>end in which case the
> intersection functions get a bit trickier). Our feature_id is
> probably equivalent to your gf column.
>
> We use the builtin pg types "point" and "box" and make an
> RTREE index over
> this:
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> --
> -- functions operating on featureloc ranges
> --
>
> -- create a point
> CREATE OR REPLACE FUNCTION create_point (int, int) RETURNS
> point AS 'SELECT point ($1, $2)' LANGUAGE 'sql';
>
> -- create a range box
> -- (make this immutable so we can index it)
> CREATE OR REPLACE FUNCTION boxrange (int, int) RETURNS box AS
> 'SELECT box (create_point(0, $1),
> create_point($2,500000000))' LANGUAGE 'sql' IMMUTABLE;
>
> -- create a query box
> CREATE OR REPLACE FUNCTION boxquery (int, int) RETURNS box AS
> 'SELECT box (create_point($1, $2), create_point($1, $2))'
> LANGUAGE 'sql' IMMUTABLE;
>
> --functional index that depends on the above functions
> CREATE INDEX binloc_boxrange ON featureloc USING RTREE
> (boxrange(fmin, fmax));
>
>
> CREATE OR REPLACE FUNCTION featureloc_slice(int, int) RETURNS
> setof featureloc AS
> 'SELECT * from featureloc where boxquery($1, $2) @
> boxrange(fmin,fmax)' LANGUAGE 'sql';
>
> 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 =
> featureloc.srcfeature_id)
> WHERE boxquery($2, $3) @ boxrange(fmin,fmax)
> AND srcf.name = $1 '
> LANGUAGE 'sql';
>
> 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 = $1 '
> LANGUAGE 'sql';
>
> -- 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=feature.feature_id)
> INNER JOIN featureloc AS y ON (y.feature_id=$1)
> WHERE
> x.srcfeature_id = y.srcfeature_id AND
> ( x.fmax >= y.fmin AND x.fmin <= y.fmax ) '
> LANGUAGE 'sql';
>
> 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=feature.feature_id)
> INNER JOIN featureloc AS y ON (y.feature_id=$1)
> WHERE
> x.srcfeature_id = y.srcfeature_id AND
> ( x.fmax < y.fmin OR x.fmin > y.fmax ) '
> LANGUAGE 'sql';
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> Cheers
> Chris
>
> > Thanks,
> > Sean
> >
> >
> > ---------------------------(end of
> > broadcast)---------------------------
> > TIP 1: if posting/reading through Usenet, please send an appropriate
> > subscribe-nomail command to majordomo@postgresql.org
> so that your
> > message can get through to the mailing list cleanly
> >
>
>
>
> ---------------------------(end of
> broadcast)---------------------------
> TIP 6: explain analyze is your friend
>
The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking 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 computer
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2005-09-21 19:43 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2005-09-21 17:52 R-tree and start/end queries Sean Davis <sdavis2@mail.nih.gov>
2005-09-21 18:38 ` Bruno Wolff III <bruno@wolff.to>
2005-09-21 19:43 ` Tom Lane <tgl@sss.pgh.pa.us>
2005-09-21 19:13 ` Chris Mungall <cjm@fruitfly.org>
2005-09-21 19:29 Re: R-tree and start/end queries Dmitri Bichko <dbichko@aveopharma.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox