Hi all,

Since I was at first Oracle DBA, I've been told many times at
professional trainings that when there is a table wich primary key is
generated by a sequence, it is worth create a RTREE index on it rather
than a BTREE (for index balancing reasons).

But, I wanted to try it with my PostgreSQL 7.1.3 and:

---
contacts=# \d t_contact
                                       Table "t_contact"
     Attribute     |          Type          |
Modifier                     
-------------------+------------------------+--------------------------------------------------
 cnt_id            | integer                | not null default nextval('contact_id_seq'::text)

[snipped all other columns...]

contacts=# drop index t_contacts_pkey;
DROP

contacts=# create unique index t_contacts_pkey on t_contact using rtree
(cnt_id);
ERROR:  DefineIndex: unique indices are only available with the btree
access method

contacts=# create index t_contacts_pkey on t_contact using rtree
(cnt_id);
ERROR:  DefineIndex: opclass "int4_ops" not supported by access method
"rtree"
---

So I think there are 2 possible reasons:

1) PostgreSQL has strong algorithms to manage indexes greatly, avoiding
this kind of BTREE index being unbalanced time passing ( I mean a kind
of automatic detection of unbalanced BTREE => triggers a DROP and CREATE
index...)

2) It is not yet implemented and you want to do it for the next version
:)

Whih of 1) & 2) is true?

Where to find more information about index management in PostgreSQL?

Thanks a lot.


-- 
Jean-Paul ARGUDO                     		IDEALX S.A.S
Consultant bases de donnï¿½es			15-17, av. de Sï¿½gur
http://IDEALX.com/ 				F-75007 PARIS

Fri, 25 Jan 2002 09:56:18 +0100
Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com>
RTREE Index on primary key generated by a sequence
On Fri, Jan 25, 2002 at 09:56:18AM +0100,
  Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com> wrote:
> Hi all,
> 
> Since I was at first Oracle DBA, I've been told many times at
> professional trainings that when there is a table wich primary key is
> generated by a sequence, it is worth create a RTREE index on it rather
> than a BTREE (for index balancing reasons).

The documentation gives the specific algorithms used:
The B-tree index is an implementation of Lehman-Yao high-concurrency
   B-trees. The R-tree index method implements standard R-trees using
   Guttman's quadratic split algorithm. The hash index is an
   implementation of Litwin's linear hashing. We mention the algorithms
   used solely to indicate that all of these access methods are fully
   dynamic and do not have to be optimized periodically (as is the case
   with, for example, static hash access methods).

Fri, 25 Jan 2002 07:54:18 -0600
Bruno Wolff III <bruno@wolff.to>
Re: RTREE Index on primary key generated by a sequence
Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com> writes:
> Since I was at first Oracle DBA, I've been told many times at
> professional trainings that when there is a table wich primary key is
> generated by a sequence, it is worth create a RTREE index on it rather
> than a BTREE (for index balancing reasons).

Huh?

RTREEs are for two-or-more-dimensional data (the implementation in PG
only handles 2-D, IIRC).  So they're not applicable to scalar data.
In any case, the claim that RTREEs are more readily balanced than BTREEs
seems totally unfounded to me.

In PG, the btree implementation is by far the best-tested,
best-optimized index access method we have; for example, it's the only
one that has decent support for concurrent access.  If you want to use
one of the other ones, I'd recommend you have a darn good reason.

			regards, tom lane

Fri, 25 Jan 2002 10:19:25 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: RTREE Index on primary key generated by a sequence 
Tom,

Since my english is not so fluent, I found on the net a little
explication about Reverse Key Indexes (not RTREE, sorry :).

As an explication, you could read there the point 9 :
http://oracle.oreilly.com/news/oraclepp_0900.html

Wich I copy here : ï¿½


9.Use Reverse Key Indexes. An index block
typically references more rows than are
contained in each data block for the
corresponding table. When an index is based on
a column that increases in a sequential
fashion, and two or more instances are
inserting data into the underlying
table, there is a strong likelihood that both
instances will be contending for the
same index block. This is because sequential
index entries are likely to be in the
same block. Reverse key indexes reverse the
bytes in each index entry, causing
sequential entries to be dispersed across the
index tree. Hence, there is less chance
of contention for the same index block. One
trade-off involved with using this
technique is that by its nature, reverse key indexes
cannot be used as the basis for an index
range scan. 

