Thread: 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.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 standardR-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 nothave to be optimized periodically (as is the case with, for example, static hash access methods).
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
>>>Bruno Wolff III said:> The documentation gives the specific algorithms used:> The B-tree index is an implementation ofLehman-Yao high-concurrency> B-trees. The R-tree index method implements standard R-trees using> Guttman's quadraticsplit 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 optimizedperiodically (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
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.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
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.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