Tom Lane wrote:
> There are several places in tuplesort.c (and perhaps elsewhere) where
> we explicitly work around limitations of various platforms' qsort()
> functions. Notably, there's this bit in comparetup_index_btree
>
> /*
> * If key values are equal, we sort on ItemPointer. This does not affect
> * validity of the finished index, but it offers cheap insurance against
> * performance problems with bad qsort implementations that have trouble
> * with large numbers of equal keys.
> */
Hmm, wasn't this supposed to be there to fix a problem with Lehman &
Yao's btree definition, that required all keys to be distinct?
[ checks the README ]
Okay, it seems I'm wrong; it has nothing to do with what we pass to
qsort.
The requirement that all btree keys be unique is too onerous,but the algorithm won't work correctly without it.
Fortunately,it isonly necessary that keys be unique on a single tree level, because L&Yonly use the assumption of key
uniquenesswhen re-finding a key in aparent page (to determine where to insert the key for a split page).Therefore, we
canuse the link field to disambiguate multipleoccurrences of the same user key: only one entry in the parent levelwill
bepointing at the page we had split.
--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support
