Horton

Thread

  1. RE: [HACKERS] Indexing for geographic objects?

    Michael Ansley (UK) <michael.ansley@intec-telecom-systems.com> — 2000-11-26T11:34:16Z

    Hi,

Remember also that the GiST library has been integrated into PG, (my brother
is doing some thesis workon that at the moment), and you can create new
index types relatively quickly (assuming that you understand the indexing
theory ;-) using this mechanism.  Run a web search on GiST for more info.

Currently GiST has support for btree and rtree indexes, and possibly r+ or *
trees, I can't remember which, if any, and IIRC, at least a couple more.
However, if you have a requirement or 3d indexing, and you have the
knowledge available, you should be able to hack a few 3d indexes together
quite quickly.


Cheers...
 

-----Original Message-----
From: Tom Lane
To: Franck Martin
Cc: pgsql-general; pgsql-hackers
Sent: 11-26-00 4:35 AM
Subject: Re: [HACKERS] Indexing for geographic objects? 

Franck Martin <franck@sopac.org> writes:
> I would greatly appreciate if someone could guide me through the
> methodology to build an index for a custom type or point me to some
> readings where the algorithm is explained (web, book, etc...).

The Programmer's Guide chapter "Interfacing Extensions To Indices"
outlines the procedure for making a new datatype indexable.  It
only discusses the case of adding btree support for a new type,
though.  For other index classes such as R-tree there are different
sets of required operators, which are not as well documented but
you can find out by looking at code for the already-supported
datatypes.

> I plan to use 3D geographical objects...

That's a bit hard since we don't have any indexes suitable for 3-D
coordinates --- the existing R-tree type is for 2-D objects.  What's
more it assumes that coordinates are Euclidean, which is probably
not the model you want for geographical coordinates.

