[GENERAL] RE: [HACKERS] Indexing for geographic objects?
It seems that R-trees become inefficient when the number of dimensions increase. Has anyone thoght of a transparent way to use Peano codes (hhcode in Oracle lingo), and use B-tree indexes instead? Also, I've read that R-trees sometimes suffer a lot when an update overflows a node in the index. The only initial problem I see with Peano codes is that the index is made on real cubes (all dimensions are equal, due to the recursive decomposition of space). To overcome that, people have talked about using multiple-entry-indexes. That is, an object is decomposed in a number of cubes (not too many), which are then indexed. In this case, there should be a way to make intersection searches be transparent. Oracle does it using tables and merge-joins. I have thought of using GiST to do that, but it seemed too advanced for me yet. So I thought of using the Oracle technique (make tables and use joins). Problem: I would need a C function to make the cubes describing an spatial object, but currently C functions cannot return more than one value (have of thoght of returning an array, but have not tried it). And making inserts directly from a C function has been described as magic stuff in the documentation. Yours sincerely, Edmar Wiggers BRASMAP Information Systems +55 48 9960 2752
Re: [GENERAL] RE: [HACKERS] Indexing for geographic objects?
Edmar Wiggers wrote: It seems that R-trees become inefficient when the number of dimensions increase. Has anyone thoght of a transparent way to use Peano codes (hhcode in Oracle lingo), and use B-tree indexes instead? Do you have a reference, or more information on what a Peano code is? Bernie
[GENERAL] Re: [HACKERS] Indexing for geographic objects?
[EMAIL PROTECTED] 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
[GENERAL] RE: [HACKERS] Indexing for geographic objects?
Title: RE: [HACKERS] Indexing for geographic objects? 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 '; '[EMAIL PROTECTED]' Sent: 11-27-00 3:32 AM Subject: Re: [HACKERS] Indexing for geographic objects? Michael Ansley [EMAIL PROTECTED] 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 **
[GENERAL] Re: [HACKERS] Indexing for geographic objects?
[EMAIL PROTECTED] writes: Tom Lane wrote: Michael Ansley [EMAIL PROTECTED] 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
[GENERAL] Re: [HACKERS] Indexing for geographic objects?
Michael Ansley [EMAIL PROTECTED] 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
[GENERAL] RE: [HACKERS] Indexing for geographic objects?
Title: 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 [EMAIL PROTECTED] 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 **
[GENERAL] Re: [HACKERS] Indexing for geographic objects?
Franck Martin [EMAIL PROTECTED] 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
