Further Block B-tree thoughts

Just to let everyone know, I'm continuing work on the Block B-tree idea
discussed earlier.

The current plan is to have a (compressed) bitmap of offsets attached to
index tuples, to allow vacuuming. For example, if we have a heap like this:

2
4
6
8
-
10
12
14
16
5
-
18
20

where dashes represent page boundaries, the corresponding index would
look like:

low key -> heap blk no (offsets)
2 -> 1 (1,2)
5 -> 2 (5)
6 -> 1 (3,4)
10 -> 2 (1,2,3,4)
18 -> 3 (1,2)

So each index tuple points to a group of tuples that are located on the
same page. The grouped tuples have keys in the range "this index key" -
"next index key", and there's no other tuples with a key in that range.
On index page boundaries, the high key of the page can be used instead
of the next index key to simplify insertion and scanning.

When scanning, index quals need to be rechecked after fetching the heap
tuples, unless the index tuple pointed to just one heap tuple, or we're
doing a range scan and both the min and max key of the group are within
the range. And to do a regular ordered index scan, tuples within a group
need to be sorted.

The current B-tree is a special case of this design, where each index
tuple points to a single heap tuple.

At first I thought this would be a new index access method, but it now
seems that it makes more sense to integrate this with the normal B-tree,
assuming that the behavior and performance is the same when all index
tuples point to single heap tuples.

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