In theory you could build a new index type suitable for indexing
3-D points, using the R-tree code as a starting point.  I wouldn't
class it as a project suitable for a newbie however :-(.

Depending on what your needs are, you might be able to get by with
projecting your objects into a flat 2-D coordinate system and using
an R-tree index in that space.  It'd just be approximate but that
might be close enough for index purposes.

			regards, tom lane


**********************************************************************
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they
are addressed. If you have received this email in error please notify
the system manager.

This footnote also confirms that this email message has been swept by
MIMEsweeper for the presence of computer viruses.

www.mimesweeper.com
**********************************************************************

  2. RE: [HACKERS] Indexing for geographic objects?

    Oleg Bartunov <oleg@sai.msu.su> — 2000-11-26T14:55:58Z

    I'm also interested in GiST and would be happy if somebody could provide
workable example. I have an idea to use GiST indices for our fulltextsearch
system.

	Regards,

			Oleg
On Sun, 26 Nov 2000, Michael Ansley wrote:

> Date: Sun, 26 Nov 2000 11:34:16 -0000
> From: Michael Ansley <Michael.Ansley@intec-telecom-systems.com>
> To: 'Tom Lane ' <tgl@sss.pgh.pa.us>, 'Franck Martin ' <franck@sopac.org>
> Cc: 'pgsql-general ' <pgsql-general@postgresql.org>,
>     'pgsql-hackers ' <pgsql-hackers@postgresql.org>,
>     "'t.h.p.ansley@durham.co.uk'" <t.h.p.ansley@durham.co.uk>
> Subject: RE: [HACKERS] Indexing for geographic objects? 
> 
> Hi,
> 
> Remember also that the GiST library has been integrated into PG, (my brother
> is doing some thesis workon that at the moment), and you can create new
> index types relatively quickly (assuming that you understand the indexing
> theory ;-) using this mechanism.  Run a web search on GiST for more info.
> 
> Currently GiST has support for btree and rtree indexes, and possibly r+ or *
> trees, I can't remember which, if any, and IIRC, at least a couple more.
> However, if you have a requirement or 3d indexing, and you have the
> knowledge available, you should be able to hack a few 3d indexes together
> quite quickly.
> 
> 
> Cheers...
>  
> 
> -----Original Message-----
> From: Tom Lane
> To: Franck Martin
> Cc: pgsql-general; pgsql-hackers
> Sent: 11-26-00 4:35 AM
> Subject: Re: [HACKERS] Indexing for geographic objects? 
> 
> Franck Martin <franck@sopac.org> writes:
> > I would greatly appreciate if someone could guide me through the
> > methodology to build an index for a custom type or point me to some
> > readings where the algorithm is explained (web, book, etc...).
> 
> The Programmer's Guide chapter "Interfacing Extensions To Indices"
> outlines the procedure for making a new datatype indexable.  It
> only discusses the case of adding btree support for a new type,
> though.  For other index classes such as R-tree there are different
> sets of required operators, which are not as well documented but
> you can find out by looking at code for the already-supported
> datatypes.
> 
> > I plan to use 3D geographical objects...
> 
> That's a bit hard since we don't have any indexes suitable for 3-D
> coordinates --- the existing R-tree type is for 2-D objects.  What's
> more it assumes that coordinates are Euclidean, which is probably
> not the model you want for geographical coordinates.
> 
> In theory you could build a new index type suitable for indexing
> 3-D points, using the R-tree code as a starting point.  I wouldn't
> class it as a project suitable for a newbie however :-(.
> 
> Depending on what your needs are, you might be able to get by with
> projecting your objects into a flat 2-D coordinate system and using
> an R-tree index in that space.  It'd just be approximate but that
> might be close enough for index purposes.
> 
> 			regards, tom lane
> 
> 
> **********************************************************************
> This email and any files transmitted with it are confidential and
> intended solely for the use of the individual or entity to whom they
> are addressed. If you have received this email in error please notify
> the system manager.
> 
> This footnote also confirms that this email message has been swept by
> MIMEsweeper for the presence of computer viruses.
> 
> www.mimesweeper.com
> **********************************************************************
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  3. Re: [HACKERS] Indexing for geographic objects?

    selkovjr@mcs.anl.gov — 2000-11-26T19:15:20Z

    Oleg Bartunov <oleg@sai.msu.su> wrote:
>
> I'm also interested in GiST and would be happy if somebody could provide
> workable example. I have an idea to use GiST indices for our fulltextsearch
> system.
> 

I have recently replied to Franck Martin in regards to this indexing
question, but I didn't think the subject was popular enough for me to
contaminate the list(s). You prove me wrong. Here goes:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
To: Franck Martin <franck@sopac.org>
From: selkovjr@mcs.anl.gov
Reply-to: selkovjr@mcs.anl.gov
Subject: Re: [HACKERS] Indexing for geographic objects? 
In-reply-to: <3A1EE0F4.3DC4161B@sopac.org> 
Comments: In-reply-to Franck Martin <franck@sopac.org>
   message dated "Sat, 25 Nov 2000 10:43:16 +1300."
Mime-Version: 1.0 (generated by tm-edit 7.108)
Date: Sat, 25 Nov 2000 02:56:03 -0600

It is probably possible to hook up an extension directly with the
R-tree methods available in postgres -- if you stare at the code long
enough and figure how to use the correct strategies. I chose an easier
path years ago and I am still satisfied with the results. Check out
the GiST -- a general access method built on top of R-tree to provide
a user-friendly interface to it and to allow indexing of more abstract
types, for which straight R-tree is not directly applicable.

I have a small set of complete data types, of which a couple
illustrate the use of GiST indexing with the geometrical objects, in:

http://wit.mcs.anl.gov/~selkovjr/pg_extensions/

If you are using a pre-7.0 postrgres, grab the file contrib.tgz,
otherwise take contrib-7.0.tgz. The difference is insignificant, but
the pre-7.0 version will not fit the current schema. Unpack the source
into postgresql-*/contrib and follow instructions in the README
files. The types of interest for you will be seg and cube. You will
find pointers to the original sources and docs in the CREDITS section
of the README file. I also have a version of the original example code
in pggist-patched.tgz, but I did not check if it works with current
postgres. It should not be difficult to fix it if it doesn't -- the
recent development in the optimizer area made certain things
unnecessary.

You might want to check out a working example of the segment data type at:

http://wit.mcs.anl.gov/EMP/indexing.html

(search the page for 'KM')

I will be glad to help, but I would also recommend to send more
sophisticated questions to Joe Hellerstein, the leader of the original
postgres team that developed GiST. He was very helpful whenever I
turned to him during the early stages of my data type project.

--Gene

  4. Re: [HACKERS] Indexing for geographic objects?

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-11-27T03:32:41Z

    Michael Ansley <Michael.Ansley@intec-telecom-systems.com> writes:
> Remember also that the GiST library has been integrated into PG, (my brother
> is doing some thesis workon that at the moment),

Yeah?  Does it still work?

Since the GIST code is not tested by any standard regress test, and is
so poorly documented that hardly anyone can be using it, I've always
assumed that it is probably suffering from a severe case of bit-rot.

I'd love to see someone contribute documentation and regression test
cases for it --- it's a great feature, if it works.

			regards, tom lane

  5. Re: [HACKERS] Indexing for geographic objects?

    selkovjr@mcs.anl.gov — 2000-11-27T18:36:42Z

    Tom Lane wrote:
> Michael Ansley <Michael.Ansley@intec-telecom-systems.com> writes:
> > Remember also that the GiST library has been integrated into PG, (my brother
> > is doing some thesis workon that at the moment),
> 
> Yeah?  Does it still work?

You bet. One would otherwise be hearing from me. I depend on it quite
heavily and I am checking with almost every release. I am now current
with 7.0.2 -- this time it required some change, although not in the c
code. And that's pretty amazing: I was only screwed once since
postgres95 -- by a beta version I don't remember now; then I
complained and the problem was fixed. I don't even know whom I owe
thanks for that.

> Since the GIST code is not tested by any standard regress test, and is
> so poorly documented that hardly anyone can be using it, 
I've always
> assumed that it is probably suffering from a severe case of bit-rot.
> 
> I'd love to see someone contribute documentation and regression test
> cases for it --- it's a great feature, if it works.

The bit rot fortunately did not happen, but the documentation I
promised Bruce many months ago is still "in the works" -- meaning,
something interfered and I haven't had a chance to start. Like a
friend of mine muses all the time, "Promise doesn't mean
marriage". Boy, do I feel guilty.

It's a bit better with the testing. I am not sure how to test the
GiST directly, but I have adapted the current version of regression
tests for the data types that depend on it. One can find them in my
contrib directory, under test/ (again, it's
http://wit.mcs.anl.gov/~selkovjr/pg_extensions/contrib.tgz)

It would be nice if at least one of the GiST types became a built-in
(that would provide for a more intensive testing), but I can also
think of the contrib code being (optionally) included into the main
build and regression test trees. The top-level makefile can have a
couple of special targets to build and test the contribs. I believe my
version of the tests can be a useful example to other contributors
whose code is already in the source tree.

--Gene

  6. Re: [HACKERS] Indexing for geographic objects?

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-11-27T19:07:16Z

    selkovjr@mcs.anl.gov writes:
> Tom Lane wrote:
>> Michael Ansley <Michael.Ansley@intec-telecom-systems.com> writes:
>>>> Remember also that the GiST library has been integrated into PG, (my brother
>>>> is doing some thesis workon that at the moment),
>> 
>> Yeah?  Does it still work?

> You bet. One would otherwise be hearing from me. I depend on it quite
> heavily and I am checking with almost every release.

That's very good to hear!  I was not aware that anyone was banging on it.

It seems like it would be a fine idea to adopt your stuff at least into
the contrib part of the distribution, maybe even (or eventually) into
the main release.  I think we could probably make it part of the regress
tests even if it's contrib --- there's precedent, as regress already
uses some contrib stuff.

Do you have any problem with releasing your stuff under the Postgres
distribution terms (BSD license)?

			regards, tom lane

  7. Re: [HACKERS] Indexing for geographic objects?

    selkovjr@mcs.anl.gov — 2000-11-28T00:53:10Z

    Tom Lane wrote:

> Do you have any problem with releasing your stuff under the Postgres
> distribution terms (BSD license)?

No, I don't see any problem with the BSD license, or any other
license, for that matter. I just had some reservations about releasing
stuff that was far from perfect, and it took me a while to realize
it could be useful as it is for some, and serve as a good starting
point for others. Now I wonder, what does it take to be in contrib?

> there's precedent, as regress already
> uses some contrib stuff.

I'd be curious to find out what that stuff is and how it's done. 

--Gene

  8. Re: [HACKERS] Indexing for geographic objects?

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-11-28T05:07:49Z

    selkovjr@mcs.anl.gov writes:
> Tom Lane wrote:
>> Do you have any problem with releasing your stuff under the Postgres
>> distribution terms (BSD license)?

> No, I don't see any problem with the BSD license, or any other
> license, for that matter. I just had some reservations about releasing
> stuff that was far from perfect, and it took me a while to realize
> it could be useful as it is for some, and serve as a good starting
> point for others. Now I wonder, what does it take to be in contrib?

Just contributing it ;-), which I take the above as permission to do.
When I come up for air from the IPC-hacking I'm doing, I'll grab your
tarball and see about adding it as a contrib module.

Many thanks!

			regards, tom lane

  9. Re: Indexing for geographic objects?

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-08T15:16:30Z

    Hi,

We've done some work with GiST indices and found a little problem
with optimizer. The problem could be reproduced with Gene's code
(link is in original message below). test data and sql I could send - 
it's just 52Kb gzipped file. What is a reason for optimizer to decide
that sequential scan is better (look below for a numbers).
Implicite disabling of seq scan gave much  better timings.

	Regards,
		
		Oleg


test=# explain select * from test where s @ '1.05 .. 3.95';
NOTICE:  QUERY PLAN:

Seq Scan on test  (cost=0.00..184.01 rows=5000 width=12)

EXPLAIN

% ./bench.pl -d test -b 100
total: 3.19 sec; number: 100; for one: 0.032 sec; found 18 docs

test=# set enable_seqscan = off;
SET VARIABLE
test=# explain select * from test where s @ '1.05 .. 3.95';
NOTICE:  QUERY PLAN:

Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)

EXPLAIN
% ./bench.pl -d test -b 100  -i
total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs


On Mon, 27 Nov 2000 selkovjr@mcs.anl.gov wrote:

> Date: Mon, 27 Nov 2000 12:36:42 -0600
> From: selkovjr@mcs.anl.gov
> To: Tom Lane <tgl@sss.pgh.pa.us>
> Cc: 'pgsql-general ' <pgsql-general@postgresql.org>,
>     'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> Subject: Re: [HACKERS] Indexing for geographic objects? 
> 
> Tom Lane wrote:
> > Michael Ansley <Michael.Ansley@intec-telecom-systems.com> writes:
> > > Remember also that the GiST library has been integrated into PG, (my brother
> > > is doing some thesis workon that at the moment),
> > 
> > Yeah?  Does it still work?
> 
> You bet. One would otherwise be hearing from me. I depend on it quite
> heavily and I am checking with almost every release. I am now current
> with 7.0.2 -- this time it required some change, although not in the c
> code. And that's pretty amazing: I was only screwed once since
> postgres95 -- by a beta version I don't remember now; then I
> complained and the problem was fixed. I don't even know whom I owe
> thanks for that.
> 
> > Since the GIST code is not tested by any standard regress test, and is
> > so poorly documented that hardly anyone can be using it, 
> I've always
> > assumed that it is probably suffering from a severe case of bit-rot.
> > 
> > I'd love to see someone contribute documentation and regression test
> > cases for it --- it's a great feature, if it works.
> 
> The bit rot fortunately did not happen, but the documentation I
> promised Bruce many months ago is still "in the works" -- meaning,
> something interfered and I haven't had a chance to start. Like a
> friend of mine muses all the time, "Promise doesn't mean
> marriage". Boy, do I feel guilty.
> 
> It's a bit better with the testing. I am not sure how to test the
> GiST directly, but I have adapted the current version of regression
> tests for the data types that depend on it. One can find them in my
> contrib directory, under test/ (again, it's
> http://wit.mcs.anl.gov/~selkovjr/pg_extensions/contrib.tgz)
> 
> It would be nice if at least one of the GiST types became a built-in
> (that would provide for a more intensive testing), but I can also
> think of the contrib code being (optionally) included into the main
> build and regression test trees. The top-level makefile can have a
> couple of special targets to build and test the contribs. I believe my
> version of the tests can be a useful example to other contributors
> whose code is already in the source tree.
> 
> --Gene
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  10. Re: Indexing for geographic objects?

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-12-08T15:47:37Z

    Oleg Bartunov <oleg@sai.msu.su> writes:
> We've done some work with GiST indices and found a little problem
> with optimizer.

> test=# set enable_seqscan = off;
> SET VARIABLE
> test=# explain select * from test where s @ '1.05 .. 3.95';
> NOTICE:  QUERY PLAN:

> Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)

> EXPLAIN
> % ./bench.pl -d test -b 100  -i
> total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs

I'd venture that the major problem here is bogus estimated selectivities
for rtree/gist operators.  Note the discrepancy between the estimated
row count and the actual (I assume the "found 18 docs" is the true
number of rows output by the query).  With an estimated row count even
half that (ie, merely two orders of magnitude away from reality ;-))
the thing would've correctly chosen the index scan over sequential.

