Re: Brain dump: btree collapsing

Tom Lane kirjutas N, 13.02.2003 kell 20:10:
> "Curtis Faith" <curtis@galtcapital.com> writes:
> > I don't dispute their conclusions in that context and under the
> > circumstances they outline of random distribution of deletion and
> > insertion values for the index keys.  [But the random-distribution
> > assumption doesn't always hold.]
> 
> That's a fair point.  Nonetheless, we have little choice: we cannot
> move keys around during concurrent operations.  If we push keys to
> the right, we may cause an indexscan moving left to miss them, and
> vice versa.  So we can only eliminate empty pages.

But if we would allow the scans to find the same keys twice without ill
effects (as was suggested earlier, for using btrees to index arrays),
then we could possibly 1) copy the key to the right 2) wait for all
right-to-left scans that have fallen between old and new values to pass
and only then 3) delete the "old left" key. 

This could solve the concurrency issue as well.

> We could possibly allow VACUUM FULL to collapse partly-full pages,
> since in that case we know there are no concurrent scans.
> 
>             regards, tom lane
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly