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
**********************************************************************

Search Discussions

  • Oleg Bartunov at Nov 26, 2000 at 3:01 pm
    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
  • Selkovjr at Nov 26, 2000 at 7:19 pm

    Oleg Bartunov 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
  • Franck Martin at Nov 27, 2000 at 2:21 am
    It seems that your code is exactly what I want.

    I have already created geographical objects which contains MBR(Minimum
    Bounding Rectangle) in their structure, so it is a question of rewriting
    your code to change the access to the cube structure to the MBR structure
    inside my geoobject. (cf http://fmaps.sourceforge.net/) Look in the CVS for
    latest. I have been slack lately on the project, but I'm not forgetting it.

    Quickly I ran through the code, and I think your cube is strictly speaking a
    box, which also a MBR.

    However I didn't see the case of intersection, which is the main question
    when you want to display object that are visible inside a box.

    I suppose your code is under GPL, and you have no problem for me to use it,
    providing I put your name and credits somewhere.

    Cheers.

    Franck Martin
    Database Development Officer
    SOPAC South Pacific Applied Geoscience Commission
    Fiji
    E-mail: franck@sopac.org
    Web site: http://www.sopac.org/

    This e-mail is intended for its recipients only. Do not forward this e-mail
    without approval. The views expressed in this e-mail may not be necessarily
    the views of SOPAC.

    -----Original Message-----
    From: selkovjr@mcs.anl.gov
    Sent: Saturday, 25 November 2000 8:56
    To: Franck Martin
    Subject: Re: [HACKERS] Indexing for geographic objects?

    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
  • Hannu Krosing at Nov 27, 2000 at 9:17 am

    Franck Martin wrote:

    It seems that your code is exactly what I want.

    I have already created geographical objects which contains MBR(Minimum
    Bounding Rectangle) in their structure, so it is a question of rewriting
    your code to change the access to the cube structure to the MBR structure
    inside my geoobject. (cf http://fmaps.sourceforge.net/) Look in the CVS for
    latest. I have been slack lately on the project, but I'm not forgetting it.

    Quickly I ran through the code, and I think your cube is strictly speaking a
    box, which also a MBR.

    However I didn't see the case of intersection, which is the main question
    when you want to display object that are visible inside a box.

    I suppose your code is under GPL, and you have no problem for me to use it,
    providing I put your name and credits somewhere.
    It would be much better if it were under the standard PostgreSQL license
    and
    if it is included in the standard distribution.

    As Tom said, working Gist would be a great feature.

    Now if only someone would write the regression tests ;)

    BTW, the regression tests for pl/pgsql seem to be somewhat sparse as
    well,
    missing at least some types of loops, possibly more.
    Franck Martin
    Database Development Officer
    SOPAC South Pacific Applied Geoscience Commission
    Fiji
    E-mail: franck@sopac.org
    Web site: http://www.sopac.org/

    This e-mail is intended for its recipients only. Do not forward this e-mail
    without approval. The views expressed in this e-mail may not be necessarily
    the views of SOPAC.

    -----Original Message-----
    From: selkovjr@mcs.anl.gov
    Sent: Saturday, 25 November 2000 8:56
    To: Franck Martin
    Subject: Re: [HACKERS] Indexing for geographic objects?

    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
  • Selkovjr at Nov 28, 2000 at 12:03 am

    Franck Martin wrote:
    I have already created geographical objects which contains MBR(Minimum
    Bounding Rectangle) in their structure, so it is a question of rewriting
    your code to change the access to the cube structure to the MBR structure
    inside my geoobject. (cf http://fmaps.sourceforge.net/) Look in the CVS for
    latest. I have been slack lately on the project, but I'm not forgetting it.
    I see where you are aiming. I definitely want to be around when it
    starts working.
    Quickly I ran through the code, and I think your cube is strictly speaking a
    box, which also a MBR.
    Yes, cube is definitely a misnomer -- it suggests things are
    equihedral, which they aren't. I am still looking for a short name or
    an acronym that would indicate it is a box with an arbitrary number of
    dimensions. With your application, you will surely benefit from a
    smaller and faster code geared specifically for 3D.
    However I didn't see the case of intersection, which is the main question
    when you want to display object that are visible inside a box.
    The procedure is there, it is called cube_inter, but there is no
    operator for it.
    I suppose your code is under GPL, and you have no problem for me to use it,
    providing I put your name and credits somewhere.
    No problem at all -- I will be honored if you use it. Was I careless
    enough not to include a license? It's not exactly a GPL -- it's
    completely unrestricted. I should have said that somewhere.

    Good luck,

    --Gene
  • Nathan Myers at Nov 28, 2000 at 1:57 am

    On Mon, Nov 27, 2000 at 06:03:33PM -0600, selkovjr@mcs.anl.gov wrote:
    Franck Martin wrote:
    I suppose your code is under GPL, and you have no problem for me to
    use it, providing I put your name and credits somewhere.
    No problem at all -- I will be honored if you use it. Was I careless
    enough not to include a license? It's not exactly a GPL -- it's
    completely unrestricted. I should have said that somewhere.
    Note that (AIUI) placing code in the public domain leaves you liable
    for damages from somebody misusing it. You have to retain copyright
    just to be able to disclaim liability, in the license -- but then you
    need to actually have a license. That's why you don't see much public
    domain software. (I am not a lawyer.)

    Nathan Myers
    ncm@zembu.com
  • Tom Lane at Nov 27, 2000 at 3:34 am

    Michael Ansley 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
  • Selkovjr at Nov 27, 2000 at 6:36 pm

    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
  • Tom Lane at Nov 27, 2000 at 7:07 pm

    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
  • Selkovjr at Nov 28, 2000 at 12:53 am

    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
  • Tom Lane at Nov 28, 2000 at 5:07 am

    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
  • Michael Ansley at Nov 27, 2000 at 12:45 pm
    To be honest, Tom, I've always seen GiST not just as a great feature, but as
    an essential feature. Using Stonebraker's definition of an
    object-relational database (which I tend to do, as it's the only one that
    I've read about in depth), we really need to be able to properly index
    complex data, and using GiST, we can. Besides, it's just plain useful ;-)

    MikeA


    -----Original Message-----
    From: Tom Lane
    To: Michael Ansley
    Cc: 'Franck Martin '; 'pgsql-general '; 'pgsql-hackers ';
    't.h.p.ansley@durham.co.uk'
    Sent: 11-27-00 3:32 AM
    Subject: Re: [HACKERS] Indexing for geographic objects?

    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


    **********************************************************************
    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
    **********************************************************************

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppgsql-hackers @
categoriespostgresql
postedNov 26, '00 at 11:32a
activeNov 28, '00 at 5:07a
posts13
users7
websitepostgresql.org...
irc#postgresql

People

Translate

site design / logo © 2021 Grokbase