5000 looks like a suspiciously round number ... how many rows are in
the table?  Have you done a vacuum analyze on it?

			regards, tom lane

  11. Re: Indexing for geographic objects?

    Marc G. Fournier <scrappy@hub.org> — 2000-12-08T16:19:56Z

    just a note here ... recently, we had a client with similar problems with
using index scan, where turning off seqscan did the trick ... we took his
tables, loaded them into a v7.1beta1 server and it correctly comes up with
the index scan ...

Oleg, have you tried this with v7.1 yet?  

On Fri, 8 Dec 2000, Tom Lane wrote:

> Oleg Bartunov <oleg@sai.msu.su> writes:
> > We've done some work with GiST indices and found a little problem
> > with optimizer.
> 
> > test=# set enable_seqscan = off;
> > SET VARIABLE
> > test=# explain select * from test where s @ '1.05 .. 3.95';
> > NOTICE:  QUERY PLAN:
> 
> > Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)
> 
> > EXPLAIN
> > % ./bench.pl -d test -b 100  -i
> > total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs
> 
> I'd venture that the major problem here is bogus estimated selectivities
> for rtree/gist operators.  Note the discrepancy between the estimated
> row count and the actual (I assume the "found 18 docs" is the true
> number of rows output by the query).  With an estimated row count even
> half that (ie, merely two orders of magnitude away from reality ;-))
> the thing would've correctly chosen the index scan over sequential.
> 
> 5000 looks like a suspiciously round number ... how many rows are in
> the table?  Have you done a vacuum analyze on it?
> 
> 			regards, tom lane
> 

