On Thu, 2004-08-26 at 11:18, Bruce Momjian wrote:
> How do vendors actually implement auto-clustering? I assume they move
> rows around during quiet periods or have lots of empty space in each
> value bucket.
As far as I know, Oracle does it by having a B-Tree organized heap (a
feature introduced around v8 IIRC), basically making the primary key
index and the heap the same physical structure. Any non-index columns
are stored in the index along with the index columns. Implementing it
is slightly weird because searching the index and selecting the rows
from the heap are not separate operations.
The major caveat to having tables of this type is that you can only have
a primary key index. No other indexes are possible because the "heap"
constantly undergoes local reorganizations if you have a lot of write
traffic, the same kind of reorganization you would normally expect in a
BTree index.
The performance improvements come from two optimizations. First, you
have to touch significantly fewer blocks to get all the rows, even
compared to a CLUSTERed heap. Second, the footprint is smaller and
plays nicely with the buffer cache.
When I've used these types of heaps in Oracle 8 on heavily used tables
with tens of millions of rows, we frequently got a 10x or better
performance improvement on queries against those tables. It is only
really useful for tables with vast quantities of relatively small rows,
but it can be a lifesaver in those cases.
J. Andrew Rogers