ï¿½


Thanks.

-- 
Jean-Paul ARGUDO                     		IDEALX S.A.S
Consultant bases de donnï¿½es			15-17, av. de Sï¿½gur
http://IDEALX.com/ 				F-75007 PARIS

Fri, 25 Jan 2002 16:55:58 +0100
Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com>
Re: RTREE Index on primary key generated by a sequence
>>>Bruno Wolff III said:
 > The documentation gives the specific algorithms used:
 > The B-tree index is an implementation of Lehman-Yao high-concurrency
 >    B-trees. The R-tree index method implements standard R-trees using
 >    Guttman's quadratic split algorithm. The hash index is an
 >    implementation of Litwin's linear hashing. We mention the algorithms
 >    used solely to indicate that all of these access methods are fully
 >    dynamic and do not have to be optimized periodically (as is the case
 >    with, for example, static hash access methods).

I was under the impression that hash indexes were not recommended for 
concurrent updates etc?

Daniel


Fri, 25 Jan 2002 17:58:28 +0200
Daniel Kalchev <daniel@digsys.bg>
Re: RTREE Index on primary key generated by a sequence 
Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com> writes:
> Since my english is not so fluent, I found on the net a little
> explication about Reverse Key Indexes (not RTREE, sorry :).

> As an explication, you could read there the point 9 :
> http://oracle.oreilly.com/news/oraclepp_0900.html

> ... Reverse key indexes reverse the
> bytes in each index entry, causing
> sequential entries to be dispersed across the
> index tree.

Hmm.  I think you could implement that with a custom index opclass
consisting of operators that flipped the bytes before comparison.
Not clear that it'd really buy you enough to be worth the trouble,
but if someone wants to try it...

> ... One
> trade-off involved with using this
> technique is that by its nature, reverse key indexes
> cannot be used as the basis for an index
> range scan. 

The way this would show up in Postgres is that you would use the
standard integer = operator as the = member of the opclass, but
all the other members would be byte-reversed-comparison operators
that would never be useful in real-world queries.

			regards, tom lane

Fri, 25 Jan 2002 11:32:37 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: RTREE Index on primary key generated by a sequence 
Okay Tom,

That closes the thread ;-)

Thanks for such expertise, hope one day I'll reach a 10% of yours :-)

Regards,

-- 
Jean-Paul ARGUDO                     		IDEALX S.A.S
Consultant bases de donnï¿½es			15-17, av. de Sï¿½gur
http://IDEALX.com/ 				F-75007 PARIS

Fri, 25 Jan 2002 17:43:50 +0100
Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com>
Re: RTREE Index on primary key generated by a sequence
Tom Lane wrote:
> 
> Jean-Paul ARGUDO <jean-paul.argudo@IDEALX.com> writes:
> > Since my english is not so fluent, I found on the net a little
> > explication about Reverse Key Indexes (not RTREE, sorry :).
> 
> > As an explication, you could read there the point 9 :
> > http://oracle.oreilly.com/news/oraclepp_0900.html
> 
> > ... Reverse key indexes reverse the
> > bytes in each index entry, causing
> > sequential entries to be dispersed across the
> > index tree.
> 
> Hmm.  I think you could implement that with a custom index opclass
> consisting of operators that flipped the bytes before comparison.
> Not clear that it'd really buy you enough to be worth the trouble,
> but if someone wants to try it...
> 
> > ... One
> > trade-off involved with using this
> > technique is that by its nature, reverse key indexes
> > cannot be used as the basis for an index
> > range scan.
> 
> The way this would show up in Postgres is that you would use the
> standard integer = operator as the = member of the opclass, but
> all the other members would be byte-reversed-comparison operators
> that would never be useful in real-world queries.

Never is too strong word. I guess that if index block contention is
serious enough problem for insert-intensive aplication and you need 
only = access then this could be a good thing. 

OTOH it will probably be not so good for cache usage and update 
locality so it may not be as good as it sounds even for the above
scenario.

---------------
Hannu

Fri, 25 Jan 2002 19:28:02 +0200
Hannu Krosing <hannu@tm.ee>
Re: RTREE Index on primary key generated by a sequence