Marc G. Fournier                   ICQ#7615664               IRC Nick: Scrappy
Systems Administrator @ hub.org 
primary: scrappy@hub.org           secondary: scrappy@{freebsd|postgresql}.org

  12. Re: Indexing for geographic objects?

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-08T17:41:32Z

    On Fri, 8 Dec 2000, Tom Lane wrote:

> Date: Fri, 08 Dec 2000 10:47:37 -0500
> From: Tom Lane <tgl@sss.pgh.pa.us>
> To: Oleg Bartunov <oleg@sai.msu.su>
> Cc: selkovjr@mcs.anl.gov, 'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> Subject: Re: [HACKERS] Indexing for geographic objects? 
> 
> Oleg Bartunov <oleg@sai.msu.su> writes:
> > We've done some work with GiST indices and found a little problem
> > with optimizer.
> 
> > test=# set enable_seqscan = off;
> > SET VARIABLE
> > test=# explain select * from test where s @ '1.05 .. 3.95';
> > NOTICE:  QUERY PLAN:
> 
> > Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)
> 
> > EXPLAIN
> > % ./bench.pl -d test -b 100  -i
> > total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs
> 
> I'd venture that the major problem here is bogus estimated selectivities
> for rtree/gist operators.  Note the discrepancy between the estimated
> row count and the actual (I assume the "found 18 docs" is the true
> number of rows output by the query).  With an estimated row count even

yes, 18 docs is the true number

> half that (ie, merely two orders of magnitude away from reality ;-))
> the thing would've correctly chosen the index scan over sequential.
> 
> 5000 looks like a suspiciously round number ... how many rows are in
> the table?  Have you done a vacuum analyze on it?

park-lane:~/app/pgsql/gist_problem$ wc SQL 
   10009   10049  157987 SQL
about 10,000 rows, 
relevant part of script is:
.....skipped...
1.9039...3.5139
1.8716...3.9317
\.
CREATE INDEX test_seg_ix ON test USING gist (s);
vacuum analyze;
^^^^^^^^^^^^^^
explain select * from test where s @ '1.05 .. 3.95';
set enable_seqscan = off;
explain select * from test where s @ '1.05 .. 3.95';

	Regards,
		Oleg


> 
> 			regards, tom lane
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  13. Re: Indexing for geographic objects?

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-08T17:45:09Z

    On Fri, 8 Dec 2000, The Hermit Hacker wrote:

> Date: Fri, 8 Dec 2000 12:19:56 -0400 (AST)
> From: The Hermit Hacker <scrappy@hub.org>
> To: Tom Lane <tgl@sss.pgh.pa.us>
> Cc: Oleg Bartunov <oleg@sai.msu.su>, selkovjr@mcs.anl.gov,
>     'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> Subject: Re: [HACKERS] Indexing for geographic objects? 
> 
> 
> just a note here ... recently, we had a client with similar problems with
> using index scan, where turning off seqscan did the trick ... we took his
> tables, loaded them into a v7.1beta1 server and it correctly comes up with
> the index scan ...
> 
> Oleg, have you tried this with v7.1 yet?  

Not yet. Just a plain 7.0.3 release. Will play with 7.1beta.
But we're working in real life and need things to work in production :-)

	regards,
		Oleg

> 
> On Fri, 8 Dec 2000, Tom Lane wrote:
> 
> > Oleg Bartunov <oleg@sai.msu.su> writes:
> > > We've done some work with GiST indices and found a little problem
> > > with optimizer.
> > 
> > > test=# set enable_seqscan = off;
> > > SET VARIABLE
> > > test=# explain select * from test where s @ '1.05 .. 3.95';
> > > NOTICE:  QUERY PLAN:
> > 
> > > Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)
> > 
> > > EXPLAIN
> > > % ./bench.pl -d test -b 100  -i
> > > total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs
> > 
> > I'd venture that the major problem here is bogus estimated selectivities
> > for rtree/gist operators.  Note the discrepancy between the estimated
> > row count and the actual (I assume the "found 18 docs" is the true
> > number of rows output by the query).  With an estimated row count even
> > half that (ie, merely two orders of magnitude away from reality ;-))
> > the thing would've correctly chosen the index scan over sequential.
> > 
> > 5000 looks like a suspiciously round number ... how many rows are in
> > the table?  Have you done a vacuum analyze on it?
> > 
> > 			regards, tom lane
> > 
> 
> Marc G. Fournier                   ICQ#7615664               IRC Nick: Scrappy
> Systems Administrator @ hub.org 
> primary: scrappy@hub.org           secondary: scrappy@{freebsd|postgresql}.org 
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  14. Re: Indexing for geographic objects?

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-12-08T17:59:27Z

    Oleg Bartunov <oleg@sai.msu.su> writes:
