Understanding GIN posting trees

I have a couple of questions on GIN:

The code seems to assume that it's possible for the same TID to appear 
twice for a single key (see addItemPointersToTuple()). I understand that 
it's possible for a single heap tuple to contain the same key twice. For 
example if you index an array of integers like [1,2,1]. But once you've 
inserted all the keys for a single heap item, you never try to insert 
the same TID again, so no duplicates should occur.

Looking at the history, it looks like pre-8.4 we assumed that no such 
duplicates are possible. Duplicates of a single key for one column are 
eliminated in extractEntriesSU(), but apparently when the multi-column 
support was added, we didn't make the de-duplication to run across the 
keys extracted from all columns. Now that the posting tree/list 
insertion code has to deal with duplicates anyway, the de-duplication 
performed in extractEntriesSU() seems pointless. But I wonder if it 
would be better to make extractEntriesSU() remove duplicates across all 
columns, so that the insertion code wouldn't need to deal with duplicates.

Dealing with the duplicates in the insertion code isn't particularly 
difficult. And in fact, now that we only support the getbitmap method, 
we wouldn't really need to eliminate duplicates anyway. But I have an 
ulterior motive:

Why is the posting tree a tree? AFAICS, we never search it using the 
TID, it's always scanned in whole. It would be simpler to store the TIDs 
in a posting list in no particular order. This could potentially make 
insertions cheaper, as you could just append to the last posting list 
page for the key, instead of traversing the posting tree to a particular 
location. You could also pack the tids denser, as you wouldn't need to 
reserve free space for additions in the middle.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com