> 1. The PG 4.2 code used an OID appended to the key to ensure that
> btree items are unique.  This fixes the Lehman and Yao algorithm's
> assumption of unique keys *for insertions*, since the item being
> inserted must have an OID different from existing items even if the
> key values are equal.  However there is still an issue for *lookups*,
> since we are necessarily doing a lookup with just a key value, and
> we want to find all index items with that same key value regardless
> of OID.

This is not right. OIDs were used *only* to find parent tuple in
_bt_getstackbuf, where only *per level* uniqueness is required.
I removed OIDs because of on any level there are no two (or more)
tuples pointing to the same place - i.e. TID may be used.
BTW, there were only single-key indices in Postgres-95 (and 4.2 too?) -
i.e. OID could not be used in key.

> 3. Awhile back Vadim removed the added-OID code and added a bunch of
> logic for explicit management of chains of duplicate keys.  In
> retrospect this change was probably a mistake.  For btree items that
> point to heap tuples we can use the tuple TID as tie-breaker (since
> an index should never contain two items with the same key and TID).
> Btree internal pages need an added field since they have to 
> consider the TID as part of the key (and the field that is the TID in a 
> leaf page is used as the down-link pointer in non-leaf pages).

While implementing multi-key btree-s for 6.1 I found problems with
duplicates handling and this is why extra logic was added. But I never
was happy with this logic -:)

Note that using TID as part of key would give us additional feature:
fast heap tuple --> index tuple look up. With this feature vacuum wouldn't
have to read entire index to delete a few items... and this will be required
for space re-using without vacuum...

Vadim

Tue, 18 Jul 2000 17:18:15 -0700
"Mikheev, Vadim" <vmikheev@SECTORBASE.COM>
RE: btree split logic is fragile in the presence of lar
	ge index items
"Mikheev, Vadim" <vmikheev@SECTORBASE.COM> writes:
> While implementing multi-key btree-s for 6.1 I found problems with
> duplicates handling and this is why extra logic was added. But I never
> was happy with this logic -:)

Do you not like the proposal I was suggesting?  I thought it was pretty
much what you said yourself a few months ago...

			regards, tom lane

Wed, 19 Jul 2000 11:45:19 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: btree split logic is fragile in the presence of lar ge index
	items
> Note that using TID as part of key would give us additional feature:
> fast heap tuple --> index tuple look up. With this feature vacuum wouldn't
> have to read entire index to delete a few items... and this will be required
> for space re-using without vacuum...

Wow, this seems like a huge win.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Wed, 26 Jul 2000 23:27:09 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: btree split logic is fragile in the presence of lar ge index
 items