>> 5000 looks like a suspiciously round number ... how many rows are in
>> the table?  Have you done a vacuum analyze on it?

> about 10,000 rows, 

So the thing is estimating 0.5 selectivity, which is a fallback for
operators it knows nothing whatever about.

[ ... digs in Selkov's scripts ... ]

CREATE OPERATOR @ (
   LEFTARG = seg, RIGHTARG = seg, PROCEDURE = seg_contains,
   COMMUTATOR = '~'
);

CREATE OPERATOR ~ (
   LEFTARG = seg, RIGHTARG = seg, PROCEDURE = seg_contained,
   COMMUTATOR = '@'
);

Sure 'nuff, no selectivity info attached to these declarations.
Try adding

   RESTRICT = contsel, JOIN = contjoinsel

to them.  That's still an entirely bogus estimate, but at least
it's a smaller bogus estimate ... small enough to select an indexscan,
one hopes (see utils/adt/geo_selfuncs.c).

I have not dug through Gene's stuff to see which other indexable
operators might be missing selectivity estimates, but I'll bet there
are others.  If you have the time to look through it and submit a
patch, I can incorporate it into the version that will go into contrib.

			regards, tom lane

  15. Re: Indexing for geographic objects?

    Marc G. Fournier <scrappy@hub.org> — 2000-12-08T18:03:54Z

    On Fri, 8 Dec 2000, Oleg Bartunov wrote:

> On Fri, 8 Dec 2000, The Hermit Hacker wrote:
> 
> > Date: Fri, 8 Dec 2000 12:19:56 -0400 (AST)
> > From: The Hermit Hacker <scrappy@hub.org>
> > To: Tom Lane <tgl@sss.pgh.pa.us>
> > Cc: Oleg Bartunov <oleg@sai.msu.su>, selkovjr@mcs.anl.gov,
> >     'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> > Subject: Re: [HACKERS] Indexing for geographic objects? 
> > 
> > 
> > just a note here ... recently, we had a client with similar problems with
> > using index scan, where turning off seqscan did the trick ... we took his
> > tables, loaded them into a v7.1beta1 server and it correctly comes up with
> > the index scan ...
> > 
> > Oleg, have you tried this with v7.1 yet?  
> 
> Not yet. Just a plain 7.0.3 release. Will play with 7.1beta.
> But we're working in real life and need things to work in production :-)

Okay, then I believe that what you are experience wiht v7.0.3 is already
fixed in v7.1beta, based on similar results I got with some queries and
then tested uver v7.1 ...

 > 
> 	regards,
> 		Oleg
> 
> > 
> > On Fri, 8 Dec 2000, Tom Lane wrote:
> > 
> > > Oleg Bartunov <oleg@sai.msu.su> writes:
> > > > We've done some work with GiST indices and found a little problem
> > > > with optimizer.
> > > 
> > > > test=# set enable_seqscan = off;
> > > > SET VARIABLE
> > > > test=# explain select * from test where s @ '1.05 .. 3.95';
> > > > NOTICE:  QUERY PLAN:
> > > 
> > > > Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)
> > > 
> > > > EXPLAIN
> > > > % ./bench.pl -d test -b 100  -i
> > > > total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs
> > > 
> > > I'd venture that the major problem here is bogus estimated selectivities
> > > for rtree/gist operators.  Note the discrepancy between the estimated
> > > row count and the actual (I assume the "found 18 docs" is the true
> > > number of rows output by the query).  With an estimated row count even
> > > half that (ie, merely two orders of magnitude away from reality ;-))
> > > the thing would've correctly chosen the index scan over sequential.
> > > 
> > > 5000 looks like a suspiciously round number ... how many rows are in
> > > the table?  Have you done a vacuum analyze on it?
> > > 
> > > 			regards, tom lane
> > > 
> > 
> > Marc G. Fournier                   ICQ#7615664               IRC Nick: Scrappy
> > Systems Administrator @ hub.org 
> > primary: scrappy@hub.org           secondary: scrappy@{freebsd|postgresql}.org 
> > 
> 
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83
> 
> 

Marc G. Fournier                   ICQ#7615664               IRC Nick: Scrappy
Systems Administrator @ hub.org 
primary: scrappy@hub.org           secondary: scrappy@{freebsd|postgresql}.org

  16. Re: Indexing for geographic objects?

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-08T19:03:15Z

    On Fri, 8 Dec 2000, Tom Lane wrote:

