Bruce,
> 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.
That's how SQL Server does it. In old versions (6.5) you had to manually
send commands to update the cluster, same as PG. Also, when you create a
cluster (or an index or table for that matter) you can manually set an amount
of "space" to be held open on each data page for updates.
Also keep in mind that SQL Server, as a "single-user database" has a much
easier time with this. They don't have to hold several versions of an index
in memory and collapse it into a single version at commit time.
All that being said, we could do a better job of "auto-balancing" clustered
tables. I believe that someone was working on this in Hackers through what
they called "B-Tree Tables". What happened to that?
--
Josh Berkus
Aglio Database Solutions
San Francisco