Re: RTREE Index on primary key generated by a sequence

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

On Fri, Jan 25, 2002 at 09:56:18AM +0100,
Jean-Paul ARGUDO <jean-paul(dot)argudo(at)IDEALX(dot)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).

Jean-Paul ARGUDO <jean-paul(dot)argudo(at)IDEALX(dot)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

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

Jean-Paul ARGUDO <jean-paul(dot)argudo(at)IDEALX(dot)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

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

Tom Lane wrote:
>
> Jean-Paul ARGUDO <jean-paul(dot)argudo(at)IDEALX(dot)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