> Date: Fri, 08 Dec 2000 12:59:27 -0500
> From: Tom Lane <tgl@sss.pgh.pa.us>
> To: Oleg Bartunov <oleg@sai.msu.su>
> Cc: selkovjr@mcs.anl.gov, 'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> Subject: Re: [HACKERS] Indexing for geographic objects? 
> 
> Oleg Bartunov <oleg@sai.msu.su> writes:
> >> 5000 looks like a suspiciously round number ... how many rows are in
> >> the table?  Have you done a vacuum analyze on it?
> 
> > about 10,000 rows, 
> 
> So the thing is estimating 0.5 selectivity, which is a fallback for
> operators it knows nothing whatever about.
> 
> [ ... digs in Selkov's scripts ... ]
> 
> CREATE OPERATOR @ (
>    LEFTARG = seg, RIGHTARG = seg, PROCEDURE = seg_contains,
>    COMMUTATOR = '~'
> );
> 
> CREATE OPERATOR ~ (
>    LEFTARG = seg, RIGHTARG = seg, PROCEDURE = seg_contained,
>    COMMUTATOR = '@'
> );
> 
> Sure 'nuff, no selectivity info attached to these declarations.
> Try adding
> 
>    RESTRICT = contsel, JOIN = contjoinsel
> 
> to them.  That's still an entirely bogus estimate, but at least
> it's a smaller bogus estimate ... small enough to select an indexscan,
> one hopes (see utils/adt/geo_selfuncs.c).

Great ! Now we have better plan:

test=# explain select * from test where s @ '1.05 .. 3.95';
NOTICE:  QUERY PLAN:

Index Scan using test_seg_ix on test  (cost=0.00..61.56 rows=100 width=12)

EXPLAIN


> 
> I have not dug through Gene's stuff to see which other indexable
> operators might be missing selectivity estimates, but I'll bet there
> are others.  If you have the time to look through it and submit a
> patch, I can incorporate it into the version that will go into contrib.
> 

We didn't look at Gene's stuff yet. Maybe Gene could find a time to
check his code.

> 			regards, tom lane
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  17. Re: Indexing for geographic objects?

    selkovjr@mcs.anl.gov — 2000-12-09T03:22:02Z

    Tom Lane wrote: 
> Oleg Bartunov <oleg@sai.msu.su> writes:
> > We've done some work with GiST indices and found a little problem
> > with optimizer.
> 
> > test=# set enable_seqscan = off;
> > SET VARIABLE
> > test=# explain select * from test where s @ '1.05 .. 3.95';
> > NOTICE:  QUERY PLAN:
> 
> > Index Scan using test_seg_ix on test  (cost=0.00..369.42 rows=5000 width=12)
> 
> > EXPLAIN
> > % ./bench.pl -d test -b 100  -i
> > total: 1.71 sec; number: 100; for one: 0.017 sec; found 18 docs
> 
> I'd venture that the major problem here is bogus estimated selectivities
> for rtree/gist operators.

Yes, the problem is, I didn't have the foggiest idea how to estimate
selectivity, nor I had any stats when I developed the type. Before
7.0, I had some success using selectivity estimators of another
datatype (I think that was int, but I am not sure). In 7.0, most of
those estimators were gone and I have probably chosen the wrong ones
or none at all, just so I could get it to work again. The performance
was good enough for my taste, so I have even forgotten that was an
issue.

I know, I know: 'good enough' is never good. I apoligize.

--Gene

  18. index support for arrays (GiST)

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-13T15:48:40Z

    Hi,

we are getting a bit close to add index support for int arrays using
GiST interface. This will really drive up performance of our full text
search fully based on postgresql. We have a problem with broken index
and couldn't find a reason. I attached archive with sources
for GiST functions and test suite to show a problem - vacuum analyze
at end end of TESTSQL should complain about broken index.
Here is a short description:
1. untar in contrib 7.0.*
2. cd _intarray
3. edit Makefile for TESTDB (name of db for test)
4. createdb TESTDB
5. gmake
6. gmake install
7. psql TESTDB < TESTSQL

	Regards,

		Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  19. Re: index support for arrays (GiST)

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-15T12:08:26Z

    Well,

we found an answer ourserlves. Patch for 7.0.3 is included below.
Credits to Teodor Sigaev (teodor@stack.net)
Some comments: 

>From src/backend/access/gist/gist.c
/*
** Take a compressed entry, and install it on a page.  Since we now know
** where the entry will live, we decompress it and recompress it using
** that knowledge (some compression routines may want to fish around
** on the page, for example, or do something special for leaf nodes.)
*/

After compressing of index it's written to disk decompressed (!) which
is the reason we have the problem with broken index !
It looks like other people just didn't use index decompression function
(at least in Gene's code decompression function just do return  ) and 
that's why this bug was not discovered. We could make a patch for 
upcoming 7.1 if hackers desired. I consider this patch as a bugfix
not a new feature or improvement. We got a very promising results.

Another question to this code is - why gistPageAddItem does
compress - decompress - compress. It's not clear from the comment.

	Best regards,

		Oleg

-------------------------------------------------------------------------
maze% diff -c backend/access/gist/gist.c 
backend/access/gist/gist.c.orig  
*** backend/access/gist/gist.c  Fri Dec 15 13:03:40 2000
--- backend/access/gist/gist.c.orig     Fri Dec 15 13:00:50 2000
***************
*** 374,380 ****
  {
        GISTENTRY       tmpcentry;
        IndexTuple      itup = (IndexTuple) item;
-       OffsetNumber    retval;
  
        /*
         * recompress the item given that we now know the exact page and
--- 374,379 ----
***************
*** 386,400 ****
                                   IndexTupleSize(itup) -
sizeof(IndexTupleData), FALSE);
        gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
                                   offsetNumber, dentry->bytes, FALSE);
!       *newtup = gist_tuple_replacekey(r, tmpcentry, itup);
!       retval = PageAddItem(page, (Item) *newtup,
IndexTupleSize(*newtup),
!                                               offsetNumber, flags);
        /* be tidy */
        if (tmpcentry.pred != dentry->pred
                && tmpcentry.pred != (((char *) itup) +
sizeof(IndexTupleData)))
                pfree(tmpcentry.pred);
  
!       return (retval);
  }
  
  
--- 385,398 ----
                                   IndexTupleSize(itup) -
sizeof(IndexTupleData), FALSE);
        gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
                                   offsetNumber, dentry->bytes, FALSE);
