
> There was some discussion of doing that, but it fell down on the little
> problem that in normal index-search cases you *don't* know the heap tid
> you are looking for.

I can not follow here. It does not matter if you don't know a trailing 
part of the key when doing a btree search, it only helps to directly find the 
leaf page.

> 
> > And in above case, the keys (since identical except xtid) will stick close 
> > together, thus caching will be good.
> 
> Even without key-collision problems, deleting N tuples out of a total of
> M index entries will require search costs like this:
> 
> bulk delete in linear scan way:
> 
> 	O(M)		I/O costs (read all the pages)
> 	O(M log N)	CPU costs (lookup each TID in sorted list)
> 
> successive index probe way:
> 
> 	O(N log M)	I/O costs for probing index
> 	O(N log M)	CPU costs for probing index (key comparisons)

both	O(N log (levels in index))

> So, as I said to Hiroshi, this alternative looks to me like a possible
> future refinement, not something we need to do in the first version.

Yes, I thought it might be easier to implement than the index scan :-)

Andreas

Fri, 18 May 2001 17:28:28 +0200
Zeugswetter Andreas SB  <ZeugswetterA@wien.spardat.at>
AW: AW: AW: Plans for solving the VACUUM problem 