!       *newtup = gist_tuple_replacekey(r, *dentry, itup);
        /* be tidy */
        if (tmpcentry.pred != dentry->pred
                && tmpcentry.pred != (((char *) itup) +
sizeof(IndexTupleData)))
                pfree(tmpcentry.pred);
  
!       return (PageAddItem(page, (Item) *newtup,
IndexTupleSize(*newtup),
!                                               offsetNumber, flags));
  }
  

-----------------------------------------------------------------------



On Wed, 13 Dec 2000, Oleg Bartunov wrote:

> Date: Wed, 13 Dec 2000 18:48:40 +0300 (GMT)
> From: Oleg Bartunov <oleg@sai.msu.su>
> To: selkovjr@mcs.anl.gov
> Cc: Tom Lane <tgl@sss.pgh.pa.us>, vmikheev@SECTORBASE.COM,
>     'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> Subject: [HACKERS] index support for arrays (GiST)
> 
> Hi,
> 
> we are getting a bit close to add index support for int arrays using
> GiST interface. This will really drive up performance of our full text
> search fully based on postgresql. We have a problem with broken index
> and couldn't find a reason. I attached archive with sources
> for GiST functions and test suite to show a problem - vacuum analyze
> at end end of TESTSQL should complain about broken index.
> Here is a short description:
> 1. untar in contrib 7.0.*
> 2. cd _intarray
> 3. edit Makefile for TESTDB (name of db for test)
> 4. createdb TESTDB
> 5. gmake
> 6. gmake install
> 7. psql TESTDB < TESTSQL
> 
> 	Regards,
> 
> 		Oleg
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  20. Re: index support for arrays (GiST)

    Oleg Bartunov <oleg@sai.msu.su> — 2000-12-15T15:45:54Z

    On Fri, 15 Dec 2000, Thomas Lockhart wrote:

> Date: Fri, 15 Dec 2000 15:47:01 +0000
> From: Thomas Lockhart <lockhart@alumni.caltech.edu>
> To: Oleg Bartunov <oleg@sai.msu.su>
> Cc: selkovjr@mcs.anl.gov, Tom Lane <tgl@sss.pgh.pa.us>,
>     vmikheev@SECTORBASE.COM,
>     'pgsql-hackers ' <pgsql-hackers@postgresql.org>
> Subject: Re: [HACKERS] index support for arrays (GiST)
> 
> > It looks like other people just didn't use index decompression function
> > (at least in Gene's code decompression function just do return  ) and
> > that's why this bug was not discovered. We could make a patch for
> > upcoming 7.1 if hackers desired. I consider this patch as a bugfix
> > not a new feature or improvement. We got a very promising results.
> 
> Yes, send patches! Thanks to you and Gene for getting GiST back into
> view; it seems like a great feature which was neglected for too long.
> 

We found one more bug with handling NULL values, so continue digging :-)

	Олег

>                        - Thomas
> 

_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  21. Re: index support for arrays (GiST)

    Thomas Lockhart <lockhart@alumni.caltech.edu> — 2000-12-15T15:47:01Z

    > It looks like other people just didn't use index decompression function
> (at least in Gene's code decompression function just do return  ) and
> that's why this bug was not discovered. We could make a patch for
> upcoming 7.1 if hackers desired. I consider this patch as a bugfix
> not a new feature or improvement. We got a very promising results.

Yes, send patches! Thanks to you and Gene for getting GiST back into
view; it seems like a great feature which was neglected for too long.

                       - Thomas